mpcqpsolver

Solve a quadratic programming problem using the KWIK algorithm

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=12xHx+fx

subject to inequality constraints Axb, and equality constraints Aeqx=beq. 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(x)=0.5x12+x22-x1x2-2x1-6x2,

subject to the constraints

x10x20x1+x22-x1+2x222x1+x23.

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

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(x)=3x12+0.5x22-2x1x2-3x1+4x2,

subject to the constraints

x10x1+x25x1+2x27.

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 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 Axb 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. For an example of a custom MPC application using mpcqpsolver, see Solve Custom MPC Quadratic Programming Problem and Generate Code.

Algorithms

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

The KWIK algorithm defines inequality constraints as Axb rather than Axb, as in the quadprog command.

References

[1] Schmid, C., and L. T. Biegler. "Quadratic programming methods for reduced Hessian SQP." Computers & Chemical Engineering. Vol. 18, No. 9, 1994, pp. 817–832.

Extended Capabilities

Introduced in R2015b