10. 近似点算子

The proximal mapping

0. 前言

• 介绍了近似点映射以及一些常见的函数的近似点映射的例子。

1. Closed function

1.1 Closed set

• A set $C$ is closed if it contains its boundary: $$x^k\in C, x^k\rightarrow \overline{x}\Rightarrow\overline{x}\in C$$

• Notice: $$C \text{ closed}\Rightarrow A^{-1}C\text{ closed}\\ C \text{ closed}, AC=\{Ax\mid x\in C\}\text{ might be open}$$

1.2 Closed function

• See slides

2. Conjugate function

2.1 Recall and some example.

• See slides

3. Proximal mapping

• Definition: proximal mapping of a closed convex function $f$ is

  $$\text{prox}_f(x)=\arg\min_u(f(u)+\frac{1}{2}\|u-x\|^2_2)$$

  加入二次项保证强凸性，使 $\arg\min$ 的值唯一

  闭性质保证一定有 $\arg\min$

  将 $x$ 映射到近似点 $u$ (意义？)

• Subgradient characterization

• $$u=\text{prox}_f(x)\Leftrightarrow x-u\in\partial f(u)\tag{10-1}$$

  Proof:

  $$\begin{align} &\because0\in\partial f(u)+(u-x)\\ &\therefore x-u\in\partial f(u) \end{align}$$

$$f(x)=g(x)+a^Tx,\ \ \ \ \text{prox}_f(x)=\text{prox}_g(x-a)$$ $$f(x)=g(x)+\frac{\mu}{2}\|x-a\|^2_2\ \ \ \ \text{prox}_{\theta g}(\theta x+(1-\theta)a)$$

• Moreau decomposition

$$x=\text{prox}_f(x)+\text{prox}_{f^*}(x), \forall x$$

​ Follows form:

$$\begin{align} u=\text{prox}_f(x)&\Leftrightarrow x-u\in\partial f(u)\text{ (10-1)}\\ &\Leftrightarrow u\in\partial f^*(x-u)\text{ (8-1)}\\ &\Leftrightarrow x-u=\text{prox}_{f^*}(x)\text{ (10-1)} \end{align}$$

​ Decomposition:

$$x=P_L(x)+P_{L^\perp}(x)$$

​ with $f=\delta{L}, f^*=\delta{L^\perp}$ .

​ Extended version

• Composition with affine mapping

$$f(x)=g(Ax+b)$$

由 g 的近似点映射求 f 的并不容易

但是如果 $AA^T=(1/\alpha)I$ ，则 f 有解析的近似点映射(slides)

4. Projections

近似点映射对各种集合的投影有比较好的性质。例子见slides。

5. Support functions, norms, distances

同上，例子见slides。