计算科学 - 只有一个二次约束的非凸二次？ - 吾爱随笔录

只有一个二次约束的非凸二次？

计算科学优化非凸的

2021-12-12 14:41:55

我有一个形式为非凸优化问题：

\begin{aligned} min_{b, ξ, η} \sum_{i = 1}^{n} b_{i} ξ_{i} + γ ‖ η ‖ \\ s.t. b \geq 0, b^{T} 1 = 1, b_{i} \leq \frac{1}{n - n_{m}}, ξ \geq 0, ξ_{i} \geq 1 - a_{i}^{T} η \end{aligned}

$\begin{align} \min_{b,\xi,\eta} \sum_{i=1}^{n} b_i \xi_i + \gamma \Vert \eta \Vert \cr \text{s.t.} b\geq 0, b^\mathsf{T} 1 = 1,b_i \leq \frac{1}{n-n_m}, \xi \geq 0 , \xi_i \geq 1-a_i^\mathsf{T} \eta\cr \end{align}$ 在Boyd 和 Vandenberghe 的 Convex Optimization附录 B (p. 653) 中，据说只有一个二次约束的非凸二次具有很强的对偶性，即你可以找到它是对偶的，然后找到对偶的最优值，它是相等的到非凸二次全局最优。

我的问题是：我可以针对上述问题执行此程序吗？如何执行？它是解决上述关于 $b,\xi$ 问题的最佳方法吗？

2个回答

根据 Boyd 和 Vandenberghe 的 B.1 节中的推导，您可以解决原始的 SDP 对偶以获得最佳目标函数值似乎是合理的。您还可以解决对偶的对偶，这是对原始问题的 SDP 松弛。

按照 Boyd 的表示法，假设您的问题的原始变量用向量 $x$ 表示，SDP 松弛的决策变量（即对偶的对偶）用 $X$ 表示。有两种情况：

的最优值 $X$ 具有形式 $vv^{T}$ ；那么 $v$ 是非凸原始的最优解。
对于任何的所有最优值都不能以的形式表示，在这种情况下，不可能从 SDP 松弛中恢复原始最优解。 $X$ $vv^{T}$ $v$

在第二种情况下，一切都没有丢失：通过强对偶性，SDP 松弛的最佳目标函数值等于原始的最佳目标函数值。这种观察在以下策略中很有用：

求解 SDP 松弛，它为您提供最佳目标函数值。此操作可以使用 SDP 求解器来完成，如果您的实例不是太大，这在理论上是有效的，并且对于当前的求解器是实用的。
将此最优目标函数值提供给全局优化求解器（例如，GLOMIQO、BARON、Couenne、Bonmin 等）。这些求解器的工作原理是生成子问题序列，这些子问题会在最佳目标函数值上生成下限和上限；在此过程中，它们还产生可行的解决方案（用于上限）。
由于您已经从 SDP 松弛中知道了最优目标函数值，因此您可以准确计算任何上限的最优性差距。这种计算是对这些求解器给出的最优性差距的估计的显着改进，这些估计通常通过取最佳上限和下限的差来计算。
此外，由于您已经知道 SDP 松弛的最佳目标函数值，因此您可能会在下限问题中节省一些工作，因为您不需要下限。

您描述的情况，您可以有效地确定最佳解决方案值，但不一定在哪里获得它，这不是我通常看到在求解器中明确处理的情况，因为它很少见。通常，最优目标函数值是事先不知道的，也不容易确定。但是，将这些信息合并到公式中的一种方法是将其作为下限包含在约束中。

最后，关于线性化技术，您可以查看Misener 和 Floudas在全局优化背景下的工作，这可能会将您的问题简化为解决一堆混合整数线性程序。

$b$ 是 bang-bang，即将 1 放在最小的位置。所以对于任何固定，部分是已知的 $b$ $\xi$ $\eta$ $b, \xi$

b^{⊤} ξ = min (max (1 - a_{i}^{⊤} η, 0))

$b^\top\xi=\min(\max(1-a_i^\top\eta,0))$

问题简化为 $\eta$

其它你可能感兴趣的问题

上一篇是否可以将 Eigtool 用于广义问题伪谱？下一篇用分块对角矩阵求解线性系统的速度