quadprog (Optimization Toolbox)

Solve the quadratic programming problem

where 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,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 problem above while additionally satisfying the equality constraints Aeq*x = beq.

x = quadprog(H,f,A,b,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.

x = quadprog(H,f,A,b,lb,ub,x0)

sets the starting point to x0.

x = quadprog(H,f,A,b,lb,ub,x0,options)

minimizes with the optimization parameters specified in the structure options.

[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.

Arguments

The arguments passed into the function are described in Table 1-1. The arguments returned by the function are described in Table 1-2. Details relevant to quadprog are included below for options, exitflag, lambda, and output.


`options`	Optimization parameter options. You can set or change the values of these parameters using the `optimset` function. Some parameters apply to all algorithms, some are only relevant when using the large-scale algorithm, and others are only relevant when using the medium-scale algorithm. We start by describing the `LargeScale` option since it states a preference for which algorithm to use. It is only a preference since certain conditions must be met to use the large-scale algorithm. For `quadprog`, when the problem has only upper and lower bounds, i.e., no linear inequalities or equalities are specified, the default algorithm is the large-scale method. Or, if the problem given to `quadprog` has only linear equalities, i.e., no upper and lower bounds or linear inequalities are specified, and the number of equalities is no greater than the length of `x`, the default algorithm is the large-scale method. Otherwise the medium-scale algorithm will be used. The parameter to set an algorithm preference: `LargeScale` - Use large-scale algorithm if possible when set to `'on'`. Use medium-scale algorithm when set to `'off'`.
	Parameters used by both the large-scale and medium-scale algorithms: `Diagnostics` - Print diagnostic information about the function to be minimized. `Display` - Level of display. `'off'` displays no output; `'iter'` displays output at each iteration; `'final'` displays just the final output.
	`MaxIter` - Maximum number of iterations allowed. `TolFun` - Termination tolerance on the function value. `TolX` - Termination tolerance on `x`.
	Parameters used by the large-scale algorithm only: `MaxPCGIter` - Maximum number of PCG (preconditioned conjugate gradient) iterations (see the Algorithm section below). `PrecondBandWidth` - Upper bandwidth of preconditioner for PCG. By default, diagonal preconditioning is used (upper bandwidth of 0). For some problems, increasing the bandwidth reduces the number of PCG iterations. `TolPCG` - Termination tolerance on the PCG iteration. `TypicalX` - Typical `x` values.
`exitflag`	Describes the exit condition: `> 0` indicates that the function converged to a solution `x`. `0` indicates that the maximum number of function evaluations or iterations was reached. `< 0` indicates that the function did not converge to a solution.
`lambda`	A structure containing the Lagrange multipliers at the solution `x` (separated by constraint type): `lambda.lower` for the lower bounds `lb`. `lambda.upper` for the upper bounds `ub`. `lambda.ineqlin` for the linear inequalities. `lambda.eqlin` for the linear equalities.
`output`	A structure whose fields contain information about the optimization: `output.iterations` - The number of iterations taken. `output.algorithm` - The algorithm used. `output.cgiterations` - The number of PCG iterations (large-scale algorithm only). `output.firstorderopt` - A measure of first-order optimality (large-scale algorithm only).

Examples

Find values of x that minimize

subject to

First note that this function may 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: []
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 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. 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, then 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 parameter is 'off'), and the x returned is not a solution but a direction of negative curvature with respect to H.

Algorithm

Large-scale optimization. When the problem given to quadprog has only upper and lower bounds, i.e., no linear inequalities or equalities are specified, the default algorithm is the large-scale method. Or, if the problem given to quadprog has only linear equalities, i.e., no upper and lower bounds or linear inequalities are specified the default algorithm is the large-scale method.

This method is a subspace trust-region method based on the interior-reflective Newton method described in [2]. Each iteration involves the approximate solution of a large linear system using the method of preconditioned conjugate gradients (PCG). See the trust-region and preconditioned conjugate gradient method descriptions in the Large-Scale Algorithms chapter.

Medium-scale optimization. quadprog uses an active set method, which is also a projection method, similar to that described in [1]. It finds an initial feasible solution by first solving a linear programming problem. This method is discussed in the Introduction to Algorithms chapter.

Diagnostics

Large-scale optimization. The large-scale code will not allow equal upper and lower bounds. For example if lb(2)==ub(2) then quadprog gives the 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 solution 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, may 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 parameter 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 a minimum was not found); when a finite solution does exist, quadprog may only give local minima since the problem may 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 occur, the medium-scale algorithm will be called instead. See Table 1-4 for more information on what problem formulations are covered and what information must be provided.

References

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

[2] 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.

[ Previous | Help Desk ]