The Optimization Package
The Optimization package provides commands to find the minimum or maximum of various types of functions subject to various types of constraints. This worksheet provides a few basic examples of each type of problem the package is capable of solving. Further information can be found on the help pages for the package and each of the individual package members. In this worksheet, we will be minimizing a function (referred to as the objective function) subject to a number of constraints. Certain maximize examples are included as well. In any of the examples, the maximize option can be added to the command to find the maximum instead of the minimum. Also note that in each case we are only finding a locally optimal value.
Introduction to the Optimization Package
restart
The following command allows you to use the short form of the command names in the Optimization package.
withOptimization:withplots:
The commands in the Optimization package allow you to specify the objective function and the constraints in several different ways. This worksheet deals with the algebraic form of the objective function and constraints. The other forms are Matrix form and procedure form where Matrix form is covered in a separate example worksheet.
In general, an optimization problem is of the form
min fx where x is in ℝn
subject to cix≤0 for i in I, cix=0 for i in E
The Optimization package handles several types of objective and constraint functions. Each type of problem is a subtype of the next one.
Objective Function/Constraint/Command
Linear/Linear/LPSolve
Quadratic/Linear/QPSolve
Nonlinear(General)/Nonlinear(General)/NLPSolve
There is also a minimize command that will attempt to automatically select the best algorithm for a given problem. In addition, there is a command, LSSolve, which minimizes functions of the form
fx=12 ∑i=1nrix2
Linear Programming Example 1
For a first example, we have a simplex two dimensional linear programming problem.
min −2 x−y
subject to
y≤4 x+12
y≤−5 x+2
0≤x
0≤y
obj:=−2x−y
obj≔−2x−y
cnsts:=y≤4x+12,y≤−5x+2,0≤x,0≤y
cnsts≔y≤4x+12,y≤−5x+2,0≤x,0≤y
The plot below shows the feasible region in yellow, the contours of the objective function, and the optimal solution as a green circle.
p1:=inequalcnsts,x=−0.5..2,y=−0.5..2,optionsexcluded=color=white,optionsfeasible=color=yellow:p2:=contourplotobj,x=−0.5..2,y=−0.5..2:p3≔pointplot0.1666,1.166,symbolsize=13,color=green:displayp1,p2,p3
The command returns the optimal function values, as well as the point at which the optimal value occurs.
LPSolveobj,cnsts
−1.50000000000000,x=0.166666666666667,y=1.16666666666667
Alternatively, we could use the first two constraints and the nonnegative option.
LPSolveobj,cnsts1..2,assume=nonnegative
The first element of the solution is the minimum value that the objective function obtains, while satisfying the constraints. The second element indicates a point where the minimum is reached. This point is not necessarily unique.
Linear Programming Example 2
We can also include equality constraint as the next example shows. This example also demonstrates the maximize option.
obj:=2x+y+z
obj≔2x+y+z
cnsts:=y≤4x+12,y≤−5x+2,z=−2x3−2y3+203
cnsts≔y≤4x+12,y≤−5x+2,z=−2x3−2y3+203
LPSolveobj,cnsts,assume=nonnegative,maximize
7.27777777777778,x=0.166666666666667,y=1.16666666666667,z=5.77777777777778
Quadratic Programming Example
For a first example of a quadratic program, we will use:
min 4x2−y+x+5
subject to −11≤x+y−7 x
11 x2+y≤0
−4≤x
obj:=4x2−y+x+5
obj≔4x2+x−y+5
cnsts:=−11≤x+y−7x,11x2+y≤0,−4≤x
cnsts≔−11≤−6x+y,11x2+y≤0,−4≤x
The plot below shows the feasible region in yellow and the contours of the objective function. The green circle indicates the optimal point.
p1:=contourplotobj,x=−4..4,y=−10..10,contours=30:p2:=inequalcnsts,x=−4..4,y=−10..10,optionsexcluded=color=white,optionsfeasible=color=yellow:p3≔pointplot−0.8125,4.486,symbolsize=13,color=green:displayp1,p2,p3
The QPSolve command returns the optimal function values, as well as the point at which the optimal value occurs.
QPSolve4x2−y+x+5,−11≤x+y−7x,11x2+y≤0,−10≤x
2.35937499999999,x=−0.812500000000001,y=4.46875000000001
Nonlinear Programming
The NLPSolve command allows us to solve problems of a fairly general nature. As long as the derivative of the objective function and constraint function is continuous, we can use NLPSolve. Our first basic example of nonlinear programming is a simple univariate minimization of a polynomial.
p:=0.004126984123x7−0.1091666666x6+7.078095236x+1.136388888x5−18.19500000x2−5.845833331x4+15.23138888x3+2
p≔0.004126984123x7−0.1091666666x6+7.078095236x+1.136388888x5−18.19500000x2−5.845833331x4+15.23138888x3+2
This plot shows the function and the minimum found by NLPSolve.
p1:=plotp,x=0..6:p2:=pointplot4.8877,0.6883,symbolsize=13,color=green:displayp1,p2
We can minimize this function in the range [0..6].
NLPSolvep,x=0..6
0.683344558794943,x=4.88774385576649
We can also maximize the function.
NLPSolvep,x=0..6,maximize
2.80062108007189,x=2.97993884682345
We can minimize more complex functions such as:
f:=xerfxcosx
f≔xerfxcosx
s:=NLPSolvef,x=1..20
s≔−9.47729425947979,x=9.52933438691188
Below we plot the function f and the minimum point. We can see that NLPSolve finds a local minimum, not necessarily a global one.
p1:=plotf,x=1..20:p2:=pointplotrhss21,s1,color=green,symbolsize=14:displayp1,p2
We can also minimize multivariate functions such as
f:=100y−x22+1−x2
f≔100−x2+y2+1−x2
with
NLPSolvef,x=−10..10,y=−10..10,initialpoint=x=−1.2,y=1
1.79319068453110564×10−16,x=0.999999988744863,y=0.999999976764186
Curve Fitting with Least Squares
restartwithOptimization:
We can use the least squares command to do curve fitting. For example, if we have the following data points, (xi,yi):
data:=1,1.5,2,3.5,2.5,1.9,3.1,4.5,4.3,1.9,4.7,2.4,5.8,3,6,5.7,6.6,3.4,6.7,0.5,7.1,4,7.4,1.7
data≔1,1.5,2,3.5,2.5,1.9,3.1,4.5,4.3,1.9,4.7,2.4,5.8,3,6,5.7,6.6,3.4,6.7,0.5,7.1,4,7.4,1.7
and we want to fit the data with a quintic polynomial. Let our quintic be,
px=ax5+bx4+cx3+dx2+ex+f.
Now we need to find a,b,c,d,e, and, f such that
12∑x=112pxi−yi2
is a minimum.
LSSolve takes as input a list of the residues pxi−yi.
p:=ax5+bx4+cx3+dx2+ex+f
p≔ax5+bx4+cx3+dx2+ex+f
residues:=mapd→px=d1|px=d1−d2,data
residues≔a+b+c+d+e+f−1.5,32a+16b+8c+4d+2e+f−3.5,97.65625a+39.0625b+15.625c+6.25d+2.5e+f−1.9,286.29151a+92.3521b+29.791c+9.61d+3.1e+f−4.5,1470.08443a+341.8801b+79.507c+18.49d+4.3e+f−1.9,2293.45007a+487.9681b+103.823c+22.09d+4.7e+f−2.4,6563.56768a+1131.6496b+195.112c+33.64d+5.8e+f−3,7776a+1296b+216c+36d+6e+f−5.7,12523.32576a+1897.4736b+287.496c+43.56d+6.6e+f−3.4,13501.25107a+2015.1121b+300.763c+44.89d+6.7e+f−0.5,18042.29351a+2541.1681b+357.911c+50.41d+7.1e+f−4,22190.06624a+2998.6576b+405.224c+54.76d+7.4e+f−1.7
Now we can call LSSolve with the residues.
sol:=LSSolveresidues
sol≔9.79941650829796096,a=0.00506817808955152,b=−0.148717633940652,c=1.53722867786023,d=−7.04487080570615,e=14.2425902266783,f=−7.12139344171469
Our polynomial becomes:
poly:=evalp,sol2
poly≔0.00506817808955152x5−0.148717633940652x4+1.53722867786023x3−7.04487080570615x2+14.2425902266783x−7.12139344171469
We can now plot the data and the curve
withplots:p1≔pointplotdata: p2≔plotpoly,x=0.9..8:displayp1,p2
Return to Index for Example Worksheets
Download Help Document
