Syntax Supported by the IML Procedure and the iml Action
QPSOLVE Call
CALL QPSOLVE (rc, xres, Q, c <, A> <, b> <, opt> <, rowsense> <, L> <, U> ) ;
This subroutine is supported by the IML procedure and the iml action.
The QPSOLVE subroutine solves a quadratic programming problem. For any quadratic multivariate polynomial in n variables, you can express the quadratic polynomial by using matrices and vectors. If you represent 
as an n-dimensional column vector, then the polynomial 
can be written as
where 
is an 
symmetric matrix, 
is a column vector of n linear coefficients, and 
is a constant. This quadratic function is the objective function for the quadratic programming problem.
The QPSOLVE function finds the n-dimensional vector, , that maximizes or minimizes the quadratic objective function, possibly subject to linear constraints and boundary constraints. The vector is returned as a row vector. The general linear constraints are of the form 
, where 
represents equality (=) or inequality (
or 
) and 
is the ith row of a matrix, A. The boundary constraints are of the form 
.
The required input arguments to the QPSOLVE subroutine are as follows:
- Q
-
is a symmetric matrix of coefficients for the purely quadratic terms. The matrix is the Hessian matrix of second derivatives of the polynomial f.
The Hessian matrix can be represented in dense form or in sparse form.
In dense form, all
entries of the matrix must be specified. This is the most common representation, and it is used in subsequent examples. If 
, the dense specification must be used. -
The sparse representation can be useful when
has many zero elements. You can specify a 
matrix in which each row represents one of the k nonzero elements of . The first column contains the row locations, the second column contains the column locations, and the third column specifies the value of the nonzero element. For example, the value Q[1,2] = 7is represented by a row that has the values (1, 2, 7).Notice that this order of columns is different from the order that is returned by the SPARSE function. The following example converts a dense matrix,
Q, into a sparse matrix,S, and passes the sparse matrix to the QPSOLVE subroutine:n = 5; Q = 2*I(n); /* multiple of the identity matrix */ c = -2*(1:n); /* c = {-2 -4 -6 ... -2*n} */ S = sparse(Q, "SYM")[ ,3:1]; /* convert dense Q to sparse S */ call qpsolve(rc, x, S, c); /* pass S to QPSOLVE */ /* the solution vector is x = {1 2 3 ... n} */
- c
is a vector of linear coefficients. If c is an n-dimensional vector, then it contains the coefficients of the linear terms. If c is an
-dimensional vector, then the first n elements represent the linear coefficients and the last element is the constant term () for the quadratic polynomial. The constant term affects only the value of the objective function, not its derivatives or the location of the optimal solution.
In addition, you can specify the following optional arguments:
- A
is an
matrix that defines the linear constraints on the solution. You can use the A keyword to specify the matrix A. - b
is a vector of dimension m that specifies the right-hand side of the constraint equations. You can use the B keyword to specify the vector b. If you do not specify the rowsense argument, all constraints are equality constraints:
. - opt
-
is a numeric vector that contains values that control various options for the QPSOLVE subroutine. You can use the OPT keyword to specify the vector opt. If an element is missing, a default value is used.
The control vector supports two options. In the following list, assume that the opt argument is the vector {objSense, printLevel}.
- objSense
specifies whether the QPSOLVE subroutine should solve a minimization problem or a maximization problem. Use
opt[1] = 1to specify minimization andopt[1] = -1to specify maximization. The default value is 1.- printLevel
-
specifies the amount of printed output. The following values are valid:
- 0
The subroutine does not display any tables. This is the default value.
- 1
The subroutine displays the "Final Parameter Estimates" table, which shows the final parameter estimates and the final gradient.
- 2
The subroutine displays the table for printLevel=1 and also the "Iteration History" table, which contains information about the objective function and the size of the gradient at each step of the iteration.
- rowsense
is a row vector of dimension m that specifies the "sense" of a constraint—that is, whether it is an equality or inequality constraint. You can use the ROWSENSE keyword to specify the vector rowsense. Each element can have the value 'E', 'L', or 'G', which stand for equal, less than or equal to, and greater than or equal to, respectively. For example, if A and b have three rows, then the vector
r = {L, G, E}specifies that the solution must satisfy the constraintsA[1,]*x <= b[1],A[2,]*x >= b[2], andA[3,]*x = b[3]. If the rowsense vector is omitted, all constraints are assumed to be equality constraints.- L
specifies an optional vector of dimension n that specifies lower bounds on the solution. You can use the L keyword to specify the vector L. If you do not specify L, no variable is bounded below. If L[j] is a missing value, then the jth variable is not bounded below. For example, if you specify
L = {., 0, -1}, then the first component of the solution is not bounded below, the second component is bounded below by 0, and the third component is bounded below by
. - U
specifies an optional vector of dimension n that specifies upper bounds on the solution. You can use the U keyword to specify the vector U. If you do not specify U, no variable is bounded above. If U[j] is a missing value, then the jth variable is not bounded above. For example, if you specify
U = {., 10, 1}, then the first component of the solution is not bounded above, the second component is bounded above by 10, and the third component is bounded above by 1.
The QPSOLVE subroutine returns the following values. A positive value indicates a successful solution. A negative solution indicates that a solution was not found.
- rc
-
returns one of the following scalar return codes:
Table 5: Return Codes for the QPSOLVE Subroutine
rc Termination Reason 1 The solution is optimal. 2 The solution is conditionally optimal. -1 The solution is infeasible or the constraints are misspecified. -2 The solution is unbounded or infeasible. -3 The subroutine failed to solve the problem. -4 The subroutine could not obtain enough memory. -5 The time limit was exceeded. -6 The maximum number of iterations was exceeded. -7 The problem is not convex. You might have misspecified the objSense argument for an unbounded problem. -8 The problem is not concave. You might have misspecified the objSense argument for an unbounded problem.
- xres
returns the solution in a row vector of length n.
The QPSOLVE subroutine solves quadratic programs, which means that it optimizes a quadratic polynomial. If you represent the variable vector () as a column vector, the quadratic program has the following matrix formulation:
If 
is not specified, the QPSOLVE subroutine solves the unconstrained problem. If is specified but the rowsense vector is not specified, the subroutine solves the constrained problem subject to 
.
The Constrained Betts Function
You can use the QPSOLVE subroutine to find the optimum value of the constrained Betts problem. The constrained Betts problem has the following function and constraints:
The optimization problem can be expressed in matrix form by defining
Then the objective function for 
is
You can use calculus to show that the value 
is the minimum value of the polynomial in the constraint region. The following statements use the QPSOLVE subroutine to solve for a minimum of the constrained Betts problem. (Specify OPT=–1 when you want to find a maximum.) The solution is shown in Figure 289.
/* coefficients of quadratic, linear, and constant terms */
Q = { 0.02 0.0 ,
0.0 2.0 };
c = { 0. 0. -100};
/* constraints */
A = {10 -1} ;
rowsense = 'G';
b = 10;
L = { 2 -50};
U = { 50 50};
call qpsolve(rc, xres, Q, c, A, b, , rowsense, L, U); /* default is min */
print rc, xres;
Figure 289: Solution to a Quadratic Programming Problem
| rc |
|---|
| 1 |
| xres | |
|---|---|
| 2 | 0 |
The Q argument specifies the matrix that defines the quadratic coefficients. The c argument specifies the linear coefficients and includes the constant coefficient as the last element. The arguments A, b, and rowsense specify the general linear constraint. The vectors L and U specify the boundary constraints.
You can use keywords to specify the optional parameters of the QPSOLVE call. By using keyword parameters, you can specify only the relevant parameters. For example, if you want to use keyword parameters to specify the previous problem, you can use either of the following statements:
/* Alternatively, use keyword parameters */
call qpsolve(rc, xres, Q, c) OPT=1 A=A b=b RowSense=rowsense L=L U=U;
call qpsolve(rc, xres, Q, c) OPT=1 A={10 -1} b=10 ROWSENSE='G'
L={2 -50} U={50 50};
If you want to use only the boundary constraints, you can omit the keywords that specify general linear constraints:
call qpsolve(rc, xres, Q, c) L=L U=U;
You can use the following function to evaluate the quadratic function at the solution. The following statements also compute the linear constraint at the solution. As shown in Figure 290, the value of the linear constraint is greater than 10, as required by the constraint 
.
/* Evaluate the quadratic function in matrix form.
Q : n x n symmetric matrix,
c : vector of length n or n+1. First n elements are linear coefficients.
If c has n+1 elements, then const = c[n+1].
x : n x p matrix. Evaluate each column of x:
f(x) = 0.5*x` * Q * x + c`*x + const
*/
start EvalQuadVec(X, Q, c);
k = nrow(Q); L = colvec(c); const = 0;
if nrow(L)>k then do;
const = L[k+1];
L = L[1:k];
end;
f = j(1, ncol(X), .);
do i = 1 to ncol(X);
v = X[,i];
f[i] = 0.5 * v`*Q*v + L`*v + const;
end;
return f;
finish;
/* xres is a row vector; pass in a column vector */
y = EvalQuadVec(xres`, Q, c); /* evaluate objective function at solution */
constraint = A*xres`; /* should be greater than or equal to 10 */
print y, constraint;
Figure 290: Objective Function and Constraint at the Solution
| y |
|---|
| -99.96 |
| constraint |
|---|
| 20 |