mpcActiveSetSolver

Solve quadratic programming problem using active-set algorithm

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.

[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

Solve Quadratic Programming Problem Using Active-Set Solver

Find the values of x that minimize

$$f\left(x\right)=0.5x_1^2+x_2^2-x_1{x}_2-2x_1-6x_2,$$

subject to the constraints

$$\begin{array}{l}{x}_1\ge 0\\ x_2\ge 0\\ x_1+x_2\le 2\\ -x_1+2x_2\le 2\\ 2x_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 = 5×1 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

H — Hessian matrix

n-by-n matrix

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));

f — Multiplier of the objective function linear term

column vector of length n

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

A — Linear inequality constraint coefficients

m-by-n matrix

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

b — Right-hand side of inequality constraints

column vector of length m

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

Aeq — Linear equality constraint coefficients

q-by-n matrix

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

beq — Right-hand side of equality constraints

column vector of length q

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

iA0 — Initial active inequalities

logical vector of length m

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.

options — Option set for mpcActiveSetSolver

ActiveSet object

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

Output Arguments

x — Optimal solution to the QP problem

column vector of length n

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.

exitflag — Solution validity indicator

positive integer | 0 | -1 | -2

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

Value	Description
> 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.

iA — Active inequalities

logical vector of length m

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.

lambda — Lagrange multipliers

structure

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

Field	Description
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 for Linear MPC.

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.

Extended Capabilities

C/C++ Code Generation

Generate C and C++ code using MATLAB® Coder™.

Usage notes and limitations:

• You can use mpcActiveSetSolver as a general-purpose QP solver that supports code generation. To specify solver options, use mpcActiveSetOptions. Create the function myCode, which uses mpcActiveSetSolver and mpcActiveSetOptions.

  function [out1,out2] = myCode(in1,in2)
  %#codegen
  ...
  options = mpcActiveSetOptions;
  [x,status] = mpcActiveSetSolver(Linv,f,A,b,Aeq,Beq,iA0,options);
  ...

  Generate C code with MATLAB^® Coder™.

  func = 'myCode';
  cfg = coder.config('mex'); % or 'lib', 'dll'
  codegen('-config',cfg,func,'-o',func);

• For code generation, use the same precision for all real inputs, including options. Configure the precision as 'double' or 'single' using mpcActiveSetOptions.

GPU Code Generation
Generate CUDA® code for NVIDIA® GPUs using GPU Coder™.

Version History

Introduced in R2020a