IDL Analyst Reference Guide: Optimization

IMSL_QUADPROG

The IMSL_QUADPROG function solves a quadratic programming (QP) problem subject to linear equality or inequality constraints.

Syntax

Result = IMSL_QUADPROG(a, b, g, h [, DIAG=variable] [, /DOUBLE] [, DUAL=variable] [, MEQ=value] [, OBJ=variable])

Return Value

The solution x of the QP problem.

Arguments

a

Two-dimensional matrix containing the linear constraints.

b

One-dimensional matrix of the right-hand sides of the linear constraints.

g

One-dimensional array of the coefficients of the linear term of the objective function.

h

Two-dimensional array of size N_ELEMENTS(g) x N_ELEMENTS(g) containing the Hessian matrix of the objective function. It must be symmetric positive definite. If h is not positive definite, the algorithm attempts to solve the QP problem with h replaced by h + Diag*I, such that h + Diag*I is positive definite.

Keywords

DIAG

Name of the variable into which the scalar, equal to the multiple of the identity matrix added to h to give a positive definite matrix, is stored.

DOUBLE

If present and nonzero, double precision is used.

DUAL

Name of the variable into which an array with N_ELEMENTS(g) elements, containing the Lagrange multiplier estimates, is stored.

MEQ

Number of linear equality constraints. If MEQ is used, then the equality constraints are located at a(i, *) for i = 0, ..., Meq – 1.
Default: MEQ = N_ELEMENTS(a(*, 0)) n; i.e., all constraints are equality constraints.

OBJ

Name of variable into which optimal object function found is stored.

Discussion

The IMSL_QUADPROG function is based on M.J.D. Powell's implementation of the Goldfarb and Idnani dual quadratic programming (QP) algorithm for convex QP problems subject to general linear equality/inequality constraints (Goldfarb and Idnani 1983). That is, problems of the form:

subject to:

given the vectors b₀, b₁, and g, and the matrices H, A₀, and A₁. Matrix H is required to be positive definite. In this case, a unique x solves the problem, or the constraints are inconsistent. If H is not positive definite, a positive definite perturbation of H is used in place of H. For more details, see Powell (1983, 1985).

If a perturbation of H, H + aI, is used in the QP problem, H + aI also should be used in the definition of the Lagrange multipliers.

Example

In this example, the QP problem:

min f(x) = –x²₀ + x²₁ ⁺ x²₂ + x²₃ + x²₄ – 2x₁x₂ – 2x₃x₄ –2x₀

subject to:

x₀ + x₁ + x₂ + x₃ + x₄ = 5

x₂ – 2x₃ – 2x₄ = –3

is solved.

RM, a, 2, 5  
; Define the coefficient matrix A.  
row 0: 1 1 1  1  1  
row 1: 0 0 1 -2 -2  
h = [[2,  0,  0,  0,  0], [0,  2, -2,  0,  0], $  
   [0, -2,  2,  0,  0], [0,  0,  0,  2, -2], $  
   [0,  0,  0, -2,  2]]  
; Define the Hessian matrix of the objective function. Notice  
; that since h is symmetric, the array concatenation operators  
; "[ ]" are used to define it.  
b = [5, -3]  
; Define b.  
g = [ -2, 0, 0, 0, 0]  
; Define g.  
x = IMSL_QUADPROG(a, b, g, h)  
; Call IMSL_QUADPROG.  
PM, x  
; Output solution.  
Solution:  
         1.00000  
         1.00000  
         1.00000  
         1.00000  
         1.00000