您现在的位置是:首页 > 技术教程 正文

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

admin 阅读: 2024-04-02
后台-插件-广告管理-内容页头部广告(手机)

二次规划

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

已知目标函数为:

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

x x x需满足约束条件

0 < x < 2 00<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 < 0 x^2-1<0 x21<0就是凸集, x 2 − 1 > 0 x^2-1>0 x21>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)=x22x+1

x x x需满足约束条件

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

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

求解步骤如下:

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

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

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

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

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

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

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

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

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

标签:
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

在线投稿:投稿 站长QQ:1888636

后台-插件-广告管理-内容页尾部广告(手机)
关注我们

扫一扫关注我们,了解最新精彩内容

搜索