二次规划问题(qp)和序列二次规划问题(sqp)的简单理解

二次规划

二次规划问题(qp)是目标函数为二次函数，约束条件为线性约束的问题，可以简化为初中数学进行表达，即:

已知目标函数为:

需满足约束条件

求在为多少时取最小值

以上即为最简单的一维的二次规划表达例子，扩展到高维的话，则为向量矩阵形式，但原理是一样的。

对于高维二次规划问题，求解过程并不像初中数学那样简单，因此会采用其他的方法，如内点法和有效集法等。

对于工程师而言，我们在编写代码的时候，并不关心二次规划问题的求解细节，所以一般是把二次规划问题建立好后，直接调用三方库进行求解。

目前常用的c++求解库是qpoases和osqp，MATLAB的话有个quadprog可用于求解qp。

二次规划问题是一个典型的非线性规划问题，与非线性规划相对的概念是线性规划，对，就是高中数学的学的那个。

二次规划问题还是一个典型的凸优化问题。凸优化问题(Convex optimization problem)要求目标函数为凸函数，而且定义域为凸集。这里的定义域指的就是约束，简单理解就是就是凸集，就是非凸集。另外，凸优化还要求等式约束均为仿射函数。凸优化问题的特点是局部最优解就是全局最优解。

注意: 只要目标函数不是二次函数，或约束不是线性约束，满足其中任意一个，则此问题就不是二次规划问题。非二次规划问题可能是凸问题，也可能是非凸问题。

非二次规划问题求解思路如下:

1. 当目标函数仍为二次函数，但约束为非线性约束时，我们可采用ipopt三方库直接求解，或者用序列二次规划(sqp)进行求解，下节详细介绍。

2. 当目标函数不为二次函数，且约束为非线性约束时，我们似乎只能采用ipopt三方库进行求解了。

序列二次规划

当二次规划的约束为非线性约束时，通常会采用sqp进行求解，用连续求解qp的方法来得到非线性约束条件下的最优解，上述的qpoases和osqp均无法直接求解非线性约束问题，所以如果使用这两个库的话，
只能采用sqp的方法求解，sqp会求解一连串的qp问题。注意，sqp是结果，而不是原因，只有在非线性约束的情况下才会考虑sqp求解，如果问题本身就是线性约束，则直接用qp解就行。

我们将上述qp问题进行改造，得到一个非线性优化问题:

已知目标函数为:

需满足约束条件

求在为多少时取最小值

求解步骤如下:

1. 因为约束为非线性约束，所以先将约束进行线性化，约束原方程为，这里我们选择在的位置进行线性化，根据泰勒展开，
   我们可以得到，所以原约束条件变成了

2. 步骤1将非线性约束转换成了线性约束，因此是标准qp，可以用三方库进行第一次qp求解，求解得到一个最优值，这里解出来最优解为，记录此时目标函数值

3. 将非线性约束在第2步解出的处进行线性化，线性化后原约束变成了，调用第三方库解第二次qp，这里解出来最优解为记录此时目标函数值

4. 比较和的值的差距，发现差了0.0625，假设我们判断收敛的阈值为两次qp间解算的目标函数值差距不能超过0.001，则此时判断sqp并未收敛，继续计算

5. 将非线性约束在第3步解出的处进行线性化，调用第三方库解第三次qp，这里解出来最优解为记录此时目标函数值

6. 将非线性约束在第5步解出的处进行线性化，调用第三方库解第四次qp，这里解出来最优解为记录此时目标函数值

7. 将非线性约束在第6步解出的处进行线性化，调用第三方库解第五次qp，这里解出来最优解为记录此时目标函数值

8. 比较和的值的差距，发现差距不到0.001了，此时我们认为sqp已经收敛了，此时得到的最优解即为整个sqp问题的最优解

仍无法理解的问题: 为什么连续求解qp直至最后收敛，其结果就是问题最优解，这个证明是怎么来的，有什么简单的理解方法吗? 欢迎大家讨论补充。