Fenchel对偶与近端算子

Fenchel对偶是拉格朗日对偶的推广，它不依赖于显式的约束形式，而是通过共轭函数直接在原始和对偶空间之间建立联系。近端算子是求解非光滑凸优化问题的核心工具，其理论基础正是Fenchel共轭。

1. Fenchel共轭函数

1.1 定义

Fenchel共轭（也称Legendre变换）是实分析中Legendre变换在高维非光滑情形下的推广。

定义：给定函数 $f:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$，其 Fenchel共轭 $f^{\ast }:{\mathbb{R}}^n\to \mathbb{R}\cup \{+\infty \}$ 定义为

$$f^{\ast }(y)=\underset{x\in {\mathbb{R}}^n}{\sup }\{y^{T}x-f(x)\}$$

注意：这里 sup 不限制在 $\text{dom}(f)$ 内，定义域自动满足 $\text{dom}(f^{\ast })=\{y\mid f^{\ast }(y)<+\infty \}$。

1.2 共轭函数的性质

基本性质：

1. 凸性：$f^{\ast }$ 总是闭凸函数（$f$ 的支撑函数）

2. Fenchel不等式（双向不等式）：

$$f(x)+f^{\ast }(y)\ge x^{T}y,\forall x,y$$

3. 双向共轭：如果 $f$ 是闭凸函数，则 $f^{\ast \ast }=f$

4. 对称性：$f$ 的共轭的共轭是原函数（闭凸函数）

次微分形式：

$$y\in \partial f(x)⟺x\in \partial f^{\ast }(y)⟺f(x)+f^{\ast }(y)=x^{T}y$$

1.3 常见函数的共轭

原函数 $f(x)$	共轭函数 $f^{\ast }(y)$	条件
$\frac{1}{2}\Vert x{\Vert }_2^2$	$\frac{1}{2}\Vert y{\Vert }_2^2$	-
$\Vert x{\Vert }_1$	${\delta }_{\{\Vert y{\Vert }_{\infty }\le 1\}}$	指示函数
$\Vert x\Vert$	${\delta }_{\{\Vert y{\Vert }_{\ast }\le 1\}}$	对偶范数
$-\log x$	$-1-\log (-y)$	$y<0$
$e^x$	$y\log y-y$	$y>0$
$x\log x$	$e^{y-1}$	-
$I_C(x)$	${\sigma }_C(y)={\sup }_{x\in C}{y}^{T}x$	支撑函数
$\frac{1}{2}{x}^{T}Qx$	$\frac{1}{2}{y}^T{Q}^{-1}y$	$Q\succ 0$

1.4 共轭与Legendre变换

在一维可微严格凸函数情形，Fenchel共轭简化为经典Legendre变换：

设 $f:\mathbb{R}\to \mathbb{R}$ 严格凸可微，则

$$f^{\ast }(y)=y(f^{\prime }{)}^{-1}(y)-f((f^{\prime }{)}^{-1}(y))$$

几何上，共轭函数在点 $(x,f(x))$ 的切线斜率为 $y$ 时与 $y$-轴的截距为 $f^{\ast }(y)$。

2. Moreay包络与近端算子

2.1 Moreau包络

定义（Moreay包络）：给定闭凸函数 $f$，其 Moreay包络 $e_{\lambda f}:{\mathbb{R}}^n\to \mathbb{R}$ 定义为

$$e_{\lambda f}(x)=\underset{y}{\inf }\left\{f(y)+\frac{1}{2\lambda }\Vert y-x{\Vert }_2^2\right\}$$

其中 $\lambda >0$ 是平滑化参数。

核心性质：

1. 光滑性：$e_{\lambda f}$ 是 $\frac{1}{\lambda }$-光滑的凸函数
2. 收敛性：$\lambda \to 0$ 时，$e_{\lambda f}(x)\to f(x)$
3. 梯度公式：$\nabla e_{\lambda f}(x)=\frac{x-{\text{prox}}_{\lambda f}(x)}{\lambda }$

2.2 近端算子

近端算子（Proximal Operator） 是Moreay包络的核心组成部分：

定义：给定闭凸函数 $f$，其 近端算子 ${\text{prox}}_f:{\mathbb{R}}^n\to {\mathbb{R}}^n$ 定义为

$${\text{prox}}_f(x)=\arg \underset{y}{\min }\left\{f(y)+\frac{1}{2}\Vert y-x{\Vert }_2^2\right\}$$

更一般地，对于参数 $\lambda$：

$${\text{prox}}_{\lambda f}(x)=\arg \underset{y}{\min }\left\{f(y)+\frac{1}{2\lambda }\Vert y-x{\Vert }_2^2\right\}$$

2.3 近端算子的性质

基本性质：

1. 存在唯一性：对于闭凸函数 $f$，${\text{prox}}_f(x)$ 总是存在且唯一

2. 固定点性质：

$$x^{\ast }={\text{prox}}_f(x^{\ast })⟺x^{\ast }\in \arg \min f$$

3. 分离性质：如果 $f=g+h$，且 $g,h$ 的近端算子易计算，可分解计算

4. ** Moreau 分解**（对于闭凸集 $C$）：

$$x=P_C(x)+P_{N_C}(x)$$

其中 $P_{N_C}$ 是法锥上的投影。

2.4 常见近端算子

函数 $f$	近端算子 ${\text{prox}}_f$	说明
$\frac{\mu }{2}\Vert x{\Vert }_2^2$	$\frac{1}{1+\mu }x$	收缩算子
$\Vert x{\Vert }_1$	${\text{soft}}_{\tau }(x)$	软阈值（见下）
$\Vert x{\Vert }_{\infty }$	投影到 ${\ell }_{\infty }$ 球	$x$ 按幅截断
$I_C(x)$	$P_C(x)$	投影算子
$-\log x$	$x+\sqrt{x^2+2}$	-
$\frac{1}{2}\Vert x-b{\Vert }_2^2$	$b$	平移不变

软阈值算子（Soft Thresholding）：

$${\text{soft}}_{\tau }(x{)}_i=\text{sign}(x_i)\cdot \max \{|x_i|-\tau ,0\}$$

这是 $L^1$ 正则化（Lasso）的闭式解。

3. Fenchel-Rockafellar对偶

3.1 问题形式

Fenchel-Rockafellar对偶处理以下形式的问题：

$$\begin{array}{rl}\underset{x}{\min }& f(x)+g(Ax)\end{array}$$

其中 $f,g$ 是闭凸函数，$A\in {\mathbb{R}}^{m\times n}$ 是线性算子。

3.2 Fenchel对偶定理

Fenchel对偶定理：上述问题的对偶问题为

$$\underset{y}{\max }-f^{\ast }(-A^{T}y)-g^{\ast }(y)$$

且在一定约束规范下，强对偶成立。

约束规范（Slater类型）：

• 存在 $x_0$ 使得 $f(x_0)<+\infty$ 且 $g(A{x}_0)<+\infty$
• 存在 $y_0$ 使得 $f^{\ast }(-A^T{y}_0)<+\infty$ 且 $g^{\ast }(y_0)<+\infty$

3.3 与拉格朗日对偶的关系

Fenchel对偶可以视为拉格朗日对偶的推广，通过引入变量 $z=Ax$：

原始问题（引入变量）：

$$\begin{array}{rl}\underset{x,z}{\min }& f(x)+g(z)\\ \text{s.t.}& Ax-z=0\end{array}$$

拉格朗日函数：

$$L(x,z,y)=f(x)+g(z)+y^T(Ax-z)$$

对偶函数：

$$\begin{array}{rl}\underset{y}{\sup }L(x,z,y)& =\underset{y}{\sup }[f(x)+(A^{T}y{)}^{T}x+g(z)-y^{T}z]\\ & =\{\begin{array}{ll}f(x)+g^{\ast }(A^{T}y)& z\text{ 无约束}\\ +\infty & \text{否则}\end{array}\end{array}$$

这正是Fenchel对偶形式。

4. 对偶算法与原始-对偶方法

4.1 原始-对偶梯度上升

对于问题 ${\min }_{x}f(x)+g(Ax)$，原始-对偶更新为：

$$\{\begin{array}{l}{x}^{k+1}={\text{prox}}_{\tau f}(x^k-\tau A^T{y}^k)\\ y^{k+1}={\text{prox}}_{\sigma g^{\ast }}(y^k+\sigma A(2x^{k+1}-x^k))\end{array}$$

这称为 Chambolle-Pock算法 或 原始-对偶混合梯度法 (PDHG)。

4.2 Douglas-Rachford分裂

对于问题 $\min f(x)+g(x)$，Douglas-Rachford迭代为：

$$\{\begin{array}{l}{x}^{k+1}={\text{prox}}_{\tau f}(z^k)\\ y^{k+1}={\text{prox}}_{\tau g}(2x^{k+1}-z^k)\\ z^{k+1}=z^k+y^{k+1}-x^{k+1}\end{array}$$

4.3 ADMM（交替方向乘子法）

ADMM 是Douglas-Rachford的变体，适用于可分离问题：

$$\begin{array}{rl}\underset{x,z}{\min }& f(x)+g(z)\\ \text{s.t.}& Ax+Bz=c\end{array}$$

更新：

$$\{\begin{array}{l}{x}^{k+1}={\text{prox}}_{\rho f}(z^k-u^k-\frac{1}{\rho }{A}^{+}(A{z}^k+Bz-c))\\ z^{k+1}={\text{prox}}_{\rho g}(x^{k+1}-u^k-\frac{1}{\rho }{B}^{+}(A{x}^{k+1}+Bz-c))\\ u^{k+1}=u^k+A{x}^{k+1}+B{z}^{k+1}-c\end{array}$$

5. 近端梯度法

5.1 问题形式

近端梯度法（Proximal Gradient Method） 求解复合凸优化问题：

$$\underset{x}{\min }g(x)+h(x)$$

其中 $g$ 是 $L$-光滑凸函数，$h$ 是闭凸函数（可能非光滑）。

5.2 算法

$$x^{k+1}={\text{prox}}_{{\alpha }_{k}h}(x^k-{\alpha }_k\nabla g(x^k))$$

当 ${\alpha }_k=1/L$ 时，称为 ISTA（Iterative Shrinkage-Thresholding Algorithm）。

加速版本（FISTA）：

$$\{\begin{array}{l}{t}_{k+1}=\frac{1+\sqrt{1+4t_k^2}}{2}\\ x^{k+1}={\text{prox}}_{\alpha h}(y^k-\alpha \nabla g(y^k))\\ y^{k+1}=x^{k+1}+\frac{t_k-1}{t_{k+1}}(x^{k+1}-x^k)\end{array}$$

5.3 收敛性

定理：设 $g$ 为 $L$-光滑凸函数，$h$ 为闭凸函数，则近端梯度法满足

$$f(x^k)-f^{\ast }=O\left(\frac{1}{k}\right)$$

FISTA 可达到 $O(1/k^2)$ 最优收敛率。

6. 在机器学习中的应用

6.1 Lasso问题

Lasso 问题：

$$\underset{w}{\min }\frac{1}{2}\Vert y-Xw{\Vert }^2+\lambda \Vert w{\Vert }_1$$

使用近端梯度法求解：

$$w^{k+1}={\text{soft}}_{\lambda \alpha }(w^k-\alpha X^T(X{w}^k-y))$$

6.2 Group Lasso

Group Lasso 问题：

$$\underset{w}{\min }\frac{1}{2}\Vert y-Xw{\Vert }^2+\lambda \sum _{g\in \mathcal{G}}\Vert w_g{\Vert }_2$$

近端算子为组软阈值：

$${\text{prox}}_{\lambda h}(w{)}_g=w_g\cdot {\left(1-\frac{\lambda }{\Vert w_g{\Vert }_2}\right)}_{+}$$

6.3 Total Variation正则化

图像去噪中的TV正则化：

$$\underset{u}{\min }\frac{1}{2}\Vert u-u_0{\Vert }^2+\lambda \Vert \nabla u{\Vert }_1$$

近端算子涉及解线性方程组，可使用共轭梯度法。

7. 与深度学习的联系

7.1 隐式正则化的近端视角

梯度下降的隐式正则化效应可以解释为近端算子¹：

考虑带 $L^2$ 正则化的梯度步：

$$x^{k+1}=(1-\alpha \lambda )x^k-\alpha \nabla f(x^k)$$

这可以视为最小化问题的近似解：

$$x^{k+1}\approx \arg \underset{y}{\min }\left\{f(x^k)+\nabla f(x^k{)}^T(y-x^k)+\frac{1}{2\alpha }\Vert y-x^k{\Vert }^2+\frac{\lambda }{2}\Vert y{\Vert }^2\right\}$$

7.2 网络剪枝与近端算子

权重剪枝可以建模为近端操作：

幅度剪枝：

$$w^{k+1}={\text{prox}}_{\lambda \Vert \cdot {\Vert }_0}(w^k-\alpha \nabla f(w^k))$$

其中 $L_0$ 近端算子实现硬阈值。

7.3 网络权重归一化

某些权重归一化方法可以解释为投影操作：

$$w\leftarrow \frac{w}{\Vert w\Vert }\cdot \min (\Vert w\Vert ,c)=P_{\{\Vert w\Vert \le c\}}(w)$$

7.4 优化器的近端解释

Adam和其他自适应优化器可以视为近端梯度法的变体，通过估计二阶信息调整步长和方向²。

8. 扩展：非欧几里得几何

8.1 Bregman散度

Bregman散度 $D_{\varphi }$ 基于凸函数 $\varphi$：

$$D_{\varphi }(x,y)=\varphi (x)-\varphi (y)-⟨\nabla \varphi (y),x-y⟩$$

8.2 Bregman近端算子

基于Bregman散度的近端算子：

$${\text{prox}}_{\varphi }^f(x)=\arg \underset{y}{\min }\{f(y)+D_{\varphi }(y,x)\}$$

8.3 Mirror Descent

Mirror Descent算法：

$$x^{k+1}={\text{prox}}_{\varphi }^f(x^k-{\alpha }_k\nabla f(x^k))$$

这推广了欧几里得空间中的投影梯度下降。

9. 总结

Fenchel对偶理论和近端算子提供了分析和求解凸优化问题的强大框架：

1. Fenchel共轭 建立了函数与其对偶之间的对称关系
2. Moreay包络 提供了将非光滑问题光滑化的工具
3. 近端算子 使得复合优化问题的求解成为可能
4. Fenchel-Rockafellar对偶 统一了多种对偶理论
5. Bregman散度 将理论推广到非欧几里得几何

这些工具在机器学习算法设计、深度学习理论分析、以及高效优化算法实现中都发挥着关键作用。

参考资料

---

相关主题：凸优化基础理论atamente、 拉格朗日对偶与KKT条件atamente、 信息几何基础

Footnotes

1. Zhang, C., et al. (2025). Understanding the Implicit Regularization of Gradient Descent in Over-parameterized Models. arXiv:2505.17304. ↩

2. Jacobs, T., et al. (2025). Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias? ICML 2025. ↩