Documentation

## Description

Solver for quadratic objective functions with linear constraints.

quadprog finds a minimum for a problem specified by

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

You can pass f, lb, and ub as vectors or matrices; see Matrix Arguments.

### Note

quadprog applies only to the solver-based approach. For a discussion of the two optimization approaches, see First Choose Problem-Based or Solver-Based Approach.

x = quadprog(H,f) returns a vector x that minimizes 1/2*x'*H*x + f'*x. The input H must be positive definite for the problem to have a finite minimum. If H is positive definite, then the solution x = H\(-f).

example

x = quadprog(H,f,A,b) minimizes 1/2*x'*H*x + f'*x subject to the restrictions A*x  b. The input A is a matrix of doubles, and b is a vector of doubles.

example

x = quadprog(H,f,A,b,Aeq,beq) solves the preceding problem subject to the additional restrictions Aeq*x = beq. Aeq is a matrix of doubles, and beq is a vector of doubles. If no inequalities exist, set A = [] and b = [].

example

x = quadprog(H,f,A,b,Aeq,beq,lb,ub) solves the preceding problem subject to the additional restrictions lb  x  ub. The inputs lb and ub are vectors of doubles, and the restrictions hold for each x component. If no equalities exist, set Aeq = [] and beq = [].

### Note

If the specified input bounds for a problem are inconsistent, the output x is x0 and the output fval is [].

quadprog resets components of x0 that violate the bounds lb  x  ub to the interior of the box defined by the bounds. quadprog does not change components that respect the bounds.

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) solves the preceding problem starting from the vector x0. If no bounds exist, set lb = [] and ub = []. Some quadprog algorithms ignore x0; see x0.

example

x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options) solves the preceding problem using the optimization options specified in options. Use optimoptions to create options. If you do not want to give an initial point, set x0 = [].

example

x = quadprog(problem) returns the minimum for problem, where problem is a structure described in Description. Create problem by exporting a problem using the Optimization app; see Exporting Your Work. Alternatively, create a problem structure from an OptimizationProblem object by using prob2struct.

example

[x,fval] = quadprog(___), for any input variables, also returns fval, the value of the objective function at x:

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

example

[x,fval,exitflag,output] = quadprog(___) also returns exitflag, an integer that describes the exit condition of quadprog, and output, a structure that contains information about the optimization.

example

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

## Examples

collapse all

Find the minimum of

$f\left(x\right)=\frac{1}{2}{x}_{1}^{2}+{x}_{2}^{2}-{x}_{1}{x}_{2}-2{x}_{1}-6{x}_{2}$

subject to the constraints

$\begin{array}{l}{x}_{1}+{x}_{2}\le 2\\ -{x}_{1}+2{x}_{2}\le 2\\ 2{x}_{1}+{x}_{2}\le 3.\end{array}$

In quadprog syntax, this problem is to minimize

$f\left(x\right)=\frac{1}{2}{x}^{T}Hx+{f}^{T}x$,

where

$\begin{array}{l}\mathit{H}=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]\\ \mathit{f}=\left[\begin{array}{c}-2\\ -6\end{array}\right],\end{array}$

subject to the linear constraints.

To solve this problem, first enter the coefficient matrices.

H = [1 -1; -1 2];
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

[x,fval,exitflag,output,lambda] = ...
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Examine the final point, function value, and exit flag.

x,fval,exitflag
x = 2×1

0.6667
1.3333

fval = -8.2222
exitflag = 1

An exit flag of 1 means the result is a local minimum. Because H is a positive definite matrix, this problem is convex, so the minimum is a global minimum.

Confirm that H is positive definite by checking its eigenvalues.

eig(H)
ans = 2×1

0.3820
2.6180

Find the minimum of

$f\left(x\right)=\frac{1}{2}{x}_{1}^{2}+{x}_{2}^{2}-{x}_{1}{x}_{2}-2{x}_{1}-6{x}_{2}$

subject to the constraint

${x}_{1}+{x}_{2}=0.$

In quadprog syntax, this problem is to minimize

$f\left(x\right)=\frac{1}{2}{x}^{T}Hx+{f}^{T}x$,

where

$\begin{array}{l}\mathit{H}=\left[\begin{array}{cc}1& -1\\ -1& 2\end{array}\right]\\ \mathit{f}=\left[\begin{array}{c}-2\\ -6\end{array}\right],\end{array}$

subject to the linear constraint.

To solve this problem, first enter the coefficient matrices.

H = [1 -1; -1 2];
f = [-2; -6];
Aeq = [1 1];
beq = 0;

Call quadprog, entering [] for the inputs A and b.

[x,fval,exitflag,output,lambda] = ...
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Examine the final point, function value, and exit flag.

x,fval,exitflag
x = 2×1

-0.8000
0.8000

fval = -1.6000
exitflag = 1

An exit flag of 1 means the result is a local minimum. Because H is a positive definite matrix, this problem is convex, so the minimum is a global minimum.

Confirm that H is positive definite by checking its eigenvalues.

eig(H)
ans = 2×1

0.3820
2.6180

Find the x that minimizes the quadratic expression

$\frac{1}{2}{x}^{T}Hx+{f}^{T}x$

where

$\mathit{H}=\left[\begin{array}{ccc}1& -1& 1\\ -1& 2& -2\\ 1& -2& 4\end{array}\right]$, $\mathit{f}=\left[\begin{array}{c}2\\ -3\\ 1\end{array}\right]$,

subject to the constraints

$0\le x\le 1$, $\sum x=1/2$.

To solve this problem, first enter the coefficients.

H = [1,-1,1
-1,2,-2
1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;

Call quadprog, entering [] for the inputs A and b.

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

0.0000
0.5000
0.0000

Set options to monitor the progress of quadprog.

Define a problem with a quadratic objective and linear inequality constraints.

H = [1 -1; -1 2];
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];

To help write the quadprog function call, set the unnecessary inputs to [].

Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = [];

Call quadprog to solve the problem.

Iter            Fval  Primal Infeas    Dual Infeas  Complementarity
0   -8.884885e+00   3.214286e+00   1.071429e-01     1.000000e+00
1   -8.331868e+00   1.321041e-01   4.403472e-03     1.910489e-01
2   -8.212804e+00   1.676295e-03   5.587652e-05     1.009601e-02
3   -8.222204e+00   8.381476e-07   2.793826e-08     1.809485e-05
4   -8.222222e+00   3.064216e-14   1.352696e-12     7.525735e-13

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

0.6667
1.3333

Create a problem structure using a Problem-Based Optimization Workflow. Create an optimization problem equivalent to Quadratic Program with Linear Constraints.

x = optimvar('x',2);
objec = x(1)^2/2 + x(2)^2 - x(1)*x(2) - 2*x(1) - 6*x(2);
prob = optimproblem('Objective',objec);
prob.Constraints.cons1 = sum(x) <= 2;
prob.Constraints.cons2 = -x(1) + 2*x(2) <= 2;
prob.Constraints.cons3 = 2*x(1) + x(2) <= 3;

Convert prob to a problem structure.

problem = prob2struct(prob);

Warning: Your Hessian is not symmetric. Resetting H=(H+H')/2.
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 2×1

0.6667
1.3333

fval = -8.2222

Solve a quadratic program and return both the solution and the objective function value.

H = [1,-1,1
-1,2,-2
1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

-3.5714
2.9286
3.6429

fval = -47.1786

Check that the returned objective function value matches the value computed from the quadprog objective function definition.

fval2 = 1/2*x'*H*x + f'*x
fval2 = -47.1786

To see the optimization process for quadprog, set options to show an iterative display and return four outputs. The problem is to minimize

$\frac{1}{2}{x}^{T}Hx+{f}^{T}x$

subject to

$0\le x\le 1$,

where

$\mathit{H}=\left[\begin{array}{ccc}2& 1& -1\\ 1& 3& \frac{1}{2}\\ -1& \frac{1}{2}& 5\end{array}\right]$, $\mathit{f}=\left[\begin{array}{c}4\\ -7\\ 12\end{array}\right]$.

Enter the problem coefficients.

H = [2 1 -1
1 3 1/2
-1 1/2 5];
f = [4;-7;12];
lb = zeros(3,1);
ub = ones(3,1);

Set the options to display iterative progress of the solver.

Iter            Fval  Primal Infeas    Dual Infeas  Complementarity
0    2.691769e+01   1.582123e+00   1.712849e+01     1.680447e+00
1   -3.889430e+00   0.000000e+00   8.564246e-03     9.971731e-01
2   -5.451769e+00   0.000000e+00   4.282123e-06     2.710131e-02
3   -5.499997e+00   0.000000e+00   1.221903e-10     6.939689e-07
4   -5.500000e+00   0.000000e+00   5.842173e-14     3.469847e-10

Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
x = 3×1

0.0000
1.0000
0.0000

fval = -5.5000
exitflag = 1
output = struct with fields:
message: '...'
algorithm: 'interior-point-convex'
firstorderopt: 1.5921e-09
constrviolation: 0
iterations: 4
linearsolver: 'dense'
cgiterations: []

Solve a quadratic programming problem and return the Lagrange multipliers.

H = [1,-1,1
-1,2,-2
1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.

Examine the Lagrange multiplier structure lambda.

disp(lambda)
ineqlin: 12.0000
eqlin: [0x1 double]
lower: [3x1 double]
upper: [3x1 double]

The linear inequality constraint has an associated Lagrange multiplier of 12.

Display the multipliers associated with the lower bound.

disp(lambda.lower)
5.0000
0.0000
0.0000

Only the first component of lambda.lower has a nonzero multiplier. This generally means that only the first component of x is at the lower bound of zero. Confirm by displaying the components of x.

disp(x)
0.0000
1.5000
1.5000

## Input Arguments

collapse all

Quadratic objective term, specified as a symmetric real matrix. H represents the quadratic in the expression 1/2*x'*H*x + f'*x. If H is not symmetric, quadprog issues a warning and uses the symmetrized version (H + H')/2 instead.

If the quadratic matrix H is sparse, then by default, the 'interior-point-convex' algorithm uses a slightly different algorithm than when H is dense. Generally, the sparse algorithm is faster on large, sparse problems, and the dense algorithm is faster on dense or small problems. For more information, see the LinearSolver option description and interior-point-convex quadprog Algorithm.

Example: [2,1;1,3]

Data Types: double

Linear objective term, specified as a real vector. f represents the linear term in the expression 1/2*x'*H*x + f'*x.

Example: [1;3;2]

Data Types: double

Linear inequality constraints, specified as a real matrix. A is an M-by-N matrix, where M is the number of inequalities, and N is the number of variables (number of elements in x0). For large problems, pass A as a sparse matrix.

A encodes the M linear inequalities

A*x <= b,

where x is the column vector of N variables x(:), and b is a column vector with M elements.

For example, to specify

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

enter these constraints:

A = [1,2;3,4;5,6];
b = [10;20;30];

Example: To specify that the x components sum to 1 or less, use A = ones(1,N) and b = 1.

Data Types: double

Linear inequality constraints, specified as a real vector. b is an M-element vector related to the A matrix. If you pass b as a row vector, solvers internally convert b to the column vector b(:). For large problems, pass b as a sparse vector.

b encodes the M linear inequalities

A*x <= b,

where x is the column vector of N variables x(:), and A is a matrix of size M-by-N.

For example, to specify

x1 + 2x2 ≤ 10
3x1 + 4x2 ≤ 20
5x1 + 6x2 ≤ 30,

enter these constraints:

A = [1,2;3,4;5,6];
b = [10;20;30];

Example: To specify that the x components sum to 1 or less, use A = ones(1,N) and b = 1.

Data Types: double

Linear equality constraints, specified as a real matrix. Aeq is an Me-by-N matrix, where Me is the number of equalities, and N is the number of variables (number of elements in x0). For large problems, pass Aeq as a sparse matrix.

Aeq encodes the Me linear equalities

Aeq*x = beq,

where x is the column vector of N variables x(:), and beq is a column vector with Me elements.

For example, to specify

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,

enter these constraints:

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Example: To specify that the x components sum to 1, use Aeq = ones(1,N) and beq = 1.

Data Types: double

Linear equality constraints, specified as a real vector. beq is an Me-element vector related to the Aeq matrix. If you pass beq as a row vector, solvers internally convert beq to the column vector beq(:). For large problems, pass beq as a sparse vector.

beq encodes the Me linear equalities

Aeq*x = beq,

where x is the column vector of N variables x(:), and Aeq is a matrix of size Me-by-N.

For example, to specify

x1 + 2x2 + 3x3 = 10
2x1 + 4x2 + x3 = 20,

enter these constraints:

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Example: To specify that the x components sum to 1, use Aeq = ones(1,N) and beq = 1.

Data Types: double

Lower bounds, specified as a real vector or real array. If the number of elements in x0 is equal to the number of elements in lb, then lb specifies that

x(i) >= lb(i) for all i.

If numel(lb) < numel(x0), then lb specifies that

x(i) >= lb(i) for 1 <= i <= numel(lb).

If there are fewer elements in lb than in x0, solvers issue a warning.

Example: To specify that all x components are positive, use lb = zeros(size(x0)).

Data Types: double

Upper bounds, specified as a real vector or real array. If the number of elements in x0 is equal to the number of elements in ub, then ub specifies that

x(i) <= ub(i) for all i.

If numel(ub) < numel(x0), then ub specifies that

x(i) <= ub(i) for 1 <= i <= numel(ub).

If there are fewer elements in ub than in x0, solvers issue a warning.

Example: To specify that all x components are less than 1, use ub = ones(size(x0)).

Data Types: double

Initial point, specified as a real vector. This input is optional. x0 applies only to the 'trust-region-reflective' algorithm when there are only bound constraints.

If you do not specify x0, quadprog sets all components of x0 to a point in the interior of the box defined by the bounds. quadprog ignores x0 for the 'interior-point-convex' algorithm and for the 'trust-region-reflective' algorithm with equality constraints.

Example: [1;2;1]

Data Types: double

Optimization options, specified as the output of optimoptions or a structure such as optimset returns.

Some options are absent from the optimoptions display. These options appear in italics in the following table. For details, see View Options.

All Algorithms

 Algorithm Choose the algorithm:'interior-point-convex' (default)'trust-region-reflective'The 'interior-point-convex' algorithm handles only convex problems. The 'trust-region-reflective' algorithm handles problems with only bounds or only linear equality constraints, but not both. For details, see Choosing the Algorithm. Diagnostics Display diagnostic information about the function to be minimized or solved. The choices are 'on' or 'off' (default). Display Level of display (see Iterative Display):'off' or 'none' displays no output.'final' displays only the final output (default).The 'interior-point-convex' algorithm allows additional values:'iter' specifies an iterative display.'iter-detailed' specifies an iterative display with a detailed exit message.'final-detailed' displays only the final output with a detailed exit message. MaxIterations Maximum number of iterations allowed; a positive integer. For a 'trust-region-reflective' equality-constrained problem, the default value is 2*(numberOfVariables - numberOfEqualities).For all other algorithms and problems, the default value is 200.For optimset, the option name is MaxIter. See Current and Legacy Option Name Tables. OptimalityTolerance Termination tolerance on the first-order optimality; a positive scalar.For a 'trust-region-reflective' equality-constrained problem, the default value is 1e-6.For a 'trust-region-reflective' bound-constrained problem, the default value is 100*eps, about 2.2204e-14.For 'interior-point-convex' algorithms, the default value is 1e-8.For optimset, the option name is TolFun. See Current and Legacy Option Name Tables. StepTolerance Termination tolerance on x; a positive scalar.For 'trust-region-reflective', the default value is 100*eps, about 2.2204e-14.For 'interior-point-convex', the default value is 1e-12.For optimset, the option name is TolX. See Current and Legacy Option Name Tables.

'trust-region-reflective' Algorithm Only

'interior-point-convex' Algorithm Only

 ConstraintTolerance Tolerance on the constraint violation; a positive scalar. The default is 1e-8.For optimset, the option name is TolCon. See Current and Legacy Option Name Tables. LinearSolver Type of internal linear solver in the algorithm:'auto' (default) — Use 'sparse' if the H matrix is sparse and 'dense' otherwise.'sparse' — Use sparse linear algebra. See Sparse Matrices (MATLAB).'dense' — Use dense linear algebra.

Problem structure, specified as a structure with these fields:

 H Symmetric matrix in 1/2*x'*H*x f Vector in linear term f'*x Aineq Matrix in linear inequality constraints Aineq*x ≤ bineq bineq Vector in linear inequality constraints Aineq*x ≤ bineq Aeq Matrix in linear equality constraints Aeq*x = beq beq Vector in linear equality constraints Aeq*x = beq lb Vector of lower bounds ub Vector of upper bounds x0 Initial point for x solver 'quadprog' options Options created using optimoptions or the Optimization app

The required fields are H, f, solver, and options. When solving, quadprog ignores any fields in problem other than those listed.

Data Types: struct

## Output Arguments

collapse all

Solution, returned as a real vector. x is the vector that minimizes 1/2*x'*H*x + f'*x subject to all bounds and linear constraints. x can be a local minimum for nonconvex problems. For convex problems, x is a global minimum. For more information, see Local vs. Global Optima.

Objective function value at the solution, returned as a real scalar. fval is the value of 1/2*x'*H*x + f'*x at the solution x.

Reason quadprog stopped, returned as an integer described in this table.

 All Algorithms 1 Function converged to the solution x. 0 Number of iterations exceeded options.MaxIterations. -2 Problem is infeasible. Or, for 'interior-point-convex', the step size was smaller than options.StepTolerance, but constraints were not satisfied. -3 Problem is unbounded. 'interior-point-convex' Algorithm 2 Step size was smaller than options.StepTolerance, constraints were satisfied. -6 Nonconvex problem detected. -8 Unable to compute a step direction. 'trust-region-reflective' Algorithm 4 Local minimum found; minimum is not unique. 3 Change in the objective function value was smaller than options.FunctionTolerance. -4 Current search direction was not a direction of descent. No further progress could be made.

Information about the optimization process, returned as a structure with these fields:

 iterations Number of iterations taken algorithm Optimization algorithm used cgiterations Total number of PCG iterations ('trust-region-reflective' algorithm only) constrviolation Maximum of constraint functions firstorderopt Measure of first-order optimality linearsolver Type of internal linear solver, 'dense' or 'sparse' ('interior-point-convex' algorithm only) message Exit message

Lagrange multipliers at the solution, returned as a structure with these fields:

 lower Lower bounds lb upper Upper bounds ub ineqlin Linear inequalities eqlin Linear equalities

For details, see Lagrange Multiplier Structures.

## Algorithms

collapse all

### 'interior-point-convex'

The 'interior-point-convex' algorithm attempts to follow a path that is strictly inside the constraints. It uses a presolve module to remove redundancies and to simplify the problem by solving for components that are straightforward.

The algorithm has different implementations for a sparse Hessian matrix H and for a dense matrix. Generally, the sparse implementation is faster on large, sparse problems, and the dense implementation is faster on dense or small problems. For more information, see interior-point-convex quadprog Algorithm.

### 'trust-region-reflective'

The 'trust-region-reflective' 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). For more information, see trust-region-reflective quadprog Algorithm.

## Alternative Functionality

### App

You can use the Optimization app for quadratic programming. Enter optimtool at the MATLAB® command line, and choose the quadprog - Quadratic programming solver. For more information, see Optimization App.

### Problem-Based Approach

You can solve quadratic programming problems using the Problem-Based Optimization Setup. For examples, see Quadratic Programming.

## 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, 1996, pp. 1040–1058.

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

[3] Gould, N., and P. L. Toint. “Preprocessing for quadratic programming.” Mathematical Programming. Series B, Vol. 100, 2004, pp. 95–132.