# Documentation

### This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the 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(H,f,...) [x,fval,exitflag] = quadprog(H,f,...) [x,fval,exitflag,output] = quadprog(H,f,...) [x,fval,exitflag,output,lambda] = quadprog(H,f,...) ```

## Description

Finds a minimum for a problem specified by

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

f, lb, and ub can be passed as vectors or matrices; see Matrix Arguments.

`x = quadprog(H,f)` returns a vector `x` that minimizes `1/2*x'*H*x + f'*x`. `H` must be positive definite for the problem to have a finite minimum.

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

`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 = []`.

`x = quadprog(H,f,A,b,Aeq,beq,lb,ub)` solves the preceding problem subject to the additional restrictions `lb `` x `` ub`. `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 Input Arguments.

`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 = []`.

`x = quadprog(problem)` returns the minimum for `problem`, where `problem` is a structure described in Input Arguments. Create `problem` by exporting a problem using the Optimization app; see Exporting Your Work.

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

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

```[x,fval,exitflag] = quadprog(H,f,...)``` `exitflag`, a scalar that describes the exit condition of `quadprog`.

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

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

## Input Arguments

`H`

Symmetric matrix of doubles. Represents the quadratic in the expression `1/2*x'*H*x + f'*x`.

The `'interior-point-convex'` 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.

`f`

Vector of doubles. Represents the linear term in the expression `1/2*x'*H*x + f'*x`.

`A`

Matrix of doubles. Represents the linear coefficients in the constraints `A*x `` b`.

`b`

Vector of doubles. Represents the constant vector in the constraints `A*x `` b`.

`Aeq`

Matrix of doubles. Represents the linear coefficients in the constraints `Aeq*x = beq`.

`beq`

Vector of doubles. Represents the constant vector in the constraints `Aeq*x = beq`.

`lb`

Vector of doubles. Represents the lower bounds elementwise in `lb `` x `` ub`.

`ub`

Vector of doubles. Represents the upper bounds elementwise in `lb `` x `` ub`.

`x0`

Vector of doubles. Optional. The initial point for the `trust-region-reflective` algorithm when there are only bound constraints.

If you do not give `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.

`options`

Options created using `optimoptions` or the Optimization app.

Some options are absent from the `optimoptions` display. These options are listed in italics. For details, see View Options.

All Algorithms

 `Algorithm` Choose the algorithm:`'interior-point-convex'` (default)`'trust-region-reflective'`The `'trust-region-reflective'` algorithm handles problems with only bounds, or only linear equality constraints, but not both. The `'interior-point-convex'` algorithm handles only convex problems. 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 just the final output (default).The `'interior-point-convex'` algorithm allows additional values:`'iter'` gives iterative display.`'iter-detailed'` gives iterative display with a detailed exit message.`'final-detailed'` displays just 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 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'`, the default value is `1e-8`. For `optimset`, the 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 name is `TolX`. See Current and Legacy Option Name Tables.

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 name is `TolFun`. See Current and Legacy Option Name Tables. `HessianMultiplyFcn` Hessian multiply function, specified as a function handle. For large-scale structured problems, this function computes the Hessian matrix product `H*Y` without actually forming `H`. The function has the form`W = hmfun(Hinfo,Y)`where `Hinfo` and possibly some additional parameters contain the matrices used to compute `H*Y`.See Quadratic Minimization with Dense, Structured Hessian for an example that uses this option.For `optimset`, the name is `HessMult`. See Current and Legacy Option Name Tables. 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 name is `TolCon`. See Current and Legacy Option Name Tables.

`problem`

Structure encapsulating the `quadprog` inputs and options:

 `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

## Output Arguments

`x`

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.

`fval`

Value of `1/2*x'*H*x + f'*x` at the solution `x`, a double.

`exitflag`

Integer identifying the reason the algorithm terminated. The following lists the values of `exitflag` and the corresponding reasons the algorithm terminated:

 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`, step size smaller than `options.StepTolerance`, but constraints are not satisfied. `-3` Problem is unbounded. `interior-point-convex` Algorithm `2` Step size smaller than `options.StepTolerance`, constraints satisfied. `-6` Nonconvex problem detected. `-8` Unable to compute a step direction. `trust-region-reflective` Algorithm `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.

`output`

Structure containing information about the optimization. The fields are:

 `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 `message` Exit message

`lambda`

Structure containing the Lagrange multipliers at the solution `x` (separated by constraint type). The fields are:

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

For details, see Lagrange Multiplier Structures.

## Examples

Solve a simple quadratic programming problem: find values of `x` that minimize

`$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

x1 + x2 ≤ 2
x1 + 2x2 ≤ 2
2x1 + x2 ≤ 3
0 ≤ x1, 0 ≤ x2.

In matrix notation this is

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

where

1. Enter the 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);```
2. Set the options to use the `'interior-point-convex'` algorithm with no display:

```options = optimoptions('quadprog',... 'Algorithm','interior-point-convex','Display','off');```
3. Call `quadprog`:

```[x,fval,exitflag,output,lambda] = ... quadprog(H,f,A,b,[],[],lb,[],[],options);```
4. Examine the final point, function value, and exit flag:

``` x,fval,exitflag x = 0.6667 1.3333 fval = -8.2222 exitflag = 1```
5. 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. You can see `H` is positive definite by noting all its eigenvalues are positive:

```eig(H) ans = 0.3820 2.6180```

Use the `'interior-point-convex'` algorithm to solve a sparse quadratic program.

1. Generate a sparse symmetric matrix for the quadratic form:

```v = sparse([1,-.25,0,0,0,0,0,-.25]); H = gallery('circul',v);```
2. Include the linear term for the problem:

`f = -4:3;`
3. Include the constraint that the sum of the terms in the solution `x` must be less than `-2`:

`A = ones(1,8);b = -2;`
4. Set options to use the `'interior-point-convex'` algorithm and iterative display:

```opts = optimoptions('quadprog',... 'Algorithm','interior-point-convex','Display','iter');```
5. Run the `quadprog` solver and observe the iterations:

```[x fval eflag output lambda] = quadprog(H,f,A,b,[],[],[],[],[],opts); First-order Total relative Iter f(x) Feasibility optimality error 0 -2.000000e+000 1.000e+001 4.500e+000 1.200e+001 1 -2.630486e+001 0.000e+000 9.465e-002 9.465e-002 2 -2.639877e+001 0.000e+000 3.914e-005 3.914e-005 3 -2.639881e+001 0.000e+000 3.069e-015 6.883e-015 Minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the default value of the function tolerance, and constraints are satisfied to within the default value of the constraint tolerance.```
6. Examine the solution:

```fval,eflag fval = -26.3988 eflag = 1```

For the `'interior-point-convex'` algorithm, an exit flag of `1` means the result is a global minimum.

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

## Alternatives

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.

## 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., W. Murray, and M. H. Wright, Practical Optimization, Academic Press, London, UK, 1981.

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