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

二次规划

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

已知目标函数为:

f
(
x
)
=
x
2
−
2
∗
x
+
1
f(x)=x^2-2*x+1
f(x)=x2−2∗x+1

$x$需满足约束条件

$0<x<2$

求$f(x)$在$x$为多少时取最小值

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

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

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

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

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

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

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

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

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

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

序列二次规划

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

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

已知目标函数为:

f
(
x
)
=
x
2
−
2
∗
x
+
1
f(x)=x^2-2*x+1
f(x)=x2−2∗x+1

$x$需满足约束条件

x
2
<
0.5
x^2<0.5
x2<0.5

求$f(x)$在$x$为多少时取最小值

求解步骤如下:

1. 因为约束为非线性约束，所以先将约束进行线性化，约束原方程为
   c
   (
   x
   )
   =
   x
   2
   c(x)=x^2
   c(x)=x2，这里我们选择在$x=10$的位置进行线性化，根据泰勒展开
   f
   (
   x
   )
   =
   f
   (
   x
   )
   +
   f
   ′
   (
   x
   )
   1
   !
   (
   x
   −
   x
   )
   f(x)=f(x_0)+\frac{f'(x_0)}{1!}(x-x_0)
   f(x)=f(x0​)+1!f′(x0​)​(x−x0​)，
   我们可以得到$c(x)=20x-100$，所以原约束条件变成了$20x-100<0.5$

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

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

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

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

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

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

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

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