Proximal Algorithms 6 Evaluating

作者: 馒头and花卷 | 来源:发表于2019-06-18 10:25 被阅读0次

Proximal Algorithms 6 Evaluating
Proximal Algorithms 4 Algorithms
Proximal Algorithms 3 Interpreta
Proximal Algorithms 7 Examples a
Proximal Algorithms 5 Parallel a
Proximal Algorithms 2 Properties
Proximal Algorithms 1 介绍
远端与近端
Python学算法的高分github
Symbol.iterator:"@@iterator"]错误

Proximal Algorithms

需要注意的一点是，本节所介绍的例子可以通过第二节的性质进行延展.

一般方法

一般情况下proximal需要解决下面的问题:

在这里插入图片描述
其中, .

我们可以使用梯度方法(或次梯度)方法来求解, 还有一些投影方法，内点法等等.

二次函数

如果 $f(x) = (1/2) x^TAx + b^Tx + c$ , 其中 $A \in \mathbb{S}^n_+$ ，于是:
$\mathbf{prox}_{\lambda f}(v) = (I+\lambda A)^{-1}(v-\lambda b)$
证:
设 $\varphi(x) = (1/2)x^TAx$ , 根据第二节介绍的仿射性质可得:
$\mathbf{prox}_{\lambda f}(v) = \mathbf{prox}_{\lambda \varphi}(v-\lambda b)$
又 $\partial \varphi=A$ , 故得证.

特别的 $f(x) = b^Tx + c$ 则 $\mathbf{prox}_{\lambda f}(v)=v-\lambda b$ , $f(x)=c$ , $\mathbf{prox}_{\lambda f}(v)=v$ , 而当 $f(x)=(1/2)\|\cdot\|_2^2$ 时:
$\mathbf{prox}_{\lambda f}(v) = (\frac{1}{1+\lambda})v$
这玩意儿有时候被称为压缩算子.

估计proximal operator的时候，需要求解一个线性方程组:
$(I + \lambda A) x = v - \lambda b$
线性方程组怎么求解这里就不讨论了吧.

不过，这个应该多数用在 $f(x) + g(x)$ 这种情况吧，因为如果单纯想要最小化 $f(x)$ ，直接可以求出显示解，所以可能是 $f(x) + |x|$ 这种类型的？

平滑函数

文章里介绍了如何用梯度方法和牛顿方法，不提了.

标量函数

$f: \mathbb{R} \rightarrow \mathbb{R} \cup \{+\infty\}$ , 通过之前几节的介绍，这个情况还是蛮有意义的，因为通过proximal operator的可分性质等，有很好的扩展.
显然，此时，最优条件为:
$v \in \lambda \partial f(x) + x$
比如：
$f(x) = - \log x \\ \Rightarrow \mathbf{prox}_{\lambda f}(v) = \frac{v+\sqrt{v^2 + 4\lambda}}{2}$
又比如当 $f(x) = |x|$ :

在这里插入图片描述

一般的标量函数

如果对于 $f$ ，其次梯度是可获得的，那么我们可以利用localization method来有效估计 $\mathbf{prox}_{\lambda f}$ , 这种方法有点类似于二分法.

我们从 $[l, u] \in \mathbf{dom} f$ 开始, 如果 $v$ 在区间之外，返回最靠近 $v$ 的点？(应该就是挑 $\mathbf{dom} f$ 中最靠经 $v$ 的点作为边界吧) 算法会在 $u-l < \epsilon$ 的时候终止.

在这里插入图片描述
注：上面的第一步的意思应该是如果在区间里面就取，否则取中间的点.
如果,那么, 显然，当不是最优的，而是一个下界. 为了说明这一点，假设. 因为, 所以，则(因为凸函数的次梯度是单调的), 令:

于是

等式右边是, 所以新的就是一端小于0，一端大于0，不过这对一开始的有要求吧.

如果 $f$ 是二阶连续可微的，那么，可以用guarded Newton方法来找 $x^*$ ，不理解曲中的缘由，贴个图吧.

在这里插入图片描述

多边形

这一小节，考虑投影至多边形的问题，多边形可以用一系列线性方程和不等式描述:
$\mathcal{C} = \{x \in \mathbb{R}^n| Ax=b, Cx\le d\}$
其中 $A \in \mathbb{R}^{m \times n}, C = \mathbb{R}^{p \times n}$ .

投影问题可以表示为(计算 $\mathbf{prox}$ 便会遇到此问题):

在这里插入图片描述

对偶

当 $m, p$ 都远小于 $n$ 的时候，利用对偶方法是方便的.

(6.4)的对偶问题是:

在这里插入图片描述
其中为对偶变量(上面的式子不难推出，这里不证了).

对偶问题是:
$\begin{array} {lc} \max & g(v, \eta) \\ s.t. & \eta \ge 0 \end{array}$
这是一个 $m+p$ 个变量的二阶规划(QP)问题，且:
$x^* = v - A^T \lambda^* - C^Tv^*$
这个最优解的恢复是由KKT条件得来的.上面的问题，似乎可以用内点法有效解决，下次找机会再看看. 文章还提到了如何使得QP问题能够简单并行，这里便不多赘述了.

仿射集合

即
$\mathcal{C} = \{x \in \mathbb{R}^n| Ax=b\}$
则:
$\Pi_{\mathcal{C}} (v) = v - A^{\dagger}(Av - b)$
其中 $A^{\dagger}$ 是伪逆.
如果 $m<n, A$ 满秩，那么:
$\Pi_{\mathcal{C}}(v) = v-A^T(AA^T)^{-1}(Av-b)$
这个我可以用一种比较麻烦的方法证明.
假设最优解为: $v-A^T(AA^T)^{-1}(Av-b)+u$ ,因为
$A(v-A^T(AA^T)^{-1}(Av-b))=b$
所以，根据线性方程组解的理论可知:
$Au=0$
那么问题可以转换为:
$\begin{array}{lc} \min & \|A^T(AA^T)^{-1}(Av-b)-u\|_2^2 \\ s.t. & Au=0 \end{array}$
再根据线性方程组的理论可知， $u$ 属于 $A$ 的核，设:
$A = UDV^T$
其中 $U \in \mathbb{R}^{m \times k }, D \in \mathbb{R}^{k \times k}, V \in \mathbb{R}^{n \times k}$ .
我们只要找出 $A^T(AA^T)^{-1}(Av-b)$ 在核空间的投影即可:
$(I-VV^T)A^T(AA^T)^{-1}(Av-b)=0$
即投影为0，也就是说 $x=0$ , 这也就证明了
$\Pi_{\mathcal{C}}(v) = v-A^T(AA^T)^{-1}(Av-b)$

半平面

此时 $\mathcal{C} = \{x | a^Tx \le b\}$ , 而:
$\Pi_{\mathcal{C}}(v) = v- \frac{(a^Tv-b)_+}{\|a\|_2^2}$
其中 $(u)_+=\max \{u, 0\}$ .

这个可以画个图来证明，注意到 $\frac{(a^Tv-b)_+}{\|a\|_2^2}$ 和点到直线距离的联系.

Box

box为如下形式 $\mathcal{C} = \{x | l \le x \le u\}$ , 及:

在这里插入图片描述
如果则:

这个感觉是显然的.

Simplex

Simplex 为如下形式 $\mathcal{C} = \{z| z\ge 0, 1^Tz=1\}$ , 及
$\Pi_{\mathcal{C}}(v) = (v - \nu \mathbf{1})_+$
对于某些 $\nu \in \mathbb{R}$ .
满足
$\mathbf{1}^T(v-\nu \mathbf{1})_+=1$
利用二分法可以求解.

Cones

令 $\mathcal{K}$ 为锥，以及 $\mathcal{K}^*$ 为其对偶锥. 那么问题为:
$\begin{array}{lc} \min & \|x-v\|_2^2 \\ s.t. & x \in \mathcal{K} \end{array}$

对偶锥的定义:
$\mathcal{K}^* =\{y| x^Ty \ge 0, \forall x \in \mathcal{K}\}$

对偶最优条件为：

在这里插入图片描述
这个条件我是存疑的，这样子原问题应该是，当然，这应该无伤大雅.

二阶锥

$\mathcal{C} = \{(x, t) \in \mathbb{R}^{n+1} | \|x\|_2 \le t\}$

在这里插入图片描述
上面的东西，通过考虑下面的问题:

可以获得，第二种情况是不需讨论的, 那么先来看第一种情况。
在的情况下，, 不妨令.则，原问题为:

在处取得极值，但是，所以此时, 所以. 的时候，，于是原问题为:

那么，显然没有0的时候小.

第三种情况的分析是类似的.

半正定锥

$\mathcal{C} = \mathbb{S}^n_+$ , 此时
$\Pi_{\mathcal{C}}(V) = \sum_{i=1}^n (\lambda_i)_+ u_iu_i^T$
其中 $\sum_{i=1}^n \lambda_i u_iu_i^T$ 为特征分解.

指数锥

不了解，截个图吧

在这里插入图片描述

Pointwise maximum and supremum

max

如果 $f(x) = \max_{i} x_i$ , 根据其上镜图，我们有等价形式:
$\begin{array}{lc} \min & t + (1/2\lambda) \|x-v\|_2^2 \\ s.t. & x_i \le t, \: i=1,\ldots, n \end{array}$
其拉格朗日对偶形式为:
$L(x, t, \mu) = t + (1/2\lambda) \|x-v\|_2^2 + \mu^T(x-t \mathbf{1})$
KKT条件为:

在这里插入图片描述
如果，则表示(通过第三个条件), 如果，则表示, 又，总结为:

再根据第五个条件可得:

这个可以用半分法求解，初始的区间为.

最后
$x^* = \min \{t^*, v_i\}.$

support function

$\mathcal{C}$ 是一个凸集，其support function为:
$S_{\mathcal{C}} (x) = \sup_{y \in \mathcal{C}} y^Tx.$

support function的共轭是指示函数.

$S_{\mathcal{C}}^*(z)=\sup_x (z^Tx - f(x)) = I_{\mathcal{C}}.$
通过Moreau 分解我们知道:
$\mathbf{prox}_{\lambda S_{\mathcal{C}}} (v) = v - \lambda \Pi_{\mathcal{C}} (v / \lambda)$

一个例子是 $f(x) = x_{[1]}+x_{[2]}+\ldots + x_{[k]}$ , 表 $x$ 的前k个最大的和，可以用以下凸集的support function来表示:
$\mathcal{C} = \{y | 0 \preceq y \preceq 1, 1^Ty=k\}.$

Norms and norm balls

$f=\|\cdot\|$ 为一般的定义在 $\mathbb{R}^n$ 上的范数，则 $f^*=I_{\mathcal{B}}$ , 其中 $\mathcal{B}$ 为对偶范数的单位球.

我们知道 $f(x)=\sup_y \{y^Tx|\|y\|_*\le 1\}$ , 此为 $\mathcal{B}=\{y | \|y\|_*\le 1\}$ 的支撑函数，故 $f^*=I_{\mathcal{B}}$ .

对偶不是共轭的特例？

于是根据Moreau分解，有以下式子成立：

在这里插入图片描述

Euclidean 范数

当 $f = \|\cdot\|_2$ 的时候:

在这里插入图片描述
以及：

在这里插入图片描述

$\ell_1$ and $\ell_{\infty}$ norms

$\ell_{\infty}$ 的 $\mathcal{B}$ 是box，所以根据之前讨论过的:

在这里插入图片描述
引文和互为对偶，所以当的时候:

在这里插入图片描述
可以用更为紧凑的形式表示:

欲计算 $\ell_{\infty}$ 的proximal operator并不容易，因为投影到 $\ell_1$ 的单位球比较麻烦.
我们需要计算一个 $\lambda$ ，满足:
$\sum_{i=1}^n (|v_i| - \lambda)_+=1.$
可以用类似半分法的方法求解.

Elastic net

$f(x) = \|x\|_1 + (\gamma/2) \|x\|_2^2$ , $\gamma > 0$ .
此时
$\mathbf{prox}_{\lambda f}(v) = (\frac{1}{1+\lambda \gamma}) \mathbf{prox}_{\lambda \|\cdot\|_1}(v).$

范数和

$f(x) = \sum_{g \in \mathcal{G}} \|x_g\|_2$
其中 $\mathcal{G}$ 是 $[n]$ 的一个分割, 则:
$(\mathbf{prox}_{\lambda f}(v))_g = (1-\frac{\lambda}{\|v_g\|_2})_+ v_g$

sublevel set and epigradph

下水平集

$f$ 的 $t-$ 下水平集合为:
$\mathcal{S} = \{x \in \mathbb{R}^n| f(x) \le t\}$
假设 $v \not \in \mathcal{S}$ , 否则 $\Pi_{\mathcal{S}}(v)=v$ .
此时 $\Pi_{\mathcal{S}}(v)$ 可以转化为下列问题:
$\begin{array}{lc} \min & \frac{1}{2}\|x-v\|_2^2 \\ s.t. & f(x) \le t. \end{array}$
通过KKT条件可得最优条件为:
$0 \in x - v + \lambda \partial f(x), \quad f(x)=t, \quad \lambda > 0$
第一个条件，表示 $\Pi_{\mathcal{S}}(v) = \mathbf{prox}_{\lambda f}(v)$ , 再根据第二个条件可得:
$f(\mathbf{prox}_{\lambda f}(v)) = t$

我们可以通过二分法来寻找 $\lambda$ .

上镜图

函数 $f$ 的上镜图为:
$\mathbf{epi}f=\{(x, t)| x \in \mathbf{dom} f, f(x) \le t\}.$
针对 $\Pi_{\mathbf{epi} f}(v, s)$ :
$\begin{array}{lc} \min & \frac{1}{2} \|x-v\|_2^2 + \frac{1}{2}(t-s)^2 \\ s.t. & f(x) \le t. \end{array}$
同样假设 $f(v) > s$ KKT条件为:
$f(x) = t \\ 0 \in x-v + \lambda \partial f(x) \\ t-s=\lambda \\ \lambda > 0.$
所以
$v \in x+ (f(x)-s) \partial f(x).$
论文说这个问题比较难成立，有另外一种表示方法:

在这里插入图片描述
不知道怎么推的.

Matrix functions

Elementwise functions

这里将矩阵 $A \in \mathbb{R}^{m \times n}$ 视为 $\mathbb{R}^{mn}$ 的向量，就能利用之前的方法了，比如 $\ell_1$ 的方法:
$\|A\|_1 = \sum_{i=1}^m \sum_{j=1}^n |a_{ij}|$

正交不变

函数 $F: \mathbb{R}^{m \times n} \rightarrow \mathbb{R}$ ,正交不变是指:
$F(VXU)=F(X).$
其中 $U \in \mathbb{R}^{n \times n}, V \in \mathbb{R}^{m \times m}$ 为正交矩阵, 这也意味着:
$F(x) = F(\mathbf{diag}(\sigma_s(X))).$
其中 $\sigma_s:\mathbb{R}^{m\times n }\rightarrow \mathbb{R}^{\min\{m, n\}}$ 是奇异值映射.
正交不变算子 $F$ 可以表示为: $f \circ \sigma_s$ , 而
$\partial F(X) = \{V\mathbf{diag}(\mu) U| \mu \in \partial f(\sigma_s(X)\},$
其中 $X= V\mathbf{diag}(\sigma_s(X))U$ . 这个的推导见之前关于矩阵次梯度的介绍.

这意味着:
$\mathbf{prox}_{\lambda F}( A) = V\mathbf{diag}(\mathbf{prox}_{\lambda f}(\sigma_s (A)))U.$
这个没依照论文来，论文似乎有更加直接的证明方法，我来讲一下我的:
$\begin{array}{ll} \mathbf{prox}_{\lambda F}(A) &= \mathrm{argmin} \quad \lambda F(X) + \frac{1}{2} \|X-A\|_F^2 \\ \end{array}$
最优条件为:
$\lambda \partial F(X) +X=A.$
假设 $X= V\mathbf{diag}(\sigma_s(X))U$ , 则:
$V(\lambda \mathbf{diag}(\mu)+\mathbf{diag}(\sigma_s(X))U=A.$
显然 $A$ 的奇异值分解也为:
$A =V\mathbf{diag}(\sigma_s(A))U \\ \Rightarrow \lambda \mathbf{diag}(\mu)+\mathbf{diag}(\sigma_s(X))=\mathbf{diag}(\sigma_s(A))$
而
$\begin{array}{ll} \mathbf{prox}_{\lambda f}(\sigma_s(A)) &= \mathrm{argmin}_{\sigma_s(X)} \quad \lambda f(\sigma_s(X)) + \frac{1}{2} \|\sigma_s(X)-\sigma_s(A)\|_2^2. \\ \end{array}$
其最优条件为:
$\lambda u+\sigma_s(X)-\sigma_s(A)=0.$
显然二者的最有条件是一样的，所以成立.
当 $F: \mathbb{S}^n \rightarrow \mathbb{R}$ , 且 $F(UXU^T)=F(X)$ :
$\mathbf{prox}_{\lambda F}(A) = U\mathbf{diag}(\mathbf{prox}_{\lambda f}(\sigma(A)))U^T$
其中 $A=U\mathbf{diag}(\sigma(A))U^T$ .

后面还有一些关于矩阵范数，一些特殊集合的投影，以及如何求解对数障碍问题.

在这里插入图片描述

Proximal Algorithms 6 Evaluating
Proximal Algorithms 需要注意的一点是，本节所介绍的例子可以通过第二节的性质进行延展. 一般方法...
Proximal Algorithms 4 Algorithms
Proximal Algorithms 这一节介绍了一些利用proximal的算法. Proximal minim...
Proximal Algorithms 3 Interpreta
Proximal Algorithms 这一节，作者总结了一些关于proximal的一些直观解释 Moreau-Y...
Proximal Algorithms 7 Examples a
本节介绍一些例子. LASSO 考虑如下问题:其中. proximal gradient method proxi...
Proximal Algorithms 5 Parallel a
Proximal Algorithms 这一节，介绍并行算法的实现. 问题的结构令. 给定, 让表示向量的一个子...
Proximal Algorithms 2 Properties
可分和如果可分为俩个变量:, 于是: 这个性质在并行算法的设计中非常有用。基本的运算如果, : 如果, : ...
Proximal Algorithms 1 介绍
Proximal Algorithms 定义令为闭的凸函数，即其上镜图:为非空闭的凸集，定义域：近端算子(是这...
远端与近端
Proximal. This is a (reational) term that defines somethi...
Python学算法的高分github
The Algorithms | Python: All Algorithms implemented in Py...
Symbol.iterator:"@@iterator"]错误
undefined is not a function(evaluating '_iterator[typeof ...

Proximal Algorithms 6 Evaluating

一般方法

二次函数

平滑函数

标量函数

一般的标量函数

多边形

对偶

仿射集合

半平面

Box

Simplex

Cones

二阶锥

半正定锥

指数锥

Pointwise maximum and supremum

max

support function

Norms and norm balls

Euclidean 范数

and norms

Elastic net

范数和

sublevel set and epigradph

下水平集

上镜图

Matrix functions

Elementwise functions

正交不变

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

$\ell_1$ and $\ell_{\infty}$ norms