# mpcqpsolver

(To be removed) Solve a quadratic programming problem using the KWIK algorithm

mpcqpsolver will be removed in a future release. Use mpcActiveSetSolver instead. For more information, see Compatibility Considerations.

## Description

example

[x,status] = mpcqpsolver(Linv,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\ge b$, and equality constraints ${A}_{eq}x={b}_{eq}$. status indicates the validity of x.

example

[x,status,iA,lambda] = mpcqpsolver(Linv,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 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.

Aeq = [];
beq = zeros(0,1);

Find the lower-triangular Cholesky decomposition of H.

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

It is good practice to verify that H is positive definite by checking if p = 0.

p
p = 0

Create a default option set for mpcActiveSetSolver.

opt = mpcqpsolverOptions;

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

iA0 = false(size(b));

Solve the QP problem.

[x,status] = mpcqpsolver(Linv,f,A,b,Aeq,beq,iA0,opt);

Examine the solution, x.

x
x = 2×1

0.6667
1.3333

Find the values of x that minimize

$f\left(x\right)=3{x}_{1}^{2}+0.5{x}_{2}^{2}-2{x}_{1}{x}_{2}-3{x}_{1}+4{x}_{2},$

subject to the constraints

$\begin{array}{l}{x}_{1}\ge 0\\ {x}_{1}+{x}_{2}\le 5\\ {x}_{1}+2{x}_{2}\le 7.\end{array}$

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

H = [6 -2; -2 1];
f = [-3; 4];

Specify the inequality constraint parameters.

A = [1 0; -1 -1; -1 -2];
b = [0; -5; -7];

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

Aeq = [];
beq = zeros(0,1);

Find the lower-triangular Cholesky decomposition of H.

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

Verify that H is positive definite by checking if p = 0.

p
p = 0

Create a default option set for mpcqpsolver.

opt = mpcqpsolverOptions;

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

iA0 = false(size(b));

Solve the QP problem.

[x,status,iA,lambda] = mpcqpsolver(Linv,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 = 3x1 logical array

1
0
0

There is a single active inequality constraint.

View the Lagrange multiplier for this constraint.

lambda.ineqlin(1)
ans = 5.0000

## Input Arguments

collapse all

Inverse of lower-triangular Cholesky decomposition of Hessian matrix, specified as an n-by-n matrix, where n > 0 is the number of optimization variables. For a given Hessian matrix, H, Linv can be computed as follows:

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

H is an n-by-n matrix, which must be symmetric and positive definite. If p = 0, then H is positive definite.

Note

The KWIK algorithm requires the computation of Linv instead of using H directly, as in the quadprog (Optimization Toolbox) command.

Multiplier of objective function linear term, specified as a column vector of length n.

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

If your problem has no inequality constraints, use [].

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

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

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

If your problem has no equality constraints, use [].

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

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 according to the following:

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

• For a cold start, 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 status = -2.

Option set for mpcqpsolver, specified as a structure created using mpcqpsolverOptions.

## Output Arguments

collapse all

Optimal solution to the QP problem, returned as a column vector of length n. mpcqpsolver always returns a value for x. To determine whether the solution is optimal or feasible, check the solution status.

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

ValueDescription
> 0x is optimal. status represents the number of iterations performed during optimization.
0The maximum number of iterations was reached. The solution, x, may be suboptimal or infeasible.
-1The problem appears to be infeasible, that is, the constraint $Ax\ge b$ cannot be satisfied.
-2An 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 the solution x.

Use iA to warm start a subsequent mpcqpsolver solution.

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

FieldDescription
ineqlinMultipliers of the inequality constraints, returned as a vector of length n. When the solution is optimal, the elements of ineqlin are nonnegative.
eqlinMultipliers 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:

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

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

• mpcqpsolver provides access to the QP solver used by Model Predictive Control Toolbox™ software. Use this command to solve QP problems in your own custom MPC applications.

## Algorithms

mpcqpsolver 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 R2015b

expand all