本讲的主要内容是数学工具中的Fenchel-Rockafellar对偶理论。学习目标包括定义Fenchel-Rockafellar对偶的概念，以及通过实例展示如何运用这个对偶理论来求解优化问题。课程内容分为四个部分：首先回顾Fenchel-Legendre共轭的定义和支撑函数，然后介绍Fenchel-Rockafellar对偶本身，接着讨论如何使用这个对偶工具，最后通过实践练习来巩固理解。
Fenchel-Legendre共轭函数的定义
共轭函数是对偶理论的核心概念。设 \mathcal{H} 是一个Hilbert空间，考虑函数 f: \mathcal{H} \to [-\infty, +\infty]。函数 f 的Fenchel-Legendre共轭定义为另一个函数 f^*: \mathcal{H} \to [-\infty, +\infty]，其定义方式为：
这个定义的几何意义可以这样理解：对于给定的 u，我们在 f 的定义域上寻找所有点 x，使得线性函数 \langle x \mid u \rangle 与 f(x) 之间的差距最大。从图形上看，\langle x \mid u \rangle 表示斜率为 u 的线性函数，而 f^*(u) 则是这条直线与函数 f 之间能达到的最大"垂直距离"。这个上确界操作实际上是在所有可能的 x 值上寻找最优配置，因此共轭函数 f^* 本质上编码了原函数 f 的全局信息。
共轭函数的具体例子
通过两个例子可以更好地理解共轭的计算。第一个例子是二次函数 f = \frac{1}{2}\|\cdot\|^2，其共轭函数恰好是它自己，即 f^* = \frac{1}{2}\|\cdot\|^2。这个结果说明二次范数函数在共轭变换下保持不变，这个性质在后续的对偶理论中会经常用到。
第二个例子更具一般性。对于定义在实数上的函数 (\forall x \in \mathbb{R}) \, f(x) = \frac{1}{q}|x|^q，其中 q \in ]1, +\infty[，我们可以计算出其共轭为 (\forall u \in \mathbb{R}) \, f^*(u) = \frac{1}{q^*}|u|^{q^*}，这里的 q^* 满足共轭指数关系 \frac{1}{q} + \frac{1}{q^*} = 1。这个例子展示了幂函数的共轭仍然是幂函数，但指数变成了共轭指数。共轭指数的关系源于Hölder不等式，这个关系在分析中非常基础。
共轭函数的重要性质
共轭函数具有若干重要的代数和分析性质。首先，如果原函数 f 是偶函数，那么其共轭 f^* 也是偶函数。这个性质体现了对称性在共轭变换下的保持。
对于标量乘法，有性质：对任意 \alpha \in ]0, +\infty[，函数 \alpha f 的共轭为 (\alpha f)^* = \alpha f^*(\cdot/\alpha)。这里需要注意的是，共轭不是简单地将 \alpha 乘到 f^* 上，而是需要对自变量做相应的缩放。这个性质在处理带有尺度参数的优化问题时很有用。
对于平移和仿射变换，性质更为复杂：对任意 (y, v) \in \mathcal{H}^2 和 \alpha \in \mathbb{R}，有
这个公式描述了当原函数经过平移、加上线性项和常数项后，其共轭函数如何相应变化。这里的变换规则并不直观，但可以通过共轭的定义直接验证。
如果 \mathcal{G} 是另一个Hilbert空间，L \in \mathcal{B}(\mathcal{G}, \mathcal{H}) 是一个同构映射，那么复合函数 f \circ L 的共轭为 (f \circ L)^* = f^* \circ (L^{-1})^*。这个性质说明共轭运算与线性变换的复合满足某种对偶关系。
从凸分析的角度看，共轭函数 f^* 总是下半连续的且是凸的。这是一个非常重要的性质，即使原函数 f 不具有这些性质，其共轭也自动获得了良好的凸性和连续性。这解释了为什么共轭在优化理论中如此有用。
最后，f^*(0) 的值等于 -\inf f。这个简单的等式连接了共轭在零点的取值与原函数的下确界，在对偶理论中用于建立原问题和对偶问题最优值之间的关系。
Fenchel-Young不等式
这是共轭理论中最基础的不等式。如果函数 f: \mathcal{H} \to ]-\infty, +\infty] 是proper的（即存在至少一点使得 f 取有限值），那么对任意 (x, u) \in \mathcal{H}^2，都有
这个不等式的证明非常直接。根据共轭的定义，对任意 u \in \mathcal{H} 和任意 x \in \mathcal{H}，由于 f^*(u) 是上确界，必然有
移项即得Fenchel-Young不等式。这个不等式建立了原函数和共轭函数之间的基本关系，在对偶理论和变分不等式中扮演核心角色。它说明了 f(x) 和 f^*(u) 的和总是被内积 \langle x \mid u \rangle 所控制，这个界在某些特殊的 (x, u) 对上可以取到等号，这些点对应着对偶问题的最优性条件。
可分离函数的共轭
在处理多变量优化问题时，经常遇到可分离的函数结构。设 (\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] 是proper函数。定义可分离函数
这个函数的特点是在每个坐标分量上独立地作用，总的函数值是各分量函数值的和。对于这种可分离结构，共轭函数具有非常好的性质：对任意 u = (u_i)_{i \in I} \in \mathcal{H}，有
这个结果表明，可分离函数的共轭等于各分量函数共轭的和。换句话说，共轭运算保持了函数的可分离结构。这个性质在实际计算中非常有用，因为它允许我们将高维问题分解为多个低维问题分别处理。
作为这个性质的一个具体应用，考虑 \mathbb{R}^N 上的 q-范数函数：(\forall x \in \mathbb{R}^N) \, f(x) = \frac{1}{q}\|x\|_q^q，其中 q \in ]1, +\infty[。这个函数可以写成可分离形式 f(x) = \sum_{i=1}^N \frac{1}{q}|x_i|^q。利用前面的结果，我们知道每个分量的共轭是 \frac{1}{q^*}|\cdot|^{q^*}，因此整个函数的共轭为
这里 \frac{1}{q} + \frac{1}{q^*} = 1。这个结果将一维幂函数的共轭推广到了高维空间，并且说明了 q-范数函数和 q^*-范数函数通过共轭关系相联系。这个对偶关系在泛函分析和优化理论中有深刻的应用，特别是在研究不同范数空间之间的对偶性时。
支撑函数
支撑函数是凸分析中另一个基础概念，它与指示函数的共轭直接相关。设 \mathcal{H} 是Hilbert空间，C \subset \mathcal{H} 是其中的一个子集。集合 C 的支撑函数 \sigma_C 定义为：对任意 u \in \mathcal{H}，
这个定义实际上等于指示函数 \iota_C 的共轭，即 \sigma_C(u) = \iota_C^*(u)。回顾指示函数的定义：\iota_C(x) 在 x \in C 时取值为 0，否则为 +\infty。根据共轭的定义，
因为只有当 x \in C 时 \iota_C(x) = 0，否则项 \langle x \mid u \rangle - \iota_C(x) 会是 -\infty，不会影响上确界。
从几何角度理解支撑函数：给定方向 u，支撑函数 \sigma_C(u) 度量的是集合 C 中的点在方向 u 上的投影能达到的最大值。图示展示了这个几何意义：对于给定的 u，我们考虑线性泛函 \langle x \mid u \rangle，它在不同的 x 处取不同的值。支撑函数的值就是当 x 遍历整个集合 C 时，这个线性泛函所能达到的上确界。从另一个角度看，\sigma_C(u) 实际上给出了与方向 u 正交的超平面与集合 C 相切时，该超平面到原点的有向距离。
这里有一个关于双共轭的注记。如果 C 是非空闭凸集，那么指示函数的双共轭等于自身，即 \sigma_C^* = \iota_C^{**} = \iota_C。这个性质来源于凸分析的一个基本定理：对于proper下半连续凸函数，双共轭运算返回函数的闭凸包络，而对于非空闭凸集的指示函数，这个包络恰好是自身。这个结果建立了支撑函数和指示函数之间的对偶关系：通过支撑函数，我们可以完全刻画闭凸集的性质。
支撑函数的例子
第一个例子考虑实数上的分段线性函数。设
其中参数满足 -\infty \leq \delta_1 < \delta_2 \leq +\infty。这个函数在负半轴和正半轴上分别是斜率为 \delta_1 和 \delta_2 的线性函数，在原点处取值为 0。这样定义的函数 f 实际上是某个闭实数区间 C 的支撑函数，该区间的下确界为 \delta_1，上确界为 \delta_2。换句话说，C = [\delta_1, \delta_2]（在端点可能是无穷的情况下理解为相应的射线或整个实轴）。这个例子说明，对于一维空间中的区间，其支撑函数就是这种分段线性形式，不同的方向 u（在一维中就是 u 的正负号）对应着取区间的左端点或右端点与 u 的内积。
第二个例子涉及范数的对偶。设 f 是 \mathbb{R}^N 上的 \ell^q 范数，其中 q \in [1, +\infty]。这个范数函数可以表示为某个集合的支撑函数，具体地，f = \sigma_C，其中
这里 q^* 是 q 的共轭指数，满足 \frac{1}{q} + \frac{1}{q^*} = 1。集合 C 是 q^*-范数意义下的单位球。为了验证这个等式，利用Hölder不等式：对任意 u \in \mathbb{R}^N，
最后一个等号是因为对 \|x\|_{q^*} \leq 1 的 x，内积 \langle u \mid x \rangle 由Hölder不等式被 \|u\|_q \|x\|_{q^*} 所界定，且这个界可以通过选取适当的 x 达到（具体地，取 x 为使Hölder不等式取等的方向）。这个结果表明，q-范数函数是 q^*-范数单位球的支撑函数，这反映了 \ell^q 空间和 \ell^{q^*} 空间之间的对偶关系。
特别地，当 q = 1 时，共轭指数 q^* = \infty，因此 \ell^1 范数是 \ell^\infty-范数单位球的支撑函数。在 \mathbb{R}^N 上，\ell^\infty-范数的单位球恰好是超立方体 [-1, 1]^N，所以 \|\cdot\|_1 = \sigma_{[-1, 1]^N}。这个具体的例子清楚地展示了不同范数空间之间通过支撑函数建立的对偶联系。
练习题：共轭函数的计算
这部分通过两个练习题来巩固共轭函数的计算方法。
第一题要求计算线性函数的共轭。对于 \mathbb{R}^N 中给定的向量 c，考虑函数
这是一个线性泛函。要计算它的共轭 f^*(u)，根据定义进行：
这里关键在于分析这个上确界。当 u - c \neq 0 时，内积 \langle u - c \mid x \rangle 可以通过选择 x 在 u - c 方向上任意大而趋于无穷。具体地，取 x = t(u - c)，当 t \to +\infty 时，\langle u - c \mid x \rangle = t\|u - c\|^2 \to +\infty。因此当 u \neq c 时，f^*(u) = +\infty。反之，当 u = c 时，u - c = 0，上确界中的表达式恒为 0，故 f^*(c) = 0。综合起来，
这个结果表明线性泛函的共轭是单点集的指示函数。这个例子揭示了一个深刻的对偶关系：在原空间中最简单的函数（线性函数）对应到对偶空间中最集中的对象（单点集）。
第二题涉及平移后的非负象限指示函数。函数定义为
其中 c \in \mathbb{R}^N 是给定向量。这个函数在 x - c \in [0, \infty[^N 时取值 0，否则为 +\infty。换句话说，函数在平移后的非负象限 c + [0, \infty[^N 上有限。计算共轭时，
由于指示函数的存在，上确界实际上只需在 x - c \in [0, \infty[^N 上进行：
做变量替换 y = x - c，即 x = y + c，其中 y \in [0, \infty[^N。这样
由于 \langle u \mid c \rangle 是常数，可以提出来：
现在需要分析第二项。对于 y = (y_1, \ldots, y_N) 其中所有 y_i \geq 0，有 \langle u \mid y \rangle = \sum_{i=1}^N u_i y_i。如果存在某个 i 使得 u_i > 0，那么可以让对应的 y_i \to +\infty 而使内积趋于无穷，因此上确界为 +\infty。只有当所有 u_i \leq 0 时，上确界才有限，此时最优选择是 y = 0，上确界为 0。因此
结合起来，
这个结果展示了平移和约束如何在共轭变换下相互作用：原函数中对变量的非负约束对应到共轭函数中对偶变量的非正约束，而原函数的平移对应到共轭函数中添加的线性项。
Fenchel-Rockafellar对偶问题
现在进入本讲的核心内容，即Fenchel-Rockafellar对偶理论。这个理论为一大类优化问题建立了系统的对偶框架。
原问题的设定如下。设 \mathcal{H} 和 \mathcal{G} 是两个实Hilbert空间，f: \mathcal{H} \to ]-\infty, +\infty] 和 g: \mathcal{G} \to ]-\infty, +\infty] 是两个proper函数，L \in \mathcal{B}(\mathcal{H}, \mathcal{G}) 是从 \mathcal{H} 到 \mathcal{G} 的有界线性算子。原问题要求
这个问题的结构是：目标函数由两部分组成，第一部分 f(x) 直接作用在决策变量 x 上，第二部分 g(Lx) 通过线性算子 L 将 x 映射到另一个空间后再施加函数 g。这种结构在约束优化、正则化问题、以及许多工程和统计应用中普遍存在。定义原问题的最优值为
对应的对偶问题通过共轭函数构造。对偶问题要求
其中 L^* 是 L 的伴随算子，f^* 和 g^* 分别是 f 和 g 的Fenchel-Legendre共轭。对偶问题的最优值定义为
对偶问题的构造基于共轭的性质，它将原空间中的优化问题转换到对偶空间中。这里 v 可以理解为拉格朗日乘子或对偶变量，它编码了原问题中由线性算子 L 引入的耦合关系。
弱对偶性
弱对偶定理是对偶理论的基础结果。在上述设置下，设 \mathcal{H} 和 \mathcal{G} 是两个实Hilbert空间，f 是从 \mathcal{H} 到 ]-\infty, +\infty] 的proper函数，g 是从 \mathcal{G} 到 ]-\infty, +\infty] 的proper函数，L \in \mathcal{B}(\mathcal{H}, \mathcal{G})。定义原问题最优值
和对偶问题最优值
弱对偶性断言：\mu \geq -\mu^*。如果 \mu \in \mathbb{R}，那么量 \mu + \mu^* 称为对偶间隙。对偶间隙度量了原问题和对偶问题最优值之间的差距，它总是非负的。当对偶间隙为零时，称为强对偶性成立，这意味着原问题和对偶问题的最优值相等（符号相反）。弱对偶性的证明相对直接，它主要依赖于Fenchel-Young不等式，而强对偶性的成立则需要额外的条件，这将在后续内容中讨论。
弱对偶性的证明
弱对偶定理的证明基于Fenchel-Young不等式的巧妙应用。对任意 x \in \mathcal{H} 和 v \in \mathcal{G}，我们可以对函数 f 和 g 分别应用Fenchel-Young不等式。
对于函数 f 和配对 (x, u)，Fenchel-Young不等式给出 f(x) + f^*(u) \geq \langle x \mid u \rangle。这里取 u = -L^* v，得到
对于函数 g 和配对 (y, v)，同样有 g(y) + g^*(v) \geq \langle y \mid v \rangle。这里取 y = Lx，得到
将这两个不等式相加：
右边的两项可以利用伴随算子的性质简化。伴随算子 L^* 的定义是 \langle Lx \mid v \rangle = \langle x \mid L^* v \rangle，因此
所以对任意 x \in \mathcal{H} 和 v \in \mathcal{G}，都有
重新整理这个不等式：
这个不等式对所有 x 和 v 都成立。对左边关于 x 取下确界，对右边关于 v 取上确界（注意负号）：
但这里对偶问题定义的是 \mu^* = \inf_{v \in \mathcal{G}} \left( f^*(-L^* v) + g^*(v) \right)，所以
即 \mu + \mu^* \geq 0。这就是弱对偶性。这个证明的核心在于Fenchel-Young不等式提供了原变量和对偶变量之间的基本关系，而伴随算子的性质使得交叉项恰好抵消。
强对偶性
强对偶性是说原问题和对偶问题的最优值相等（除了符号），即对偶间隙为零。然而强对偶性并不总是成立，它需要额外的条件。
强对偶定理的陈述如下。设 \mathcal{H} 和 \mathcal{G} 是两个实Hilbert空间，假设 f \in \Gamma_0(\mathcal{H})，g \in \Gamma_0(\mathcal{G})，L \in \mathcal{B}(\mathcal{H}, \mathcal{G})。这里 \Gamma_0 表示proper、下半连续、凸函数的集合。如果满足条件
那么强对偶性成立：
这里需要注意，对偶问题的下确界实际上可以达到（即存在最小值），这由定理保证。强对偶性的条件 0 \in \text{int}(\text{dom } g - L(\text{dom } f)) 称为内点条件或约束规范条件，它确保了原问题和对偶问题之间没有对偶间隙。
注记1给出了验证内点条件的两个充分条件。如果满足以下任一条件：
或
那么 0 \in \text{int}(\text{dom } g - L(\text{dom } f))。
这个注记的证明如下。假设存在 x \in \text{int}(\text{dom } g) \cap L(\text{dom } f)，这意味着 x 既在 \text{dom } g 的内部，又在 L(\text{dom } f) 中。由于 x 是 \text{dom } g 的内点，存在以 x 为中心、半径为 \rho \in ]0, +\infty[ 的开球 B(x, \rho) 使得 B(x, \rho) \subset \text{dom } g。现在考虑平移后的球：
这个包含关系成立是因为：对任意 y \in B(x, \rho)，有 y \in \text{dom } g，而 x \in L(\text{dom } f)，所以 y - x \in \text{dom } g - L(\text{dom } f)。由于 B(0, \rho) 是原点的一个邻域，这表明 0 是集合 \text{dom } g - L(\text{dom } f) 的内点。第二个充分条件的证明采用类似的论证，只是角色互换。
为了理解内点条件的含义，我们需要回顾集合运算的定义。对于两个集合 A 和 B：
- 闵可夫斯基和：A + B = \{x = a + b \mid (a, b) \in A \times B\}
- 闵可夫斯基差：A - B = \{x = a - b \mid (a, b) \in A \times B\}
- 线性算子作用：LA = \{y = La \mid a \in A\}
因此，\text{dom } g - L(\text{dom } f) 是集合 \{z = y - Lx \mid (y, x) \in \text{dom } g \times \text{dom } f\}。条件 0 \in \text{int}(\text{dom } g - L(\text{dom } f)) 的几何意义是：存在 y_0 \in \text{dom } g 和 x_0 \in \text{dom } f 使得 y_0 = Lx_0，并且在这个交点附近，\text{dom } g 和 L(\text{dom } f) 有一定的"重叠余地"。这个条件排除了两个定义域仅在边界上相切的退化情况，确保了对偶问题的良好性态。
强对偶性下的最优性条件
注记2给出了当强对偶性成立且原问题和对偶问题都达到最优值时的重要刻画。设 \hat{v} \in \mathcal{G} 是对偶问题的最优解，即
如果原问题也存在最优解 \hat{x} \in \mathcal{H} 使得
那么这两个最优解之间满足以下关系：
这两个等式说明Fenchel-Young不等式在最优点处取等号。要理解这个结果的意义，回顾Fenchel-Young不等式一般给出 f(x) + f^*(u) \geq \langle x \mid u \rangle。在这里，第一个等式可以重写为
这表明在原问题和对偶问题的最优解处，函数 f 与其共轭之间的不等式达到紧致。类似地，第二个等式表明
证明过程如下。根据Fenchel-Young不等式，对任意 x 和 u 都有
如果这两个不等式中有任何一个是严格不等式，那么将它们相加会得到
即
利用伴随算子的性质 \langle L^* \hat{v} \mid \hat{x} \rangle = \langle \hat{v} \mid L\hat{x} \rangle，上式简化为
这与强对偶性 \mu^* = -\mu 矛盾。因此两个不等式都必须取等号。这个结果在优化理论中具有深刻含义：它给出了原问题和对偶问题最优解之间的显式对应关系，这种关系在算法设计和最优性条件的验证中非常有用。
使用Fenchel-Rockafellar对偶
现在进入第三部分，讨论如何实际应用Fenchel-Rockafellar对偶理论。对偶理论不仅是数学上优美的结果，更是解决实际优化问题的有力工具。通过对偶变换，我们常常可以将原本困难的问题转化为更易处理的形式，或者获得问题解的性质和界。
极小极大定理
极小极大定理是对偶理论的一个经典应用，它在博弈论、鞍点问题、以及许多优化算法中都有基础性作用。定理的陈述如下。
设 \mathcal{H} 和 \mathcal{G} 是两个Hilbert空间，L \in \mathcal{B}(\mathcal{H}, \mathcal{G}) 是有界线性算子。设 C 是 \mathcal{H} 的非空闭凸集，D 是 \mathcal{G} 的非空闭有界凸集。那么交换极小和极大运算的顺序不改变结果：
这个定理断言，对于双线性形式 \langle Lx \mid v \rangle，先对 v 求最大再对 x 求最小，与先对 x 求最小再对 v 求最大，得到的结果相同。
证明利用Fenchel-Rockafellar对偶。首先，左边可以写成
这里用到了支撑函数的定义：\max_{v \in D} \langle Lx \mid v \rangle = \sigma_D(Lx)，以及指示函数 \iota_C 的作用是将优化限制在集合 C 上。另外，由于 D 是有界的，对任意 y \in \mathcal{G}，
这表明 \sigma_D 的定义域是整个 \mathcal{G}，即 \text{dom } \sigma_D = \mathcal{G}。由于 C \neq \varnothing，有 \text{int}(\text{dom } \sigma_D) \cap L(C) = \mathcal{G} \cap L(C) \neq \varnothing（因为 L(C) \subset \mathcal{G}）。此外，\iota_C \in \Gamma_0(\mathcal{H}) 且 \sigma_D = \iota_D^* \in \Gamma_0(\mathcal{G})，所以强对偶性的条件满足。应用强对偶定理：
这里用到了 \iota_C^* = \sigma_C 和 \sigma_D^* = \iota_D^{**} = \iota_D（因为 D 是闭凸的）。继续化简，
这就证明了极小极大等式。
博弈论解释
极小极大定理有直观的博弈论解释。考虑两个玩家的零和博弈，玩家各有 N 个可能的行动，编号为 \{1, \ldots, N\}。假设两个玩家独立地选择行动（例如石头剪刀布）。对每个 (i, j) \in \{1, \ldots, N\}^2，设 L_{i,j} 是当第一个玩家选择行动 j 而第二个玩家选择行动 i 时，第二个玩家获得的奖励。相应地，-L_{i,j} 是第一个玩家的奖励，因为这是零和博弈。假设第一个玩家的混合策略是概率分布 x = (x^{(1)}, \ldots, x^{(N)})，其中 x^{(i)} 是选择第 i 个行动的概率；第二个玩家的混合策略是 v = (v^{(1)}, \ldots, v^{(N)})。这两个策略都被约束在单纯形上，即属于凸集
第二个玩家的期望奖励是
其中 L = (L_{i,j})_{1 \leq i,j \leq N} 是支付矩阵。相应地，第一个玩家的期望奖励是 -\langle Lx \mid v \rangle。
玩家1认为玩家2足够聪明，会选择策略 v 来最大化自己的奖励 \langle Lx \mid v \rangle，给定玩家1的选择 x。因此玩家1的最优策略是最小化玩家2能达到的最好奖励，即求解
反之，如果玩家2采用类似的保守策略，会求解
极小极大定理断言这两个值相等。这意味着存在一个均衡，在这个均衡点上，两个玩家采用各自的最优混合策略后，得到的期望奖励是确定的，不依赖于谁先选择。这个共同的值称为博弈的值，而使得极小极大等式成立的策略对 (x^*, v^*) 称为纳什均衡。极小极大定理从数学上保证了这样的均衡在零和博弈中总是存在的（在混合策略意义下），这是博弈论的基石性结果之一。
练习题：线性规划的Fenchel-Rockafellar对偶
这个练习展示了如何将经典的线性规划对偶理论纳入Fenchel-Rockafellar框架。给定矩阵 L \in \mathbb{R}^{K \times N}，向量 b \in \mathbb{R}^K 和 c \in \mathbb{R}^N，考虑原始线性规划问题：
这个问题要在非负象限中寻找向量 x，使得线性目标函数 \langle c \mid x \rangle 最小，同时满足线性不等式约束 Lx \geq b。练习要求证明这个问题的对偶问题是：
将线性规划问题转化为Fenchel-Rockafellar形式
为了应用Fenchel-Rockafellar对偶理论，需要将原始问题改写成 \inf_{x \in \mathcal{H}} (f(x) + g(Lx)) 的形式。原问题可以等价地写为：
这里引入了两个指示函数。第一个 \iota_{[0, \infty[^N}(x) 强制要求 x 在非负象限，当 x \in [0, \infty[^N 时取值0，否则为 +\infty。第二个 \iota_{[0, \infty[^K}(Lx - b) 强制要求约束 Lx - b \geq 0（即 Lx \geq b）。因此原问题变成了寻找
其中 f(x) = \langle c \mid x \rangle + \iota_{[0, \infty[^N}(x) 和 g(y) = \iota_{[0, \infty[^K}(y - b)。注意这里线性算子就是 L 本身，而函数 g 作用在平移后的变量 Lx - b 上，这通过重新定义 g 来实现平移。
计算共轭函数
首先计算 f^*(u)。根据定义：
由于指示函数的存在，上确界只需在 x \in [0, \infty[^N 上进行：
对于这个上确界，如果存在某个分量 (u - c)_i > 0，那么可以让对应的 x_i \to +\infty 使得内积趋于无穷。只有当所有分量 (u - c)_i \leq 0 时，上确界才有限，此时最优选择是 x = 0，上确界为0。因此：
这可以进一步写为 f^*(u) = \iota_{]-\infty, c]}(u)，其中不等式是逐分量理解的。
接下来计算 g^*(v)。由于 g(y) = \iota_{[0, \infty[^K}(y - b)，这是指示函数的平移，利用前面练习的结果：
这里 \iota_{]-\infty, 0]^K}(v) 要求 v 的所有分量非正。
验证强对偶条件
为了应用强对偶定理，需要验证内点条件 0 \in \text{int}(\text{dom } g - L(\text{dom } f))。首先识别各函数的定义域：
- f \in \Gamma_0(\mathbb{R}^N) 且 \text{dom } f = [0, \infty[^N（因为 f 在非负象限上是线性函数，在其他地方为无穷）
- g \in \Gamma_0(\mathbb{R}^K) 且 \text{dom } g = [b_1, \infty[ \times \ldots \times [b_K, \infty[（因为 g(y) 要求 y - b \geq 0）
- L \in \mathcal{B}(\mathbb{R}^N, \mathbb{R}^K)
验证内点条件的一个充分条件是 \text{int}(\text{dom } g) \cap L(\text{dom } f) \neq \varnothing。\text{dom } g 的内部是 \{y \in \mathbb{R}^K \mid y > b\}（严格不等式），即所有分量都严格大于 b 的对应分量。因此，只要存在 x \in [0, \infty[^N 使得 Lx > b（严格不等式），内点条件就满足，强对偶性就成立。
推导对偶问题
根据Fenchel-Rockafellar对偶理论，对偶问题是
将之前计算的共轭代入：
第一个指示函数要求 -L^\top v - c \leq 0，即 -L^\top v \leq c，也就是 L^\top v \geq -c。但这里需要重新整理：\iota_{]-\infty, 0]^N}(-L^\top v - c) 实际上要求 -L^\top v - c \in ]-\infty, 0]^N，即 -L^\top v \leq c，因此 L^\top v \geq -c。不对，让我重新看：
\iota_{]-\infty, c]}(u) 要求 u \leq c，所以 f^*(u) = \iota_{]-\infty, c]}(u)。因此 f^*(-L^\top v) = \iota_{]-\infty, c]}(-L^\top v)，这要求 -L^\top v \leq c。
对偶问题变为：
由于 v \leq 0，可以改写为 v \in ]-\infty, 0]^K。注意到这是一个最小化问题，而通常线性规划对偶写成最大化。将 v 替换为 -y，其中 y \geq 0：
因此对偶问题等价于
这正是标准的线性规划对偶形式。由于强对偶性成立（在内点条件下），我们有原问题最优值等于对偶问题最优值的负数，即线性规划的强对偶定理。这个推导展示了Fenchel-Rockafellar对偶框架如何统一地包含了线性规划对偶理论。
实践练习
课程的第四部分是一个实践练习，通过一个具体的优化问题来比较直接求解和对偶求解的方法。
设 N \in \mathbb{N} 且 N \geq 2。考虑在 \mathbb{R}^N 上定义的函数 f：
优化问题是在约束条件
下最小化这个函数。这个问题结合了指数函数和线性项，约束是一个简单的线性不等式，要求所有分量的和至少为1。
练习要求比较两种方法：第一种是用经典的约束优化算法直接求解原问题（内点法，将在后续课程中学习）；第二种是先构造对偶问题，然后求解对偶问题。通过这个对比，可以看到对偶理论在实际计算中的优势。
原问题的直接求解
问题1要求实现经典的约束连续优化算法。可以使用Matlab中的fmincon指令或Python中的scipy.minimize指令。这些是通用的优化求解器，能够处理带有一般约束的非线性优化问题。
需要报告的结果包括：函数的最优值、算法的执行时间、最优解 x 的轨迹（即优化过程中 x 如何收敛到最优解）。这些数值实验应该针对三个不同的维度：N = 10, 100, 1000。通过这些不同规模的问题，可以观察算法的可扩展性，即当问题维度增大时，求解时间如何增长。
用对偶理论重新表述问题
问题2要求利用Fenchel-Rockafellar对偶来重新表述优化问题。首先需要将问题写成 f(x) + g(Lx) 的标准形式。然后解析地计算函数 f 和 g 的共轭。最后，给出对偶问题的完整表达式，并指出这是一个单变量的有界约束优化问题。
对偶问题相比原问题有显著的简化：原问题是 N 维的（需要优化 N 个变量），而对偶问题只是一维的（只需要优化一个标量变量）。这种维度的降低在实际计算中带来巨大的优势，特别是当 N 很大时。
利用强对偶性的注记2，可以说明一旦求解了对偶问题得到最优的对偶变量 \hat{v}，就能够通过显式公式恢复出原问题的最优解 \hat{x}。这提供了从对偶解到原解的桥梁。
对偶问题的求解
问题3要求实现标量优化算法来求解对偶问题，该问题只涉及一个变量且有界约束。可以使用Matlab的fminbnd指令。然后将得到的结果与问题1的结果进行比较，验证两种方法是否得到相同的最优值，以及在计算效率上有何差异。
问题的Fenchel-Rockafellar形式
将原问题改写为标准形式。要最小化的函数是
约束 \sum_{i=1}^N x^{(i)} \geq 1 等价于 Lx \geq 1，其中 L = \mathbf{1}_{1 \times N} 是 1 \times N 的全1行向量。因此问题可以写成
其中 g = \iota_{[1, \infty[} 是半无限区间 [1, \infty[ 的指示函数，L = \mathbf{1}_{1 \times N}。
验证强对偶性的条件。函数 f 属于 \Gamma_0(\mathbb{R}^N)，因为它是指数函数和线性函数的和，这些都是凸的、连续的、proper的。函数 g 属于 \Gamma_0(\mathbb{R})，它的定义域是 \text{dom } g = [1, \infty[。线性算子 L \in \mathcal{B}(\mathbb{R}^N, \mathbb{R})。
要验证内点条件 0 \in \text{int}(\text{dom } g - L(\text{dom } f))。由于 \text{dom } f = \mathbb{R}^N，有 L(\text{dom } f) = \mathbb{R}。因此 \text{dom } g - L(\text{dom } f) = [1, \infty[ - \mathbb{R} = \mathbb{R}，其内部是 \mathbb{R}，显然 0 \in \mathbb{R}。另一种验证方法：\text{int}(\text{dom } g) = ]1, \infty[，只要存在 x \in [0, \infty[^N 使得 Lx > 1（例如取所有分量都足够大），内点条件就满足。所以强对偶性成立。
共轭函数的计算
计算 f^*(u)。函数 f 具有可分离结构，可以写成
根据可分离函数的共轭性质，
对于每个分量函数，
这等价于计算 \exp 的共轭在 v - \frac{i}{N} 处的值。对于指数函数的共轭 \exp^*(w) = \sup_{y \in \mathbb{R}} (wy - \exp(y))，当 w > 0 时，函数 wy - \exp(y) 在 \hat{y} = \log(w) 处达到最大值（通过求导可得）。将 \hat{y} 代入，得到
当 w = 0 时，上确界为 0 - 1 = -1；当 w < 0 时，由于指数函数增长速度超过线性，上确界为 +\infty。因此完整的表达式是
这里约定 0 \log(0) = 0。应用到 f_i^*：
因此整体的共轭为
计算 g^*(v)。由于 g = \iota_{[1, \infty[}，这是前面练习中见过的类型。对于 g(y) = \iota_{[1, \infty[}(y)，根据练习结果（平移后的非负象限指示函数），
这要求 v \leq 0。
对偶问题的表达式
根据Fenchel-Rockafellar对偶，
由于 L = \mathbf{1}_{1 \times N}，其转置 L^\top = \mathbf{1}_{N \times 1} 是列向量，因此 -L^\top v = -v \mathbf{1}_{N \times 1}，即所有分量都是 -v。代入：
指示函数的约束合并起来。\iota_{[0, \infty[}(-v - \frac{i}{N}) 要求 -v - \frac{i}{N} \geq 0 对所有 i = 1, \ldots, N，即 -v \geq \frac{i}{N}，最严格的约束是 -v \geq \frac{N}{N} = 1，即 v \leq -1。结合 \iota_{]-\infty, 0]}(v) 的约束 v \leq 0，最终约束是 v \leq -1。化简目标函数：
这是一个关于单变量 v 的优化问题，变量受到下界约束 v \leq -1。相比原问题的 N 维优化，这是显著的简化。
从对偶解恢复原解
利用强对偶性的注记2。设 \hat{v} 是对偶问题的最优解，使得
如果原问题存在最优解 \hat{x} 使得 \mu = f(\hat{x}) + g(L\hat{x})，那么
这个等式说明在 u = -L^\top \hat{v} 处，Fenchel-Young不等式取等号。对于可分离函数，这意味着对每个分量 i，
对于函数 f_i(z) = \exp(z) + \frac{i}{N} z，当 u > 0 时，函数 \langle u \mid z \rangle - f_i(z) = uz - \exp(z) - \frac{i}{N} z 在 \hat{z}_u = \log(u - \frac{i}{N}) 处最大化（通过对 z 求导：u - \exp(\hat{z}) - \frac{i}{N} = 0，得 \exp(\hat{z}) = u - \frac{i}{N}）。因此对于 u > \frac{i}{N}，最优点是 \hat{z}_u = \log(u - \frac{i}{N})，从而
在我们的情况下，u^{(i)} = -\hat{v} - \frac{i}{N}，因此
等等，让我重新检查。实际上，对于 f_i(z) = \exp(z) + \frac{i}{N} z，其共轭在 u 处对应的最优点满足
所以 \hat{z} = \log(u - \frac{i}{N})。在我们的设置中，u^{(i)} = -\hat{v}（因为 -L^\top \hat{v} 的每个分量都是 -\hat{v}），所以
综合起来，原问题的最优解可以从对偶解通过公式
恢复。由于函数 f(x) + g(Lx) 是强制的（当 \|x\| \to \infty 时趋于无穷）、严格凸的、下半连续的且proper的，最优解 \hat{x} 是唯一的。这个显式公式提供了从标量对偶解到 N 维原解的直接转换，展示了对偶方法的强大之处。