bat365 Homepage

quadprog

Quadratic programming

collapse all in page

Syntax

x = quadprog(H,f)

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,output]
= quadprog(___)

[x,fval,exitflag,output,lambda]
= quadprog(___)

[wsout,fval,exitflag,output,lambda]
= quadprog(H,f,A,b,Aeq,beq,lb,ub,ws)

Description

Solver for quadratic objective functions with linear constraints.

quadprog finds a minimum for a problem specified by

$\min_{x} \frac{1}{2} x^{T} H x + f^{T} x such that {\begin{matrix} A \cdot x \leq b, \\ A e q \cdot x = b e q, \\ l b \leq x \leq u b . \end{matrix}$

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.

Note

x0 is a required argument for the 'active-set' algorithm.

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, a structure described in problem. Create the problem structure using dot notation or the struct function. 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.

example

[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws) starts quadprog from the data in the warm start object ws, using the options in ws. The returned argument wsout contains the solution point in wsout.X. By using wsout as the initial warm start object in a subsequent solver call, quadprog can work faster.

Examples

collapse all

Quadratic Program with Linear Constraints

Open Live Script

Find the minimum of

$f (x) = \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} \leq 2 \\ - x_{1} + 2 x_{2} \leq 2 \\ 2 x_{1} + x_{2} \leq 3 . \end{array}$

In quadprog syntax, this problem is to minimize

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

where

$\begin{array}{l} H = [\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}] \\ f = [\begin{matrix} - 2 \\ - 6 \end{matrix}], \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];

Call quadprog.

[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,A,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.

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

x,fval,exitflag

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

Quadratic Program with Linear Equality Constraint

Open Live Script

Find the minimum of

$f (x) = \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 (x) = \frac{1}{2} x^{T} H x + f^{T} x$ ,

where

$\begin{array}{l} H = [\begin{matrix} 1 & - 1 \\ - 1 & 2 \end{matrix}] \\ f = [\begin{matrix} - 2 \\ - 6 \end{matrix}], \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] = ...
   quadprog(H,f,[],[],Aeq,beq);

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

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

Quadratic Minimization with Linear Constraints and Bounds

Open Live Script

Find the x that minimizes the quadratic expression

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

where

$H = [\begin{matrix} 1 & - 1 & 1 \\ - 1 & 2 & - 2 \\ 1 & - 2 & 4 \end{matrix}]$ , $f = [\begin{matrix} 2 \\ - 3 \\ 1 \end{matrix}]$ ,

subject to the constraints

$0 \leq x \leq 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.

x = quadprog(H,f,[],[],Aeq,beq,lb,ub)

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.

Quadratic Minimization with Nondefault Options

Open Live Script

Set options to monitor the progress of quadprog.

options = optimoptions('quadprog','Display','iter');

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.

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

 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.

Quadratic Problem from `prob2struct`

Open Live Script

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);

Solve the problem using quadprog.

[x,fval] = quadprog(problem)

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.

fval = -8.2222

Return `quadprog` Objective Function Value

Open Live Script

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;
[x,fval] = quadprog(H,f,A,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.

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

Examine `quadprog` Optimization Process

Open Live Script

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} H x + f^{T} x$

subject to

$0 \leq x \leq 1$ ,

where

$H = [\begin{matrix} 2 & 1 & - 1 \\ 1 & 3 & \frac{1}{2} \\ - 1 & \frac{1}{2} & 5 \end{matrix}]$ , $f = [\begin{matrix} 4 \\ - 7 \\ 12 \end{matrix}]$ .

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.

options = optimoptions('quadprog','Display','iter');

Call quadprog with four outputs.

[x fval,exitflag,output] = quadprog(H,f,[],[],[],[],lb,ub,[],options)

 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.

fval = -5.5000

exitflag = 1

output = struct with fields:
            message: 'Minimum found that satisfies the constraints....'
          algorithm: 'interior-point-convex'
      firstorderopt: 1.5921e-09
    constrviolation: 0
         iterations: 4
       linearsolver: 'dense'
       cgiterations: []

Return `quadprog` Lagrange Multipliers

Open Live Script

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);
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb);

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

Return Warm Start Object

To speed subsequent quadprog calls, create a warm start object.

options = optimoptions('quadprog','Algorithm','active-set');
x0 = [1 2 3];
ws = optimwarmstart(x0,options);

Solve a quadratic program using ws.

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [-7;-12;-15];
A = [1,1,1];
b = 3;
lb = zeros(3,1);
tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc

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.
Elapsed time is 0.021717 seconds.

Change the objective function and solve the problem again.

f = [-10;-15;-20];

tic
[ws,fval,exitflag,output,lambda] = quadprog(H,f,A,b,[],[],lb,[],ws);
toc

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.
Elapsed time is 0.018485 seconds.

Input Arguments

collapse all

`H` — Quadratic objective term
symmetric real matrix

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

`f` — Linear objective term
real vector

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

`A` — Linear inequality constraints
real matrix

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, consider these inequalities:

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30,

Specify the inequalities by entering the following 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

`b` — Linear inequality constraints
real vector

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, consider these inequalities:

x₁ + 2x₂ ≤ 10
3x₁ + 4x₂ ≤ 20
5x₁ + 6x₂ ≤ 30.

Specify the inequalities by entering the following 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

`Aeq` — Linear equality constraints
real matrix

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, consider these inequalities:

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20,

Specify the inequalities by entering the following 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

`beq` — Linear equality constraints
real vector

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, consider these equalities:

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

Specify the equalities by entering the following 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

`lb` — Lower bounds
real vector | real array

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 lb has fewer elements than x0, solvers issue a warning.

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

Data Types: double

`ub` — Upper bounds
real vector | real array

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 ub has fewer elements than x0, solvers issue a warning.

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

Data Types: double

`x0` — Initial point
real vector

Initial point, specified as a real vector. The length of x0 is the number of rows or columns of H.

x0 applies to the 'trust-region-reflective' algorithm when the problem has only bound constraints. x0 also applies to the 'active-set' algorithm.

Note

x0 is a required argument for the 'active-set' algorithm.

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

`options` — Optimization options
output of `optimoptions` | structure such as `optimset` returns

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 Optimization Options.

All Algorithms

`Algorithm`	Choose the algorithm: `'interior-point-convex'` (default) `'trust-region-reflective'` `'active-set'` 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. The `'active-set'` algorithm handles indefinite problems provided that the projection of `H` onto the nullspace of `Aeq` is positive semidefinite. 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'` and `'active-set'` algorithms allow 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)`. `'active-set'` has a default of `10(numberOfVariables + numberOfConstraints)`. For all other algorithms and problems, the default value is `200`. For `optimset`, the option name is `MaxIter`. See Current and Legacy Option Names.
`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 the `'interior-point-convex'` and `'active-set'` algorithms, the default value is `1e-8`. See Tolerances and Stopping Criteria. For `optimset`, the option name is `TolFun`. See Current and Legacy Option Names.
`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 `'active-set'`, the default value is `1e-8`. For `optimset`, the option name is `TolX`. See Current and Legacy Option Names.

'trust-region-reflective' Algorithm Only

`FunctionTolerance`	Termination tolerance on the function value; a positive scalar. The default value depends on the problem type: bound-constrained problems use `100*eps`, and linear equality-constrained problems use `1e-6`. See Tolerances and Stopping Criteria. For `optimset`, the option name is `TolFun`. See Current and Legacy Option Names.
`HessianMultiplyFcn`	Hessian multiply function, specified as a function handle. For large-scale structured problems, this function computes the Hessian matrix product `HY` without actually forming `H`. The function has the form W = hmfun(Hinfo,Y) where `Hinfo` (and potentially some additional parameters) contain the matrices used to compute `HY`. See Quadratic Minimization with Dense, Structured Hessian for an example that uses this option. For `optimset`, the option name is `HessMult`. See Current and Legacy Option Names.
MaxPCGIter	Maximum number of PCG (preconditioned conjugate gradient) iterations; a positive scalar. The default is `max(1,floor(numberOfVariables/2))` for bound-constrained problems. For equality-constrained problems, `quadprog` ignores `MaxPCGIter` and uses `MaxIterations` to limit the number of PCG iterations. For more information, see Preconditioned Conjugate Gradient Method.
PrecondBandWidth	Upper bandwidth of the preconditioner for PCG; a nonnegative integer. By default, `quadprog` uses diagonal preconditioning (upper bandwidth `0`). For some problems, increasing the bandwidth reduces the number of PCG iterations. Setting `PrecondBandWidth` to `Inf` uses a direct factorization (Cholesky) rather than the conjugate gradients (CG). The direct factorization is computationally more expensive than CG, but produces a better quality step toward the solution.
`SubproblemAlgorithm`	Determines how the iteration step is calculated. The default, `'cg'`, takes a faster but less accurate step than `'factorization'`. See trust-region-reflective quadprog Algorithm.
TolPCG	Termination tolerance on the PCG iteration; a positive scalar. The default is `0.1`.
`TypicalX`	Typical `x` values. The number of elements in `TypicalX` equals the number of elements in `x0`, the starting point. The default value is `ones(numberOfVariables,1)`. `quadprog` uses `TypicalX` internally for scaling. `TypicalX` has an effect only when `x` has unbounded components, and when a `TypicalX` value for an unbounded component exceeds `1`.

'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 Names.

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.
'dense' — Use dense linear algebra.

'active-set' Algorithm Only

ConstraintTolerance

Tolerance on the constraint violation; a positive scalar. The default value is 1e-8.

For optimset, the option name is TolCon. See Current and Legacy Option Names.

ObjectiveLimit

A tolerance (stopping criterion) that is a scalar. If the objective function value goes below ObjectiveLimit and the current point is feasible, the iterations halt because the problem is unbounded, presumably. The default value is -1e20.

`problem` — Problem structure
structure

Problem structure, specified as a structure with these fields:

`H`	Symmetric matrix in `1/2x'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 `optimset`

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

Note

You cannot use warm start with the problem argument.

Data Types: struct

`ws` — Warm start object
object created using `optimwarmstart`

Warm start object, specified as an object created using optimwarmstart. The warm start object contains the start point and options, and optional data for memory size in code generation. See Warm Start Best Practices.

Example: ws = optimwarmstart(x0,options)

Output Arguments

collapse all

`x` — Solution
real vector

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.

`wsout` — Solution warm start object
`QuadprogWarmStart` object

Solution warm start object, returned as a QuadprogWarmStart object. The solution point is wsout.X.

You can use wsout as the input warm start object in a subsequent quadprog call.

`fval` — Objective function value at solution
real scalar

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.

`exitflag` — Reason `quadprog` stopped
integer

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.
`'active-set'` Algorithm
`-6`	Nonconvex problem detected; projection of `H` onto the nullspace of `Aeq` is not positive semidefinite.

Note

Occasionally, the 'active-set' algorithm halts with exit flag 0 when the problem is, in fact, unbounded. Setting a higher iteration limit also results in exit flag 0.

`output` — Information about optimization process
structure

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

`lambda` — Lagrange multipliers at solution
structure

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.

`'active-set'`

The 'active-set' algorithm is a projection method, similar to the one described in [2]. The algorithm is not large-scale; see Large-Scale vs. Medium-Scale Algorithms. For more information, see active-set quadprog Algorithm.

Warm Start

A warm start object maintains a list of active constraints from the previous solved problem. The solver carries over as much active constraint information as possible to solve the current problem. If the previous problem is too different from the current one, no active set information is reused. In this case, the solver effectively executes a cold start in order to rebuild the list of active constraints.

Alternative Functionality

App

The Optimize Live Editor task provides a visual interface for quadprog.

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.

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

quadprog supports code generation using either the codegen (MATLAB Coder) function or the MATLAB^® Coder™ app. You must have a MATLAB Coder license to generate code.
The target hardware must support standard double-precision floating-point computations. You cannot generate code for single-precision or fixed-point computations.
Code generation targets do not use the same math kernel libraries as MATLAB solvers. Therefore, code generation solutions can vary from solver solutions, especially for poorly conditioned problems.
quadprog does not support the problem argument for code generation.
```
[x,fval] = quadprog(problem) % Not supported
```
All quadprog input matrices such as A, Aeq, lb, and ub must be full, not sparse. You can convert sparse matrices to full by using the full function.
The lb and ub arguments must have the same number of entries as the number of columns in H or must be empty [].
If your target hardware does not support infinite bounds, use optim.coder.infbound.
For advanced code optimization involving embedded processors, you also need an Embedded Coder^® license.
You must include options for quadprog and specify them using optimoptions. The options must include the Algorithm option, set to 'active-set'.
```
options = optimoptions('quadprog','Algorithm','active-set');
[x,fval,exitflag] = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options);
```
Code generation supports these options:
- Algorithm — Must be 'active-set'
- ConstraintTolerance
- MaxIterations
- ObjectiveLimit
- OptimalityTolerance
- StepTolerance

Generated code has limited error checking for options. The recommended way to update an option is to use optimoptions, not dot notation.

opts = optimoptions('quadprog','Algorithm','active-set');
opts = optimoptions(opts,'MaxIterations',1e4); % Recommended
opts.MaxIterations = 1e4; % Not recommended

Do not load options from a file. Doing so can cause code generation to fail. Instead, create options in your code.
If you specify an option that is not supported, the option is typically ignored during code generation. For reliable results, specify only supported options.

For an example, see Generate Code for quadprog.

Version History

Introduced before R2006a

quadprog

Syntax

Description

Examples

Quadratic Program with Linear Constraints

Quadratic Program with Linear Equality Constraint

Quadratic Minimization with Linear Constraints and Bounds

Quadratic Minimization with Nondefault Options

Quadratic Problem from prob2struct

Return quadprog Objective Function Value

Examine quadprog Optimization Process

Return quadprog Lagrange Multipliers

Return Warm Start Object

Input Arguments

H — Quadratic objective term symmetric real matrix

f — Linear objective term real vector

A — Linear inequality constraints real matrix

b — Linear inequality constraints real vector

Aeq — Linear equality constraints real matrix

beq — Linear equality constraints real vector

lb — Lower bounds real vector | real array

ub — Upper bounds real vector | real array

x0 — Initial point real vector

options — Optimization options output of optimoptions | structure such as optimset returns

problem — Problem structure structure

ws — Warm start object object created using optimwarmstart

Output Arguments

x — Solution real vector

wsout — Solution warm start object QuadprogWarmStart object

fval — Objective function value at solution real scalar

exitflag — Reason quadprog stopped integer

output — Information about optimization process structure

lambda — Lagrange multipliers at solution structure

Algorithms

'interior-point-convex'

'trust-region-reflective'

'active-set'

Warm Start

Alternative Functionality

App

References

Extended Capabilities

C/C++ Code Generation Generate C and C++ code using MATLAB® Coder™.

Version History

See Also

Topics

Quadratic Problem from `prob2struct`

Return `quadprog` Objective Function Value

Examine `quadprog` Optimization Process

Return `quadprog` Lagrange Multipliers

`H` — Quadratic objective term
symmetric real matrix

`f` — Linear objective term
real vector

`A` — Linear inequality constraints
real matrix

`b` — Linear inequality constraints
real vector

`Aeq` — Linear equality constraints
real matrix

`beq` — Linear equality constraints
real vector

`lb` — Lower bounds
real vector | real array

`ub` — Upper bounds
real vector | real array

`x0` — Initial point
real vector

`options` — Optimization options
output of `optimoptions` | structure such as `optimset` returns

`problem` — Problem structure
structure

`ws` — Warm start object
object created using `optimwarmstart`

`x` — Solution
real vector

`wsout` — Solution warm start object
`QuadprogWarmStart` object

`fval` — Objective function value at solution
real scalar

`exitflag` — Reason `quadprog` stopped
integer

`output` — Information about optimization process
structure

`lambda` — Lagrange multipliers at solution
structure

`'interior-point-convex'`

`'trust-region-reflective'`

`'active-set'`

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.