[MPC] ② quadprog solves positive definite, semi positive definite and negative definite quadratic programming

One 、 summary

The first issue of the article has already introduced , Quadratic programming problem and matlab Of quadprog How to use the function , Details visible ：quadprog Function details . In the quadratic programming problem , According to the positive definiteness of Hessian matrix , Quadratic programming problems can be divided into strictly convex 、 Convex 、 Nonconvex quadratic problem . In order to verify ,matlab Of quadprog Function's ability to solve three quadratic problems , In this paper, various types of Hessian matrices are generated , And try quadprog To solve the .

Two 、Matlab verification

（ One ） Hessen positive definite 、 Semi positive definite 、 Negative definite matrix generation

Hessian matrix first needs to satisfy matrix symmetry , At the same time, the positive definiteness of the matrix is determined according to the eigenvalue . therefore , For simplicity, the diagonal matrix is generated directly for verification .

H_posi=diag([1,2,3]);
H_semi=diag([0,2,3]);
H_nega=diag([-1,-2,-3]);

（ Two ） Matrix positive definiteness verification

Matrix positive definiteness judgment ： Mainly to make use of eig Function to solve the eigenvalue of a matrix , And judge the positive and negative of single eigenvalue .

%  Judgment matrix m It's positive definite 、 Semi positive definite or negative definite 
%  Matrix input required m
%  for example ：m = [2 -1; -1 2]; 

if issymmetric(m) %  Check whether the matrix is symmetrical 
    % disp(' Matrix symmetry ');
    d = eig(m); %  Calculate the eigenvalue of the matrix 
    if all(d > 0)
        disp(' The matrix is positive definite ');
    elseif all(d >= 0)
        disp(' Matrix positive semidefinite ');
    else
        disp(' Matrix negative definite ');
    end
else
    disp(' Matrix asymmetry ');
end

（ 3、 ... and ） Various types of quadratic solver

clear;clc;
H_posi=diag([1,2,3]);
H_semi=diag([0,2,3]);
H_nega=diag([-1,-2,-3]);

A = [1 1 1; -1 2 1; 2 1 1];
b = [2; 2; 3];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;
x_posi = quadprog(H_posi,f,A,b,Aeq,beq,lb,ub)
x_semi = quadprog(H_semi,f,A,b,Aeq,beq,lb,ub)
x_nega = quadprog(H_nega,f,A,b,Aeq,beq,lb,ub)

3、 ... and 、 Solution result

Three types of quadratic programming problems ,quadprog Functions can be solved . But the nonconvex case , There will be non convex function prompt .

Find the minimum value that meets the constraint .
Optimization completed , Because the objective function does not decrease in the feasible direction . Do not reduce in the feasible direction , Within the optimality tolerance .
And the constraint conditions are satisfied within the allowable value of the constraint conditions . < Stop standard details >

Four 、quadprog Algorithm to choose

quadprog The solver contains three quadratic programming algorithms , have access to optimoptions To configure Algorithm Options .

• ‘interior-point-convex’（ The default value is ）
• ‘trust-region-reflective’
• 'active-set

Algorithm selection principle ：

• If you encounter a convex problem , Or don't know if your problem is convex , Please use ‘interior-point-convex’.
• If your nonconvex problem has only boundaries or only linear equality constraints , Please use ‘trust-region-reflective’.
• If you have a positive semidefinite problem with a large number of linear constraints without a large number of variables , Please try ‘active-set’.