Documentation

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

`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 some `quadprog` algorithms:

• `active-set`

• `trust-region-reflective` 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.

All Algorithms

 `Algorithm` Choose the algorithm:`'interior-point-convex'` (default)`'trust-region-reflective'``'active-set'` (will be removed in a future release)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. `MaxIter` 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`.

All Algorithms Except active-set

 `TolFun` Termination tolerance on the function value, 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`. `TolX` 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-8`.

trust-region-reflective Algorithm Only

 `HessMult` Function handle for a Hessian multiply function. 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. `MaxPCGIter` Maximum number of PCG (preconditioned conjugate gradient) iterations, a positive scalar. The default is `max(1,floor(numberOfVariables/2))`. 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. `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

 `TolCon` Tolerance on the constraint violation, a positive scalar. The default is `1e-8`.

`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.MaxIter`. `-2` Problem is infeasible. `-3` Problem is unbounded. `interior-point-convex` Algorithm `-6` Nonconvex problem detected. `trust-region-reflective` Algorithm `3` Change in the objective function value was smaller than `options.TolFun`. `-4` Current search direction was not a direction of descent. No further progress could be made. `active-set` Algorithm `4` Local minimizer was found. `-7` Magnitude of search direction became too small. No further progress could be made. The problem is ill-posed or badly conditioned.

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

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.

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

`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. For more information, see `active-set` `quadprog` Algorithm.

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.