凸优化笔记18：近似点算子 Proximal Mapping

前面讲了梯度下降法，分析了其收敛速度，对于存在不可导的函数介绍了次梯度的计算方法以及次梯度下降法，这一节要介绍的内容叫做近似点算子(Proximal mapping)，也是为了处理非光滑问题。

1. 闭函数

在引入闭函数(closed function)的概念之前，我们先回顾一下闭集的概念：集合 $\mathcal{C}$ 是闭的，如果它包含边界，也即 $$x^k\in \mathcal{C},x^k\to \overline{x}\Rightarrow \overline{x}\in \mathcal{C}$$ 并且有以下几个简单的原则可以保持集合闭的性质：

1. 闭集的交集还是闭集；
2. 有限个闭集的并集还是闭集；
3. 如果 $\mathcal{C}$ 是闭集，则线性映射的原象也是闭集，也即 $\{x|Ax\in \mathcal{C}\}$ 是闭集。

第 3 条原则反过来则不一定成立，也即如果 $$ 是闭集，那么 $$ 则不一定是闭集，比如我们可以取函数 $$ 的 epigraph 为闭集 $$，然而 $$ 向 $$ 轴的投影则是一个开集，严格表示与图示如下 $$

第3条逆原则反例	第3条逆原则充分条件

当然，如果加一些其他的约束条件，则可以保证第 3 条反过来也成立：$$ 是闭的，如果

1. $$ 是闭的且为凸集；
2. 并且 $$ 不存在一个可以无穷延伸的方向(recession direction)属于 $$ 的零空间，也即 $$，图示即如上。

然后我们就可以定义闭函数(closed function)了，函数 $$ 为闭的，如果他的 epigraph 为闭集或者他的所有下水平集为闭集。有以下两种简单的特殊情况：

1. 如果 $$ 连续且定义域 $$ 为闭的，则 $$ 为闭函数；
2. 如果 $$ 连续且定义域 $$ 为开的，则 $$ 为闭函数当且仅当其在 $$ 边界处收敛至 $$。

例子 1：$$

例子 2：闭集的指示函数 $$

反例 3：$$ 或者 $$ 不是闭函数

反例 4：开集的指示函数不是闭函数

闭函数有一些有用的性质，比如：

1. $$ 为闭函数当且仅当他的所有下水平集都是闭集；
2. 如果 $$ 为闭函数，且下水平集有界，那么存在最小值点(minimizer)。

Theorem (Weierstrass) ：假设集合 $$ ($$空间中有限维向量子空间) 非空且闭，并且连续函数 $$ 的所有下水平集都有界，则 $$ 存在全局最小值点(global minimizer)。

对于闭函数来说也有一些原则可以保持闭的性质：

1. 如果 $$ 均为闭函数，则 $$ 为闭函数
2. 如果 $$ 为闭函数，则 $$ 为闭函数
3. 如果任意 $$ 都是闭函数，则 $$ 为闭函数

2. 共轭函数

共轭函数(conjugate function) 前面已经讲过了，这里再简单回顾一遍。函数 $$ 的共轭函数定义为 $$

并且共轭函数有一些重要的性质：

1. 共轭函数一定是闭函数，且为凸函数，不论 $$ 是否为凸函数或闭函数（因为 $$ 的 epigraph 可以看成很多个半空间的交集）；
2. (Fenchel’s inequality) $$
3. (Legendre transform) 如果 $$ 为凸函数且为闭函数，则有 $$
4. 如果 $$ 为凸函数且为闭函数，则 $$

除此之外还有一些代数变换的原则，推导也都比较简单：

1. $$
2. $$
3. $$
4. $$

共轭函数的计算就不多举例子了，这里主要列出来后面用的比较多的而且比较重要的，其他的可以参考前面的笔记 6：

例子 1：$$ 为凸集，则指示函数 $$，其共轭函数为支撑函数 $$ 如果求两次共轭函数也很容易得到：支撑函数的共轭函数为指示函数。

例子 2：范数 $$ 的共轭函数也是指示函数 $$

3. 近似点算子

首先给出来近似点算子(Proximal mapping)的定义：闭凸函数 $$ 的近似点算子定义为 $$ 根据这个定义，实际上我们是在求解函数 $$ 的最小值，由于 $$ 是闭函数且下水平集有界，因此最小值一定存在；同时由于 $$ 为强凸函数，因此最小值点唯一。

那么怎么理解这个算子函数 $$ 呢？可以看到这实际上是一个 $$ 的映射。如果 $$，则应该有 $$。下面看一些简单的例子。

例子 1：二次函数 $$ $$ 例子 2：欧几里得范数 $$ $$ 例子 3：Logarithmic barrier $$

上面是比较简单的例子，近似点算子也有一些很容易验证的代数运算规律：

1. $$
2. $$ (注意 $$ 是标量)
3. $$
4. $$
5. $$，其中 $$
6. $$，对于一般的 $$ 并不能得到比较好的性质，但如果 $$，则有

$$

前面几条都比较容易证明，最后一条证明可以等价于求解 $$ 可以先求解 $$ 向超平面 $$ 投影来消去 $$，然后再计算 $$。

除此之外，有一个非常重要的等式：

Moreau decomposition： $$

Remarks：为什么说这个式子重要呢？因为他把原函数和共轭函数的 proximal mapping 联系起来了，如果其中一个比较难计算，那么我们可以通过另一个来计算。这个式子可以怎么理解呢？可以看成是一种正交分解，举个栗子，如果我们取一个子空间 $$，他的正交空间为 $$，令函数 $$ 为子空间 $$ 的指示函数也即 $$，那么很容易验证共轭函数 $$。而根据定义也可以得到 $$ 恰好就是 $$ 在子空间 $$ 上的投影，记为 $$，同样的 $$，因此上面的 Moreau decomposition 就可以写为 $$，这正好就是一个正交分解。可以根据下图理解

moreau decomposition

如果对原始的 Moreau decomposition 做简单的代数变换，就可以得到 $$ $$ 证明过程用到了共轭函数的性质 $$。

后面两个小节则主要是近似点算子的应用，一个是计算投影，另一个是与支撑函数、距离相关的内容。

4. 投影

为什么突然讲到投影呢？因为对指示函数应用近似点算子，实质上就是在计算投影。举个栗子就明白了：对于集合 $$ 与集合外一点 $$，$$ 向集合 $$ 的投影可以表示为 $$ 若投影点为 $$，则这可以等价表示为 $$ 因此 $$ 就是 $$ 向集合 $$ 的投影点(对于 $$ 同样成立)。那么只要我们取不同的 $$，就能得到各种类型集合的投影表达式，下面举一些例子。

超平面：$$ with $$ $$ 仿射集：$$ $$ 半空间：$$ with $$ $$ 矩形：$$ $$ 非负象限：$$ $$ 概率单形：$$ $$ 其中 $$ 由以下方程解出 $$ 这个的证明有一点难度，关键是首先要把约束条件 $$ 转换为指示函数表示 $$ 然后将拉格朗日函数分解成求和的形式 $$ 对上面这个求和项进行分情况讨论就能得到解析表达式了，不过真的很繁琐。

超平面与矩形交集：$$ $$ 其中 $$ 由以下方程解出 $$ 证明跟上面的概率单形是类似的，也需要拆写成多项求和的形式分别求解。

欧几里得球：$$ $$ 1 范数球：$$

若 $$ 则 $$；否则 $$ 其中 $$ 由以下等式获得 $$ 证明业与前面的类似，需要写成求和项的形式，然后对每一项求解。

二阶锥：$$ $$ 正定锥：$$ $$ 其中 $$

5. 支撑函数、范数与距离

这一小节标题看起来很复杂，牵涉到了支撑函数、范数、到集合的距离，但实际上都还是在计算投影，为什么这么说呢？回忆一下，支撑函数的共轭函数是不是 $$ 函数？范数的共轭函数是不是 $$ 函数？到集合的距离是不是就等于到投影点的距离？所以这一小节是上一小节“投影”的自然延伸，其中为了把原函数与共轭函数联系在一起，用到了 Moreau decomposition。我们一个一个来看。 $$ 支撑函数：$$，因此近似点算子为 $$ 范数：$$，其中 $$，近似点算子为 $$ 其中 $$

与一点的距离：$$，可以取 $$ $$ 到集合的距离：到闭凸集 $$ 的距离定义为 $$ $$ 如果是距离取平方 $$，则有 $$ 这个证明贴在下面

proof 1

proof 2