二次规划的kkt条件（二次规划问题(qp)和序列二次规划问题(sqp)的简单理解）
二次规划
二次规划问题(qp)是目标函数为二次函数 ，约束条件为线性约束的问题 ，可以简化为初中数学进行表达 ，即:
已知目标函数为:
f
(
x
)
=
x
2
−
2
∗
x
+
1
f(x)=x^2-2*x+1
f(x)=x2−2∗x+1x
x
x需满足约束条件<
x
<
2
0
0<x<2求
f
(
x
)
f(x)
f(x)在x
x
x为多少时取最小值以上即为最简单的一维的二次规划表达例子 ，扩展到高维的话 ，则
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就是非凸集 。另外 ，凸优化还要求等式约束均为仿射函数 。凸优化问题的特点是局部最优解就是全局最优解 。注意: 只要目标函数不是二次函数 ，或约束不是线性约束 ，满足其中任意一个 ，则此问题就不是二次规划问题 。非二次规划问题可能是凸问题 ，也可能是非凸问题 。
非二次规划问题求解思路如下:
当目标函数仍为二次函数 ，但约束为非线性约束时 ，我们可采用ipopt三方库直接求解 ，或者用序列二次规划(sqp)进行求解 ，下节详细介绍 。
当目标函数不为二次函数 ，且约束为非线性约束时 ，我们似乎只能采用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+1x
x
x需满足约束条件x
2
<
0.5
x^2<0.5
x2<0.5求
f
(
x
)
f(x)
f(x)在x
x
x为多少时取最小值求解步骤如下:
因为约束为非线性约束 ，所以先将约束进行线性化 ，约束原方程为
c
(
x
)
=
x
2
c(x)=x^2
c(x)=x2 ，这里我们选择在x
=
10
x=10
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
)
=
20
x
−
100
c(x)=20x-100
c(x)=20x−100 ，所以原约束条件变成了20
x
−
100
<
0.5
20x-100<0.5
20x−100<0.5步骤1将非线性约束转换成了线性约束 ，因此是标准qp ，可以用三方库进行第一次qp求解 ，求解得到一个最优
x
x
x值 ，这里解出来最优解为x
=
1
x=1
x=1 ，记录此时目标函数值f
1
=
f1=0
f1=0将非线性约束在第2步解出的
x
x
x处进行线性化 ，线性化后原约束变成了2
x
−
1
<
0.5
2x-1<0.5
2x−1<0.5 ，调用第三方库解第二次qp ，这里解出来最优解为x
=
0.75
，
x=0.75 ，
x=0.75 ，记录此时目标函数值f
2
=
0.0625
f2=0.0625
f2=0.0625比较
f
1
f1
f1和f
2
f2
f2的值的差距 ，发现差了0.0625 ，假设我们判断收敛的阈值为两次qp间解算的目标函数值差距不能超过0.001 ，则此时判断sqp并未收敛 ，继续计算将非线性约束在第3步解出的
x
x
x处进行线性化 ，调用第三方库解第三次qp ，这里解出来最优解为x
=
0.7083
，
x=0.7083 ，
x=0.7083 ，记录此时目标函数值f
3
=
0.085
f3=0.085
f3=0.085将非线性约束在第5步解出的
x
x
x处进行线性化 ，调用第三方库解第四次qp ，这里解出来最优解为x
=
0.7071
，
x=0.7071 ，
x=0.7071 ，记录此时目标函数值f
4
=
0.086
f4=0.086
f4=0.086将非线性约束在第6步解出的
x
x
x处进行线性化 ，调用第三方库解第五次qp ，这里解出来最优解为x
=
0.7071
，
x=0.7071 ，
x=0.7071 ，记录此时目标函数值f
5
=
0.086
f5=0.086
f5=0.086比较
f
4
f4
f4和f
5
f5
f5的值的差距 ，发现差距不到0.001了 ，此时我们认为sqp已经收敛了 ，此时得到的最优解x
x
x即为整个sqp问题的最优解仍无法理解的问题: 为什么连续求解qp直至最后收敛 ，其结果就是问题最优解 ，这个证明是怎么来的 ，有什么简单的理解方法吗? 欢迎大家讨论补充 。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！