# mpcActiveSetSolver

Solve quadratic programming problem using active-set algorithm

Since R2020a

## Syntax

``````[x,exitflag] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options)``````
``````[x,exitflag,iA,lambda] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options)``````

## Description

Using `mpcActiveSetSolver`, you can solve a quadratic programming (QP) problem using an active-set algorithm. This function provides access to the built-in Model Predictive Control Toolbox™ active-set QP solver.

Using an active-set solver can provide fast and robust performance for small-scale and medium-scale optimization problems in both double and single precision.

This solver is useful for:

• Advanced MPC applications that are beyond the scope of Model Predictive Control Toolbox software.

• Custom QP applications, including applications that require code generation.

Alternatively, you can also access the built-in interior-point QP solver using `mpcInteriorPointSolver`.

example

``````[x,exitflag] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options)``` finds an optimal solution `x` to a quadratic programming problem by minimizing the objective function:$J=\frac{1}{2}{x}^{⊺}Hx+{f}^{⊺}x$subject to inequality constraints $Ax\le b$ and equality constraints ${A}_{eq}x={b}_{eq}$. `exitflag` indicates the validity of `x`.```
``````[x,exitflag,iA,lambda] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,options)``` also returns the active inequalities `iA` at the solution, and the Lagrange multipliers `lambda` for the solution.```

## Examples

collapse all

Find the values of x that minimize

`$f\left(x\right)=0.5{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}\ge 0\\ {x}_{2}\ge 0\\ {x}_{1}+{x}_{2}\le 2\\ -{x}_{1}+2{x}_{2}\le 2\\ 2{x}_{1}+{x}_{2}\le 3.\end{array}$`

Specify the Hessian matrix and linear multiplier vector for the objective function.

```H = [1 -1; -1 2]; f = [-2; -6];```

Specify the inequality constraint parameters.

```A = [-1 0; 0 -1; 1 1; -1 2; 2 1]; b = [0; 0; 2; 2; 3];```

Define `Aeq` and `beq` to indicate that there are no equality constraints.

```n = length(f); Aeq = zeros(0,n); beq = zeros(0,1);```

Create a default option set for `mpcActiveSetSolver`.

`opt = mpcActiveSetOptions;`

To cold start the solver, define all inequality constraints as inactive.

`iA0 = false(size(b));`

Solve the QP problem.

`[x,exitflag] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,opt);`

Examine the solution `x`.

`x`
```x = 2×1 0.6667 1.3333 ```

When solving the QP problem, you can also determine which inequality constraints are active for the solution.

`[x,exitflag,iA,lambda] = mpcActiveSetSolver(H,f,A,b,Aeq,beq,iA0,opt);`

Check the active inequality constraints. An active inequality constraint is at equality for the optimal solution.

`iA`
```iA = 5x1 logical array 0 0 1 1 0 ```

There is a single active inequality constraint. View the Lagrange multiplier for this constraint.

`lambda.ineqlin(1)`
```ans = 0 ```

## Input Arguments

collapse all

Hessian matrix, specified as a symmetric n-by-n matrix, where n > 0 is the number of optimization variables.

The active-set QP algorithm requires that the Hessian matrix be positive definite. To determine whether `H` is positive definite, use the `chol` function.

`[~,p] = chol(H);`

If `p` = 0, then `H` is positive definite. Otherwise, `p` is a positive integer.

The active-set QP algorithm computes the lower-triangular Cholesky decomposition (`Linv`) of the Hessian matrix. If your application requires repetitive calls of `mpcActiveSetSolver` using a constant Hessian matrix, you can improve computational efficiency by computing `Linv` once and passing it to `mpcActiveSetSolver` instead of the Hessian matrix. To do so, you must set the `UseHessianAsInput` field of `options` to `false`.

```options = mpcActiveSetOptions; options.UseHessianAsInput = false;```

To compute `Linv`, use the following code.

```[L,p] = chol(H,'lower'); Linv = linsolve(L,eye(size(L)),struct('LT',true));```

Multiplier of the objective function linear term, specified as a column vector of length n, where n is the number of optimization variables.

Linear inequality constraint coefficients, specified as an m-by-n matrix, where n is the number of optimization variables and m is the number of inequality constraints.

If your problem has no inequality constraints, use `zeros(0,n)`.

Right-hand side of inequality constraints, specified as a column vector of length m, where m is the number of inequality constraints.

If your problem has no inequality constraints, use `zeros(0,1)`.

Linear equality constraint coefficients, specified as a q-by-n matrix, where n is the number of optimization variables and q <= n is the number of equality constraints. Equality constraints must be linearly independent with ```rank(Aeq) = q```.

If your problem has no equality constraints, use `zeros(0,n)`.

Right-hand side of equality constraints, specified as a column vector of length q, where q is the number of equality constraints.

If your problem has no equality constraints, use `zeros(0,1)`.

Initial active inequalities, where the equal portion of the inequality is true, specified as a logical vector of length m, where m is the number of inequality constraints. Specify `iA0` as follows:

• If your problem has no inequality constraints, use `false(0,1)`.

• For a cold start, use `false(m,1)`.

• For a warm start, set `iA0(i) == true` to start the algorithm with the ith inequality constraint active. Use the optional output argument `iA` from a previous solution to specify `iA0` in this way. If both `iA0(i)` and `iA0(j)` are `true`, then rows i and j of `A` should be linearly independent. Otherwise, the solution can fail with `exitflag = -2`.

Option set for `mpcActiveSetSolver`, specified as an `ActiveSet` options object, which you can create using `mpcActiveSetOptions`.

## Output Arguments

collapse all

Optimal solution to the QP problem, returned as a column vector of length n, where n is the number of optimization variables. `mpcActiveSetSolver` always returns a value for `x`. To determine whether the solution is optimal or feasible, check `exitflag`.

Solution validity indicator, returned as an integer according to the following table.

ValueDescription
`> 0``x` is optimal. In this case, `exitflag` represents the number of iterations performed during optimization.
`0`

The maximum number of iterations was reached. Solution `x` might be suboptimal or infeasible.

To determine if `x` is infeasible, check whether the solution violates the constraint tolerance specified in `options`.

`feasible = (A*x-b) <= options.ConstraintTolerance;`

If any element of `feasible` is `false`, then `x` is infeasible.

`-1`The problem appears to be infeasible, that is, the constraint $Ax\le b$ cannot be satisfied.
`-2`An unrecoverable numerical error occurred.

Active inequalities, where the equal portion of the inequality is true, returned as a logical vector of length m. If `iA(i) == true`, then the ith inequality is active for solution `x`.

Use `iA` to warm start a subsequent `mpcActiveSetSolver` solution.

Lagrange multipliers, returned as a structure with the following fields.

FieldDescription
`ineqlin`Multipliers of the inequality constraints, returned as a vector of length n. When the solution is optimal, the elements of `ineqlin` are nonnegative.
`eqlin`Multipliers of the equality constraints, returned as a vector of length q. There are no sign restrictions in the optimal solution.

## Tips

• The KWIK algorithm requires that the Hessian matrix H be positive definite. When calculating `Linv`, use the `chol` function.

`[L,p] = chol(H,'lower');`

If `p` = 0, then `H` is positive definite. Otherwise, `p` is a positive integer.

• `mpcActiveSetSolver` provides access to the default active-set QP solver used by Model Predictive Control Toolbox software. Use this command to solve QP problems in your own custom MPC applications. For an example of a custom MPC application using `mpcActiveSetSolver`, see Solve Custom MPC Quadratic Programming Problem and Generate Code.

## Algorithms

`mpcActiveSetSolver` solves the QP problem using an active-set method, the KWIK algorithm, based on [1]. For more information, see QP Solvers.

## References

[1] Schmid, C., and L.T. Biegler. "Quadratic Programming Methods for Reduced Hessian SQP." Computers & Chemical Engineering 18, no. 9 (September 1994): 817–32. https://doi.org/10.1016/0098-1354(94)E0001-4.

## Version History

Introduced in R2020a