计算科学 - SCP（顺序凸规划）与 SQP（顺序二次规划） - 吾爱随笔录

SCP（顺序凸规划）与 SQP（顺序二次规划）

计算科学优化约束优化凸优化

2021-12-13 14:02:39

有人可以从高层次上解释一下 SCP 和 SQP 解决非线性（非凸）程序的区别吗？

假设我的问题类似于

min_{x} . f (x)

$\min\limits_x. \quad f(x)$

s . t . g (x) \leq 0

$s.t. \quad g(x) \leq 0$

其中和都是（通常）非凸的。 $f$ $g$

我的理解是（无论是信任区域还是线搜索变体）SCP 通过围绕当前迭代的凸近似来解决问题，并类似地线性化约束并求解凸子问题 $\tilde f$ $x^k$ $g(x) \approx \tilde g(x) = g(x^k) + \nabla g(x^k)(x-x^k)$

min_{x} . \tilde{f} (x)

$\min\limits_x. \quad \tilde f(x)$

s . t . \tilde{g} (x) \leq 0

$s.t. \quad \tilde g(x) \leq 0$

获得下一次迭代或至少方向使得。 $x^{k+1}$ $d$ $x^{k+1} = x^k + \alpha d$

就我的理解而言，同样地，SQP 通过解决二次问题找到下一个迭代

min_{x} . \hat{f} (x)

$\min\limits_x. \quad \hat f(x)$

s . t . \hat{g} (x) \leq 0

$s.t. \quad \hat g(x) \leq 0$

其中和其中是 Hessian 或其近似值。 $\hat g = g(x^k) + \nabla g(x^k)(x-x^k)$ $\hat f(x) = f(x^k) + \nabla f(x^k)d + d B_k d$ $B_k$

那么这两种方法之间的区别仅仅是目标的凸近似的假设形状吗？ $f$

还是我遗漏了一些细节？

1个回答

在 SCP（又名 SCA）中，在每次外部迭代中：

目标函数由凸近似代替，不一定是二次的。

非线性不等式约束被凸近似代替，不一定是线性的。非线性等式约束被线性近似代替。

因此，在 SCP 的每次外部迭代中，都会解决一个凸优化问题。

在 SQP（又名 SCA）中，在每次外部迭代中：

目标函数被（拉格朗日的）二次近似代替，不一定是凸的。

非线性约束被线性近似所取代。

因此，在 SQP 的每次外迭代中，都会求解二次规划 (QP) 问题，但它不一定是凸的。

实际上，还有其他可能性，既不对应于 SCP 也不对应于 SQP，例如在每次外部迭代时，用可能的非凸二次近似替换目标函数，同时保留凸圆锥约束。

无论是使用 SCP、SQP 还是其他一些变体，实现收敛（全局收敛到局部最优或至少是静止点）的关键是使用信任区域或线搜索。不幸的是，许多人（他的名字恰好不是斯蒂芬·博伊德）在没有他的能力和判断力的情况下实施了没有信任区域或行搜索的“粗制”SCP。这通常会导致惨淡的失败，正如http://ask.cvxr.com/充斥着如此糟糕的实现所证明的那样。使用现有的高质量局部或全局非凸非线性求解器会更好地为大多数人服务。此类求解器的长度超过 10 行是有原因的。

其它你可能感兴趣的问题

上一篇求解三角形网格上的测地线会产生负距离下一篇三线性六角元素