quadprog - Solve quadratic programming problems

Equation

Finds a minimum for a problem specified by

H, A, and Aeq are matrices, and f, b, beq, lb, ub, and x are vectors.

Syntax

x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(problem)
[x,fval] = quadprog(...)
[x,fval,exitflag] = quadprog(...)
[x,fval,exitflag,output] = quadprog(...)
[x,fval,exitflag,output,lambda] = quadprog(...)

Description

x = quadprog(H,f,A,b) returns a vector x that minimizes 1/2*x'*H*x + f'*x subject to A*x ≤ b.

x = quadprog(H,f,A,b,Aeq,beq) solves the preceding problem while additionally satisfying the equality constraints Aeq*x = beq. If no inequalities exist, set A = [] and b = [].

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that the solution is in the range lb ≤ x ≤ ub. If no equalities exist, set Aeq = [] and beq = [].

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) sets the starting point to x0. If no bounds exist, set lb = [] and ub = [].

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) minimizes with the optimization options specified in the structure options. Use optimset to set these options. If you do not wish to give an initial point, set x0 = [].

x = quadprog(problem) finds the minimum for problem, where problem is a structure described in Input Arguments.

Create the structure problem by exporting a problem from Optimization Tool, as described in Exporting to the MATLAB Workspace.

[x,fval] = quadprog(...) returns the value of the objective function at x:

fval = 0.5*x'*H*x + f'*x.

[x,fval,exitflag] = quadprog(...) returns a value exitflag that describes the exit condition of quadprog.

[x,fval,exitflag,output] = quadprog(...) returns a structure output that contains information about the optimization.

[x,fval,exitflag,output,lambda] = quadprog(...) returns a structure lambda whose fields contain the Lagrange multipliers at the solution x.

Note   If the specified input bounds for a problem are inconsistent, the output x is x0 and the output fval is []. Components of x0 that violate the bounds lb ≤ x ≤ ub are reset to the interior of the box defined by the bounds. Components that respect the bounds are not changed. If no x0 is provided, all components of x0 are set to a point in the interior of the box defined by the bounds.

Input Arguments

Function Arguments contains general descriptions of arguments passed into quadprog. Options provides function-specific details for the options values.

Output Arguments

Function Arguments contains general descriptions of arguments returned by quadprog. This section provides function-specific details for exitflag, lambda, and output:

Options

Optimization options. Use optimset to set or change the values of these options. Some options apply to all algorithms, and some are only relevant when using the large-scale algorithm. See Optimization Options for detailed information.

Medium-Scale and Large-Scale Algorithms

Both the medium-scale and large-scale algorithms use the following options:

Large-Scale Algorithm Only

The large-scale algorithm uses the following options:

W = hmfun(Hinfo,Y)

Examples

Find values of x that minimize

subject to

x₁ + x₂ ≤ 2
–x₁ + 2x₂ ≤ 2
2x₁ + x₂ ≤ 3
0 ≤ x₁, 0 ≤ x₂.

First, note that this function can be written in matrix notation as

where

Enter these coefficient matrices.

H = [1 -1; -1 2] 
f = [-2; -6]
A = [1 1; -1 2; 2 1]
b = [2; 2; 3]
lb = zeros(2,1)

Next, invoke a quadratic programming routine.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,A,b,[],[],lb)

This generates the solution

x = 
     0.6667
     1.3333
fval =
    -8.2222
exitflag =
     1
output = 
       iterations: 3
        algorithm: 'medium-scale: active-set'
    firstorderopt: []
     cgiterations: []
          message: 'Optimization terminated.'
lambda = 
      lower: [2x1 double]
      upper: [2x1 double]
      eqlin: [0x1 double]
    ineqlin: [3x1 double]

lambda.ineqlin
ans =
    3.1111
    0.4444
         0
lambda.lower
ans =
     0
     0

Nonzero elements of the vectors in the fields of lambda indicate active constraints at the solution. In this case, the first and second inequality constraints (in lambda.ineqlin) are active constraints (i.e., the solution is on their constraint boundaries). For this problem, all the lower bounds are inactive.

Notes

In general quadprog locates a local solution unless the problem is strictly convex.

Better numerical results are likely if you specify equalities explicitly, using Aeq and beq, instead of implicitly, using lb and ub.

If the components of x have no upper (or lower) bounds, then quadprog prefers that the corresponding components of ub (or lb) be set to Inf (or -Inf for lb) as opposed to an arbitrary but very large positive (or negative in the case of lower bounds) number.

Large-Scale Optimization

By default, quadprog uses the large-scale algorithm if you specify the feasible region using one, but not both, of the following types of constraints:

• Upper and lower bounds constraints

• Linear equality constraints, in which the columns of the constraint matrix Aeq are linearly independent. Aeq is typically sparse.

You cannot use inequality constraints with the large-scale algorithm. If the preceding conditions are not met, quadprog reverts to the medium-scale algorithm.

If you do not supply x0, or x0 is not strictly feasible, quadprog chooses a new strictly feasible (centered) starting point.

If an equality constrained problem is posed and quadprog detects negative curvature, the optimization terminates because the constraints are not restrictive enough. In this case, exitflag is returned with the value -1, a message is displayed (unless the options Display option is 'off'), and the x returned is not a solution but a direction of negative curvature with respect to H.

Algorithm

Large-Scale Optimization

The large-scale algorithm is a subspace trust-region method based on the interior-reflective Newton method described in [1]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). See Trust-Region Methods for Nonlinear Minimization and Preconditioned Conjugate Gradient Method.

Medium-Scale Optimization

quadprog uses an active set method, which is also a projection method, similar to that described in [2]. It finds an initial feasible solution by first solving a linear programming problem. This method is discussed in Medium-Scale quadprog Algorithm.

Diagnostics

Large-Scale Optimization

The large-scale method does not allow equal upper and lower bounds. For example, if lb(2) == ub(2), then quadprog gives this error:

Equal upper and lower bounds not permitted
in this large-scale method.
Use equality constraints and the medium-scale
method instead.

If you only have equality constraints you can still use the large-scale method. But if you have both equalities and bounds, you must use the medium-scale method.

Medium-Scale Optimization

When the problem is infeasible, quadprog gives this warning:

Warning: The constraints are overly stringent;
     there is no feasible solution.

In this case, quadprog produces a result that minimizes the worst case constraint violation.

When the equality constraints are inconsistent, quadprog gives this warning:

Warning: The equality constraints are overly stringent;
     there is no feasible solution.

Unbounded solutions, which can occur when the Hessian H is negative semidefinite, can result in

Warning: The solution is unbounded and at infinity;
     the constraints are not restrictive enough.

In this case, quadprog returns a value of x that satisfies the constraints.

Limitations

At this time the only levels of display, using the Display option in options, are 'off' and 'final'; iterative output using 'iter' is not available.

The solution to indefinite or negative definite problems is often unbounded (in this case, exitflag is returned with a negative value to show that a minimum was not found); when a finite solution does exist, quadprog might only give local minima, because the problem might be nonconvex.

Large-Scale Optimization

The linear equalities cannot be dependent (i.e., Aeq must have full row rank). Note that this means that Aeq cannot have more rows than columns. If either of these cases occurs, the medium-scale algorithm is called instead.

Large-Scale Problem Coverage and Requirements

References

[1] Coleman, T.F. and Y. Li, "A Reflective Newton Method for Minimizing a Quadratic Function Subject to Bounds on some of the Variables," SIAM Journal on Optimization, Vol. 6, Number 4, pp. 1040-1058, 1996.

[2] Gill, P. E. and W. Murray, and M.H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

See Also

linprog, lsqlin, optimtool

For more details about the quadprog algorithms, see Quadratic Programming. For more examples of quadratic programming, see Quadratic Programming Examples.

optimtool

Recommended Products

• MATLAB
• Signal Processing Toolbox
• Optimization Toolbox
• Statistics Toolbox
• Control System Toolbox

Get MATLAB trial software

Includes the most popular MATLAB recorded presentations with Q&A sessions led by MATLAB experts.

Get the Interactive Kit