What do Asset Portfolio Optimization and Laundry Portfolio Optimization Have in Common?

[#1]

Most natural phenomenon and real-world business problems are intrinsically non-linear, for example:

1. Finding the best asset allocation for the fixed amount of money you have for investments
2. The spread of gossip/news in Social Networks, the spread of an infectious disease
3. Equations describing quantum mechanics, electromagnetism, fluid dynamics

   … the list is endless

Often, Linear programming is unable to capture the complex relationships between inputs and outcomes, and as in the examples mentioned above, Nonlinear Optimization must be used and then extended to deal with integer variables becoming a mixed integer nonlinear optimization.

In this article, I will provide examples of problems that can be solved with nonlinear optimization and provide coding examples of new features in SAS Optimization 8.3 that take advantage of the distributed, cloud-based computational environment that SAS Viya provides.

Mixed integer nonlinear optimization is used to determine the best allocation of labor and capital for optimal production of detergents, as well as, for creating trading strategies in the stock market with the purpose of selecting entry and exit points of stocks, to maximize profit and minimize risk.

In 2014, the SAS OR Center of Excellence was a finalist for the Wagner Prize with the entry Statistical & Optimization Techniques for Laundry Portfolio Optimization at P&G. (View the video.) The goal of the project was to set the portfolio strategy for the multi-billion-dollar laundry powder business. This work identified strategies to save $5-20 M and one of the models developed and solved was a Highly Nonconvex Mixed Integer Nonlinear Problem.

The graph below is just in two-dimensions and has two minimum points, one is a local minimum and the second is the global minimum.

Real world problems have many variables and typically a non-linear problem might have many local minima/maxima; imagine an egg carton distorted in multi-dimensions. SAS algorithms can find the global optimum, or a good approximation to it, in a multi-dimensional space.

For the SAS NLP solver it is recommended that the functions describing the objective and the equality and inequality constraints are twice continuously differentiable.

SAS NLP has the option Multistart. When using this option, the local solver solves the problem from different starting points, finding a better local optimum as a result.

The NLP solver implements the following primal-dual methods for finding a local optimum:

• Interior point trust-region line-search algorithm. It is the default, it uses a primal-dual interior point method. This technique is recommended for both small- and large-scale nonlinear optimization problems. This is the preferred solver if the problem includes many inactive constraints.
• Active-set trust-region line-search algorithm uses a primal-dual active-set method. This technique is recommended for both small- and large-scale nonlinear optimization problems. This is the preferred solver if the problem includes only bound constraints or if the optimal active set can be quickly determined by the solver.

The code below optimizes a function that has many local minima. Without the multistart option the minimum found is 607.03. However, when multistart is used the minimum found is 0.029. A significant difference!

/* Using CAS to solve NLP_Problems that have several local minima */
/* The following SAS statements show how you can solve this problem in a distributed computing environment. After you create a CAS session named mysess, you specify the SESSREF="mySession" option to run the OPTMODEL procedure on CAS. */

cas mySession3 sessopts=(caslib=CASUSER timeout=1800 locale="en_US" metrics=true);

proc optmodel sessref="mySession3" nthreads=4;
   var x{i in 1..5} >= -5 <= 5 init -2;

   min f=(x[1] - 1)^2 + (x[1] - x[2])^2 + (x[2] - x[3])^3 +
         (x[3] - x[4])^4 + (x[4] - x[5])^4;

   con g1: x[1] + x[2]^2 + x[3]^3 =  2 + 3*sqrt(2);
   con g2: x[2] + x[4]   - x[3]^2 = -2 + 2*sqrt(2);
   con g3: x[1]*x[5] = 2;

   solve with nlp/ multistart=(maxstarts=20) ;
   print x;
quit;

About this example, note the following:

• In the CAS declaration:
  1. The CAS session is named mySession3, which will be referred by the sessref option in the proc optmodel line.
  2. Metrics=true
• In the proc optmodel:
  1. sessref=”mySession3” specifies the name of the CAS session to which you want to connect. It indicates that you want optmodel to interact with that specific cas session. The NLP solver will run in that specific cas session. Within proc optmodel you can reset the current cas session to a different cas session, when for example, you want to access different caslibs from the current cas session.
  2. Declarations for decision variables, constraints and objective function to be minimized
  3. The line in the code where the option multistart is specified: solve with nlp/multistart=(maxstarts=20)

The next example shows how to use the COFOR statement which offers a simple way to exploit parallel processing by solving independent problems concurrently, on either one machine or distributed across multiple machines. You are unlikely to see any benefit from COFOR when each solve is fast.  The best performance improvement from COFOR arises when each solve takes at least several seconds.  Otherwise, the communication overhead swamps any improvement from parallelism.

A key distinction between the COFOR and FOR statements is that in a COFOR loop you are solving independent optimization problems. When you call a solver in a FOR loop, the problems might be independent or not, you might be even calling different solvers.

cas mySession2 sessopts=(caslib=CASUSER timeout=1800 locale="en_US"  metrics=true);
libname CASUSER cas caslib=CASUSER;
 
Data casuser.Bounds;
Input period lower upper;
Datalines;
1   0.1   3
2  -3.1   4
3  -6.1   3.5
4   0.1  10
;
 
proc optmodel sessref="mySession2" ;
 
set Period;
num lower{Period};
num upper{Period};
num lowB;
num upB ;
 
read data casuser.bounds into PERIOD=[period] lower upper;
 
 
   var x{1..8} >= lowB <= upB; x[1] = 3; x[2] = 3; min f = 0.4*(x[1]/x[7])^0.67 + 0.4*(x[2]/x[8])^0.67 + 10 - x[1] - x[2]; con c1: 1 - 0.0588*x[5]*x[7] - 0.1*x[1] >= 0;
   con c2: 1 - 0.0588*x[6]*x[8] - 0.1*x[1] - 0.1*x[2] >= 0;
   con c3: 1 - 4*x[3]/x[5] - 2/(x[3]^0.71*x[5]) - 0.0588*x[7]/x[3]^1.3 >= 0;
   con c4: 1 - 4*x[4]/x[6] - 2/(x[4]^0.71*x[6]) - 0.0588*x[8]/x[4]^1.3 >= 0;
   con c5: 0.1 <= f <= 4.2;
 
 
cofor { p in Period} do;
	lowB= lower[p];
	upB=upper[p];
	put lowB= ; put upB= ;
 
   solve with nlp / algorithm=activeset 
		multistart=(maxstarts=20) seed=12345 nthreads=4;
 
 
   print  x;
end;
 quit;
 
 
CAS mySession2 TERMINATE;

In this example, COFOR is used to solve four different instances of a highly Nonlinear Optimization problem. For each case, the variables bounds change. In addition to declaring the CAS session and caslibs, other key steps in this code are:

• How the read data statement uses Period as an index, which is a column in the casuser.bounds cas table.
• The COFOR loop that is used to change the variables upper and lower bounds

For an additional COFOR example, check out the SAS Global Forum paper SAS1758-2018: Using SAS/OR® to Optimize Scheduling and Routing of Service Vehicles by Rob Pratt.

The last example shows how to use the runOptmodel action in the Optimization Action Set. The runOptmodel action provides access to the OPTMODEL modeling language and multiple mathematical programming solvers within the CAS environment, one of them the NLP solver. Moreover, runOptmodel provides optimization modeling access from any programming language that SAS Viya supports, currently R, Python, and Lua.

proc cas;
	loadactionset "optimization";
	source pgm; /*to assign optmodel code to pgm string variable*/
		var x{i in 1..5} >= -5 <= 5 init -2;

   		min f=(x[1] - 1)^2 + (x[1] - x[2])^2 + (x[2] - x[3])^3 +
         	(x[3] - x[4])^4 + (x[4] - x[5])^4;

   		con g1: x[1] + x[2]^2 + x[3]^3 =  2 + 3*sqrt(2);
   		con g2: x[2] + x[4]   - x[3]^2 = -2 + 2*sqrt(2);
   		con g3: x[1]*x[5] = 2;


   		solve with nlp/   multistart=(maxstarts=20) seed=12345 nthreads=4;
   		print  x;
     endsource;
	
	optimization.runOptmodel / code=pgm;

	run;
quit;

CAS mySession3 TERMINATE;

Notice the changes that are needed to use runOptmodel:

• Use proc cas
• Load the action set Optimization and use the CASL statement source which embeds text in the program and assign it to the pgm string variable
• Notice that the Action Set Optimization calls runOptModel

Conclusion

SAS Optimization provides algorithms for Solving Nonlinear Optimization problems which take advantage of the distributed, cloud-based computational environment that SAS Viya provides. As shown in the coding examples, implementing these algorithms is very easy.

References

Mathematical Optimization Programming Guide

SAS1758-2018: Using SAS/OR® to Optimize Scheduling and Routing of Service Vehicles by Rob Pratt

SAS OR Center of Excellence’s finalist entry to the 2014 Wagner Prize - Statistical & Optimization Techniques for Laundry Portfolio Optimization at P&G