轨迹规划-二次规划QP
1. 二次规划的由来
在1940年左右（1939年 Leonid Kantorovich 总结发表了线性规划）， 线性规划LP被提出来， 10年后， QP作为Non-Linear Programming, NLP被总结发表。
顾名思义， 二次规划就是把一次规划（线性规划， LP）的目标公式扩展到二次函数：
这里 Q 是对称矩阵（Symmetric Matrix）
那么这样修改目标之后， 会带来什么改变？
首先从图上来看， 最大的变化就是二次带来等高线（ contour line ）不再是直线， 这样使得最值点不再是限制多面体的角上，可能是边上，或者内部。
同时， 这样改变之后有什么好处？
QP第一次统一了线性规划LP和最小二乘法LS,
欧式距离： 最小二乘法，LS
Hamitton 距离，或者Chebyshev距离： 线性回归， LP
这样，基于利用QP就可以统一描述不同距离公式下的回归的参数求解。
前面， 我们说了QP是LP和LP在不同角度的扩展：
-
QP是LP的扩展， LP是QP在二次项系数为0时候（Q=0）的特例。
-
QP是LS的扩展， LS是QP在一次项系数为0， 二次项系数为I（单位阵），并且没有限制的时候的特例：
2. KKT条件
3. 二次规划的求解
一般来说， QP的求解主要有两大方面的限制（如下图所示）：
首先是Q矩阵， Q矩阵是不是半正定（Semi-Definite）的， 如果不是意味着， 目标函数是非凸（non-convex）的情况。
其次是条件关系， 是不是全部是等式（eqality-constrained）， 如果是的话， 就是一个可以直接求解的KKT系统（KKT System）， 否则的话，就是一般情况下的Convex QP问题。
总结：
对于二次规划问题，本质上就是优化问题，无非就是求解二次目标函数，使其在线性约束的条件下达到最优的问题。因为数学库中一般都有现成的求解器，比如apllo中二次规划使用的是osqp求解器，所以在实际工程中需要着重考虑的是：不是如何对二次规划进行求解，而是如何进行建模。
参考文献：