【MPC】②quadprog求解正定、半正定、负定二次规划

一、概述

第一期文章已经详细介绍，二次规划问题和matlab的quadprog函数的使用方法，详情可见：quadprog函数详解。在二次规划问题中，根据海森矩阵的正定性，二次规划问题可以分为严格凸、凸、非凸二次型问题。为了验证，matlab的quadprog函数对三种二次型问题的求解能力，本文生成各种类型的海森矩阵，并尝试用quadprog进行求解。

二、Matlab验证

（一）海森正定、半正定、负定矩阵生成

海森矩阵首先需要满足矩阵对称性，同时根据特征值判定矩阵的正定性。因此，为了简单起见直接生成对角阵进行验证。

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

（二）矩阵正定性验证

矩阵正定性判断：主要是利用eig函数求解矩阵的特征值，并判单特征值的正负。

% 判断矩阵m是正定、半正定还是负定
% 需要输入矩阵m
% 例如：m = [2 -1; -1 2]; 

if issymmetric(m) % 检查矩阵是否对称
    % disp('矩阵对称');
    d = eig(m); % 计算矩阵特征值
    if all(d > 0)
        disp('矩阵正定');
    elseif all(d >= 0)
        disp('矩阵半正定');
    else
        disp('矩阵负定');
    end
else
    disp('矩阵不对称');
end

（三）各类型二次型求解程序

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)

三、求解结果

三种类型的二次规划问题，quadprog函数均能求解。但是非凸情况，会有非凸函数提示。

找到满足约束条件的最小值。
优化完成，因为目标函数在可行的方向上是不递减的。 在可行的方向上不减少，在最优性容许值内。
并且约束条件在约束条件容许值内得到满足。 <停止标准的详细信息>

四、quadprog算法选择

quadprog求解器包含三种二次规划算法，可以使用 optimoptions 配置 Algorithm 选项。

• ‘interior-point-convex’（默认值）
• ‘trust-region-reflective’
• 'active-set

算法选择原则：

• 如果您遇到凸问题，或不知道您的问题是否为凸问题，请使用 ‘interior-point-convex’。
• 如果您的非凸问题只有边界或只有线性等式约束，请使用 ‘trust-region-reflective’。
• 如果您有具有大量线性约束而没有大量变量的半正定问题，请尝试 ‘active-set’。