计算科学 - 具有预言机给出的目标函数的凸优化 - 吾爱随笔录

具有预言机给出的目标函数的凸优化

计算科学软件凸优化

2021-11-29 19:58:15

是否有任何 C++ 凸优化求解器（或一些专用方案，但尚无求解器）可以解决具有预言机给出的目标函数值的凸优化问题？谢谢你。

我的具体问题是这样的：

max_{λ} min_{σ \in {0, 1}^{N}} E_{σ, λ}

$\mathop {\max }\limits_\lambda \mathop {\min }\limits_{\sigma \in {{\{ 0,1\} }^N}} {E_{\sigma ,\,\lambda }}$

其中 lambda 是一个向量，并且对于每个

σ \in {0, 1}^{N}

${\sigma \in {{\{ 0,1\} }^N}}$

E 是 lambda

E_{σ, λ}

${E_{\sigma ,\,\lambda }}$

换句话说：它实际上是在 lambda 上最大化由线性函数的指数数的最小值定义的分段线性函数。给定 lambda 我有一个有效的方案来获得 sigma 并因此计算

min_{σ \in {0, 1}^{N}} E_{σ, λ}

$\mathop {\min }\limits_{\sigma \in {{\{ 0,1\} }^N}} {E_{\sigma ,\,\lambda }}$ 。所以我的问题实际上是我的预言给出的目标函数的凸优化（在凹函数上最大化），我想知道是否会有一些适合这类问题的求解器。或者，如果没有可用的求解器，有任何专门的程序。

谢谢：D

2个回答

好的 - 所以你试图最大化一个分段线性的凹函数，你可以评估这个函数并在任何需要的点获得一个次梯度。这相当于仅使用函数和次梯度评估来最小化凸不可微函数（只需最小化减去目标函数。）

你应该阅读 Yuri Nesterov 关于这些问题的论文（例如http://link.springer.com/article/10.1007/s10107-004-0552-5）基本上，他为算法的最佳性能建立了界限并表明他的算法（平滑非平滑问题，然后对平滑问题应用最优算法）在收敛顺序上是最优的。

自 Nesterov 2005 年的论文以来，已经有大量关于非光滑凸优化的快速一阶方法的研究，特别是与图像处理和压缩感知相关的应用。尽管如果假设强凸性（在您的情况下可能不可能）可以实现更高的性能，但有些算法不需要这种假设。参见例如 Arnold Neumaier 的 OSGA 算法 ( http://arxiv.org/pdf/1402.1125.pdf )

如果你的目标函数是分段线性和凹的，那么它是一堆全局线性函数中的最小值。让我把它放在更常见的最小化框架中（而不是最大化——只需翻转符号）：

所以你试图解决其中是分段线性和凸的。然后我可以写其中每个都是线性的。有一个解决这个问题的规范方法，即通过引入一个标量松弛变量并将问题写为现在这是一个线性程序：目标函数和所有约束都是线性的。即使很大，只要你能表征，就有解决这个问题的非常有效的方法。在你的情况下，我想这些正是

min_{λ} f (λ)

$\min_\lambda f(\lambda)$

f (λ)

$f(\lambda)$

f (λ) = min_{i} f_{i} (λ)

$f(\lambda) = \min_i f_i(\lambda)$

f_{i}

$f_i$

μ

$\mu$

min_{λ, μ} μ so that μ \geq f_{i} (λ), i = 1... N .

$\min_{\lambda,\mu} \mu \\ \text{so that }\quad \mu \ge f_i(\lambda), \qquad i=1...N.$

f_{i}

$f_i$

E_{σ} (λ)

$E_\sigma(\lambda)$ 为每个可能的。

σ

$\sigma$

其它你可能感兴趣的问题

上一篇SPD 系统的稀疏直接求解器在方程数、带宽、非零数方面的时间复杂度？下一篇计算以树中每个节点为根的所有子树的累积权重的有效方法？