The OPTQP Procedure

Getting Started: OPTQP Procedure

Consider a small illustrative example. Suppose you want to minimize a two-variable quadratic function $f(x_1, x_2)$ on the nonnegative quadrant, subject to two constraints:

\[  \begin{array}{rccccccccl} \min &  2x_1 &  + &  3x_2 &  + &  x_1^2 &  + &  10x_2^2 &  + &  2.5 x_1 x_2 \\ \mbox{subject to} &  x_1 &  - &  x_2 &  \le &  1 & & & & \\ &  x_1 &  + &  2x_2 &  \ge &  100 & & & & \\ &  x_1 & & &  \ge &  0 & & & & \\ & & &  x_2 &  \ge &  0 & & & & \end{array}  \]

The linear objective function coefficients, vector of right-hand sides, and lower and upper bounds are identified immediately as

\[  \mathbf{c} = \left[\begin{array}{c} 2 \\ 3 \end{array}\right],\quad \mathbf{b} = \left[\begin{array}{c} 1 \\ 100 \end{array}\right],\quad \mathbf{l} = \left[\begin{array}{c} 0 \\ 0 \end{array}\right],\quad \mathbf{u} = \left[\begin{array}{c} +\infty \\ +\infty \end{array}\right]  \]

Carefully construct the quadratic matrix $\mathbf{Q}$. Observe that you can use symmetry to separate the main-diagonal and off-diagonal elements:

\[  \frac{1}{2} \mathbf{x}^\textrm {T} \mathbf{Qx} \equiv \frac{1}{2} \sum _{i, j = 1}^ n\;  x_ i\,  q_{ij}\,  x_ j = \frac{1}{2} \sum _{i = 1}^ n\;  q_{ii}\,  x_ i^2 + \sum _{i > j}\;  x_ i\,  q_{ij}\,  x_ j  \]

The first expression

\[  \frac{1}{2} \sum _{i = 1}^{n}\;  q_{ii}\,  x_ i^2  \]

sums the main-diagonal elements. Thus, in this case you have

\[  q_{11} = 2,\quad q_{22} = 20  \]

Notice that the main-diagonal values are doubled in order to accommodate the 1/2 factor. Now the second term

\[  \sum _{i > j} x_ i\,  q_{ij}\,  x_ j  \]

sums the off-diagonal elements in the strict lower triangular part of the matrix. The only off-diagonal ($x_ i\,  x_ j,\;  i\not=j$) term in the objective function is $2.5\,  x_1\,  x_2$, so you have

\[  q_{21} = 2.5  \]

Notice that you do not need to specify the upper triangular part of the quadratic matrix.

Finally, the matrix of constraints is as follows:

\[  \mathbf{A} = \left[\begin{array}{cr} 1 &  -1 \\ 1 &  2 \end{array}\right]  \]

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

The OPTQP Procedure

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.