[MPC] ① quadratic programming problem matlab solver quadprog

One 、 summary

Quadratic programming is a quadratic optimization problem with linear constraints . stay Matlab in ,quadprog It is a quadratic objective function solver with linear constraints .

（ One ） Standard form of secondary Planning

$$\underset{x}{\min }\frac{1}{2}{\mathbf{x}}^{\mathbf{T}}\mathbf{H}\mathbf{x}+{\mathbf{f}}^{\mathbf{T}}\mathbf{x}$$
Actually H yes Hessian front , yes n ride n Symmetric matrix of .

1、 Positive definiteness and function optimality of Hessian matrix

• If Hessian The matrix is positive semidefinite , Then we say that the formula is a convex quadratic programming , In this case, the difficulty of the problem is similar to that of linear programming . If at least one vector satisfies the constraint and The feasible region There is a lower bound , Then the convex quadratic programming problem has a global minimum .
• If it is positive definite , Then this kind of quadratic programming is strictly convex quadratic programming , Then the global minimum is unique .
• If it's a Indefinite matrix , Is a nonconvex quadratic programming , This kind of secondary planning is more challenging , Because they have multiple stationary points and local minimum points .

2、 Basic mathematical concepts

• Basic concepts ：https://blog.csdn.net/jbb0523/article/details/50598523
• Convex Strictly convex , give an example ：https://zhuanlan.zhihu.com/p/399549564

3、 On the positive definiteness of symmetric matrices

• Positive definite matrix ： All eigenvalues of the matrix are greater than 0
• Positive semidefinite matrices ： All eigenvalues of the matrix are non negative
• Negative definite matrix ： All eigenvalues of the matrix are less than 0

https://blog.csdn.net/Infinity_07/article/details/109569450

4、matlab just 、 Half positive 、 Negative definite matrix generation , And quadprog verification
（1）matlab Judge positive qualitative ：

%  Judgment matrix m It's positive definite 、 Semi positive definite or negative definite 
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

（2）matlab Operation of generating positive definite matrix

https://blog.csdn.net/zhao523520704/article/details/52918376/

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

（ Two ） Input parameters

Symbol	Parameter meaning
H	Quadratic objective matrix
f	Linear objective vector
A	Linear inequality matrix
b	Linear inequality vector
Aeq	Linear equality constraint matrix
beq	Linear equality constraint vector
lb	Lower bound
ub	upper bound

（ 3、 ... and ） Output parameters

Symbol	Parameter meaning
x	Explain , Returns... As a vector of real numbers
wsout	Hot start object of solution
fval	The value of the objective function at the re solution
exitflag	quadprog The reason for the stop
output	Information about the optimization process , Returns... As a structure
lambda	Lagrange multiplier at the solution

Two 、MATLAB Basic grammar

x = quadprog(H,f)
x = quadprog(H,f,A,b)
x = quadprog(H,f,A,b,Aeq,beq)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0)
x = quadprog(H,f,A,b,Aeq,beq,lb,ub,x0,options)
x = quadprog(problem)
[x,fval] = quadprog(___)
[x,fval,exitflag,output] = quadprog(___)
[x,fval,exitflag,output,lambda] = quadprog(___)
[wsout,fval,exitflag,output,lambda] = quadprog(H,f,A,b,Aeq,beq,lb,ub,ws)

3、 ... and 、MATLAB Typical solution examples

（ One ） Quadratic programming with linear inequality constraints

H = [1 -1; -1 2]; 
f = [-2; -6];
A = [1 1; -1 2; 2 1];
b = [2; 2; 3];
[x,fval,exitflag,output,lambda] = quadprog(H,f,A,b);

x =
0.6667
1.3333
fval = -8.2222
exitflag =
1

（ Two ） Quadratic programming with linear equality constraints

H = [1 -1; -1 2]; 
f = [-2; -6];
Aeq = [1 1];
beq = 0;
[x,fval,exitflag,output,lambda] = ...
   quadprog(H,f,[],[],Aeq,beq)

x = -0.8000
0.8000
fval = -1.6000
exitflag =
1

（ 3、 ... and ） Quadratic programming with linear constraints and boundaries

H = [1,-1,1
    -1,2,-2
    1,-2,4];
f = [2;-3;1];
lb = zeros(3,1);
ub = ones(size(lb));
Aeq = ones(1,3);
beq = 1/2;
x = quadprog(H,f,[],[],Aeq,beq,lb,ub);