B.4 Fenchel 对偶性

B.4 Fenchel 对偶性

在本节中，我们提出了一个关于凸优化或凸分析的替代理论，其中考虑的函数 $f$ 可能是不可微的并取无穷大值。

在本节中，集合 $x$ 表示一个内积为 $⟨\cdot ,\cdot ⟩$ 的希尔伯特空间。然而，所呈现的结果可以直接推广到巴拿赫空间的情况。我们考虑取值在 $\left[-\infty ,+\infty \right]$ 中的函数。函数 $f:x\to$ $\left[-\infty ,+\infty \right]$ 的定义域定义为集合

$$\mathrm{dom}\left(f\right)=\{x\in X:f\left(x\right)<+\infty \}.\text{\hspace{1em}(B. 15)}$$

我们扩展了凸性的定义，并说 $f:x\to \left[-\infty ,+\infty \right]$ 是凸的，如果它在 $\mathrm{dom}\left(f\right)$ 上是凸的，即对于所有 $x,x^{\prime }\in \mathrm{dom}\left(f\right)$ 和所有 $t\in \left[0,1\right]$ ，

$$f\left(tx+\left(1-t\right)x^{\prime }\right)\le tu+\left(1-t\right)v\text{\hspace{1em}(B.16)}$$

对于所有 $\left(u,v\right)\in {\mathbb{R}}^2$ ，其中 $u\ge f\left(x\right)$ 和 $v\ge f\left(x^{\prime }\right)$ 。如果一个凸函数取值在 $(-\infty ,+\infty ]$ 中，并且不均匀等于 $+\infty$ ，则称其为正则的。当其上确界闭合时，称其为闭函数。

B.4.1 次梯度

定义 B. 31 设 $f:X\to (-\infty ,+\infty ]$ 为一个凸函数。那么，向量 $g\in X$ 是 $f$ 在点 $x\in \mathrm{dom}\left(f\right)$ 处的次梯度，如果对于所有 $z\in X$ ，以下不等式成立:

$$f\left(z\right)\ge f\left(x\right)+⟨z-x,g⟩.\text{\hspace{1em}(B.17)}$$

所有在 $x$ 处的次梯度集合称为 $f$ 在 $x$ 处的次微分，并表示为 $\partial f\left(x\right)$ ，其中 $\partial f\left(x\right)=\varnothing$ 对于 $x\notin \mathrm{dom}\left(f\right)$ 。

因此，$g$ 是 $x$ 处的次梯度，当且仅当通过点 $\left(x,f\left(x\right)\right)$ 的法向量为 $g$ 的超平面位于 $f$ 的图形下方，即当它支撑 $f$ 的图形时。图 14.1 描述了这些定义。

以下引理表明，如果 $f$ 在 $x\in \mathrm{dom}\left(f\right)$ 处可微，那么它的子微分在 $x$ 处简化为其梯度。

引理 B.32 如果 $f$ 在 $x\in \mathrm{dom}\left(f\right)$ 处可微，那么 $\partial f\left(x\right)=\{\nabla f\left(x\right)\}$ 。

证明:显然，梯度 $\nabla f\left(x\right)$ 在 $x$ 处总是一个子梯度。现在，设 $g$ 在 $\partial f\left(x\right)$ 中。那么，根据子梯度的定义，对于任何 $ϵ\in \mathbb{R}$ ，

$$f\left(x+ϵ\left(\nabla f\left(x\right)-g\right)\right)\ge f\left(x\right)+ϵ⟨\nabla f\left(x\right)-g,g⟩.$$

一阶泰勒级数展开给出

$$f\left(x+ϵ\left(\nabla f\left(x\right)-g\right)\right)-f\left(x\right)=ϵ⟨\nabla f\left(x\right),\nabla f\left(x\right)-g⟩+o\left(ϵ\parallel \nabla f\left(x\right)-g\parallel \right).$$

考虑到这一点，第一个不等式可以重写为

$$ϵ\parallel \nabla f\left(x\right)-g{\parallel }^2\le o\left(ϵ\parallel \nabla f\left(x\right)-g\parallel \right),$$

这意味着 $\parallel \nabla f\left(x\right)-g\parallel =o\left(1\right)$ 和 $\nabla f\left(x\right)=g$ 。

命题 B.33 设 $f:X\to (-\infty ,+\infty ]$ 是一个适当的函数。那么，$x^{\ast }$ 是 $f$ 的全局最小化子当且仅当 $\partial f\left(x^{\ast }\right)$ 包含 0。

证明:由于 $f$ 是适当的，如果 $x^{\ast }$ 是最小化子，那么 $f\left(x^{\ast }\right)$ 不能是 $+\infty$ 。因此 $x^{\ast }$ 必须在 $\mathrm{dom}\left(f\right)$ 中(因此 $\partial f\left(x\right)$ 不定义为空)。现在，$x^{\ast }$ 是全局最小化子当且仅当对于所有 $z\in X$ ，$f\left(z\right)\ge f\left(x^{\ast }\right)$ ，即当且仅当 0 是 $f$ 在 $x^{\ast }$ 处的子梯度。

B.4.2 核心

集合 $\mathcal{C}\subseteq \mathcal{X}$ 的核心用 core( $\mathcal{C}$ ) 表示，并定义如下:

$$\mathrm{core}\left(\mathcal{C}\right)=\{x\in \mathcal{C}:\forall u\in X,\exists ϵ>0\mid \forall t\in \left[0,ϵ\right],\left(x+tu\right)\in \mathcal{C}\}.\text{\hspace{1em}(B.18)}$$

因此，对于 $x\in \mathrm{core}\left(\mathcal{C}\right)$ ，对于任何方向 $u,\left(x+tu\right)$ 在 $\mathcal{C}$ 中，$t$ 足够小。基于这个定义，核心 $\left(\mathcal{C}\right)$ 显然包含 $\mathcal{C}$ 的内部，即 int $\left(\mathcal{C}\right)$。

命题B.34 设 $h:X\to \left[-\infty ,+\infty \right]$ 是一个凸函数。如果存在 $x_0\in \mathrm{core}\left(\mathrm{dom}\left(h\right)\right)$ 使得 $h\left(x_0\right)>-\infty$ ，那么 $h\left(x\right)>-\infty$ 对于所有 $x\in X$ 。

证明:设 $x$ 在 $x$ 中。由于 $x_0$ 在核心 $\left(\mathrm{dom}\left(h\right)\right)$ 中，存在 $t>0$ 使得 $x_0^{\prime }=x_0+t\left(x_0-x\right)$ 在 $\mathrm{dom}\left(h\right)$ 中，即满足 $h\left(x_0^{\prime }\right)<+\infty$ 。由于 $x_0=\frac{1}{1+t}{x}_0^{\prime }+\frac{t}{1+t}x$ ，根据凸性，以下成立

对于所有 。

$$h\left(x_0\right)\le \frac{1}{1+t}h\left(x_0^{\prime }\right)+\frac{t}{1+t}v\iff v\ge \frac{1+t}{t}\left[h\left(x_0\right)-\frac{1}{1+t}h\left(x_0^{\prime }\right)\right]\text{\hspace{1em}(B.19)}$$

这意味着 $h\left(x\right)\ge \frac{1+t}{t}\left[h\left(x_0\right)-\frac{1}{1+t}h\left(x_0^{\prime }\right)\right]>-\infty$ ，这完成了证明。 $\square$

下一个结果的证明留给作为练习(练习B.3)。

命题B.35 设 $h:X\to (-\infty ,+\infty ]$ 是一个凸函数。那么， $h$ 在任何 $x\in \mathrm{core}\left(\mathrm{dom}\left(h\right)\right)$ 处都存在次微分。

B.4.3 伴随函数

定义B.36(伴随函数)设 $X$ 是一个 $Hilbertspace.The\mathrm{conjugate}\mathrm{function}or$ ，函数 $f:X\mapsto \left[-\infty ,+\infty \right]$ 的Fenchel伴随是一个定义为 $f^{\ast }:X\mapsto \left[-\infty ,+\infty \right]$ 的函数

$$f^{\ast }\left(u\right)=\underset{x\in \mathcal{X}}{\sup }\{⟨u,x⟩-f\left(x\right)\}.\text{\hspace{1em}(B.20)}$$

注意到 $f^{\ast }$ 是凸函数 $u\mapsto ⟨x,u⟩-f\left(x\right)$ 的点态上确界，因此是凸的。另外，如果存在 $x$ 使得 $f\left(x\right)<+\infty$ ，那么 $f>-\infty$ 。伴随关系是逆序的:对于任何 $f$ 和 $g$ ，如果 $f\le g$ ，那么 $g^{\ast }\le f^{\ast }$ 。同样，如果 $f$ 是闭的适当凸集，那么 $f^{\ast \ast }=f$ 。

图B.3说明了伴随函数的定义。如图所示，伴随函数对应于函数的图在支撑超平面及其交点方面的对偶描述。

图B.3

Illustration of the conjugate $f^{\ast }$ of a function $f$ . Given $y,x^{\ast }$ is the point at which the distance between the hyperplane of equation $z=⟨x,y⟩$ with normal $y$ (slope $y$ in dimension one) and the plot of $f\left(x\right)$ is the largest. This largest distance is equal to $f^{\ast }\left(y\right)$ . The parallel hyperplane $z=⟨x-x^{\ast },y⟩+f\left(x^{\ast }\right)$ with normal $y$ and passing through the point $(x^{\ast },f\left(x^{\ast }\right)$ is shown. This is a supporting hyperplane of the plot of $f\left(x\right)$ . The point at which it intercepts the $y$ -axis (crossing point) has $y$ -coordinate $-f^{\ast }\left(y\right)$ .

Lemma B.37 (Conjugate of extended relative entropy) $Let{p}_0\in \Delta beadistributionoverX$ such that $p_0\left(x\right)>0$ for all $x\in X$ . Define $f:{\mathbb{R}}^x\to \mathbb{R}$ by

$$f\left(p\right)=\{\begin{array}{ll}\mathrm{D}\left(p\parallel p_0\right)& \text{ if }p\in \Delta \\ +\infty & \text{ otherwise. }\end{array}$$

Then, the conjugate function $f^{\ast }:{\mathbb{R}}^x\to \mathbb{R}$ of $f$ is defined by

$$\forall q\in {\mathbb{R}}^X,f^{\ast }\left(q\right)=\log \left(\sum _{x\in X}{p}_0\left(x\right)e^{q\left(x\right)}\right).$$

Proof: By definition of $f$ , for any $q\in {\mathbb{R}}^x$ , we can write

$$\underset{p\in {\mathbb{R}}^X}{\sup }\left(⟨p,q⟩-\mathrm{D}\left(p\parallel p_0\right)\right)=\underset{p\in \Delta }{\sup }\left(⟨p,q⟩-\mathrm{D}\left(p\parallel p_0\right)\right).\text{\hspace{1em}(B.21)}$$

Fix $q\in {\mathbb{R}}^{\mathcal{X}}$ and let $\bar{q}\in \Delta$ be defined for all $x\in \mathcal{X}$ by

$$\bar{q}\left(x\right)=\frac{p_0\left(x\right)e^{q\left(x\right)}}{\sum _{x\in X}{p}_0\left(x\right)e^{q\left(x\right)}}=\frac{p_0\left(x\right)e^{q\left(x\right)}}{{\mathbb{E}}_{p_0}\left[e^q\right]}.\text{\hspace{1em}(B.22)}$$

Then, the following holds for all $p\in \Delta$ :

$$⟨p,q⟩-\mathrm{D}\left(p\parallel p_0\right)=\underset{p}{\mathbb{E}}\left[\log \left(e^q\right)\right]-\underset{p}{\mathbb{E}}\left[\log \frac{p}{p_0}\right]=\underset{p}{\mathbb{E}}\left[\log \frac{p_0{e}^q}{p}\right]=-\mathrm{D}\left(p\parallel \bar{q}\right)+\log \underset{p_0}{\mathbb{E}}\left[e^q\right].$$

Since $\mathrm{D}\left(p\parallel \bar{q}\right)\ge 0$ and $\mathrm{D}\left(p\parallel \bar{q}\right)=0$ for $p=\bar{q}$ , this shows that $\underset{p\in \Delta }{\sup }\left(p\cdot q-\mathrm{D}\left(p\parallel p_0\right)\right)=\log \left({\mathbb{E}}_{p_0}\left[e^q\right]\right)$ and concludes the proof.

Table B. 1 gives a series of other examples of functions and their conjugates. The following is an immediate consequence of the definition of the conjugate functions.

Table B. 1

Examples of functions $g$ and their conjugates $g^{\ast }$ .

$g\left( x\right)$	$\operatorname{dom}\left( g\right)$	${g}^{ * }\left( y\right)$	$\operatorname{dom}\left( {g}^{ * }\right)$
$f\left( {ax}\right) \left( {a \neq 0}\right)$	$x$	${f}^{ * }\left( \frac{y}{a}\right)$	${x}^{ * }$
$f\left( {x + b}\right)$	$x$	${f}^{ * }\left( y\right) - \langle b, y\rangle$	${x}^{ * }$
${af}\left( x\right) \left( {a > 0}\right)$	$x$	$a{f}^{ * }\left( \frac{y}{a}\right)$	${x}^{ * }$
${\alpha x} + \beta$	$\mathbb{R}$	$\left\{ \begin{array}{ll} - \beta & \text{if }y = \alpha \\ + \infty & \text{otherwise} \end{array}\right.$	$\mathbb{R}$
$\frac{{\left| x\right| }^{p}}{p}\left( {p > 1}\right)$	$\mathbb{R}$	$\frac{{\left| y\right| }^{q}}{q}\left( {\frac{1}{p} + \frac{1}{q} = 1}\right)$	$\mathbb{R}$
$\frac{-{x}^{p}}{p}\left( {0 < p < 1}\right)$	${\mathbb{R}}_{ + }$	$\frac{-{\left( -y\right) }^{q}}{q}\left( {\frac{1}{p} + \frac{1}{q} = 1}\right)$	$\mathbb{R}$ _
$\sqrt{1 + {x}^{2}}$	$\mathbb{R}$	$- \sqrt{1 - {\left( y\right) }^{2}}$	$\left\lbrack {-1,1}\right\rbrack$
$- \log \left( x\right)$	${\mathbb{R}}_{ + } \smallsetminus \{ 0\}$	$- \left( {1 + \log \left( {-y}\right) }\right)$	${\mathbb{R}}_{ - } \smallsetminus \{ 0\}$
${e}^{x}$	$\mathbb{R}$	$\left\{ \begin{array}{ll} y\log \left( y\right) - y, & \text{if }y > 0 \\ 0, & \text{if }y = 0 \end{array}\right.$	${\mathbb{R}}_{ + }$
$\log \left( {1 + {e}^{x}}\right)$	$\mathbb{R}$	$y\log \left( y\right) + \left( {1 - y}\right) \log \left( {1 - y}\right) ,\;$ if $\;0 < y < 1$ 0 , if $y = 0,1$	$\left\lbrack {0,1}\right\rbrack$
$- \log \left( {1 - {e}^{x}}\right)$	$\mathbb{R}$	$y\log \left( y\right) - \left( {1 + y}\right) \log \left( {1 + y}\right) ,\;$ if $\;y > 0$ if $y = 0$	${\mathbb{R}}_{ + }$

Proposition B.38 (Fenchel’s inequality) Let $X$ be a $Hilbertspace.Foranyfunctionf:X\mapsto$ $\left[-\infty ,+\infty \right]$ and any $x\in \mathrm{dom}\left(f\right)$ and $u\in x$ , the following inequality holds:

$$f\left(x\right)+f^{\ast }\left(u\right)\ge ⟨u,x⟩\text{\hspace{1em}(B.23)}$$

等式成立当且仅当 $u$ 是 $f$ 在 $x$ 处的子梯度。

我们将用 $A^{\ast }$ 表示一个有界(或连续)线性映射 $A:x\to y$ 的伴随算子。此外，我们用 $\mathrm{cont}\left(f\right)$ 表示那些 $x\in X$ 点的集合，在这些点上 $f:X\to \left[-\infty ,+\infty \right]$ 是有限且连续的。

定理 B.39(Fenchel 对偶定理)$LetXandybetwoHilbertspaces$、$f:X\to (-\infty ,+\infty ]$ 和 $g:y\to (-\infty ,+\infty ]$ 是两个凸函数，$A:x\to y$ 是一个有界线性映射。那么，以下两个优化问题(Fenchel 问题)

$$p^{\ast }=\underset{x\in \mathcal{X}}{\inf }\{f\left(x\right)+g\left(Ax\right)\}$$ $$d^{\ast }=\underset{y\in \mathcal{Y}}{\sup }\left\{-f^{\ast }\left(A^{\ast }y\right)-g^{\ast }\left(-y\right)\right\}$$

满足弱对偶性 $p^{\ast }\ge d^{\ast }$。如果进一步 $f$ 和 $g$ 满足条件

$$0\in \mathrm{core}\left(\mathrm{dom}\left(g\right)-A\left(\mathrm{dom}\left(f\right)\right)\right)$$

或者更强的条件

$$A\left(\mathrm{dom}\left(f\right)\right)\cap \mathrm{cont}\left(g\right)\ne \varnothing ,$$

那么强对偶性成立，即 $p^{\ast }=d^{\ast }$ 并且对偶问题中的上确界在 $d^{\ast }\in \mathbb{R}$ 时达到。

证明:通过将 Fenchel 不等式(命题 B.38)应用于 $f$ 和 $g$，对于任意的 $x\in x$ 和 $y\in \mathcal{Y}$，以下不等式成立:

$$f\left(x\right)+f^{\ast }\left(A^{\ast }y\right)\ge ⟨A^{\ast }y,x⟩=⟨y,Ax⟩=-⟨-y,Ax⟩\ge -g\left(Ax\right)-g^{\ast }\left(-y\right).$$

比较最左边的项和最右边的项得到

$$f\left(x\right)+f^{\ast }\left(A^{\ast }y\right)\ge -g\left(Ax\right)-g^{\ast }\left(-y\right)\iff f\left(x\right)+g\left(Ax\right)\ge -f^{\ast }\left(A^{\ast }y\right)-g^{\ast }\left(-y\right).$$

对最后一个不等式的左边关于 $x\in X$ 取下确界，对右边关于 $y\in y$ 取上确界得到 $p^{\ast }\ge d^{\ast }$。

现在考虑函数 $h:y\to \left[-\infty ,+\infty \right]$，它对于所有 $u\in y$ 定义为

$$h\left(u\right)=\underset{x\in \mathcal{X}}{\inf }\{f\left(x\right)+g\left(Ax+u\right)\}.\text{\hspace{1em}(B.24)}$$

由于 $\left(x,u\right)\mapsto f\left(x\right)+g\left(Ax+u\right)$ 是凸函数，$h$ 作为该函数一个变量的下确界也是凸的。$u$ 在 $\mathrm{dom}\left(h\right)$ 中当且仅当存在 $x\in \mathcal{X}$ 使得 $f\left(x\right)+g\left(Ax+u\right)<+\infty$，即存在 $x\in \mathfrak{X}$ 使得 $f\left(x\right)<+\infty$ 且 $g\left(Ax+u\right)<+\infty$，即存在 $x\in \mathrm{dom}\left(f\right)$ 使得 $\left(Ax+u\right)\in \mathrm{dom}\left(g\right)$。因此，我们有 $\mathrm{dom}\left(h\right)=\mathrm{dom}\left(g\right)-A\mathrm{dom}\left(f\right)$。

如果 $p^{\ast }=-\infty$ ，那么显然强对偶性成立。否则，$p^{\ast }>-\infty$ 。如果 $0\in \mathrm{core}(\mathrm{dom}\left(g\right)-$ $A\left(\mathrm{dom}\left(f\right)\right))=\mathrm{core}\left(\mathrm{dom}\left(h\right)\right)$ ，那么 0 在 $\mathrm{dom}\left(h\right)$ 中且 $p^{\ast }<+\infty$ 。因此，$p^{\ast }=h\left(0\right)$ 在 $\mathbb{R}$ 中。根据命题 B.34，由于 $h\left(0\right)>-\infty$ 且 $0\in \mathrm{core}\left(\mathrm{dom}\left(h\right)\right),h$ 取值在 $(-\infty ,+\infty ]$ 中。因此，根据命题 B.35，$h$ 在 0 处允许有一个子梯度 $-y$ 。根据 $y$ 的定义，对于所有 $x\in x$ 和 $u\in y$ ，

$$h\left(0\right)\le h\left(u\right)+⟨y,u⟩$$ $$\le f\left(x\right)+g\left(Ax+u\right)+⟨y,u⟩$$ $$=\left\{f\left(x\right)-⟨A^{\ast }y,x⟩\right\}+\left\{g\left(Ax+u\right)+⟨y,u⟩+⟨A^{\ast }y,x⟩\right\}$$ $$=\left\{f\left(x\right)-⟨A^{\ast }y,x⟩\right\}+\{g\left(Ax+u\right)+⟨y,Ax+u⟩\}.$$

对 $u$ 取下确界，对 $x$ 取上确界，可以得到

$$h\left(0\right)\le -f^{\ast }\left(A^{\ast }y\right)-g^{\ast }\left(-y\right)\le d^{\ast }\le p^{\ast }=h\left(0\right),$$

这证明了 $d^{\ast }=p^{\ast }$ 以及定义 $d^{\ast }$ 的上确界在 $y$ 处达到。

最后，假设 $A\left(\mathrm{dom}\left(f\right)\right)\cap \mathrm{cont}\left(g\right)\ne \varnothing$ 并且令 $u\in A\left(\mathrm{dom}\left(f\right)\right)\cap \mathrm{cont}\left(g\right)$ 。那么，$u=Ax$ ，其中 $x\in \mathrm{dom}\left(f\right)$ 和 $u\in \mathrm{cont}\left(g\right)\subseteq \mathrm{dom}\left(g\right)$ 。因此，我们有 $0=u-Ax\in \mathrm{dom}\left(g\right)-A\mathrm{dom}\left(f\right)$ 。由于 $g$ 在 $u$ 处连续且 $g\left(u\right)$ 有限，对于任何 $v\in X$ ，存在 $ϵ>0$ 使得对于所有 $t\in \left[0,ϵ\right]$ ，$g\left(u+tv\right)$ 是有限的，因此 $w_t=\left(u+tv\right)\in \mathrm{dom}\left(g\right)$ 。因此，对于任何 $t\in \left[0,ϵ\right],tv=w_t-u=$ $w_t-Ax\in \mathrm{dom}\left(g\right)-A\mathrm{dom}\left(f\right)$ ，这表明 $0\in \mathrm{core}\left(\mathrm{dom}\left(g\right)-A\left(\mathrm{dom}\left(f\right)\right)\right)$ 。

为了说明这个定理，考虑 $A$ 是恒等算子的情况。那么原优化问题就是 $\underset{x}{\min }\{f\left(x\right)+g\left(x\right)\}$ 。图 B.4 在那种情况下说明了 Fenchel 对偶定理。原问题包括找到点 $x^{\ast }$，在该点上 $f\left(x\right)$ 和 $-g\left(x\right)$ 的图像之间的距离最小，因为 $f\left(x\right)+g\left(x\right)=f\left(x\right)-\left(-g\left(x\right)\right)$ 。如图所示，在定理的条件下，这等同于寻找 $y^{\ast }$，在该点上 $f\left(x\right)$ 和 $-g\left(x\right)$ 的共轭值之差，即差值 $-f^{\ast }\left(y\right)-g^{\ast }\left(-y\right)$ 最大。