2019-11-29 凸优化proximal

2019-11-29 本文已影响0人苏格兰低地弟弟打滴滴

prox

=====

线性映射下一个集合C的像 AC是闭的一个充分条件：

C是闭且凸的，C里没有A零空间向量的射线，也就是 $A y=0, \quad \hat{x} \in C, \quad \hat{x}+\alpha y \in C \quad \forall \alpha \geq 0 \quad \Longrightarrow \quad y=0$

一个推论是：如果C是闭且凸且有界，那么AC是闭的。

=====

闭函数：如果f满足以下等价的条件那么它是闭的:

epigraph 是闭集；每个sublevel set是闭集

连续函数下的两个判断准则：

1，如果f连续并且dom f是闭的，那么f是闭的

2，如果f连续并且dom f是开的，那么f是闭的仅当并且对于每一列趋向于边界点的 $\{x_n\}$ 都有 $f(x_n)$ 趋向于无穷。

=====

闭函数判断有没有最小值点：
如果f是闭的并且每个sublevel都是有界的（所以是紧的），那么f是有最小值的。

=====

保持闭的映射：

1，如果f和g都是闭的，且dom的交集非空，那么f+g也是闭的。

2，与仿射变换的复合也是闭的： $f(A x+b)$

3，每个f都是闭的那么 $\sup _{\alpha} f_{\alpha}(x)$ 也是闭的。

=====

共轭函数：

每个 $f^{*}(y)=\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)$ 都是闭且凸的函数，无论f是不是。

$f(x)+f^{*}(y) \geq x^{T} y \quad \forall x, y$

一些常见函数的共轭函数：

$f(x)=\frac{1}{2} x^{T} A x+b^{T} x+c$ 的共轭函数是：

$f^{*}(y)=\frac{1}{2}(y-b)^{T} A^{-1}(y-b)-c$ $(A \succ 0)$

$f^{*}(y)=\frac{1}{2}(y-b)^{T} A^{\dagger}(y-b)-c, \quad \operatorname{dom} f^{*}=\operatorname{range}(A)+b$ $(A \succeq 0)$

$f(x)=\sum_{i=1}^{n} x_{i} \log x_{i} \quad f^{*}(y)=\sum_{i=1}^{n} e^{y_{i}-1}$

$f(x)=-\sum_{i=1}^{n} \log x_{i} \quad f^{*}(y)=-\sum_{i=1}^{n} \log \left(-y_{i}\right)-n$

$f(x)=-\log \operatorname{det} X \quad\left(\operatorname{dom} f=\mathbf{S}_{++}^{n}\right) \quad f^{*}(Y)=-\log \operatorname{det}(-Y)-n$

$f(x)=\left\{\begin{array}{ll}{0,} & {x \in C} \\ {+\infty,} & {x \notin C}\end{array} \quad f^{*}(y)=\sup _{x \in C} y^{T} x\right.$

$f(x)=\|x\| \quad f^{*}(y)=\left\{\begin{array}{ll}{0,} & {\|y\|_{*} \leq 1} \\ {+\infty,} & {\|y\|_{*}>1}\end{array}\right.$

=====

两重共轭：

对于任意的f ， $f^{* *}(x)$ 都是闭且凸的。而且有以下两个关系式：

$f^{* *} \leq f(x) \quad \forall x$

$\text { epi } f \subseteq \text { epi } f^{* *}(\text { for any } f)$

如果f是闭且凸的，那么就有：

$f^{* *}(x)=f(x) \quad \forall x$

$\text { epi } f=\text { epi } f^{\star *}$

$y \in \partial f(x) \Leftrightarrow x \in \partial f^{*}(y) \quad \Leftrightarrow \quad x^{T} y=f(x)+f^{*}(y)$

=====

共轭函数一些运算规则：

$f\left(x_{1}, x_{2}\right)=g\left(x_{1}\right)+h\left(x_{2}\right) \quad f^{*}\left(y_{1}, y_{2}\right)=g^{*}\left(y_{1}\right)+h^{*}\left(y_{2}\right)$

$f(x)=\alpha g(x) \quad f^{*}(y)=\alpha g^{*}(y / \alpha)$ $(\alpha>0)$

$f(x)=g(x)+a^{T} x+b$ $f^{*}(y)=g^{*}(y-a)-b$

$f(x)=\inf _{u+v=x}(g(u)+h(v))$ $f^{*}(y)=g^{*}(y)+h^{*}(y)$ ★

=====

Proximal mapping （如果f是Rn到R， prox 就是Rn到Rn）

$\operatorname{prox}_{f}(x)=\underset{u}{\operatorname{argmin}}\left(f(u)+\frac{1}{2}\|u-x\|_{2}^{2}\right)$

如果f 是闭且凸的，那么 $\operatorname{prox}_{f}(x)$ 就是存在且唯一的。

（存在性利用： $f(u)+(1 / 2)\|u-x\|_{2}^{2}$ 是闭且凸函数而且每个sublevel是有界的。同时这个函数强凸。）

$u=\operatorname{prox}_{f}(x) \quad \Longleftrightarrow \quad x-u \in \partial f(u)$

=====

一些特殊函数的prox：

$f(x)=\frac{1}{2} x^{T} A x+b^{T} x+c$ $\operatorname{prox}_{t f}(x)=(I+t A)^{-1}(x-t b)$

$f(x)=\|x\|_{2}$ $\operatorname{prox}_{t f}(x)=\left\{\begin{array}{cc}{\left(1-t /\|x\|_{2}\right) x} & {\|x\|_{2} \geq t} \\ {0} & {\text { otherwise }}\end{array}\right.$

$f(x)=-\sum_{i=1}^{n} \log x_{i}$ $\operatorname{prox}_{t f}(x)_{i}=\frac{x_{i}+\sqrt{x_{i}^{2}+4 t}}{2}, \quad i=1, \ldots, n$

$f\left(\left[\begin{array}{l}{x} \\ {y}\end{array}\right]\right)=g(x)+h(y)$ $\operatorname{prox}_{f}\left(\left[\begin{array}{l}{x} \\ {y}\end{array}\right]\right)=\left[\begin{array}{l}{\operatorname{prox}_{g}(x)} \\ {\operatorname{prox}_{h}(y)}\end{array}\right]$

$f(x)=g(\lambda x+a), \quad \operatorname{prox}_{f}(x)=\frac{1}{\lambda}\left(\operatorname{prox}_{\lambda^{2} g}(\lambda x+a)-a\right)$

$f(x)=\lambda g(x / \lambda), \quad \operatorname{prox}_{f}=\lambda \operatorname{prox}_{\lambda-1 g}(x / \lambda)$ $（\lambda>0）$

加上线性函数： $f(x)=g(x)+a^{T} x, \quad \operatorname{prox}_{f}=\operatorname{prox}_{g}(x-a)$

加上二次函数： $\begin{array}{l}{f(x)=g(x)+\frac{u}{2}\|x-a\|_{2}^{2}, \quad \operatorname{prox}_{f}(x)=\operatorname{prox}_{\theta_{g}}(\theta x+(1-\theta) a)} \\ {\text { where } \theta=1 /(1+u)}\end{array}$

=====

Moreau 分解

2019-11-29 凸优化proximal

prox

猜你喜欢

热点阅读