凸优化与共轭函数理论讲解笔记

课程大纲概述

这门课程主要围绕凸优化理论展开，分为三个核心部分。第一部分是凸性（Convexity）的基本概念和定义，这是整个优化理论的基础。在凸性的框架下，我们特别关注1.1节的定义部分，以及1.2节关于可微凸函数的刻画（Characterization of differentiable convex functions）。可微凸函数是凸优化中最重要的一类函数，因为它们既具有凸性的良好性质，又具有可微性带来的便利性。第二部分是Fenchel-Legendre共轭理论，这是凸分析中的核心工具，它建立了原函数与其共轭函数之间的对偶关系。

Gâteaux微分的定义与性质

设\mathcal{H}和\mathcal{K}是赋范空间，这意味着它们都配备了范数结构，能够衡量向量的"长度"。设C \subset \mathcal{H}是\mathcal{H}的子集，x是C的一个内点，内点的要求保证了我们可以在x的某个邻域内自由移动而不离开集合C。考虑映射T: C \to \mathcal{K}。

函数T在点x处是Gâteaux可微的，当且仅当存在一个有界线性算子T'(x) \in B(\mathcal{H}, \mathcal{K})使得对于所有y \in \mathcal{H}，下面的极限存在并且等于T'(x)y：

这个定义本质上是在说：当我们从点x出发，沿着方向y以步长\alpha移动时，函数值的变化率在\alpha趋于0时有一个确定的极限。这个极限就是函数T在x点沿y方向的方向导数。T'(x)被称为T在x处的Gâteaux导数（Gâteaux derivative），而T'(x)y被称为T在x处沿方向y的Gâteaux微分（Gâteaux differential）。

Gâteaux导数的唯一性是一个重要性质。如果T在x处是Gâteaux可微的，那么导数T'(x)是唯一确定的。这个唯一性的证明依赖于极限的性质：假设存在两个不同的算子都满足Gâteaux微分的定义，那么对于同一个方向y，我们会得到：

通过变量替换和极限运算，我们可以证明-T'(x)(-y) = T'(x)y，这确立了导数的线性性和唯一性。

当\mathcal{H}是Hilbert空间且\mathcal{K} = \mathbb{R}时，情况变得特别重要。Hilbert空间是配备了内积结构的完备空间，例如有限维欧几里得空间\mathbb{R}^n或无限维的L^2空间。在这种情况下，如果T在x处是Gâteaux可微的，根据Riesz表示定理，存在唯一的向量\nabla T(x) \in \mathcal{H}，称为T在x处的梯度（gradient），使得：

这里\langle \cdot \mid \cdot \rangle表示Hilbert空间中的内积。Riesz表示定理的作用是将线性泛函T'(x)与Hilbert空间中的一个具体向量\nabla T(x)联系起来，这使得我们可以用几何的方式理解导数：梯度\nabla T(x)指向函数增长最快的方向，其长度表示最大增长率。

Fréchet微分的定义与比较

Fréchet微分是比Gâteaux微分更强的概念。设\mathcal{H}和\mathcal{K}是赋范空间，x是C \subset \mathcal{H}的内点，T: C \to \mathcal{K}。函数T在x处是Fréchet可微的，当且仅当存在T'(x) \in B(\mathcal{H}, \mathcal{K})使得：

这个定义与Gâteaux微分的关键区别在于收敛的方式。Gâteaux微分只要求沿着每个固定方向的方向导数存在，是一种"逐方向"的微分概念。而Fréchet微分要求误差\|T(x + y) - T(x) - T'(x)y\|相对于\|y\|一致地趋于0，无论y从哪个方向趋于0。这是一种更强的、"全方向一致"的微分概念。

T'(x)被称为T在x处的Fréchet导数（Fréchet derivative），T'(x)y被称为T在x处增量为y的Fréchet微分（Fréchet differential）。Fréchet微分的几何意义是：函数T在x附近可以被线性函数T(x) + T'(x)(y - x)很好地逼近，误差是o(\|y - x\|)阶的。

两种微分概念之间存在重要的包含关系：如果T在x处是Fréchet可微的，那么它在x处必定是Gâteaux可微的，并且两个导数相等。这是因为Fréchet微分的定义隐含了所有方向导数的存在性和一致性。反之则不成立：存在在某点Gâteaux可微但不是Fréchet可微的函数。经典的例子是f(x,y) = \frac{x^3}{x^2 + y^2}（当(x,y) \neq (0,0)时）和f(0,0) = 0，这个函数在原点处Gâteaux可微但不是Fréchet可微。

这两种微分概念的区别在优化理论中具有重要意义。Fréchet可微性保证了更好的局部线性逼近性质，这对于设计和分析优化算法至关重要。而Gâteaux可微性虽然较弱，但在某些理论分析中已经足够，并且在实际计算中，方向导数往往更容易求得。

Fréchet微分的等价刻画与性质（续）

Fréchet可微的等价表述与证明

在前面我们给出了Fréchet可微的定义，现在来看一个重要的等价刻画。如果T在x处是Fréchet可微的，那么对于所有y \in \mathcal{H} \backslash \{0\}，我们有：

这个极限可以进行变形。首先，注意到分子中的T'(x)(\alpha y)由于T'(x)的线性性，可以写成\alpha T'(x)(y)。因此上式变为：

进一步化简，我们可以提取\alpha，得到：

这恰好说明了\lim_{\alpha \to 0, \alpha > 0} \frac{T(x + \alpha y) - T(x)}{\alpha} = T'(x)(y)。这个结果表明，如果函数是Fréchet可微的，那么它必然是Gâteaux可微的，并且两个导数相等。这个推导过程的关键在于Fréchet微分的一致收敛性质，它保证了当我们固定方向y并让步长\alpha趋于0时，误差项能够被控制。

Fréchet导数的唯一性与连续性

Fréchet导数具有唯一性，这是因为如果存在两个不同的有界线性算子都满足Fréchet微分的定义，那么它们的差在任何方向上都必须为零，从而两个算子必须相等。这个唯一性比Gâteaux导数的唯一性证明更直接，因为Fréchet微分的定义本身就包含了更强的一致性要求。

更重要的是，如果T在x处是Fréchet可微的，那么T在x处必定连续。证明过程如下：对于任意y \in \mathcal{H}使得x + y \in C，我们有：

第一项由Fréchet可微性可以写成o(\|y\|)，即当\|y\|足够小时，这一项相对于\|y\|可以任意小。第二项由于T'(x)是有界线性算子，存在常数M使得\|T'(x)y\| \leq M\|y\|。因此：

当y \to 0时，右边趋于0，这证明了T在x处的连续性。这个性质说明Fréchet可微性蕴含连续性，而Gâteaux可微性一般不能保证连续性，这是两者的另一个重要区别。

具体例子：有限维空间中的可微函数

考虑C \subset \mathbb{R}^N，映射T: C \to \mathbb{R}^M，其中x = (x^{(i)})_{1 \leq i \leq N}表示x的第i个分量，(T^{(j)}(x))_{1 \leq j \leq M}表示T(x)的第j个分量。设\bar{x}是C的内点。

如果对于每个j \in \{1, \ldots, M\}，函数T^{(j)}: C \to \mathbb{R}在\bar{x}的某个邻域内存在连续的偏导数，那么T在\bar{x}处是Fréchet可微的，并且其导数可以用Jacobi矩阵表示：

这个结果是多元微积分中的基本定理。偏导数的连续性保证了函数的局部线性逼近是一致的，这正是Fréchet可微性所要求的。Jacobi矩阵的第j行第i列元素\frac{\partial T_j}{\partial x_i}(\bar{x})描述了输出的第j个分量对输入的第i个分量的敏感度。

线性算子的可微性

设\mathcal{H}和\mathcal{K}是赋范空间，T \in B(\mathcal{H}, \mathcal{K})是有界线性算子。那么T在每个点x \in \mathcal{H}处都是Fréchet可微的，并且T'(x) = T。

证明非常直接：对于任意y \in \mathcal{H}，由于T的线性性，我们有：

这意味着误差项恒为零，自然满足Fréchet可微的要求。这个例子说明线性函数是最简单的可微函数，它们在每一点的导数就是自身。此外，由于T是有界算子，即T \in B(\mathcal{H}, \mathcal{K})，这保证了导数的有界性要求。

双线性函数的可微性

考虑更复杂的例子：设\mathcal{H}和\mathcal{K}是赋范空间，B: \mathcal{H}^2 \to \mathcal{K}是双线性函数，满足有界性条件：

这个条件保证了双线性函数B是连续的。现在定义T: \mathcal{H} \to \mathcal{K}为T(x) = B(x, x)。我们要证明T在每个点x \in \mathcal{H}处都是Fréchet可微的，并且T'(x)y = B(x, y) + B(y, x)。

证明的关键是计算增量：

利用双线性性展开：

因此误差项为：

由于B的有界性，我们有\|B(y, y)\| \leq M_B\|y\|^2。因此：

这证明了T的Fréchet可微性。导数T'(x)y = B(x, y) + B(y, x)是y的线性函数，这是因为B的双线性性质。当我们固定第一个变量x时，B(x, \cdot)和B(\cdot, x)都是线性的。此外，证明的续部分还验证了这个线性算子的有界性：

这表明T'(x)确实是有界线性算子，完成了Fréchet可微性的全部验证。

这个例子在优化理论中特别重要，因为许多二次型函数都可以表示为T(x) = B(x, x)的形式，其中B是对称双线性形式。在这种情况下，T'(x)y = 2B(x, y)，这就是我们熟知的二次函数的梯度公式的抽象形式。

二阶Fréchet可微函数与可微凸函数的刻画

二阶Fréchet可微性的定义

设\mathcal{H}是Hilbert空间，C \subset \mathcal{H}是开集。开集的要求比内点更强，它保证了在集合C中的每一点都有一个完整的邻域包含在C内，这对于定义高阶导数是必要的。设T: C \to \mathbb{R}在C上是Fréchet可微的，这意味着在C的每一点都存在一阶导数\nabla T(x)。

函数T在x \in C处是二阶Fréchet可微的，当且仅当存在一个有界线性算子\nabla^2 T(x) \in B(\mathcal{H}, \mathcal{H})使得：

这个定义本质上是说梯度函数\nabla T本身在x处是Fréchet可微的。二阶导数\nabla^2 T(x)描述了梯度\nabla T在x附近的线性变化率。在有限维空间中，\nabla^2 T(x)对应于Hessian矩阵，它包含了所有二阶偏导数的信息。算子\nabla^2 T(x)被称为T在x处的Hessian。

二阶导数的性质与表示

如果T在x处是二阶Fréchet可微的，那么对于任意(y, z) \in \mathcal{H}^2，二阶方向导数存在并可以表示为：

这个公式揭示了二阶导数的一个重要性质：它通过二阶差分商来刻画函数的二阶变化率。分子中的四项组合T(x + \alpha(y + z)) - T(x + \alpha y) - T(x + \alpha z) + T(x)是一个混合二阶差分，它消除了所有的一阶项，只保留了二阶效应。当\alpha \to 0时，这个差分除以\alpha^2的极限恰好给出了Hessian在方向(y, z)上的作用。

更重要的是，如果T在x处是二阶Fréchet可微的，那么它的Hessian \nabla^2 T(x)是一个自伴算子（self-adjoint operator）。这意味着对于所有y, z \in \mathcal{H}，有：

自伴性是二阶导数的一个基本对称性质，它对应于混合偏导数相等的Schwarz定理在无限维空间的推广。这个性质在优化理论中特别重要，因为自伴算子的谱理论保证了它有实特征值，这对于判断临界点的性质（极小值、极大值或鞍点）至关重要。

Taylor-Young公式

Taylor-Young公式是微分学中的基本定理，它给出了函数在某点附近的二阶近似。设\mathcal{H}是Hilbert空间，C \subset \mathcal{H}是开集，T: C \to \mathbb{R}。假设T在C上是Fréchet可微的，并且在x \in C处是二阶Fréchet可微的。那么当h \to 0时，有：

其中\epsilon: \mathcal{H} \to \mathcal{K}满足\epsilon(h) \to 0当h \to 0。这个公式的意义在于它将函数T在x附近分解为三个部分：常数项T(x)、线性项\langle \nabla T(x) \mid h \rangle、二次项\frac{1}{2}\langle h \mid (\nabla^2 T(x))h \rangle，以及高阶无穷小项\|h\|^2\epsilon(h)。

二次项\frac{1}{2}\langle h \mid (\nabla^2 T(x))h \rangle是一个二次型，它完全由Hessian算子决定。在优化问题中，这个二次型的正定性、负定性或不定性决定了x是局部极小值点、局部极大值点还是鞍点。余项\|h\|^2\epsilon(h)是o(\|h\|^2)阶的，这保证了二阶Taylor展开在x的小邻域内提供了很好的近似。

Taylor-McLaurin公式

Taylor-McLaurin公式是Taylor-Young公式的一个变体，它使用积分形式表示余项。设条件同上，并且T在[x, x + h] \subset C上连续，在]x, x + h[上二阶Fréchet可微。那么：

其中\alpha \in ]0, 1[。这个公式中的\alpha依赖于x和h，它的存在性由中值定理保证。与Taylor-Young公式不同，这里的二次项使用的是在x + \alpha h处（而不是x处）的Hessian。这个公式在证明某些优化算法的收敛性时特别有用，因为它提供了余项的确切表达式而不仅仅是渐近估计。

可微凸函数的刻画定理

这是凸优化理论中最重要的定理之一，它给出了可微凸函数的一阶条件刻画。设f: \mathcal{H} \to ]-\infty, +\infty]在其定义域\text{dom} f上是Gâteaux可微的，其中\text{dom} f是非空开凸集。那么f是凸函数当且仅当：

这个不等式有深刻的几何意义：它说明凸函数的图像总是位于其在任意点处的切平面之上。换句话说，凸函数的线性近似总是提供一个下界。

必要性证明：假设f是凸的。取x \in \text{dom} f，对于任意\alpha \in ]0, 1[和y \in \mathcal{H}，凸性定义给出：

重新整理这个不等式：

两边除以\alpha：

当\alpha \to 0^+时，左边的极限正是\langle \nabla f(x) \mid y - x \rangle，因此得到所需的不等式。

充分性证明：反过来，假设梯度不等式成立。我们需要证明f是凸的。对于任意(x, y) \in (\text{dom} f)^2和\alpha \in ]0, 1[，令z = \alpha x + (1 - \alpha)y \in \text{dom} f（因为\text{dom} f是凸集）。应用梯度不等式两次：

将第一个不等式乘以\alpha，第二个乘以(1 - \alpha)，然后相加：

这正是凸性的定义。这个刻画定理的重要性在于它将凸性这个全局性质转化为一个局部条件（涉及梯度），这使得凸函数的判定和优化变得更加可行。在实际应用中，这个定理也是许多凸优化算法（如梯度下降法）收敛性分析的基础。

可微严格凸函数与梯度单调性的刻画

可微严格凸函数的刻画

设f: \mathcal{H} \to ]-\infty, +\infty]在其定义域\text{dom} f（非空开凸集）上是Gâteaux可微的。函数f是严格凸的当且仅当对于(\text{dom} f)^2中任意x \neq y的点对(x, y)，都有：

这个刻画是凸函数刻画定理的严格版本。几何意义是：严格凸函数的图像严格位于其任意点处切平面的上方（除了切点本身）。这个"严格"性质排除了函数在某些区域是线性的可能，保证了函数具有唯一的全局最小值点（如果存在的话）。

必要性证明：假设f是严格凸的。取\text{dom} f中x \neq y的两点。对任意\alpha \in ]0, 1[，令z = \alpha x + (1 - \alpha)y \in \text{dom} f。由于f是凸的（严格凸蕴含凸），我们首先有：

将z = \alpha x + (1 - \alpha)y代入，得：

关键的一步是利用严格凸性。由于x \neq y且\alpha \in ]0, 1[，严格凸性给出：

结合上述两个不等式，我们得到：

整理后即得f(y) > f(x) + \langle \nabla f(x) \mid y - x \rangle。

充分性证明：反过来，假设严格梯度不等式对所有x \neq y成立。要证明f严格凸，取(x, y) \in (\text{dom} f)^2且x \neq y，\alpha \in ]0, 1[。令z = \alpha x + (1 - \alpha)y，由于z既不等于x也不等于y（因为\alpha \in ]0, 1[），我们可以应用严格梯度不等式：

将第一个不等式乘以\alpha，第二个乘以(1 - \alpha)并相加，梯度项相消，得到严格凸性定义。

凸函数与梯度单调性的等价关系

这是凸分析中的另一个基本刻画：f是凸函数当且仅当其梯度算子\nabla f在\text{dom} f上是单调的，即：

梯度的单调性有深刻的物理和几何意义。在物理上，它对应于保守力场的性质；在几何上，它意味着当我们从x移动到y时，梯度的变化方向与位移方向形成锐角或直角，这保证了函数沿任何方向的增长率是递增的。

必要性证明：假设f是凸的。对任意(x, y) \in (\text{dom} f)^2，凸性给出两个不等式：

将这两个不等式相加，左边相消，得到：

因此\langle \nabla f(y) - \nabla f(x) \mid y - x \rangle \geq 0，这就是梯度的单调性。

充分性证明：假设\nabla f是单调的。对任意(x, y) \in (\text{dom} f)^2，定义辅助函数\varphi: [0, 1] \to \mathbb{R}为\varphi(\alpha) = f(x + \alpha(y - x))。由于\text{dom} f是凸集且f在其上可微，\varphi在[0, 1]上连续，在]0, 1[上可微，其导数为：

根据微积分基本定理和中值定理，存在\alpha \in ]0, 1[使得：

即f(y) - f(x) = \langle \nabla f(x + \alpha(y - x)) \mid y - x \rangle。另一方面，由于x + \alpha(y - x) \in \text{dom} f且\nabla f单调，我们有：

这导出f(y) - f(x) \geq \langle \nabla f(x) \mid y - x \rangle，证明了凸性。

严格凸函数与严格单调梯度

类似地，f是严格凸函数当且仅当\nabla f在\text{dom} f上是严格单调的，即对所有x \neq y：

严格单调性保证了梯度场没有"平坦"区域，这在优化算法的收敛性分析中起着关键作用。例如，梯度下降法在严格凸函数上具有线性收敛速率，而在一般凸函数上可能只有次线性收敛速率。

二阶可微凸函数的刻画

设\mathcal{H}是Hilbert空间，f: \mathcal{H} \to ]-\infty, +\infty]在非空开凸集\text{dom} f上二阶Fréchet可微。函数f是凸的当且仅当对每个x \in \text{dom} f，Hessian算子\nabla^2 f(x)是半正定的：

这个刻画将凸性与二阶导数的正定性联系起来。半正定性意味着二次型\langle z \mid \nabla^2 f(x)z \rangle对所有方向z都非负，这保证了函数在x点的二阶Taylor展开中，二次项总是使函数值增加（或至少不减少）。在有限维情况下，这等价于Hessian矩阵的所有特征值非负。

进一步地，如果对每个x \in \text{dom} f和所有非零向量z \in \mathcal{H} \backslash \{0\}，都有：

那么f是严格凸的。正定的Hessian保证了函数在每一点都有严格的"碗状"结构，没有任何方向是平坦的。这是判断函数严格凸性的一个实用准则，特别是在有限维优化问题中。

这些刻画定理构成了凸优化理论的基础，它们不仅提供了判断函数凸性的多种等价条件，还揭示了凸函数的本质特征：一阶条件（梯度不等式）、梯度的单调性、二阶条件（Hessian的半正定性）。这些不同的视角在理论分析和算法设计中各有其重要作用。

二阶可微凸函数的证明与Fenchel-Legendre共轭理论

二阶可微凸函数刻画定理的证明

接续前面的定理，我们来看证明的具体细节。设(x, y) \in (\text{dom} f)^2且x \neq y。根据Taylor-McLaurin公式，存在u \in ]x, y[ \subset \text{dom} f使得：

如果对所有z \in \mathcal{H}都有\langle z \mid \nabla^2 f(u)z \rangle \geq 0（即Hessian半正定），那么二次项非负，因此：

这正是凸性的梯度不等式刻画。类似地，如果对所有非零z都有\langle z \mid \nabla^2 f(u)z \rangle > 0（即Hessian正定），那么对x \neq y，二次项严格为正，得到严格凸性。

反向证明：假设f是凸的。由于\text{dom} f是开集，对每个x \in \text{dom} f和z \in \mathcal{H}，存在\delta \in ]0, +\infty[使得对所有\alpha \in ]-\delta, \delta[，都有x + \alpha z \in \text{dom} f。由梯度的单调性，我们有：

这等价于\alpha^{-1}\langle \nabla f(x + \alpha z) - \nabla f(x) \mid z \rangle \geq 0。当\alpha \to 0时，左边趋于\langle \nabla^2 f(x)z \mid z \rangle，因此\langle z \mid \nabla^2 f(x)z \rangle \geq 0，证明了Hessian的半正定性。

练习4：log-sum-exp函数的凸性分析

考虑函数f: \mathbb{R}^2 \to \mathbb{R}，定义为：

这个函数在机器学习中称为log-sum-exp函数，是最大值函数的光滑逼近。我们需要判断它的凸性和严格凸性。

首先计算梯度。利用链式法则：

注意到梯度的两个分量都是正数且和为1，这实际上是一个概率分布（softmax函数）。

接下来计算Hessian矩阵。通过对梯度求导：

化简后得到：

这个Hessian矩阵可以写成秩1矩阵的形式。它的特征值为0和2，因此是半正定的但不是正定的。这证明了f是凸的但不是严格凸的。

实际上，当x = y时，我们可以验证f(x, x) = \ln(2\exp(x)) = x + \ln(2)，这在对角线上是线性的，再次确认了函数不是严格凸的。

Fenchel-Legendre共轭的定义

现在我们进入课程的第二个主要部分：Fenchel-Legendre共轭理论。设\mathcal{H}是Hilbert空间，f: \mathcal{H} \to ]-\infty, +\infty]。函数f的Fenchel-Legendre共轭（简称共轭）是函数f^*: \mathcal{H} \to [-\infty, +\infty]，定义为：

这个定义的本质是一个优化问题：对于每个u，我们寻找使得\langle x \mid u \rangle - f(x)最大的x。共轭函数f^*(u)就是这个最大值。

共轭的几何解释

共轭函数有深刻的几何意义。考虑仿射函数x \mapsto \langle x \mid u \rangle - c，它的图像是一个超平面。对于固定的u，f^*(u)是所有满足"超平面\langle x \mid u \rangle - c位于f的图像下方"的c值的下确界的相反数。

从图形上看，这相当于找到斜率为u的所有支撑超平面中，在纵轴上截距最大的那个。第一张图显示了当我们有一条斜率为u的直线\langle x \mid u \rangle时，通过向下平移直到它刚好接触函数f的图像，平移的距离就是f^*(u)。后续的图展示了这个几何过程的不同视角。

共轭函数的基本性质

性质1：定义域的刻画
\text{dom} f \neq \varnothing当且仅当对所有u \in \mathcal{H}，f^*(u) \neq -\infty。

证明：假设存在u \in \mathcal{H}使得f^*(u) = -\infty。这意味着：

这只有在\text{dom} f = \varnothing时才可能发生，因为空集的上确界定义为-\infty。

性质2：无界性的刻画
如果存在x \in \mathcal{H}使得f(x) = -\infty，那么对所有u \in \mathcal{H}，f^*(u) = +\infty。这是因为\langle x \mid u \rangle - f(x) = \langle x \mid u \rangle - (-\infty) = +\infty。

基本例子

例1：二次函数
设f = \frac{1}{2}\| \cdot \|^2，计算其共轭。对任意(x, u) \in \mathcal{H}^2：

这个表达式在x = u时达到最大值，最大值为\frac{1}{2}\|u\|^2。因此f^* = \frac{1}{2}\| \cdot \|^2，即二次函数是自共轭的。

例2：幂函数
对于x \in \mathbb{R}，设f(x) = \frac{1}{q}|x|^q，其中q \in ]1, +\infty[。其共轭函数为：

其中\frac{1}{q} + \frac{1}{q^*} = 1，即q^*是q的共轭指数。这个结果在泛函分析中称为Young不等式的极值形式，它建立了L^q和L^{q^*}空间之间的对偶关系。

共轭理论是凸优化中的核心工具，它不仅提供了对偶问题的数学框架，还在算法设计（如近端算子、对偶上升法）中起着关键作用。通过共轭变换，我们可以将原问题转化为可能更容易求解的对偶问题，这是现代优化理论的基本思想之一。

Fenchel-Legendre共轭函数的性质与计算（续）

幂函数共轭的详细推导

前面我们提到了幂函数的共轭，现在来看完整的推导过程。设f(x) = \frac{1}{q}|x|^q，其中q \in ]1, +\infty[，我们要计算f^*(u) = \sup_x \left( \langle x|u \rangle - \frac{1}{q}|x|^q \right)。

首先观察到，如果u \geq 0，那么使上确界达到最大值的\hat{x}_u必定满足\hat{x}_u = \arg\max(\langle x|u \rangle - f(x)) \geq 0。这是因为如果x < 0，将其替换为-x > 0会得到更大的值。同样，由对称性，f^*(-u) = f^*(u)且\hat{x}_{-u} = -\hat{x}_u。

对于u \geq 0和x > 0的情况，我们需要找到使xu - \frac{1}{q}x^q最大的x。通过求导：

令导数为零，得到\hat{x}_u = u^{\frac{1}{q-1}}。由于二阶导数-(q-1)x^{q-2} < 0（当x > 0时），这确实是最大值点。代入原式：

整理后：

其中q^* = \frac{q}{q-1}满足共轭指数关系\frac{1}{q} + \frac{1}{q^*} = 1。这个结果展示了L^q空间和L^{q^*}空间之间的对偶关系，是泛函分析中Hölder不等式的基础。

共轭函数的基本性质

性质1：偶函数的共轭仍是偶函数

如果f是偶函数（即f(-x) = f(x)），那么f^*也是偶函数。证明如下：

通过变量替换y = -x：

这个性质说明共轭变换保持函数的对称性。

性质2：正齐次性

对于任意\alpha \in ]0, +\infty[，有(\alpha f)^* = \alpha f^*(\cdot/\alpha)。这个性质描述了函数缩放与其共轭的关系：

通过变量替换y = x/\alpha：

性质3：仿射变换的共轭

对于(y, v) \in \mathcal{H}^2和\alpha \in \mathbb{R}，定义g(x) = f(x - y) + \langle x | v \rangle + \alpha，那么：

这个公式的推导涉及共轭定义的展开：

再通过变量替换z = x - y：

性质4：线性变换下的共轭

设\mathcal{G}是另一个Hilbert空间，L \in B(\mathcal{G}, \mathcal{H})是同构映射。如果g = f \circ L，那么(f \circ L)^* = f^* \circ (L^{-1})^*，其中(L^{-1})^*是L^{-1}的伴随算子。

证明过程：

通过变量替换y = Lx（由于L是同构，这是可行的）：

性质5：共轭函数的凸性

共轭函数f^*总是下半连续（l.s.c.）且凸的。这是因为f^*(u)定义为一族仿射函数h_x(u) = \langle x|u \rangle - f(x)的上确界，而仿射函数既是凸的又是连续的。凸函数族的上确界仍然是凸的，连续函数族的上确界是下半连续的。这个性质非常重要，它保证了即使原函数f不是凸的，其共轭f^*也必定是凸的。

性质6：在原点的值

f^*(0) = -\inf f。这是因为：

这个性质将共轭在原点的值与原函数的下确界联系起来。

Fenchel-Young不等式

这是共轭理论中最重要的不等式之一。如果f: \mathcal{H} \to ]-\infty, +\infty]是真函数（proper function，即不恒等于+\infty且在某处有限），那么对所有(x, u) \in \mathcal{H}^2：

证明非常直接。根据共轭的定义，对所有u \in \mathcal{H}和x \in \mathcal{H}：

重新整理即得Fenchel-Young不等式。这个不等式的几何意义是：函数值f(x)与共轭函数值f^*(u)之和总是不小于对偶配对\langle x|u \rangle。等号成立当且仅当u \in \partial f(x)（u是f在x处的次梯度）。

双共轭定理

定义f^{**} = (f^*)^*为f的双共轭（biconjugate）。一个关键结果是：f^{**} \leq f。

这是因为应用Fenchel-Young不等式，我们有f(x) + f^*(u) \geq \langle x|u \rangle，因此：

双共轭f^{**}实际上是f的凸下半连续包络（convex lower semicontinuous envelope），即不超过f的最大凸下半连续函数。如果f本身是凸且下半连续的，那么f^{**} = f，这就是著名的Fenchel-Moreau定理。

双共轭定理与Moreau-Fenchel定理

双共轭的基本性质（续）

前面我们证明了f^{**} \leq f。现在来看更详细的证明。首先处理特殊情况：如果存在x \in \mathcal{H}使得f(x) = -\infty，那么f^* = +\infty，进而f^{**} = -\infty。因此我们可以假设f: \mathcal{H} \to ]-\infty, +\infty]是真函数（即不取-\infty值且至少在某处有限）。

根据Fenchel-Young不等式，对所有x \in \mathcal{H}和u \in \mathcal{H}：

这意味着：

这就证明了f^{**} \leq f。双共轭f^{**}是原函数f的凸下半连续包络，它是不超过f的最大的凸下半连续函数。

共轭的单调性

如果f \leq g，那么f^* \geq g^*，并且f^{**} \leq g^{**}。这个性质说明共轭运算反转了函数的序关系。

证明第一个不等式：对任意u \in \mathcal{H}，

由于f(x) \leq g(x)对所有x成立，我们有\langle x|u \rangle - f(x) \geq \langle x|u \rangle - g(x)。因此：

这证明了f^* \geq g^*。应用同样的推理到双共轭，由于f^{**} \leq f \leq g，根据刚证明的单调性，有(f^{**})^* \geq g^*，因此f^{***} = (f^{**})^* \geq g^*。

三共轭等于一次共轭

一个重要的性质是f^{***} = f^*。证明如下：

我们已知f^{**} = (f^*)^* \leq f^*（应用双共轭不等式到f^*）。另一方面，由于f^{**} \leq f，根据共轭的单调性，f^{***} = (f^{**})^* \geq f^*。结合这两个不等式，得到f^{***} = f^*。

这个结果说明共轭运算在应用三次后会回到第一次共轭，形成了一个"循环"：f \to f^* \to f^{**} \to f^{***} = f^*。

Lemma A：仿射函数的逼近

设\mathcal{H}是Hilbert空间。

(i) 如果f \in \Gamma_0(\mathcal{H})（真凸下半连续函数的集合），那么仿射函数集合\mathcal{A}_f非空，其中\mathcal{A}_f是所有从下方界定f的仿射函数的集合，并且：

这个结果说明任何凸下半连续函数都可以表示为仿射函数族的上确界。这在几何上意味着凸函数的图像是其所有支撑超平面的包络。

(ii) 如果\mathcal{H}是有限维的，f: \mathcal{H} \to ]-\infty, +\infty]是凸的，且\bar{x} \in \text{int}(\text{dom} f)（定义域的内部），那么存在a \in \mathcal{A}_f使得f(\bar{x}) = a(\bar{x})。

这意味着在定义域内部的每一点，都存在一个支撑超平面恰好接触函数图像。这是凸分析中支撑超平面定理的一个表现形式。

插图展示了这个概念：红色曲线是函数f(x)，黑色直线是某个仿射函数a(x)，绿色区域表示所有从下方界定f的仿射函数形成的包络。在点x_0处，存在一个仿射函数恰好等于f(x_0)。

Moreau-Fenchel定理

这是共轭理论的核心定理。设\mathcal{H}是Hilbert空间，f: \mathcal{H} \to ]-\infty, +\infty]是真函数。那么：

这个等价关系完全刻画了可以通过双共轭恢复的函数类。

必要性证明：如果f^{**} = f，由于f^{**}总是下半连续且凸的（作为仿射函数族的上确界），所以f也是下半连续且凸的。

充分性证明：假设f \in \Gamma_0(\mathcal{H})。首先考虑f是仿射函数的情况，即存在(v, \alpha) \in \mathcal{H} \times \mathbb{R}使得f(x) = \langle x | v \rangle + \alpha。

计算其共轭：

如果u \neq v，上确界为+\infty；如果u = v，上确界为-\alpha。因此f^*(u) = \iota_{\{v\}}(u) - \alpha，其中\iota_{\{v\}}是单点集\{v\}的示性函数。

计算双共轭：

这证明了仿射函数满足f^{**} = f。

对于一般的凸下半连续函数f，设a: \mathcal{H} \to \mathbb{R}是满足a \leq f的仿射函数。由于a是仿射函数，有a = a^{**} \leq f^{**}。根据Lemma A(i)，f可以表示为所有这样的仿射函数的上确界：

结合已知的f^{**} \leq f，我们得到f = f^{**}。

右侧的图形展示了这个定理的几何意义：左图显示了原函数f(x)（蓝线）及其双共轭f^{**}(x)（红线）完全重合（当f是凸且下半连续时）；右图显示了共轭函数f^*(u)的形状。

Moreau-Fenchel定理的重要性在于它建立了凸分析中的对偶理论基础。它告诉我们，凸下半连续函数与其双共轭之间存在完美的对应关系，这使得我们可以通过研究共轭函数来理解原函数的性质，反之亦然。这在优化算法设计、对偶理论、以及变分分析中都有广泛应用。

Moreau-Fenchel定理的推论与可分离函数的共轭

Moreau-Fenchel定理的重要推论

如果f \in \Gamma_0(\mathcal{H})（即f是真凸下半连续函数），那么有以下重要结论：

首先，\text{dom} f \neq \varnothing当且仅当f^* > -\infty。这是因为如果定义域为空，共轭函数会取值-\infty。其次，由于f^{**} = f > -\infty，这意味着\text{dom} f^* \neq \varnothing。这两个条件共同说明了f^*也是真函数（proper function）。

由于f^*作为仿射函数族的上确界，它必然是下半连续且凸的，因此f^* \in \Gamma_0(\mathcal{H})。这个结果表明，\Gamma_0(\mathcal{H})在共轭运算下是封闭的：凸下半连续函数的共轭仍然是凸下半连续函数。

双共轭作为凸下半连续包络

设\mathcal{H}是Hilbert空间，f: \mathcal{H} \to ]-\infty, +\infty]是真函数且\text{dom} f^* \neq \varnothing。那么f^{**}是f的凸下半连续包络（lower semicontinuous convex envelope），即它是满足g(x) \leq f(x)对所有x \in \mathcal{H}成立的最大的凸下半连续函数g: \mathcal{H} \to ]-\infty, +\infty]。

这个刻画极其重要，因为它提供了一种系统的方法来"凸化"任意函数。对于一般的非凸函数f，其双共轭f^{**}给出了最佳的凸下界逼近。

证明的第一部分：设F是所有满足g(x) \leq f(x)的凸下半连续函数g: \mathcal{H} \to ]-\infty, +\infty]的集合。由于\text{dom} f^* \neq \varnothing，我们有f^{**} > -\infty。此外，f^{**} \leq f且f^{**}是凸下半连续的（作为仿射函数的上确界），因此f^{**} \in F，证明了F非空。

证明的第二部分：定义\tilde{f}: x \mapsto \sup\{g(x) \mid g \in F\}为F中所有函数的逐点上确界。这是f的凸下半连续包络的直接构造。由于\tilde{f} \leq f，它可以从\tilde{f} \in \Gamma_0(\mathcal{H})推导出。此外，f^{**} \in F意味着f^{**} \leq \tilde{f}。

根据Moreau-Fenchel定理，如果\tilde{f} \leq f，那么f^{**} \geq \tilde{f}^{**} = \tilde{f}（因为\tilde{f}是凸下半连续的）。结合f^{**} \leq \tilde{f}，我们得到\tilde{f} = f^{**}。

双共轭的几何解释

图中展示了这个概念的可视化。左图显示原函数f(x)（蓝线）和其双共轭f^{**}(x)（红线）。当f不是凸函数时，f^{**}提供了从下方的最紧凸包络。右图显示了对应的共轭函数f^*(u)。注意即使原函数f不是凸的，其共轭f^*和双共轭f^{**}都必然是凸的。

可分离函数的共轭

设(\mathcal{H}_i)_{i \in I}是Hilbert空间族，其中I \subset \mathbb{N}，定义乘积空间\mathcal{H} = \times_{i \in I} \mathcal{H}_i。对每个i \in I，设f_i: \mathcal{H}_i \to ]-\infty, +\infty]是真函数。

定义可分离函数f: \mathcal{H} \to ]-\infty, +\infty]为：

这样的函数称为可分离的，因为它可以分解为各个分量函数的和。可分离性在优化中很重要，因为它允许我们将高维问题分解为一系列低维子问题。

可分离函数共轭的主要定理：可分离函数的共轭等于各分量共轭的和：

证明：设u = (u_i)_{i \in I} \in \mathcal{H}，根据共轭的定义：

由于内积和函数都是可分离的：

关键观察是这个优化问题可以分解：上确界可以对每个分量独立进行：

这个分解之所以可能，是因为目标函数是可分离的，且没有耦合约束。

应用：\ell^q范数的共轭

作为可分离函数共轭的重要应用，考虑\mathbb{R}^N上的\ell^q范数。对任意x \in \mathbb{R}^N和q \in ]1, +\infty[，定义：

这是可分离函数f_i(x_i) = \frac{1}{q}|x_i|^q的和。由前面的结果，每个f_i的共轭为：

其中\frac{1}{q} + \frac{1}{q^*} = 1。

应用可分离函数的共轭公式：

这个结果建立了\ell^q和\ell^{q^*}范数之间的对偶关系，是Hölder不等式的基础。它显示了共轭指数q和q^*之间的深刻联系：一个空间的范数的共轭恰好是对偶空间中相应的范数。

可分离函数的共轭理论在大规模优化问题中特别有用。当目标函数或约束可以分解为独立部分的和时，我们可以利用这个性质设计并行算法，如交替方向乘子法（ADMM）或坐标下降法。每个子问题可以独立求解，这大大提高了计算效率。

支撑函数理论

支撑函数的定义

设\mathcal{H}是Hilbert空间，C \subset \mathcal{H}是一个子集。集合C的支撑函数（support function）\sigma_C定义为：

这个定义揭示了支撑函数与示性函数共轭之间的重要关系：\sigma_C = \iota_C^*，其中\iota_C是集合C的示性函数（在C内为0，在C外为+\infty）。

支撑函数的几何意义非常直观：对于给定的方向u，\sigma_C(u)表示集合C在方向u上的"最大伸展"。从原点出发，沿着u方向的射线与集合C的支撑超平面相交，\sigma_C(u)就是这个支撑超平面到原点的有向距离。

支撑函数的几何解释

图中展示了支撑函数的两个视角。左图显示了在二维情况下，对于一个区间[\delta_1, \delta_2]，支撑函数\iota_{[\delta_1,\delta_2]}(x)的图像。当x < 0时，内积\langle x | u \rangle在x = \delta_1处达到最大值\delta_1 u；当x = 0时，最大值为0；当x > 0时，最大值在x = \delta_2处达到\delta_2 u。

右图展示了支撑函数\sigma_C(u)作为u的函数的形状。注意到即使集合C不是凸的，其支撑函数\sigma_C也总是凸的，因为它是仿射函数族的上确界。支撑函数在原点附近的尖锐"谷"形状反映了集合C的有界性：当u接近0时，\sigma_C(u)也趋于0。

关键性质：闭凸集与支撑函数

一个极其重要的性质是：如果C是非空闭凸集，那么\sigma_C^* = \iota_C^{**} = \iota_C。

这个等式的意义深远。它说明对于闭凸集，我们可以通过其支撑函数完全恢复原集合。具体来说，由于\iota_C^{**} = \iota_C（根据Moreau-Fenchel定理，因为\iota_C是凸下半连续函数），集合C可以表示为：

这给出了闭凸集的一个对偶表示：它是所有满足线性不等式约束\langle x | u \rangle \leq \sigma_C(u)的点的交集。这是凸分析中分离定理的一个体现。

例子1：分段线性函数与区间的支撑函数

考虑函数f: \mathbb{R} \to ]-\infty, +\infty]定义为：

其中-\infty \leq \delta_1 < \delta_2 \leq +\infty。

这个分段线性函数实际上等于\sigma_C，其中C是闭区间[\delta_1, \delta_2]的下确界为\delta_1，上确界为\delta_2。这是因为：

• 当u < 0时，\sup_{x \in [\delta_1, \delta_2]} xu在x = \delta_1处达到，值为\delta_1 u
• 当u = 0时，对所有x \in [\delta_1, \delta_2]，xu = 0
• 当u > 0时，\sup_{x \in [\delta_1, \delta_2]} xu在x = \delta_2处达到，值为\delta_2 u

这个例子展示了支撑函数如何编码了集合的"边界信息"：支撑函数的斜率变化点恰好对应于原集合的端点。

例子2：\ell^q范数与单位球的支撑函数

设f是\mathbb{R}^N上的\ell^q范数，其中q \in [1, +\infty]。我们有f = \sigma_C，其中：

这里\frac{1}{q} + \frac{1}{q^*} = 1是共轭指数关系。

证明：根据Hölder不等式，对所有u \in \mathbb{R}^N：

最后一个等式成立是因为当x = \frac{u}{\|u\|_q}（假设u \neq 0）时上确界达到，此时\|x\|_{q^*} = 1。

这个结果建立了范数与其对偶单位球之间的深刻联系：任何范数都可以表示为其对偶单位球的支撑函数。这是凸分析中的基本对偶关系之一。

特殊情况：当q = 1时，q^* = \infty，因此\ell^1范数的单位球C = [-1, 1]^N（\ell^{\infty}单位球）。这解释了为什么\ell^1范数在优化中产生稀疏解：它的次梯度（对应于对偶单位球的极点）是坐标轴方向的单位向量。

练习题

练习1：对于每个c \in \mathbb{R}^N，求函数f: \mathbb{R}^N \to ]-\infty, +\infty]的共轭：

这是一个线性函数，其共轭将涉及示性函数。线性函数的共轭要么是0（当u = c时），要么是+\infty（当u \neq c时），因此f^*(u) = \iota_{\{c\}}(u)。

练习2：求函数g: \mathbb{R}^N \to ]-\infty, +\infty]的共轭：

这是将示性函数平移c单位。需要应用我们之前学过的仿射变换下的共轭公式。函数g表示约束x \geq c（逐分量），其共轭将涉及非负象限的支撑函数。

这些练习帮助我们理解支撑函数、示性函数和它们的共轭之间的相互关系，这些是凸优化中处理约束的基本工具。支撑函数理论为我们提供了一种统一的框架来理解集合、范数和更一般的凸函数之间的对偶关系。

练习题解答与附录：凸几何的基本结果

练习1.1：线性函数的共轭

对于f: \mathbb{R}^N \to ]-\infty, +\infty]定义为f(x) = \langle c|x \rangle，我们要计算其共轭函数。

根据共轭的定义：

这个优化问题的关键在于观察\langle u - c|x \rangle是x的线性函数。当u - c \neq 0时，由于x可以在整个\mathbb{R}^N上自由变化，我们可以选择x沿着u - c的方向并让其模长趋于无穷，这样\langle u - c|x \rangle就会趋于无穷。只有当u - c = 0，即u = c时，内积恒为零，上确界为0。因此：

这个结果表明线性函数的共轭是单点集的示性函数。从几何角度看，线性函数\langle c|x \rangle的图像是一个超平面，其共轭退化为一个点。这反映了线性函数没有"曲率"的事实——它的所有支撑超平面都是它自身。

练习1.2：平移示性函数的共轭

对于g(x) = \iota_{[0, \infty[^N}(x - c)，这是非负象限示性函数平移c单位后的结果。函数g约束x \geq c（逐分量）。

计算共轭：

上确界只在约束集x - c \in [0, \infty[^N内取得，即x \geq c。因此：

令y = x - c \geq 0，则：

内积\langle u|y \rangle = \sum_{i=1}^N u_i y_i在y \geq 0的约束下，当且仅当所有u_i \leq 0时有界。如果存在某个i使得u_i > 0，我们可以让y_i \to \infty使得上确界为+\infty。当所有u_i \leq 0时，最大值在y = 0处达到，值为0。因此：

这可以写成：g^*(u) = \langle u|c \rangle + \iota_{]-\infty, 0]^N}(u)。这个结果展示了约束集的平移如何影响其支撑函数：平移导致共轭函数增加一个线性项。

附录：凸几何的核心结果

超平面分离定理

设C是Hilbert空间\mathcal{H}的凸子集，y \in \mathcal{H}。

(i) 第一分离定理：假设C是非空闭集且y \notin C。那么存在闭半空间D使得C \subset D且y \notin D。即存在v \in \mathcal{H} \backslash \{0\}和\alpha \in \mathbb{R}使得：

证明概要：设\bar{y}是y在C上的投影。由投影的性质，对所有x \in C，有\langle x - \bar{y} | y - \bar{y} \rangle \leq 0。令v = \bar{y} - y，由于y \notin C，我们有v \neq 0。那么：

设\alpha = \inf_{x' \in C} \langle v | x' \rangle，我们得到所需的分离。这个证明的关键是利用了凸集上投影的唯一性和正交性。

(ii) 第二分离定理：假设C有非空内部且y \notin \text{int}(C)。那么存在包含y的闭超平面分离C，即存在v \in \mathcal{H} \backslash \{0\}使得：

这个定理是Hahn-Banach定理的几何形式。它说明对于具有内部的凸集，边界上的点总可以用超平面支撑。

Lemma A的详细证明

这个引理建立了凸函数可以表示为仿射函数族上确界的基本事实。

步骤1：存在仿射下界

当f \in \Gamma_0(\mathcal{H})时，存在x_0 \in \mathcal{H}使得f(x_0) < +\infty。设\eta_0 \in ]-\infty, f(x_0)[，那么(x_0, \eta_0) \notin \text{epi} f。由于\text{epi} f是\mathcal{H} \times \mathbb{R}的闭凸子集，根据超平面分离定理(i)，存在(v_0, \nu_0) \in \mathcal{H} \times \mathbb{R} \backslash \{(0, 0)\}和\alpha_0 \in \mathbb{R}使得：

关键观察是\nu_0 > 0。否则，如果\nu_0 < 0，当\eta \to +\infty时左边会变得任意小；如果\nu_0 = 0，严格不等式不可能成立。通过设置\tilde{v}_0 = -v_0/\nu_0和\tilde{\alpha}_0 = \alpha_0/\nu_0，并令\eta = f(x)，我们得到：

这证明了f被仿射函数a(x) = \tilde{\alpha}_0 + \langle \tilde{v}_0 | x \rangle从下方界定。

步骤2：证明f = \sup_{a \in \mathcal{A}_f} a

设\tilde{f} = \sup_{a \in \mathcal{A}_f} a。显然\tilde{f} \leq f。为了证明相等，需要证明\text{epi}(f) = \text{epi}(\tilde{f})。

对于每个a \in \mathcal{A}_f，由于a \leq f，我们有\text{epi}(f) \subset \text{epi}(\tilde{f})。反向包含通过反证法证明：假设(x_1, \eta_1) \notin \text{epi}(f)，即\eta_1 < f(x_1)。应用分离定理，我们可以找到仿射函数将(x_1, \eta_1)与\text{epi}(f)分离，从而证明(x_1, \eta_1) \notin \text{epi}(\tilde{f})。

步骤3：有限维情况

在有限维空间中，设\bar{x} \in \text{int}(\text{dom} f)。存在包含\bar{x}的\ell_1球\bar{B}_1(\bar{x}, \rho) \subset \text{dom} f。

通过分析f在这个球上的行为，我们可以证明f在\bar{x}附近是局部有界的。具体地，对于\bar{B}_1(\bar{x}, \rho)中的每个点x，可以将其表示为：

其中e_i是标准基，(\lambda_i)和(\zeta_i)是适当选择的系数。利用凸性，可以证明f(x) \leq M对某个常数M成立。

由于(\bar{x}, f(\bar{x})) \notin \text{int}(\text{epi}(f))，再次应用分离定理(ii)，我们可以找到恰好在\bar{x}处接触f的支撑超平面。关键技术细节是证明分离向量的垂直分量\nu > 0，这需要利用f的局部有界性。最终得到存在仿射函数a(x) = f(\bar{x}) + \langle \tilde{v} | x - \bar{x} \rangle满足a(\bar{x}) = f(\bar{x})且a \leq f。

这个引理的重要性在于它提供了凸函数的"线性化"表示，这是对偶理论和次微分理论的基础。它说明任何凸下半连续函数都可以从其所有仿射逼近中重构，这正是Moreau-Fenchel定理的几何本质。