quadraticProg¶

Solves a quadratic programming problem subject to linear equality or inequality constraints.

Synopsis¶

quadraticProg (meq, a, b, g, h)

Required Arguments¶

int meq (Input): The number of linear equality constraints.
float a[[]] (Input): Array of size m × n containing the equality constraints in the first meq rows, followed by the inequality constraints.
float b[] (Input): Array with m components containing right-hand sides of the linear constraints.
float g[] (Input): Array with n components containing the coefficients of the linear term of the objective function.
float h[[]] (Input): Array of size n × n 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 + addToDiagH * I such that h + addToDiagH * I is positive definite.

Return Value¶

The solution x of the QP problem. If no solution can be computed, then None is returned.

Optional Arguments¶

maxItn, int (Input)

Maximum number of iterations.If maxItn is set to 0, the iteration count is unbounded.

Default: maxItn = 100000

tolerance, float (Input)

This constant is used in the determination of the positive definiteness of the Hessian H. tolerance is also used for the convergence criteria of a constraint violation.

Default: tolerance = 10.0 × machine precision.

dual (Output)

An array with m components containing the Lagrange multiplier estimates. On return, the necessary space is allocated by quadraticProg.

addToDiagH (Output)

Scalar equal to the multiple of the identity matrix added to h to give a positive definite matrix.

obj (Output)

The optimal object function found.

Description¶

The function quadraticProg 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); i.e., problems of the form

\[\begin{split}\begin{array}{l} \min\limits_{x \in R^n} g^T x + \tfrac{1}{2} x^T Hx \\ \text{subject to } \begin{array}[t]{l} & A_1 x = b_1 \\ & A_2 x \geq b_2 \\ \end{array} \end{array}\end{split}\]

given the vectors \(b_1\), \(b_2\), and g, and the matrices H, \(A_1\), and \(A_2\). 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 + αI, is used in the QP problem, then H + αI also should be used in the definition of the Lagrange multipliers.

Examples¶

Example 1¶

The quadratic programming problem

\[\begin{split}\begin{array}{l} \min f(x) = x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 - 2x_2x_3 - 2x_4x_5 - 2x_1 \\ \text{subject to } \begin{array}[t]{l} & x_1 + x_2 + x_3 + x_4 + x_5 = 5 \\ & x_3 - 2x_4 - 2x_5 = -3 \\ \end{array} \end{array}\end{split}\]

is solved.

from numpy import *
from pyimsl.math.quadraticProg import quadraticProg
from pyimsl.math.writeMatrix import writeMatrix


m = 2
n = 5
meq = 2
h = array([[2.0, 0.0, 0.0, 0.0, 0.0],
           [0.0, 2.0, -2.0, 0.0, 0.0],
           [0.0, -2.0, 2.0, 0.0, 0.0],
           [0.0, 0.0, 0.0, 2.0, -2.0],
           [0.0, 0.0, 0.0, -2.0, 2.0]])
a = array([[1.0, 1.0, 1.0, 1.0, 1.0],
           [0.0, 0.0, 1.0, -2.0, -2.0]])
b = (5.0, -3.0)
g = (-2.0, 0.0, 0.0, 0.0, 0.0)

# Solve the QP problem
x = quadraticProg(meq, a, b, g, h)

# Print x
writeMatrix("x", x)

Output¶

 
                               x
          1            2            3            4            5
          1            1            1            1            1

Example 2¶

Another quadratic programming problem

\[\begin{split}\begin{array}{l} \min f(x) = x_1^2 + x_2^2 + x_3^2 \\ \text{subject to } \begin{array}[t]{l} & x_1 + 2x_2 - x_3 = 4 \\ & x_1 - x_2 + x_3 = -2 \\ \end{array} \end{array}\end{split}\]

is solved.

from __future__ import print_function
from numpy import *
from pyimsl.math.quadraticProg import quadraticProg
from pyimsl.math.writeMatrix import writeMatrix


m = 2
n = 3
meq = 2
h = array([[2.0, 0.0, 0.0],
           [0.0, 2.0, 0.0],
           [0.0, 0.0, 2.0]])
a = array([[1.0, 2.0, -1.0],
           [1.0, -1.0, 1.0]])
b = [4.0, -2.0]
g = [0.0, 0.0, 0.0]

# Solve the QP problem
obj = []
d = []
x = quadraticProg(meq, a, b, g, h,
                  obj=obj, dual=d)

# Print x
writeMatrix("x", x)

# Print d
writeMatrix("d", d)
print("")
print(" obj = %g" % (obj[0]))

Output¶

 obj = 2.85714
 
                  x
          1            2            3
      0.286        1.429       -0.857
 
            d
          1            2
      1.143       -0.571

Warning Errors¶

IMSL_NO_MORE_PROGRESS Due to the effect of computer rounding error, a change in the variables fail to improve the objective function value; usually the solution is close to optimum.

Fatal Errors¶

IMSL_SYSTEM_INCONSISTENT The system of equations is inconsistent. There is no solution.