Fenchel 对偶与原对偶单调包含

形式陈述

在有限维欧氏空间中，设 $f:\mathbb R^n\to\mathbb R\cup\{+\infty\}$ 、 $g:\mathbb R^m\to\mathbb R\cup\{+\infty\}$ 是 proper、下半连续凸函数， $A:\mathbb R^n\to\mathbb R^m$ 是线性映射。proper 表示不取 $-\infty$ 且不恒为 $+\infty$ 。考虑复合原问题与 Fenchel 共轭给出的对偶：

p^*=\inf_x P(x),\qquad P(x)=f(x)+g(Ax),

d^*=\sup_y D(y),\qquad D(y)=-f^*(-A^{\mathsf T}y)-g^*(y). \tag{1}

原、对偶可行分别表示 $P(x)$ 、 $D(y)$ 为有限实数。对任何这样的点，弱对偶给出 $D(y)\le p^*\le P(x)$ 。

以下是本页使用的相对内部资格：

\exists x_0\in\operatorname{ri}(\operatorname{dom}f) \quad\text{使}\quad Ax_0\in\operatorname{ri}(\operatorname{dom}g). \tag{CQ}

$\operatorname{ri}$ 指集合在其仿射包中的内部。因此允许定义域落在低维仿射子空间中。若 (CQ) 成立且原问题具有有限的最优点 $\bar x$ ，则对偶存在最优点 $\bar y$ ，并且

P(\bar x)=D(\bar y)=p^*=d^*.

原问题的可达性是单独的假设，不由资格条件代替。对给定原、对偶可行点，零间隙等价于两条次微分关系：

\boxed{ -A^{\mathsf T}y\in\partial f(x), \qquad y\in\partial g(Ax). } \tag{2}

即使没有 (CQ)，任何满足 (2) 的点对仍是等值最优证书。资格条件负责保证原最优点能够配上这种证书。

在乘积欧氏空间中定义

\mathcal T(x,y)= \begin{pmatrix} \partial f(x)+A^{\mathsf T}y\\ \partial g^*(y)-Ax \end{pmatrix}. \tag{3}

$\mathcal T$ 是极大单调算子，这一性质不依赖 (CQ) 或零点存在。由共轭次微分的互逆性， $0\in\mathcal T(x,y)$ 恰好就是 (2)。若零点集非空，则任意固定 $\lambda>0$ 和初值 $z_0=(x_0,y_0)$ 的精确预解迭代

z_{k+1}=J_{\lambda\mathcal T}z_k =(I+\lambda\mathcal T)^{-1}z_k \tag{4}

在范数下收敛到某个原对偶证书。这里是有限维结论；一般情形不保证唯一证书或几何速度。

直觉

两份 Fenchel–Young 不等式分别给 $f(x)$ 和 $g(Ax)$ 一个仿射下界。第一份的斜率取 $-A^{\mathsf T}y$ ，第二份取 $y$ ，配对项恰好抵消。下界之和就是 $D(y)$ ，两份同时贴住原函数就是零间隙。

原变量和对偶变量也构成一个共同的平衡系统：第一行要求原变量的次梯度与反馈价格抵消，第二行要求原变量的线性像与共轭次梯度相容。两行的线性耦合符号相反，因此在单调性内积中相互抵消。隐式步在同一个新点求解整个平衡系统；每步存在并收敛，不意味着这次耦合求解总是便宜。

例子与边界

最优值四的完整证书

取

f(x)=\frac12(x-3)^2,\qquad g(u)=|u|,\qquad Ax=2x.

两函数定义域都是实直线，(CQ) 成立。配方以及绝对值的共轭给出

f^*(s)=\frac12s^2+3s, \qquad g^*(y)=\delta_{[-1,1]}(y).

其中指标函数在区间内为零、外部为 $+\infty$ 。原、对偶目标因此为

P(x)=\frac12(x-3)^2+2|x|, \qquad D(y)=6y-2y^2\quad(-1\le y\le1).

在 $x\ge0$ 时， $P(x)=4+(x-1)^2/2$ ；在 $x<0$ 时， $P(x)=(x-5)^2/2-8>9/2$ 。所以唯一原最优点为 $\bar x=1$ ，值为四。对偶的导数 $6-4y$ 在整个 $[-1,1]$ 上为正，故唯一对偶最优点为 $\bar y=1$ ，值也为四。

证书可以直接复核：

-A^{\mathsf T}\bar y=-2=f'(1), \qquad \bar y=1\in\partial|\cdot|(2)=\{1\}.

两份等号分别是 $f(1)+f^*(-2)=2-4=-2$ 和 $g(2)+g^*(1)=2+0=2$ ；线性配对项相加为零，留下 $P(1)-D(1)=0$ 。

把一次隐式更新真正解出来

记 $N_{[-1,1]}=\partial\delta_{[-1,1]}$ 。区间内部的法锥为 $\{0\}$ ，在右端点为 $[0,\infty)$ ，左端点为 $(-\infty,0]$ ，外部为空。本例

\mathcal T(x,y)= \begin{pmatrix}x-3+2y\\N_{[-1,1]}(y)-2x\end{pmatrix}.

取 $\lambda=1$ ，输入为 $(a,b)$ 。要求 $(a,b)\in(x,y)+\mathcal T(x,y)$ ，先由第一行得到

x=\frac{a+3}{2}-y.

代入第二行有 $a+b+3\in3y+N_{[-1,1]}(y)$ 。法锥是锥，对它乘正数不变；投影的最优性条件遂给出

\boxed{ y=\operatorname{clip}_{[-1,1]}\!\left(\frac{a+b+3}{3}\right), \qquad x=\frac{a+3}{2}-y. } \tag{5}

这里 $\operatorname{clip}_{[-1,1]}(t)=\min\{1,\max\{-1,t\}\}$ 。从 $(x_0,y_0)=(0,0)$ 开始，

$k$	$x_k$	$y_k$	$P(x_k)$	$D(y_k)$	间隙
$0$	$0$	$0$	$9/2$	$0$	$9/2$
$1$	$1/2$	$1$	$33/8$	$4$	$1/8$
$2$	$3/4$	$1$	$129/32$	$4$	$1/32$
$3$	$7/8$	$1$	$513/128$	$4$	$1/128$

第一步后，(5) 始终把对偶分量截在一，原分量满足 $x_{k+1}=(x_k+1)/2$ 。归纳得到

x_k=1-2^{-k},\quad y_k=1,\quad P(x_k)-D(y_k)=\frac12\,4^{-k}\qquad(k\ge1).

本例不仅知道极限存在，还知道每一步的位置和可计算误差。这里的几何速度来自算例的额外结构，不能只由一般极大单调性推出。

从零零出发的原对偶隐式轨道，第一步到二分之一、一，此后保持对偶坐标一，原坐标依次为四分之三、八分之七并趋于一；最优值四，前三步间隙分别为八分之一、三十二分之一、一百二十八分之一。

图中每个点的横、纵坐标分别是原变量和对偶变量；第一步同时更新二者。到达 $y=1$ 后仍须继续移动 $x$ ，因为取得最优对偶下界并不表示当前原变量已经最优。

没有资格时，零间隙也可能没有乘子

取 $A=1$ 、 $f=\delta_{\{0\}}$ ，并令 $g(u)=-\sqrt u$ （ $u\ge0$ ）、在 $u<0$ 时取 $+\infty$ 。两函数都 proper、闭且凸，原问题只有可行点零，最优值为零。但 $\operatorname{ri}\operatorname{dom}f=\{0\}$ 与 $\operatorname{ri}\operatorname{dom}g=(0,\infty)$ 不相交。

这里 $f^*=0$ 。计算 $g^*(y)=\sup_{u\ge0}(yu+\sqrt u)$ ：若 $y\ge0$ ，上确界为 $+\infty$ ；若 $y<0$ ，令 $t=\sqrt u$ 配方，最大点为 $t=-1/(2y)$ ，得到 $g^*(y)=-1/(4y)$ 。故

D(y)=\frac1{4y}\quad(y<0), \qquad d^*=0=p^*,

上确界只在 $y\to-\infty$ 时逼近，没有有限最优乘子。也可由 $\partial g(0)=\varnothing$ 直接看出 (2) 无解。这说明原问题可达与零间隙仍不足以推出证书存在。

推论与应用

间隙就是两份非负余量

对原、对偶可行点，展开得到

\begin{aligned} P(x)-D(y) ={}&\bigl[f(x)+f^*(-A^{\mathsf T}y)+\langle Ax,y\rangle\bigr]\\ &+\bigl[g(Ax)+g^*(y)-\langle Ax,y\rangle\bigr]. \end{aligned} \tag{6}

每个方括号都由 Fenchel–Young 保证非负。因此间隙为零当且仅当两项分别为零，而等号条件正是 (2)。同时

0\le P(x)-p^*\le P(x)-D(y)

把任何有限的对偶下界变成原始次优性的上界。这份充分性证明完全不需要资格条件。

相对内部怎样产生支持价格

为证明资格条件的作用，引入扰动值函数

v(u)=\inf_x\{f(x)+g(Ax+u)\}, \qquad v(0)=p^*\in\mathbb R.

它由凸函数对 $x$ 部分取下确界得到，因而凸。允许有限候选值的扰动集合是

E=\operatorname{dom}g-A\operatorname{dom}f.

有限维凸集的相对内部在线性映射下满足 $L(\operatorname{ri}C)=\operatorname{ri}(LC)$ ；将其用于乘积定义域和 $L(x,w)=w-Ax$ ，由 (CQ) 得 $0\in\operatorname{ri}E$ 。

先排除 $v$ 在别处等于 $-\infty$ 的可能。若某个 $u\in E$ 有 $v(u)=-\infty$ ，由 $0\in\operatorname{ri}E$ ，可取小的 $\varepsilon>0$ 使 $-\varepsilon u\in E$ 。在后一点固定一份有限代价的可行候选，在 $u$ 处选取代价趋于负无穷的候选。给 $u$ 处的候选权重 $\varepsilon/(1+\varepsilon)$ ，给 $-\varepsilon u$ 处的候选权重 $1/(1+\varepsilon)$ ，混合扰动正好为零。凸性使混合代价也趋于负无穷，与 $v(0)$ 有限矛盾。因此 $v$ proper，定义域为 $E$ 。

proper 凸函数在定义域相对内部存在支持次梯度。选 $\bar y\in\partial v(0)$ ，就有

f(x)+g(Ax+u)\ge v(u)\ge p^*+\langle\bar y,u\rangle.

把 $w=Ax+u$ 当作独立变量，整理为

f(x)+\langle A^{\mathsf T}\bar y,x\rangle +g(w)-\langle\bar y,w\rangle\ge p^*.

固定任一有限候选 $w$ 或 $x$ 分别可知两部分都有有限下界；再对两个独立变量取下确界，得到 $D(\bar y)\ge p^*$ 。弱对偶给出反向不等式，所以对偶取得 $p^*$ 。若 $\bar x$ 为原最优点，代入 (6) 便产生完整证书。这里没有假设 $v$ 必然闭，也没有把原最优点的存在藏入资格条件。

乘积次微分加上斜对称耦合

将 (3) 写成 $\mathcal T=M+S$ ，其中

M(x,y)=\partial f(x)\times\partial g^*(y), \qquad S=\begin{pmatrix}0&A^{\mathsf T}\\-A&0\end{pmatrix}.

两份次微分的单调性相加，且 $\langle z-z',S(z-z')\rangle=0$ ，所以 $M+S$ 单调。但这还没有证明极大性。

为补全存在性，取小的 $\eta>0$ 使 $\eta\|S\|<1$ 。对任意输入 $w$ ，考虑映射

F_w(z)=J_{\eta M}(w-\eta Sz), \qquad J_{\eta M}(a,b)= \bigl(\operatorname{prox}_{\eta f}(a), \operatorname{prox}_{\eta g^*}(b)\bigr).

两个近端算子全域单值且非扩张，所以 $F_w$ 的 Lipschitz 常数至多为 $\eta\|S\|<1$ 。Banach 不动点定理给出唯一固定点 $z$ ，其方程等价于

w\in z+\eta(M+S)z.

于是 $I+\eta\mathcal T$ 满射。由 Minty 定理， $\mathcal T$ 极大单调，所有正步长的预解算子都全域存在。证明中的小 $\eta$ 只用于建立极大性，结论 (4) 的步长可以是任意固定正数。

从零点到整列收敛

给定一个零点 $z^*$ ，牢固非扩张性给出

\|z_{k+1}-z^*\|^2+\|z_{k+1}-z_k\|^2 \le\|z_k-z^*\|^2.

由此轨道有界、相邻位移趋于零。在有限维空间中取一个收敛子列，再用预解算子的连续性可知其极限为固定点；到该固定点的距离单调不增，并有子列趋于零，故整列收敛。单调算子页写出了这一一般论证的全部步骤。

复合凸资格与有限原最优点一起保证至少有一个零点；算子的极大性则保证每一步可以执行。两类假设分别承担不同任务。把 (4) 的耦合方程拆成便宜子步骤，需要进一步的算法设计与相应收敛分析；ADMM等分裂方法有自己的更新式，不能把 (5) 的先消元后投影误认成任意问题上都成立的交替更新。

参考资料

R. Tyrrell Rockafellar, Generalizations of the Proximal Method of Multipliers in Convex Optimization, 2024，§1, manuscript pp. 2–3, Eqs. (1.4)–(1.8)：复合扰动、相对内部资格及鞍点证书。本页通过值函数的支持次梯度展开资格证明，并与拉格朗日对偶的约束价格解释衔接。
Luis M. Briceño-Arias and Patrick L. Combettes, A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality, SIAM Journal on Optimization 21(4), 2011, pp. 1230–1250，§2.3, Proposition 2.7：乘积算子与斜对称耦合。本页用小步长收缩及 Minty 满射判据直接证明所需极大性。
Ernest K. Ryu and Stephen Boyd, A Primer on Monotone Operator Methods, 2016，§5.2、§6、§6.2：有限维固定点迭代、预解性质与近端点收敛。

形式陈述 ​

最优值四的完整证书 ​

把一次隐式更新真正解出来 ​

没有资格时，零间隙也可能没有乘子 ​

间隙就是两份非负余量 ​

相对内部怎样产生支持价格 ​

乘积次微分加上斜对称耦合 ​

从零点到整列收敛 ​

反向链接