Contents Previous Next Subchapters

Quadratic Programming with Inequality and Positive Constraints
Syntax Qpos(level, G, g, B, b, xout, lamout, alpout)
See Also Qbox , lemke

Description
Determine a value of x that solves the problem
     minimize  (1/2) x' G x + g' x  with respect to x
     such that x > 0
               B x - b > 0
This is Problem (10.6.1) in the second edition of Practical Methods of Optimization by R. Fletcher. The Lagrangian for this problem is
     L(x, lam, alp) = (1/2) x' G x + g' x - lam' (B x - b) - alp' x
The return value of Qpos is true if it succeeds in solving the problem and false otherwise.

The real or double-precision symmetric positive definite matrix G contains the quadratic term in the objective function. The column vector g specifies the linear term in the objective function. It has the same type and number of rows as G. The matrix B specifies the linear term in the constraint inequalities. It has the same type and column dimension as G. The column vector b specifies the constant term in the constraint inequalities. It has the same type and row dimension as B.

The input values of the parameters xout, lamout, and alpout do not matter. If the return value of Qpos is true, the output value of these parameters satisfy the Kuhn-Tucker condition in Equation (9.1.16) of Practical Methods of Optimization, namely:
1. The partial of L with respect to x is zero at the point (xout, lamout, alpout).
2. The constraints are satisfied at the point xout.
3. All of the elements of lamout and alpout are greater than zero.
4. The following equations hold  
     0 = alpout' xout
     0 = lamout' (B xout - b)
Note that because all the terms in these products are non-negative, this implies each term is zero.

The integer scalar level specifies the level of tracing inside of the Qpos function. If level > 1, the text "Beginning Qpos" and the value of G, g, B, and b are printed before attempting to solve this problem. If Qpos cannot solve the problem, the text "Qpos returns false" is printed before it returns. If Qpos does solve the problem, the output values of xout, lamout, and alpout are printed. In addition the partial of L with respect to x, and B xout - b are printed together with the text "Qpos returns true".

If level > 2, a tracing level of level - 1 is used in the call to lemke that is used by Qpos.

Example
The following is Problem 10.4 from Practical Methods of Optimization
     minimize x(1)^2 - x(1) * x(2) + x(2)^2 - 3 * x(1)
     subject to x(1) >= 0
                x(2) >= 0
       - x(1) - x(2) >= -2
The example below solves this problem

clear
#
G = {[2., -1.], [-1., 2.]}
g = {-3., 0.}
B = [-1., -1.]
b = -2.
#
level = 1
xout    = novalue
lamout  = novalue
alpout  = novalue
format real "g5.2"
flag = Qpos(level, G, g, B, b, xout, lamout, alpout)
print "flag = ", flag