mpcInteriorPointSolver

Solve a quadratic programming problem using an interior-point algorithm

Syntax

[x,exitflag] = mpcInteriorPointSolver(H,f,A,b,Aeq,beq,x0,options)

[x,exitflag,feasible,lambda] = mpcInteriorPointSolver(H,f,A,b,Aeq,beq,x0,options)

Description

Using mpcInteriorPointSolver, you can solve a quadratic programming (QP) problem using a primal-dual interior-point algorithm with a Mehrotra predictor-corrector. This function provides access to the built-in Model Predictive Control Toolbox™ interior-point QP solver.

Using an interior-point solver can provide superior performance for large-scale optimization problems, such as MPC applications that enforce constraints over large prediction and control horizons.

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 active-set QP solver using mpcActiveSetSolver.

[x,exitflag] = mpcInteriorPointSolver(H,f,A,b,Aeq,beq,x0,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,feasible,lambda] = mpcInteriorPointSolver(H,f,A,b,Aeq,beq,x0,options) also returns a logical flag feasible that indicates the feasibility of the solution and the Lagrange multipliers lambda for the solution.

Examples

Solve Quadratic Programming Problem Using Interior-Point 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);

As a best practice, verify that H is positive definite using the chol function.

[~,p] = chol(H);

If p = 0, then H is positive definite.

p

p = 
0

Create a default option set for mpcInteriorPointSolver.

opt = mpcInteriorPointOptions;

To cold start the solver, specify an initial guess of zeros for the elements of x.

x0 = zeros(n,1);

Solve the QP problem.

[x,exitflag] = mpcInteriorPointSolver(H,f,A,b,Aeq,beq,x0,opt);

Examine the solution x.

x

x = 2×1

    0.6667
    1.3333

Input Arguments

H — Hessian matrix

n-by-n matrix

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

The interior-point 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.

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

x0 — Initial guess

column vector of length n

Initial guess for the solution, where the equal portion of the inequality is true, specified as a column vector of length n, where n is the number of optimization variables. For a cold start, specify the initial guess as zeros(n,1).

options — Option set for mpcInteriorPointSolver

InteriorPoint object

Option set for mpcInteriorPointSolver, specified as an InteriorPoint options object, which you can create using mpcInteriorPointOptions.

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. mpcInteriorPointSolver always returns a value for x. To determine whether the solution is optimal or feasible, check exitflag and feasible.

exitflag — Solution validity indicator

positive integer | 0 | -1

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

Value	Description
> 0	x is optimal. exitflag represents the number of iterations performed during optimization.
0	The maximum number of iterations was reached before the solver could find an optimal solution. Solution x is feasible only if feasible is true.
-1	The problem appears to be infeasible; that is, the constraint $$Ax\le b$$ cannot be satisfied.

feasible — Solution feasibility

logical scalar

Solution feasibility, returned as a logical scalar. When exitflag is 0, the solver reached the maximum number of iterations without finding an optimal solution. This suboptimal solution, returned in x, is feasible only if feasible is true.

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

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

• mpcInteriorPointSolver provides access to the interior-point 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, see Solve Custom MPC Quadratic Programming Problem and Generate Code. This example uses mpcActiveSetSolver, however, the workflow applies to mpcInteriorPointSolver as well.

Algorithms

mpcInteriorPointSolver solves the QP problem using an interior-point method, based on [1]. For more information, see QP Solvers for Linear MPC.

References

[1] Nocedal, Jorge, and Stephen J. Wright. Numerical Optimization. New York, NY: Springer New York, 2006. https://doi.org/10.1007/978-0-387-40065-5.

Extended Capabilities

C/C++ Code Generation

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

Usage notes and limitations:

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

  function [out1,out2] = myCode(in1,in2)
  %#codegen
  ...
  options = mpcInteriorPointOptions;
  [x,exitflag] = mpcInteriorPointSolver(H,f,A,b,Aeq,Beq,x0,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 mpcInteriorPointOptions.

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

Version History

Introduced in R2020a