计算科学 - 单纯形上促进稀疏性的凸优化 - 吾爱随笔录

单纯形上促进稀疏性的凸优化

计算科学凸优化稀疏算子

2021-11-24 22:09:46

假设我们想找到函数。然后根据压缩感知领域的工作，我们可以改为最小化作为上所需稀疏约束的凸代理/松弛。 $f(x) : \mathbb{R}^d \to \mathbb{R}$

f (x) + λ ‖ x ‖_{1}

$f(x) + \lambda \|x\|_1$

‖ x ‖_{0}

$\|x\|_0$

但很多时候优化问题实际上已经被限制在一个 $\ell^1$ 球上。例如，假设我们在 $d$ 个元素上的离散概率分布空间上进行优化，可以表示为

\begin{aligned} minimize: & f (x) \\ subj. to: & x ⪰ 0 \\ ⟨ 1, x ⟩ = 1. \end{aligned}

$\begin{align*} \text{minimize: } & f(x)\\ \text{subj. to: } & x \succeq 0\\ & \langle \boldsymbol{1}, x \rangle = 1. \end{align*}$ 称这个问题为（P）。那么由于 (P) 的任何可行解都有

‖ x ‖_{1} = 1

$\|x\|_1 = 1$ ，因此添加目标惩罚

λ ‖ x ‖_{1}

$\lambda\|x\|_1$ 不会改变问题的最优解。

问题：有没有办法给 (P) 添加一个凸惩罚/约束，以便得到的问题 (P') 有一个稀疏解？

1个回答

非常有趣的问题。

一种选择是将基数正则化器放宽为无穷范数的倒数，即将 $\mathrm{card}(x)$ 替换为

1 / ‖ x ‖_{\infty} .

$1 / \|x\|_{\infty}.$ 这产生了一个非凸问题，但可以通过求解

n

$n$ 凸程序来解决，每个程序维度为

n + 1

$n+1$ 。

特别是问题

\begin{array}{ll} minimize & f (x) + λ / ‖ x ‖_{\infty} \\ subject to & x \geq 0 \\ 1^{T} x = 1 \end{array}

$\begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + \lambda /\|x\|_{\infty} \\ \mbox{subject to} & x \geq 0 \\ & \mathbf{1}^Tx = 1 \end{array} \end{equation*}$

等价于解决以下问题，对于 , $i = 1, \ldots, n$

\begin{array}{ll} minimize & f (x) + t \\ subject to & x_{i} \geq λ / t \\ x \geq 0 \\ 1^{T} x = 1 \\ t \geq 0 \end{array}

$\begin{equation*} \begin{array}{ll} \mbox{minimize} & f(x) + t \\ \mbox{subject to} & x_i \geq \lambda / t \\ & x \geq 0 \\ & \mathbf{1}^Tx = 1 \\ & t \geq 0 \end{array} \end{equation*}$

并将具有最小最优值的解决方案作为原始问题的解决方案（这里，是一个松弛变量）。 $t \in \mathbf{R}_{+}$

在某些情况下，可以证明这种松弛正好恢复了最小基数解。

这种松弛在论文“Recovery of Sparse Probabilitymeasures via Convex Programming”中提出了建议，该论文解释了如何解决松弛问题并描述了其解决方案。

其它你可能感兴趣的问题

上一篇CFD 中的基准性能：如何比较机器和代码？下一篇如何解决四阶非负 LASSO 问题？