Consider a small illustrative example. Suppose you want to minimize a two-variable quadratic function on the nonnegative quadrant, subject to two constraints:
|
The linear objective function coefficients, vector of right-hand sides, and lower and upper bounds are identified immediately as
|
Carefully construct the quadratic matrix . Observe that you can use symmetry to separate the main-diagonal and off-diagonal elements:
|
The first expression
|
sums the main-diagonal elements. Thus, in this case you have
|
Notice that the main-diagonal values are doubled in order to accommodate the 1/2 factor. Now the second term
|
sums the off-diagonal elements in the strict lower triangular part of the matrix. The only off-diagonal () term in the objective function is , so you have
|
Notice that you do not need to specify the upper triangular part of the quadratic matrix.
Finally, the matrix of constraints is as follows:
|
The SAS input data set with a quadratic programming system (QPS) format for the preceding problem can be expressed in the following manner:
data gsdata; input field1 $ field2 $ field3 $ field4 field5 $ field6 @; datalines; NAME . EXAMPLE . . . ROWS . . . . . N OBJ . . . . L R1 . . . . G R2 . . . . COLUMNS . . . . . . X1 R1 1.0 R2 1.0 . X1 OBJ 2.0 . . . X2 R1 -1.0 R2 2.0 . X2 OBJ 3.0 . . RHS . . . . . . RHS R1 1.0 . . . RHS R2 100 . . RANGES . . . . . BOUNDS . . . . . QUADOBJ . . . . . . X1 X1 2.0 . . . X1 X2 2.5 . . . X2 X2 20 . . ENDATA . . . . . ;
For more details about the QPS-format data set, see Chapter 15: The MPS-Format SAS Data Set.
Alternatively, if you have a QPS-format flat file named gs.qps, then the following call to the SAS macro %MPS2SASD translates
that file into a SAS data set, named gsdata
:
%mps2sasd(mpsfile =gs.qps, outdata = gsdata);
Note: The SAS macro %MPS2SASD is provided in SAS/OR software. See Converting an MPS/QPS-Format File: %MPS2SASD for details.
You can use the following call to PROC OPTQP:
proc optqp data=gsdata primalout = gspout dualout = gsdout; run;
The procedure output is displayed in Figure 12.2.
Figure 12.2: Procedure Output
Performance Information | |
---|---|
Execution Mode | On Client |
Number of Threads | 4 |
Problem Summary | |
---|---|
Problem Name | EXAMPLE |
Objective Sense | Minimization |
Objective Function | OBJ |
RHS | RHS |
Number of Variables | 2 |
Bounded Above | 0 |
Bounded Below | 2 |
Bounded Above and Below | 0 |
Free | 0 |
Fixed | 0 |
Number of Constraints | 2 |
LE (<=) | 1 |
EQ (=) | 0 |
GE (>=) | 1 |
Range | 0 |
Constraint Coefficients | 4 |
Hessian Diagonal Elements | 2 |
Hessian Elements Above the Diagonal | 1 |
Solution Summary | |
---|---|
Solver | QP |
Algorithm | Interior Point |
Objective Function | OBJ |
Solution Status | Optimal |
Objective Value | 15018 |
Primal Infeasibility | 3.146026E-16 |
Dual Infeasibility | 8.727374E-15 |
Bound Infeasibility | 0 |
Duality Gap | 7.266753E-16 |
Complementarity | 0 |
Iterations | 6 |
Presolve Time | 0.00 |
Solution Time | 0.25 |
The optimal primal solution is displayed in Figure 12.3.
Figure 12.3: Optimal Solution
Obs | Objective Function ID |
RHS ID | Variable Name |
Variable Type |
Linear Objective Coefficient |
Lower Bound |
Upper Bound | Variable Value |
Variable Status |
---|---|---|---|---|---|---|---|---|---|
1 | OBJ | RHS | X1 | N | 2 | 0 | 1.7977E308 | 34 | O |
2 | OBJ | RHS | X2 | N | 3 | 0 | 1.7977E308 | 33 | O |
The SAS log shown in Figure 12.4 provides information about the problem, convergence information after each iteration, and the optimal objective value.
Figure 12.4: Iteration Log
NOTE: The problem EXAMPLE has 2 variables (0 free, 0 fixed). |
NOTE: The problem has 2 constraints (1 LE, 0 EQ, 1 GE, 0 range). |
NOTE: The problem has 4 constraint coefficients. |
NOTE: The objective function has 2 Hessian diagonal elements and 1 Hessian |
elements above the diagonal. |
NOTE: The QP presolver value AUTOMATIC is applied. |
NOTE: The QP presolver removed 0 variables and 0 constraints. |
NOTE: The QP presolver removed 0 constraint coefficients. |
NOTE: The presolved problem has 2 variables, 2 constraints, and 4 constraint |
coefficients. |
NOTE: The QP solver is called. |
NOTE: The Interior Point algorithm is used. |
NOTE: The deterministic parallel mode is enabled. |
NOTE: The Interior Point algorithm is using up to 4 threads. |
Primal Bound Dual |
Iter Complement Duality Gap Infeas Infeas Infeas |
0 3.61419e+03 4.89451e+00 1.02569e+00 1.03529e+02 8.95247e-02 |
1 2.00854e+03 9.54360e-01 4.43601e-01 4.47753e+01 3.87186e-02 |
2 2.25399e+03 1.25043e-01 4.43601e-03 4.47753e-01 3.87186e-04 |
3 5.09548e+01 3.28862e-03 4.43601e-05 4.47753e-03 3.87186e-06 |
4 5.09076e-01 3.29491e-05 4.43601e-07 4.47753e-05 3.87186e-08 |
5 5.09065e-03 3.29493e-07 4.43601e-09 4.47753e-07 3.87202e-10 |
6 0.00000e+00 7.26675e-16 3.14603e-16 0.00000e+00 8.72737e-15 |
NOTE: Optimal. |
NOTE: Objective = 15018. |
NOTE: The Interior Point solve time is 0.00 seconds. |
NOTE: The data set WORK.GSPOUT has 2 observations and 9 variables. |
NOTE: The data set WORK.GSDOUT has 2 observations and 10 variables. |
See the section Interior Point Algorithm: Overview and the section Iteration Log for the OPTQP Procedure for more details about convergence information given by the iteration log.