Contents Previous Next Subchapters

Quadratic Programming with Inequality and Box Constraints
Syntax Qbox(levelQqAaxlowxup,  xoutgamoutalpoutbetaout)
See Also Qpos , Qpro

Description
Determine a value of x that solves the problem
     minimize  (1/2) xQ x + qx  with respect to x
     such that A x - a < 0
               xlow < x < xup
The Lagrangian for this problem is
     L(xgamalpbeta) = (1/2) xQ x + qx 
          + gam' (A x - a) + alp' (xlow - x) + beta' (x - xup)
The return value of Qbox is true if it succeeds in solving the problem and false otherwise.

The real or double-precision symmetric positive definite matrix Q contains the quadratic term in the objective function. The column vector q specifies the linear term in the objective function. It has the same type and number of rows as Q. The matrix A specifies the linear term in the constraint inequalities. It has the same type and column dimension as Q. The column vector a specifies the constant term in the constraint inequalities. It has the same type and row dimension as A. The column vectors xlow and xup specify the lower and upper limits for the box constraints. The have the same type and row dimension as Q. Each element of xlow must be greater than or equal the corresponding element of xup. If the corresponding elements are exactly equal, the corresponding component of x is removed from the optimization problem.

The input values of the parameters xout, gamout, alpout, and betaout do not matter. If the return value of Qbox is true, the output value of these parameters satisfy the Kuhn-Tucker condition in Equation (9.1.16) of the second edition of Practical Methods of Optimization by R. Fletcher, namely:
1. The partial of L with respect to x is zero at the point (xoutgamoutalpoutbetaout).
2. The constraints are satisfied at the point xout.
3. All of the elements of gamout, alpout, and betaout are greater than zero.
4. The following equations hold  
     0 = gamout' (a - A xout)
     0 = alpout' (xout - xlow)
     0 = betaout' (xup - xout)
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 Qbox function. If level > 1, the text "Beginning Qbox" and the value of xlow, xup, Q, q, A, and a are printed before attempting to solve this problem. If Qbox cannot solve the problem, the text "Qbox returns false" is printed before it returns. If Qbox does solve the problem, the output values of xout, gamout, alpout, and betaout are printed. In addition the partial of L with respect to x, and A xout - a are printed together with the text "Qbox returns true".

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

Example
The program below solves the problem
     minimize   x(1)^2 - (x(2) - 2)^2 + (x(3) + 2)^2
     subject to 5. - x(1) < 0 
                -1 < x(1) < +1 
                -1 < x(2) < +1
                -1 < x(3) < -1
The solution to this problem is x = [.5, -1, +1]

clear
#
level = 1
Q     = 2 * identity(3)
q     = {0., -4., +4}
A     = [-1., 0., 0.]
a     = -.5
xlow  = {-1., -1., -1.}
xup   = {+1., +1., -1.}
xout    = novalue
gamout  = novalue
alpout  = novalue
betaout = novalue
ok = Qbox(level, Q, q, A, a, xlow, xup, xout, gamout, alpout, betaout)
print "ok =", ok