优化理论导论

课程概述与优化的本质

这是CentraleSupelec大学ATSI硕士项目的优化课程，由Jean-Christophe Pesquet教授主讲。课程开篇引用了优化领域著名学者Yurii Nesterov的一段话："无论人们做什么，在某个时刻他们都会产生一种渴望，想要以最好的方式来组织事物。这种意图，当被转换成数学形式时，就变成了某种类型的优化问题。"

这段话揭示了优化问题的普遍性。从日常生活中选择最短路径，到企业决策中分配资源获得最大利润，再到机器学习中调整模型参数以最小化预测误差，这些都是优化问题。当我们把这些现实问题用数学语言精确描述出来，就形成了数学优化问题。

优化问题的数学形式

最小化问题

设有函数 f: D \mapsto [-\infty, +\infty]，其中 D \subset \mathbb{R}^N。这里 f 被称为成本函数。定义域 D 是 N 维欧氏空间的子集，代表所有可行解的集合。函数 f 的值域是扩展实数集，这意味着函数值可以取从负无穷到正无穷之间的任何实数值。

我们的目标是寻找 \hat{x} \in D 使得对于所有 x \in D，都有

这个条件的含义是：找到一个点 \hat{x}，它在可行域 D 内，并且在这个点上函数 f 的取值不大于 D 内任何其他点的函数值。换句话说，\hat{x} 是函数 f 在域 D 上的全局最小值点。

这个条件可以等价地表述为：寻找 \hat{x} \in D 使得

这里 \inf 表示下确界，即函数 f 在集合 D 上所有值的最大下界。使用下确界而不是最小值的原因是：有些情况下函数可能没有最小值（例如开区间上的递减函数），但下确界总是存在的。

最终，这个最小化问题可以简洁地表示为：寻找

这里 \text{Argmin} 是一个集合，包含了所有使函数 f 达到最小值的点。之所以是集合而不是单个点，是因为最小值点可能不唯一，例如常数函数的情况下，所有点都是最小值点。

最大化问题

在许多实际应用中，我们希望最大化某个目标，比如利润、效率或奖励。设 g 为奖励函数，我们的目标是寻找 \hat{x} \in D 使得对于所有 x \in D，都有

这里有一个关键的数学技巧：最大化问题可以转化为最小化问题。寻找使 g(\hat{x}) \geq g(x) 的点，等价于寻找使 -g(\hat{x}) \leq -g(x) 的点。这是因为不等号两边同时乘以 -1 会改变不等号的方向。因此，最大化 g(x) 等价于最小化 -g(x)。

数学上表示为

通过引入 f(x) = -g(x)，最大化问题就完全转化为了最小化问题。因此，我们可以不失一般性地只研究最小化问题，因为任何最大化问题都可以通过上述变换转化为最小化问题。这种统一处理方式大大简化了优化理论的研究和算法的设计。注意这里函数的值域是半开区间 ]-\infty, +\infty]，左端点开表示不包含 -\infty，右端点闭表示可以取到 +\infty。

优化问题的类型分类

优化问题根据可行域 D 的不同性质可以分为多种类型。每种类型都有其独特的数学性质和求解方法。

无约束优化问题

当 D = \mathbb{R}^N 时，我们称之为无约束优化问题。在这种情况下，决策变量 x 可以在整个 N 维实数空间中自由取值，没有任何限制条件。

无约束优化的特点是搜索空间是连续的、无限的，这意味着我们可以使用微分等连续数学工具来分析问题。在实际应用中，许多机器学习中的参数优化问题，如神经网络的权重优化，在不考虑正则化约束时就是典型的无约束优化问题。

无约束优化的优势在于理论相对成熟，有大量基于梯度的方法可以使用，如梯度下降法、牛顿法、拟牛顿法等。这些方法利用函数的局部信息（如梯度和海森矩阵）来寻找最优解。

离散优化问题

当 D 是可数集时，我们得到离散优化问题。可数集意味着集合中的元素可以与自然数建立一一对应关系，但集合本身可能是无限的。

与连续情况不同，离散优化中函数值只在离散的点上定义。这种问题的难点在于不能使用基于梯度的方法，因为离散点上不存在导数的概念。实际例子包括：选择最优的服务器数量（必须是整数）、网络中的路由选择问题（只能选择存在的路径）等。

离散优化通常比连续优化更难求解，因为搜索空间虽然是离散的，但可能仍然是无限的。求解方法包括动态规划、分支定界法等，这些方法通常需要利用问题的特殊结构。

组合优化问题

当 D 是有限集时，问题变成组合优化问题。这是离散优化的一个特殊情况，其中可行解的数量是有限的。

虽然可行解数量有限，但这并不意味着问题容易求解。事实上，许多组合优化问题是NP困难的，这意味着目前没有已知的多项式时间算法能够保证找到最优解。经典的组合优化问题包括：旅行商问题（从有限个城市排列中选择最短路径）、背包问题（从有限个物品中选择价值最大的组合）、图着色问题（用有限种颜色给图的节点着色）等。

理论上，由于可行解数量有限，我们总可以通过枚举所有可能来找到最优解，但当问题规模增大时，这种方法很快变得不可行。例如，n 个城市的旅行商问题有 (n-1)!/2 种可能的路径，当 n=20 时，这个数字就已经超过 10^{16}。

整数优化问题

当 D \subset \mathbb{Z}^N 时，即可行域是 N 维整数格点的子集，这构成了整数优化问题。

整数优化在实际应用中极其重要，因为许多决策本质上是离散的：生产多少件产品、雇佣多少员工、建设多少个设施等。这些量不能取分数值，必须是整数。

整数优化问题的一个重要特性是，即使目标函数和约束条件都是线性的（整数线性规划），问题仍然可能是NP困难的。这与连续的线性规划形成鲜明对比，后者可以在多项式时间内求解。混合整数规划（部分变量是整数，部分是连续的）在运筹学和工业优化中有广泛应用。

连续优化与约束优化问题

当 D 是不可数集时，我们面对的是连续优化问题。不可数集意味着集合中的元素无法与自然数建立一一对应关系，最典型的例子就是实数区间。

在实际应用中，我们很少遇到完全无约束的问题，通常决策变量需要满足某些条件。这里定义了带有 P 个等式约束和 Q 个不等式约束的优化问题，其可行域定义为

这个定义精确地描述了约束优化的本质。可行域 D 不再是整个 \mathbb{R}^N 空间，而是满足所有约束条件的点的集合。其中 \varphi_i: \mathbb{R}^N \to ]-\infty,+\infty] 是等式约束函数，每个等式约束要求 \varphi_i(x) = \delta_i，这里 \delta_i \in \mathbb{R} 是给定的常数。类似地，\psi_j: \mathbb{R}^N \to ]-\infty,+\infty] 是不等式约束函数，要求 \psi_j(x) \leq \eta_j，其中 \eta_j \in \mathbb{R} 是给定的上界。

线性约束

当约束函数具有特殊的结构时，问题会变得更容易处理。如果 \varphi_i 可以写成

的形式，其中 i \in \{1,\ldots,P\}，u_i \in \mathbb{R}^N，那么这就是线性（或仿射）等式约束。这里 \langle x \mid u_i \rangle 表示内积，在 \mathbb{R}^N 中就是 u_i^T x。线性约束的几何意义是约束定义了一个超平面。

同样，如果不等式约束 \psi_j 可以写成

的形式，其中 j \in \{1,\ldots,Q\}，v_j \in \mathbb{R}^N，那么这就是线性（或仿射）不等式约束。线性不等式约束定义的是一个半空间。

特别地，如果除了约束是线性的之外，目标函数 f 也是线性的，那么整个问题就变成了线性规划问题。线性规划是优化理论中最成功的分支之一，有多项式时间的求解算法（如内点法），在工业界有广泛应用。

约束与无约束问题的统一视角

通过巧妙地重新定义函数，我们可以将约束优化问题转化为形式上的无约束优化问题。具体方法是定义一个扩展值函数 \tilde{f}: \mathbb{R}^N \to ]-\infty,+\infty]

这个定义的巧妙之处在于：通过将可行域外的函数值设为 +\infty，我们实际上"惩罚"了不可行的点，使得任何合理的优化算法都不会选择这些点作为最优解。这样，寻找

就等价于寻找

这种处理方式允许我们用统一的数学框架来处理约束和无约束问题。在理论分析中，这种统一性非常有价值，因为我们可以将无约束优化的理论结果直接应用到约束问题上。同时，这也是许多现代优化算法（如近端梯度法、ADMM等）的理论基础。

更一般空间中的优化问题

优化理论不仅限于有限维欧氏空间 \mathbb{R}^N。在许多应用中，我们需要在更一般的空间中进行优化。这里介绍了在一般实向量空间 \mathcal{H} 中的优化问题：寻找

其中 f: \mathcal{H} \to ]-\infty,+\infty]，C \subset \mathcal{H}，且 \mathcal{H} 是一个实向量空间。

向量空间的概念比 \mathbb{R}^N 更一般，它包括了函数空间、矩阵空间等无限维或结构化的空间。这种推广在偏微分方程的最优控制、量子计算、机器学习的核方法等领域都很重要。

矩阵优化例子

设 \mathcal{H} = \mathbb{R}^{N \times N}，即 N \times N 实矩阵的空间。目标函数定义为

其中 Y \in \mathbb{R}^{N \times N} 是给定的矩阵。这个例子实际上与统计学和机器学习中协方差矩阵的最大似然估计密切相关。函数 -\ln \det X 是对数行列式的负值，它在 X 是对称正定矩阵时才有意义（因为只有正定矩阵的行列式才是正的，才能取对数）。\text{tr}(YX) 是矩阵 YX 的迹，即对角元素之和。

另一个变体是约束条件变成了 X \succ 0（表示 X 是正定的），目标函数为

其中 Y \in \mathbb{R}^{N \times N}。符号 X \succ 0 是矩阵论中的标准记号，表示 X 是正定矩阵（所有特征值都大于0）。

这些矩阵优化问题在许多领域都有应用：在统计学中用于估计协方差矩阵，在控制理论中用于设计最优控制器，在信号处理中用于传感器阵列设计，在金融中用于投资组合优化等。它们属于凸优化的范畴，有高效的求解算法。

函数空间中的优化

设 \mathcal{H} = W^{1,2}([\alpha,\beta])，其中 (\alpha,\beta) \in \mathbb{R}^2，\alpha < \beta。这个 W^{1,2}([\alpha,\beta]) 是索伯列夫空间，它的定义是

索伯列夫空间是泛函分析中极其重要的概念，它包含了所有平方可积且导数也平方可积的函数。这里 L^2([\alpha,\beta]) 表示区间 [\alpha,\beta] 上所有平方可积函数的空间，即满足

的函数 x。条件

要求函数的导数也必须平方可积，这保证了函数具有一定的光滑性——不能有太剧烈的振荡或跳变。

在这个空间中，定义约束集合

其中 (a,b) \in \mathbb{R}^2，y \in \mathcal{H}。这个约束要求函数在区间端点处取特定的值，这是典型的边界条件。目标函数定义为

这个目标函数有两部分。第一项

衡量函数 x 与目标函数 y 的接近程度，是数据拟合项。第二项

衡量函数 x 的光滑程度，导数越大表示函数变化越剧烈，这是正则化项。这种形式在信号处理、图像处理和逆问题求解中非常常见，它在拟合数据和保持解的光滑性之间寻求平衡。

这个问题实际上是变分法中的基本问题，其解满足欧拉-拉格朗日方程。在工程应用中，这类问题出现在最优控制、信号去噪、曲线拟合等领域。

著名的优化问题类别

二次规划

二次规划是优化理论中最重要的问题类别之一。设 A \in \mathbb{R}^{N \times N}，b \in \mathbb{R}^N，C \subset \mathbb{R}^N，我们要最小化

这里 \frac{1}{2}\langle x \mid Ax\rangle 是二次项，可以写成 \frac{1}{2}x^T A x，而 \langle b \mid x \rangle 是线性项，即 b^T x。系数 \frac{1}{2} 是为了简化梯度的表达式，因为当 A 对称时，有

二次规划的重要性在于它是线性规划的自然推广，同时又保持了良好的数学性质。当矩阵 A 是正定或半正定时，问题是凸的，有唯一解或凸解集。许多实际问题可以建模为二次规划，如投资组合优化（最小化风险同时满足收益约束）、支持向量机的训练、模型预测控制等。

通常约束集合 C 定义为

其中对每个 j \in \{1,\ldots,Q\}，v_j \in \mathbb{R}^N，\eta_j \in \mathbb{R}。这定义了 Q 个线性不等式约束，每个约束定义一个半空间，它们的交集形成一个凸多面体。

为了更紧凑地表示这些约束，引入矩阵记号。定义 V \in \mathbb{R}^{Q \times N} 为将所有 v_j^T 按行排列得到的矩阵

同时定义 c \in \mathbb{R}^Q 为所有上界的向量

这样约束集合可以简洁地写为

这里 Vx \leq c 表示向量不等式，即 (Vx)_j \leq c_j 对所有 j = 1,\ldots,Q 成立。这种矩阵形式不仅在理论分析中很有用，在实际算法实现中也是标准形式。

锥规划

锥规划是比二次规划更一般的优化问题类别。问题形式为

其中 f: \mathcal{H} \to ]-\infty,+\infty]，\mathcal{H} 是实向量空间，关键是 C 是 \mathcal{H} 的一个锥。

锥的数学定义是：对任意 x \in C 和任意 \alpha \in [0,+\infty[，都有 \alpha x \in C。直观地说，如果一个点在锥内，那么从原点出发经过这个点的射线都在锥内。锥结构在优化理论中很重要，因为它保证了某种齐次性，使得许多算法可以利用这种结构。

Lorentz锥

一个重要的例子是洛伦兹锥，也称为二阶锥或冰淇淋锥。在 \mathcal{H} = \mathbb{R}^{N+1} 中，洛伦兹锥定义为

这里将 (N+1) 维向量分成前 N 个分量 x 和最后一个分量 t。条件 \|x\| \leq t 要求前 N 个分量的欧氏范数不超过最后一个分量。几何上，这在三维空间中（N=2）形成一个圆锥，底面朝上，顶点在原点，这就是"冰淇淋锥"名称的由来。

洛伦兹锥在许多应用中出现：鲁棒优化（处理数据不确定性）、信号处理中的波束形成、金融中的风险管理等。二阶锥规划是指约束包含洛伦兹锥约束的优化问题，它比线性规划和二次规划更一般，但仍可以用内点法高效求解。

半正定锥

另一个极其重要的锥是半正定锥。设 \mathcal{H} = \mathbb{R}^{N \times N}，即 N \times N 实矩阵空间，C 是所有对称半正定矩阵的子集。

对称半正定矩阵 X 满足两个条件：

• X = X^T（对称性）
• 对所有 v \in \mathbb{R}^N，v^T X v \geq 0（半正定性）

这个集合确实构成一个锥，因为如果 X 是半正定的，那么对任意 \alpha \geq 0，\alpha X 也是半正定的。

半正定规划是约束包含半正定锥约束的优化问题。这类问题在许多领域都有应用：控制理论中的Lyapunov函数设计、组合优化问题的凸松弛、量子信息理论、机器学习中的核矩阵学习等。虽然半正定规划比线性规划复杂，但它仍然是凸优化问题，可以用内点法在多项式时间内求解到任意精度。

锥规划的层次结构是：线性规划 ⊂ 二阶锥规划 ⊂ 半正定规划，每一级都严格包含前一级，提供了更强的建模能力，但计算复杂度也相应增加。理解这个层次结构对于选择合适的建模框架非常重要。

半正定锥的另一种表示

在锥规划的半正定锥部分，这里给出了一个稍微不同的表示方式。当 \mathcal{H} = \mathbb{R}^{N \times N} 时，半正定锥可以表示为

符号 X \succeq 0 表示 X 是半正定矩阵。与之前的 X \succ 0（正定）相比，X \succeq 0 允许特征值为零，即矩阵可以是奇异的。这个记号的含义是：对所有非零向量 v \in \mathbb{R}^N，都有

等号成立当且仅当 v 在 X 的零空间中。半正定性是正定性的推广，在实际应用中更常见，因为许多问题自然导致半正定而非正定的矩阵。

二阶锥规划

二阶锥规划是锥规划的一个重要特例，它在线性规划和半正定规划之间提供了一个很好的折中——比线性规划更有表达力，同时比半正定规划更容易求解。SOCP的一般形式是

这里的参数需要逐一理解。对每个 j \in \{1,\ldots,Q\}，有矩阵 A_j \in \mathbb{R}^{M_j \times N}，向量 b_j \in \mathbb{R}^{M_j}，向量 c_j \in \mathbb{R}^N，标量 d_j \in \mathbb{R}，而 \mathcal{C}_{M_j} 是维数为 M_j + 1 的洛伦兹锥。目标函数 \langle e \mid x \rangle 是线性的，其中 e \in \mathbb{R}^N 是给定的系数向量。

每个约束的结构需要仔细理解。约束要求向量

属于洛伦兹锥 \mathcal{C}_{M_j}。回忆洛伦兹锥的定义，这意味着向量的前 M_j 个分量（即 A_j x + b_j）的欧氏范数必须不超过最后一个分量（即 \langle c_j \mid x \rangle + d_j），数学上写为

这种约束可以表达许多实际问题中的不确定性和鲁棒性要求。

SOCP的另一种等价形式更直观

这里直接使用范数不等式来表示二阶锥约束，参数含义与前面相同：A_j \in \mathbb{R}^{M_j \times N}，b_j \in \mathbb{R}^{M_j}，c_j \in \mathbb{R}^N，d_j \in \mathbb{R}，e \in \mathbb{R}^N。这种表示方式更容易理解约束的几何意义：每个约束定义了一个凸集，即所有使得仿射函数 A_j x + b_j 的范数不超过另一个仿射函数 \langle c_j \mid x \rangle + d_j 的点的集合。

二次约束二次规划的例子

二次约束二次规划是SOCP的一个重要特例

这里对每个 j \in \{0,\ldots,Q\}，\tilde{A}_j \in \mathbb{R}^{M_j \times N}，b_j \in \mathbb{R}^{M_j}，并且对每个 j \in \{1,\ldots,Q\}，d_j \in [0,+\infty[。注意目标函数是二次的（范数的平方），约束也是二次的。参数 d_j 必须非负，因为它表示范数的上界。

QCQP看起来是非凸的问题（因为涉及二次函数），但关键的洞察是它可以转化为SOCP。这个转化基于一个简单但重要的观察：最小化 \|\tilde{A}_0 x + b_0\|^2 等价于最小化 \|\tilde{A}_0 x + b_0\|。这是因为平方函数在非负数上是单调递增的，所以两个问题有相同的最优解。但是我们不能直接在SOCP中最小化范数，所以引入一个辅助变量。

具体的转化方法是引入辅助变量 x_0 \in \mathbb{R}，将QCQP重新表述为

这个转化的巧妙之处在于：我们不再直接最小化范数，而是最小化一个标量变量 x_0，同时约束原始目标函数的范数不超过 x_0。在最优解处，约束 \|\tilde{A}_0 x + b_0\| \leq x_0 必然取等号（否则可以减小 x_0 得到更好的目标值），所以这个问题与原始QCQP等价。

这个转化后的问题正是标准的SOCP形式：目标函数是线性的（最小化 x_0），所有约束都是二阶锥约束。这个例子展示了SOCP的强大建模能力——许多看似非凸的二次问题实际上可以转化为凸的SOCP问题。这种转化技巧在鲁棒优化、信号处理、机器学习等领域有广泛应用。

半正定规划

原始形式

半正定规划是锥规划中最一般和最强大的形式之一。SDP的原始形式为

这里需要理解几个关键的数学对象。首先，\mathcal{S}_N 表示所有 N \times N 对称矩阵的空间。对称性是重要的，因为只有对称矩阵才有实特征值，才能定义正定性。对于每个 i \in \{1,\ldots,P\}，A_i \in \mathcal{S}_N，b_i \in \mathbb{R}，这些构成线性等式约束。L \in \mathcal{S}_N 是目标函数中的系数矩阵。

目标函数 \text{tr}(LX) 是矩阵 LX 的迹，即对角元素之和。这实际上可以看作矩阵空间中的内积

因此目标函数对 X 是线性的。约束 \text{tr}(A_i X) = b_i 也是线性的，每个这样的约束定义了矩阵空间中的一个超平面。最关键的约束是 X \succeq 0，要求 X 必须是半正定的，这是一个凸约束，它定义了矩阵空间中的一个凸锥。

SDP松弛的例子

这里展示了如何将组合优化问题松弛为SDP。原始问题是

这里 x \in \{-1,1\}^N 表示 x 的每个分量只能取 +1 或 -1，这是一个离散的组合优化问题。注意到 X = xx^T 具有两个性质：第一，X \succeq 0（因为对任意向量 v，有 v^T X v = v^T x x^T v = (x^T v)^2 \geq 0）。第二，\text{diag}(X) = 1_N，即 X 的对角元素都是1（因为 X_{ii} = x_i^2 = 1 当 x_i \in \{-1,1\}）。此外，X 是秩1矩阵（因为它是向量的外积）。

这个组合问题通常很难直接求解，因为可行域是离散的。SDP松弛的核心思想是放松秩1约束，只保留半正定约束和对角约束

这个松弛去掉了 X = xx^T 的秩1要求，允许 X 是任意满足对角元素为1的半正定矩阵。这样问题从离散优化变成了连续的凸优化，可以用多项式时间算法求解。虽然松弛后的解可能不再对应原问题的可行解（因为 X 可能不是秩1的），但它提供了原问题最优值的下界。

对偶形式

SDP的对偶问题揭示了原始问题的另一个视角。对偶形式为

这里对偶变量 y \in \mathbb{R}^P 对应原始问题中的 P 个等式约束。参数包括：对每个 i \in \{1,\ldots,P\}，A_i \in \mathcal{S}_N（与原始问题相同），b \in \mathbb{R}^P 是原始问题约束右端项组成的向量，L \in \mathcal{S}_N 是原始问题的目标函数系数矩阵。

对偶问题的约束

要求矩阵 L - \sum_{i=1}^P y_i A_i 必须是半正定的。这个约束的几何意义是：我们在寻找对偶变量 y，使得 L 可以表示为 A_i 的线性组合加上一个半正定的"余量"。对偶理论告诉我们，在某些条件下（如Slater条件），原始问题和对偶问题的最优值相等，这就是强对偶性。

对偶形式的例子

这里展示了如何将一个具体问题转化为SDP对偶形式。原问题是

这里 \lambda_{\max} 表示矩阵的最大特征值。最小化最大特征值是一个常见的优化目标，在控制理论、鲁棒优化等领域经常出现。

引入辅助变量 v = \lambda_{\max}\left(\sum_{i=1}^P y_i A_i - L\right)，问题可以重写为最小化 v，但需要确保 v 确实是最大特征值的上界。矩阵的最大特征值不超过 v 等价于

其中 I 是单位矩阵。这是因为如果 \lambda 是矩阵 M 的特征值，那么 \lambda \leq v 对所有特征值成立等价于 vI - M \succeq 0。

重新整理不等式，得到

这可以进一步写成

通过设置 A_0 = -I_N（负的单位矩阵），最终得到标准的SDP对偶形式

注意这里求和从 i=0 开始，包含了 y_0 A_0 = -y_0 I_N 项。这个转化展示了如何将涉及特征值的优化问题转化为标准的SDP形式。

SDP的强大之处在于它能够处理涉及矩阵特征值、矩阵范数、矩阵不等式的复杂优化问题，同时保持凸性，使得问题可以高效求解。虽然SDP的计算复杂度比线性规划高，但对于中等规模的问题（矩阵维数几百到几千），现代的内点法求解器已经相当高效。

优化理论中需要解决的主要问题

四个核心问题

优化理论不仅关注问题的建模，更重要的是理解和解决与优化问题相关的四个核心理论和实践问题。

解的存在性与唯一性

第一个基本问题是：对于给定的优化问题，解 \hat{x} 是否存在？如果存在，是否唯一？这看似简单的问题实际上是优化理论的基石。解的存在性告诉我们问题是否有意义——如果一个优化问题没有解，那么任何算法都无法找到它。解的唯一性则决定了我们能期望什么样的结果——如果有多个最优解，算法可能收敛到其中任何一个。

在数学上，解的存在性通常通过Weierstrass定理来保证：如果目标函数在紧集上连续，则最小值一定存在。但在实际问题中，可行域可能不是紧的，或者函数可能不连续，这时需要更细致的分析。

解的刻画

第二个问题是刻画解的特征：寻找 \hat{x} 成为解的必要条件和充分条件。必要条件帮助我们缩小搜索范围——任何不满足必要条件的点都不可能是最优解。充分条件则让我们能够验证一个候选点确实是最优解。

最著名的必要条件是一阶条件（KKT条件），它说明在最优点处梯度必须满足某些条件。充分条件通常涉及二阶信息（如海森矩阵的正定性）或凸性假设。理解这些条件对于设计和分析优化算法至关重要。

算法设计

第三个问题是算法设计：在大多数实际问题中，不存在闭式解，即我们无法写出 \hat{x} = 某个明确的公式。因此需要设计迭代算法来逼近解，构建一个序列 (x_n)_{n \in \mathbb{N}}，使得

这个序列应该从某个初始点开始，通过迭代规则逐步接近最优解。算法设计的关键是确保收敛性（序列确实收敛到最优解）和实用性（每次迭代的计算是可行的）。

算法性能评估

第四个问题涉及算法的性能评估，主要包括三个方面。

收敛速度：算法收敛到最优解的快慢程度。例如，如果存在 \rho \in ]0,1[ 和 n^* \in \mathbb{N} 使得对所有 n \geq n^*，有

则称算法具有Q-线性收敛速率。这意味着误差以几何级数的速度减小，每次迭代都将误差缩小一个固定的比例 \rho。

更快的收敛速率是Q-超线性收敛

这意味着收敛速度越来越快，误差的缩小比例趋向于零。牛顿法在适当条件下就具有超线性甚至二次收敛速率。

鲁棒性：算法对数值误差的敏感程度。在实际计算中，舍入误差不可避免，一个好的算法应该对这些误差不敏感，即小的计算误差不会导致结果的大幅偏离。

可并行/分布式实现性：在大规模问题中，算法是否适合并行或分布式计算变得越来越重要。某些算法（如梯度下降的变体）天然适合并行化，而另一些（如标准牛顿法）则较难并行化。

分配问题

分配问题是优化理论在工程中的典型应用。以多描述编码为例，这是信息论和通信工程中的重要问题。

问题设定：有 N \in \mathbb{N}^* 个源编码器，每个编码器 i \in \{1,\ldots,N\} 使用的比特数为 x_i \in \mathbb{R}。虽然比特数在实际中是整数，但为了使用连续优化方法，这里放松为实数。每个编码器传输信息时的失真函数为 f_i: \mathbb{R} \to ]-\infty,+\infty]，即 x_i \mapsto f_i(x_i)，表示使用 x_i 比特时产生的失真。

优化目标是最小化总体失真

这个问题需要满足两类约束。

非负性约束：x \in [0,+\infty[^N，即每个编码器使用的比特数必须非负。这是物理约束，负的比特数没有意义。

比特率限制：\sum_{i=1}^N x_i \leq x_{\max}，总比特率不能超过信道容量 x_{\max}。这是资源约束，反映了通信信道的带宽限制。

这个问题的本质是在有限的通信资源下，如何在多个编码器之间分配比特，使得总的信息失真最小。

近似问题：神经网络

神经网络是现代机器学习的核心，其训练本质上是一个优化问题。

数学模型

前馈网络可以表示为函数组合

其中 J 是网络的层数。对每一层 j \in \{1,\ldots,J\}：

• R_j: \mathbb{R}^{N_j} \to \mathbb{R}^{N_j} 是激活算子，通常是逐元素应用的非线性函数，如sigmoid或tanh
• N_j 是第 j 层的神经元数量
• A_j = W_j \cdot +b_j 是仿射变换
• W_j \in \mathbb{R}^{N_j \times N_{j-1}} 是权重矩阵，连接第 j-1 层到第 j 层
• b_j \in \mathbb{R}^{N_j} 是偏置向量

所有参数组成参数向量

其中

是参数总数。

成本函数

训练神经网络的目标是最小化成本函数

这里：

• K 是训练序列的长度
• 对每个 k \in \{1,\ldots,K\}，s^{(k)} \in \mathbb{R}^{N_J} 是对输入 e^{(k)} \in \mathbb{R}^{N_0} 的期望响应
• \|\cdot\|_p 是 p-范数，常用 p=2（均方误差）

这揭示了深度学习的一个核心挑战：参数数量巨大（现代网络可能有数十亿参数），需要大量数据才能可靠地估计这些参数，避免过拟合。

估计问题：老旧音乐录音的修复

这是信号处理中的典型反问题。问题的背景是修复老旧或损坏的音乐录音。

退化模型

观测到的退化信号可以建模为

其中：

• y = (y_i)_{0 \leq i \leq N-1} \in \mathbb{R}^N 是退化信号（我们观测到的）
• \bar{x} = (\bar{x}_i)_{0 \leq i \leq N-1} \in \mathbb{R}^N 是原始信号（我们要恢复的）
• H \in \mathbb{R}^{N \times N} 是建模退化过程的矩阵，通常是病态的
• b \in \mathbb{R}^N 是随机扰动的实现（噪声）

矩阵 H 可能表示各种退化效应：模糊、采样、卷积等。病态性意味着 H 的逆（如果存在）对噪声非常敏感，直接求逆会放大噪声。

优化方法

通过最小化以下目标函数来确定修复信号 \hat{x}

这里 \|\cdot\| 通常是欧氏范数。但仅仅最小化这个目标函数是不够的，因为问题可能病态或欠定。因此需要加入约束来编码关于原始信号的先验信息。

约束条件

值域约束：x \in [\alpha, \beta]^N，其中 (\alpha, \beta) \in \mathbb{R}^2，\alpha \leq \beta。这反映了信号的物理限制，如音频信号的幅度范围。

均值约束：\frac{1}{N}\sum_{i=1}^N x_i = \mu，其中 \mu \in \mathbb{R}。如果知道原始信号的平均值（如直流分量），这个约束可以帮助稳定解。

有界变差约束：(\forall i \in \{0,\ldots,N-2\}) \quad |x_{i+1} - x_i| \leq M，其中 M \in ]0,+\infty[。这个约束限制了信号的变化率，促进解的平滑性，防止出现不自然的振荡。

这些约束将原本病态的问题正则化，使得解既能拟合观测数据，又符合我们对原始信号特性的认识。

课程大纲

课程给出了整个优化理论课程的大纲：

1. 引言 — 优化问题的基本概念和分类
2. 凸性与共轭 — 凸优化的理论基础
3. 最小值点的刻画 — 最优性条件
4. 对偶性 — 原始-对偶理论
5. 拉格朗日乘数法 — 处理约束优化的经典方法
6. 近端方法 — 现代优化算法
7. 内点法 — 求解大规模优化问题的高效方法
8. 随机方法 — 处理大数据和在线学习的方法

这个大纲展示了从理论基础到实际算法的完整学习路径，涵盖了优化理论的核心内容。

优化理论基础：希尔伯特空间

预希尔伯特空间的定义

预希尔伯特空间 \mathcal{H} 是一个配备了内积的实向量空间。内积是一个函数

它满足四个基本性质。

对称性：对任意 (x,y) \in \mathcal{H}^2，有

这个性质保证了两个向量的内积不依赖于顺序。在几何上，这意味着"x 在 y 方向上的投影"与"y 在 x 方向上的投影"有相同的数值关系。

可加性：对任意 (x,y,z) \in \mathcal{H}^3，有

这个性质说明内积对第一个分量是可加的。结合对称性，内积对两个分量都是可加的。

齐次性：对任意 (x,y) \in \mathcal{H}^2 和任意 \alpha \in \mathbb{R}，有

这个性质说明标量可以从内积中提取出来。可加性和齐次性结合起来，意味着内积在第一个分量上是线性的。结合对称性，内积在两个分量上都是线性的，我们称之为双线性。

正定性：对任意 x \in \mathcal{H}，有

且等号成立当且仅当 x = 0。这个性质赋予了空间几何结构，它允许我们定义长度的概念。\langle x | x \rangle 可以理解为向量 x 的"长度的平方"。正定性确保了只有零向量的长度为零。

这四个性质不是随意选择的。它们确保了内积能够推广欧几里得空间中的点积概念，同时保持了所有我们熟悉的几何性质。

由内积诱导的范数

有了内积，我们可以定义范数。对任意 x \in \mathcal{H}，定义

这个范数满足所有范数的公理。第一，非负性：\|x\| \geq 0 且 \|x\| = 0 当且仅当 x = 0，这直接来自内积的正定性。第二，齐次性：\|\alpha x\| = |\alpha| \|x\|，这可以从内积的齐次性推导。第三，三角不等式：\|x + y\| \leq \|x\| + \|y\|，这需要Cauchy-Schwarz不等式来证明。

这种由内积诱导的范数使得预希尔伯特空间成为赋范空间，进而成为度量空间（通过 d(x,y) = \|x - y\| 定义距离）。这样我们就可以讨论收敛性、连续性等拓扑概念。

平行四边形恒等式

对任意 (x,y) \in \mathcal{H}^2，有

这个恒等式的几何意义深刻：在平行四边形中，两条对角线长度的平方和等于四条边长度平方和。这个性质是由内积诱导的范数所特有的。实际上，Jordan-von Neumann定理说明：如果一个范数满足平行四边形恒等式，那么必定存在一个内积诱导出这个范数。

我们来看证明过程，它展示了内积的双线性如何导出这个结果。首先展开 \|x + y\|^2

利用内积的双线性性

由于对称性，\langle x | y \rangle = \langle y | x \rangle，所以

类似地展开 \|x - y\|^2

现在将两式相加，关键是交叉项 2\langle x | y \rangle 和 -2\langle x | y \rangle 相互抵消

这个恒等式在优化理论中很有用。它告诉我们向量和与向量差的范数之间的关系，这在分析算法的收敛性时经常出现。

中线恒等式

设 (a, b, c) \in \mathcal{H}^3，m 是线段 [b, c] 的中点，即

则有

这个恒等式描述了三角形中的一个重要几何关系：从顶点 a 到两个底角 b 和 c 的距离平方和，等于从 a 到底边中点 m 距离平方的两倍加上底边长度平方的一半。

证明的关键是利用向量分解。将 (a-b) 和 (a-c) 都表示为通过中点 m 的形式

展开右边的第一项

类似地展开第二项

现在注意到 m 是 b 和 c 的中点，所以

因此

将两个展开式相加，交叉项变为

所以

由于 \|m - b\| = \|m - c\| = \frac{1}{2}\|b - c\|，我们有

因此得到中线恒等式。这个恒等式在优化理论中很有用，特别是在分析算法的收敛性时，它可以帮助我们理解点与集合之间的距离关系。

Cauchy-Schwarz不等式

对任意 (x,y) \in \mathcal{H}^2，有

等号成立当且仅当 x = \alpha y（对某个 \alpha \in \mathbb{R}）或 y = 0。

Cauchy-Schwarz不等式是分析中最重要的不等式之一。它的几何意义是：两个向量的内积的绝对值不超过它们长度的乘积。在欧几里得空间中，如果我们将内积表示为 \langle x | y \rangle = \|x\| \|y\| \cos\theta，其中 \theta 是两向量的夹角，那么不等式就等价于 |\cos\theta| \leq 1。

这个不等式是证明三角不等式的关键。有了Cauchy-Schwarz不等式，我们可以证明

开平方就得到三角不等式。Cauchy-Schwarz不等式也是许多优化算法收敛性分析的基础工具。

内积的连续性

内积作为从 \mathcal{H}^2 到 \mathbb{R} 的函数是连续的。这意味着如果 (x_n, y_n) \to (x, y)，则

证明利用了内积的双线性和Cauchy-Schwarz不等式。设 x_n = x + \epsilon_x，y_n = y + \epsilon_y，其中 \epsilon_x, \epsilon_y 是小的扰动。那么

应用Cauchy-Schwarz不等式到每一项

当 \epsilon_x, \epsilon_y \to 0 时，右边的每一项都趋于零，因此整个差也趋于零。这证明了连续性。

内积的连续性在优化理论中至关重要。它保证了目标函数和约束函数的连续性，这是许多优化算法能够工作的前提。在无限维空间中，连续性更是确保优化问题良定性的关键条件。

希尔伯特空间的定义

一个实希尔伯特空间 \mathcal{H} 是一个完备的预希尔伯特空间。这里的"完备"意味着空间中的每个柯西序列都收敛到空间内的某个点。

什么是柯西序列？序列 (x_n) 是柯西序列，如果对任意 \epsilon > 0，存在 N 使得对所有 m, n > N，有 \|x_m - x_n\| < \epsilon。直观地说，柯西序列的点越来越接近彼此。

完备性的重要性不能被低估。在优化算法中，我们通常构造一个迭代序列来逼近最优解。如果空间不完备，这个序列可能是柯西序列（序列中的点越来越接近），但却不收敛到空间内的任何点——这意味着我们追求的"最优解"实际上不在我们的搜索空间内。完备性保证了极限过程的封闭性：如果序列在某种意义上"应该"收敛，那么它的极限确实存在于空间中。

特殊情况是 \mathcal{H} = \mathbb{R}^N，即 N 维欧几里得空间。这是最熟悉的希尔伯特空间例子。在 \mathbb{R}^N 中，内积就是标准的点积

诱导的范数是欧几里得范数

所有有限维赋范空间都是完备的，这是拓扑学中的一个重要定理。课程强调："In the following, we will only consider finite-dimension Hilbert spaces"。这个限制简化了许多技术细节，因为在有限维空间中：所有范数都等价、所有线性算子都连续、紧集等价于有界闭集等。这些性质使得有限维优化问题的分析相对简单。

线性算子及其范数

设 \mathcal{H} 和 \mathcal{G} 是两个有限维希尔伯特空间，L: \mathcal{H} \to \mathcal{G} 是线性算子。线性算子的范数定义经历了一个逐步精化的过程，每个定义都揭示了范数的不同方面。

第一个定义

这个定义说：算子 L 的范数是它能将单位球内的向量放大的最大倍数。几何上，我们考虑 \mathcal{H} 中的单位球，通过 L 映射后，它变成 \mathcal{G} 中的一个椭球（在有限维情况下），算子范数就是这个椭球的最大半径。

第二个定义

这个定义将搜索范围从单位球缩小到单位球面。为什么这两个定义等价？关键观察是线性算子的齐次性。对任意 x \neq 0，有

而 x/\|x\| 是单位向量。因此

这表明 L 在单位球内达到的最大值必定在单位球面上达到。

第三个定义

这个定义去掉了对 x 范数的限制，转而考虑所有非零向量的放大比例。这个形式最直观：算子范数是 L 能够放大向量的最大比例。通过令 y = x/\|x\|，我们可以看到这个定义与前两个等价，因为

而 y 是单位向量。这个形式在理论分析中很有用，因为它不需要预先规范化向量。

在有限维情况下，如果用矩阵表示 L，这个范数就是矩阵的谱范数（最大奇异值）。

线性算子的连续性与有界性

在有限维希尔伯特空间中，一个基本定理是：线性算子从 \mathcal{H} 到 \mathcal{G} 是连续的。这个结果在无限维空间中不成立，这是有限维分析相对简单的另一个体现。

连续性意味着如果 x_n \to x 在 \mathcal{H} 中，则 Lx_n \to Lx 在 \mathcal{G} 中。在优化中，这保证了目标函数和约束函数的连续性，使得我们可以使用极限、导数等分析工具。

对于线性算子 f: \mathcal{H} \to \mathcal{G}，以下条件等价：f 是连续的当且仅当 f 是有界的。算子 f 有界意味着存在常数 M 使得对所有 x 和 \epsilon

如果 f 不是有界的，我们可以构造一个反例来证明它不连续。假设 f 不是有界的，那么存在序列 M_n \in \mathbb{R} 使得 M_n \to \infty，并且存在序列 x_n \in \mathcal{H} 使得对所有 n

现在定义

则 \|y_n\| = 1/M_n \to 0。但是

这说明 y_n \to 0 但 f(y_n) 不趋于 f(0) = 0，因此 f 在零点不连续。

这个等价性将拓扑性质（连续性）与代数性质（有界性）联系起来，在优化理论中很重要。

线性算子的巴拿赫空间

\mathcal{B}(\mathcal{H}, \mathcal{G}) 表示从 \mathcal{H} 到 \mathcal{G} 的所有线性算子构成的巴拿赫空间。巴拿赫空间是完备的赋范向量空间，这里的范数就是算子范数。

这个空间本身的结构很丰富。它是一个向量空间（算子可以相加和数乘）。配备了算子范数，使其成为赋范空间。在有限维情况下，它是完备的，因此是巴拿赫空间。当 \mathcal{H} = \mathbb{R}^n，\mathcal{G} = \mathbb{R}^m 时，\mathcal{B}(\mathcal{H}, \mathcal{G}) 同构于 \mathbb{R}^{m \times n}（m \times n 矩阵空间）。

在优化理论中，我们经常需要优化算子本身（如在算子学习、系统辨识等问题中）。理解算子空间的结构对于设计和分析这类算法至关重要。算子范数提供了算子之间的距离度量，使得我们可以讨论算子序列的收敛性，这在迭代算法的分析中是基本工具。

伴随算子的定义

设 \mathcal{H} 和 \mathcal{G} 是两个希尔伯特空间，L \in \mathcal{B}(\mathcal{H}, \mathcal{G})。算子 L 的伴随 L^* 是定义在 \mathcal{B}(\mathcal{G}, \mathcal{H}) 中的算子，满足

这个定义初看可能显得抽象，但它有深刻的几何和代数意义。等式左边，内积 \langle y | Lx \rangle_{\mathcal{G}} 是在 \mathcal{G} 空间中 y 和 Lx 的内积。等式右边，\langle L^* y | x \rangle_{\mathcal{H}} 是在 \mathcal{H} 空间中 L^*y 和 x 的内积。伴随算子 L^* 的作用是"反向"传递信息：它将 \mathcal{G} 中的向量映射回 \mathcal{H}，使得这个等式成立。

伴随算子的存在性是Riesz表示定理的结果。对于固定的 y \in \mathcal{G}，映射 x \mapsto \langle y | Lx \rangle 是 \mathcal{H} 上的连续线性泛函。根据Riesz表示定理，存在唯一的元素（我们记为 L^*y）使得这个泛函可以表示为内积。

当上下文清楚时，我们可以省略内积的空间标记，简化为

利用实希尔伯特空间中内积的对称性，可以进一步写成

伴随算子的例子

考虑一个特殊的线性算子 L: \mathcal{H} \to \mathcal{H}^n，定义为

即将一个元素复制 n 次。它的伴随 L^*: \mathcal{H}^n \to \mathcal{H} 将向量 y = (y_1, \ldots, y_n) 映射到

证明过程展示了如何使用伴随的定义。对任意 x \in \mathcal{H} 和 y = (y_1, \ldots, y_n) \in \mathcal{H}^n

在乘积空间中，内积定义为各分量内积之和

利用内积的线性性

根据伴随的定义，这表明

这个例子说明伴随算子常常具有"逆向"的作用：如果 L 是"复制"操作，那么 L^* 是"求和"操作。

伴随算子的性质

范数的保持

一个重要的性质是

这意味着算子和它的伴随具有相同的范数。

证明利用了伴随的定义和Cauchy-Schwarz不等式。对任意 y \neq 0

利用伴随的定义

应用Cauchy-Schwarz不等式

利用算子范数的性质

对所有 y \neq 0 取上确界得到

两边平方

如果 \|L^*\| \neq 0，两边除以 \|L^*\| 得到 \|L^*\| \leq \|L\|。通过对称的论证（考虑 (L^*)^* = L），我们也能得到 \|L\| \leq \|L^*\|，因此 \|L^*\| = \|L\|。

同构的伴随

如果 L 是双射的（即同构），那么 L^{-1} \in \mathcal{B}(\mathcal{G}, \mathcal{H})，并且

这个性质的证明基于伴随定义的唯一性。对任意 y, y' \in \mathcal{H}

利用伴随的定义

再次利用伴随的定义

这表明 (L^{-1})^* L^* = \text{Id}。定义 K = (L^{-1})^* L^* - \text{Id}，则对所有 y, y'，有 \langle Ky | y' \rangle = 0。取 y' = Ky，得到

因此 Ky = 0 对所有 y 成立，即 K = 0，所以 (L^{-1})^* L^* = \text{Id}。类似地可以证明 L^* (L^{-1})^* = \text{Id}，从而

有限维空间的特殊情况

当 \mathcal{H} = \mathbb{R}^N 和 \mathcal{G} = \mathbb{R}^M 时，线性算子 L 可以用 M \times N 矩阵表示。在这种情况下

即伴随就是矩阵的转置。这可以通过直接计算验证

这里使用了矩阵乘法的结合律和转置的性质 (AB)^T = B^T A^T。这个结果将抽象的伴随算子概念与我们熟悉的矩阵转置联系起来。

伴随算子在优化理论中扮演着关键角色。在许多优化问题中，目标函数的梯度可以用算子的伴随来表示。例如，最小二乘问题

的梯度是 2A^*(Ax - b)。许多优化问题导致形式为 A^*Ax = A^*b 的正规方程，其解就是最小二乘问题的解。在凸优化的对偶理论中，原始变量和对偶变量通过伴随算子相关联。当 L = L^* 时，算子称为自伴随的，这类算子在优化中特别重要，因为它们对应于二次型的海森矩阵，其特征值都是实数。

泛函分析基础

函数的定义域与适当性

设 S 是希尔伯特空间 \mathcal{H} 的一个非空子集。希尔伯特空间是一个完备的内积空间，它为我们提供了几何直觉和分析工具的完美结合。定义函数

注意这里函数的值域扩展到了扩展实数系，包含了正负无穷。这种扩展在凸分析和优化理论中至关重要。

函数 f 的定义域被定义为

这个定义域的概念与实分析中的略有不同——它只包含那些函数值有限的点。为什么要这样定义？因为在优化理论中，我们经常使用取值为 +\infty 的函数来表示约束条件。那些取值为无穷的点实际上是"禁止"的区域，通过这种方式，我们可以用一个扩展值函数来统一表示目标函数和约束条件。

函数 f 被称为适当函数，当且仅当满足两个条件。第一，对所有 x \in S，都有 f(x) \neq -\infty，这保证了函数不会在任何点取到负无穷。第二，\text{dom} f \neq \emptyset，即至少存在一个点使得函数值有限。这两个条件共同确保了函数在分析意义上是"良好"的——既不会处处为无穷（这样优化问题就没有意义），也不会出现负无穷这种病态情况（负无穷会导致下确界不存在）。

具体例子帮助理解。第一个例子是定义在整个实数轴 \mathbb{R} 上的抛物线函数，它的定义域是整个 \mathbb{R}，这是一个适当函数。第二个例子是一个函数只在区间 [0, \delta] 上取有限值，在这个区间外取值为 +\infty，因此它的定义域是 [0, \delta]，这也是一个适当函数。这两个例子说明，即使函数在某些区域取无穷值，只要存在取有限值的区域，它仍然可以是适当的。

指示函数

指示函数是凸分析中极其重要的概念。设 C \subset \mathcal{H} 是希尔伯特空间的一个子集，C 的指示函数 \iota_C 定义为

这个定义看似简单，但蕴含深刻的数学思想。指示函数将集合的成员关系问题转化为了函数优化问题。如果要最小化包含指示函数的目标函数，优化过程自然会将解限制在集合 C 内，因为在 C 外函数值为无穷大。这是将约束优化问题转化为无约束优化问题的关键技巧。

具体来说，考虑约束优化问题

这可以等价地写成无约束形式

因为当 x \notin C 时，\iota_C(x) = +\infty 使得目标函数为无穷，自然排除了这些点。

例子是 C = [\delta_1, \delta_2]，即一个闭区间。函数 f(x) = \iota_{[\delta_1, \delta_2]}(x) 在区间 [\delta_1, \delta_2] 内取值为0，在区间外取值为 +\infty。这个例子直观地展示了指示函数如何"标记"出可行域。

希尔伯特空间中的收敛性

在有限维希尔伯特空间 \mathcal{H} 中，设 (x_n)_{n \in \mathbb{N}} 是一个序列，\hat{x} \in \mathcal{H} 是空间中的一个点。序列 (x_n)_{n \in \mathbb{N}} 收敛到 \hat{x} 的定义是

这里 \|\cdot\| 是由内积诱导的范数。这个定义将抽象的收敛概念具体化为距离趋于零的过程。记号 x_n \to \hat{x} 表示这种收敛关系。

为什么要在希尔伯特空间框架下讨论收敛？因为希尔伯特空间的完备性保证了柯西序列必定收敛。柯西序列是指序列中的点越来越接近彼此：对任意 \epsilon > 0，存在 N 使得对所有 m, n > N，有 \|x_m - x_n\| < \epsilon。完备性保证了这样的序列一定收敛到空间内的某个点，而不会"逃逸"到空间外。这为后续的分析提供了坚实基础。

子集的拓扑性质

设 S 是希尔伯特空间 \mathcal{H} 的一个子集。我们需要理解三个关键的拓扑概念。

有界性：S 是有界的，如果它能被包含在某个球内。数学上，存在 M > 0 和 x_0 \in \mathcal{H} 使得对所有 x \in S，有 \|x - x_0\| \leq M。有界性是防止序列"逃逸到无穷远"的重要性质。在优化中，有界性通常与目标函数的强制性（coercivity）相关。

闭性：S 是闭的，如果 S 中元素的每个收敛序列的极限都仍然属于 S。换句话说，如果 (x_n) \subset S 且 x_n \to x，那么 x \in S。闭集"包含了自己的所有极限点"。这个性质确保了在 S 上进行极限运算不会"跑出" S 的范围。在优化理论中，闭性保证了最优解的存在性：如果一个最小化序列收敛，其极限确实在可行域内。

紧性：S 是紧的，如果从 S 的任意序列 (x_n)_{n \in \mathbb{N}} 中，都能提取出一个收敛到 S 中某点的子序列 (x_{n_k})_{k \in \mathbb{N}}。紧性是有限维空间中最强的拓扑性质之一，它结合了有界性和闭性的优点。

有一个重要定理：当 \mathcal{H} 是有限维时，S 紧当且仅当 S 既是闭的又是有界的。这就是著名的Heine-Borel定理在有限维空间中的表述。为什么这个等价关系如此重要？因为在有限维空间中，验证紧性只需要检查闭性和有界性这两个相对简单的条件。但要注意，这个等价关系在无限维空间中不再成立，这是有限维和无限维分析的一个关键区别。

紧性在优化中有重要应用。Weierstrass定理说：连续函数在紧集上必能达到最小值。因此，如果可行域是紧的，目标函数是连续的，那么优化问题必有解。

上下极限

设 (\xi_n)_{n \in \mathbb{N}} 是扩展实数 [-\infty, +\infty] 中的一个序列。

下极限定义为

这个定义需要仔细理解。对每个 n，我们先找出从第 n 项开始的所有项的下确界 \inf\{\xi_k \mid k \geq n\}，这形成一个新序列。随着 n 增大，考虑的项越来越少，因此这个下确界序列是单调递增的（因为集合越来越小，下确界不会减小），所以极限一定存在（可能是 +\infty）。

上极限定义为

类似地，这是从第 n 项开始的所有项的上确界形成的序列的极限，这个序列是单调递减的。

有三个重要性质。

对称性关系：

这个关系揭示了上下极限之间的对偶性，通过取负可以将上极限问题转化为下极限问题。

大小关系：

这是因为对任意 n，都有 \inf\{\xi_k \mid k \geq n\} \leq \sup\{\xi_k \mid k \geq n\}，取极限后不等式仍然成立。

收敛的充要条件：

当且仅当

这个等价关系告诉我们，序列收敛等价于其振荡幅度趋于零，即上下极限重合。

上下极限与收敛的等价性证明

这个定理给出了序列极限存在的另一种刻画方式：\lim_{n \to \infty} \xi_n = \bar{\xi} 当且仅当 \liminf_{n \to \infty} \xi_n = \limsup_{n \to \infty} \xi_n = \bar{\xi}。

证明基于两个关键的等价刻画。

对于上极限，\limsup_{n \to \infty} \xi_n = \bar{\xi} 等价于：对任意 \epsilon > 0，存在 N_1 使得当 n \geq N_1 时，\xi_n \leq \bar{\xi} + \epsilon。这个条件说明了序列最终会被限制在 \bar{\xi} + \epsilon 以下，这正是上极限的几何含义——序列振荡的上界。

对于下极限，\liminf_{n \to \infty} \xi_n = \bar{\xi} 等价于：对任意 \epsilon > 0，存在 N_2 使得当 n \geq N_2 时，\xi_n \geq \bar{\xi} - \epsilon。这表明序列最终会保持在 \bar{\xi} - \epsilon 以上。

将这两个条件结合起来。当上下极限都等于 \bar{\xi} 时，选取 N = \max\{N_1, N_2\}，那么对所有 n \geq N，我们有

即

这正是序列收敛到 \bar{\xi} 的定义，即 \lim_{n \to \infty} \xi_n = \bar{\xi}。反向的证明是显然的：如果序列收敛，那么它的振荡幅度趋于零，上下极限必然相等。

上下极限的概念在分析学中极其重要。它们总是存在（在扩展实数意义下），即使原序列不收敛。它们刻画了序列的"最终行为"——下极限是序列最终能够多次接近的最小值，上极限是最大值。

上图的概念

对于函数 f: \mathcal{H} \to [-\infty, +\infty]，它的上图定义为

这个定义需要仔细理解。上图是希尔伯特空间与实数轴的笛卡尔积中的一个子集，它包含了所有位于函数图像上方（包括图像本身）的点。为什么这个概念如此重要？因为它建立了函数性质与集合几何性质之间的桥梁——我们可以通过研究上图这个集合的几何性质来理解函数的分析性质。

第一个例子是绝对值函数 f(x) = |x|，它的上图是一个V形区域的上方部分。这个区域是凸的，反映了绝对值函数的凸性。我们可以直接看到：如果 (x_1, \zeta_1) 和 (x_2, \zeta_2) 在上图中，那么它们的凸组合也在上图中，因为

第二个例子是指示函数 f(x) = \iota_{[-\delta, \delta]}(x) 的上图。它在区间 [-\delta, \delta] 上方形成一个"半带状"区域（因为在区间内函数值为0，所以上图包含所有 (x, \zeta) 其中 x \in [-\delta, \delta] 且 \zeta \geq 0）。在区间外由于函数值为无穷大，上图不包含这些区域的点。

下半连续性

函数 f: \mathcal{H} \to [-\infty, +\infty] 在点 x \in \mathcal{H} 处是下半连续的，如果对 \mathcal{H} 中的每个收敛到 x 的序列 (x_n)_{n \in \mathbb{N}}，都有

这个定义的直观理解是：当我们从任何方向接近点 x 时，函数值的下极限不会低于 f(x)。换句话说，函数不会有"向下的跳跃"。这比连续性要弱——连续函数要求 \lim f(x_n) = f(x)，而下半连续只要求下极限不小于函数值。

如果函数在 \mathcal{H} 的每个点都是下半连续的，我们说 f 在 \mathcal{H} 上是下半连续的。

下半连续性与上图闭性的等价关系

有一个关键定理：f 在 \mathcal{H} 上是下半连续的当且仅当 \text{epi} f 是闭集。这个等价关系揭示了函数分析性质与几何性质之间的深刻联系。

从几何角度看，如果上图是闭集，那么任何收敛到上图边界的序列的极限仍在上图中。具体来说，假设 (x_n, \zeta_n) \in \text{epi} f 且 (x_n, \zeta_n) \to (x, \zeta)。由于上图是闭的，(x, \zeta) \in \text{epi} f。现在如果我们取 \zeta_n = f(x_n)（即序列在函数图像上），那么 f(x_n) \to \zeta 意味着 \liminf f(x_n) = \zeta。由于 (x, \zeta) \in \text{epi} f，我们有 f(x) \leq \zeta = \liminf f(x_n)。这恰好是下半连续性的定义。

反之，如果函数是下半连续的，那么上图中任何收敛序列 (x_n, \zeta_n) \to (x, \zeta) 的极限点仍然满足 f(x) \leq \zeta。因为 f(x_n) \leq \zeta_n 且 \zeta_n \to \zeta，我们有 \liminf f(x_n) \leq \zeta。由下半连续性，f(x) \leq \liminf f(x_n) \leq \zeta，因此 (x, \zeta) \in \text{epi} f。这证明了上图是闭的。

具体例子帮助理解。连续函数自然是下半连续的。有跳跃的函数，如果跳跃是向上的（函数值增大），则保持下半连续。如果跳跃是向下的（函数值减小），则在跳跃点不下半连续。

函数可以在某些点取有限值，在其他点取无穷大值，但仍保持下半连续性。关键在于函数值的"突变"必须是向上的（包括跳到无穷大），而不能向下。

下半连续函数的性质

有三个基本性质。

连续函数是下半连续的。这是显然的，因为如果 f 连续，那么 \lim f(x_n) = f(x)，因此 \liminf f(x_n) = f(x) \geq f(x)。

有限个下半连续函数的和仍是下半连续的。设 f_1, \ldots, f_k 都是下半连续的。对于 f = f_1 + \cdots + f_k，如果 x_n \to x，那么

第一个不等号来自上下极限的次可加性，第二个不等号来自每个 f_i 的下半连续性。这个性质在构造目标函数时非常有用，它保证了我们可以将多个下半连续的惩罚项相加而不失去下半连续性。

设 (f_i)_{i \in I} 是一族下半连续函数，则

也是下半连续的。这是一个深刻的结果，它说明下半连续性在取上确界运算下是保持的。

证明利用上图的性质。设 C_i 是 f_i 的上图，C 是 f = \sup_{i \in I} f_i 的上图。关键观察是

即上确界函数的上图是所有函数上图的交集。

这可以通过等价关系链验证

由于每个 f_i 是下半连续的，每个 C_i 都是闭集。闭集的交集仍然是闭集（这是拓扑学的基本结果），因此 C = \text{epi} f 是闭集，从而 f 是下半连续的。这个证明优雅地将函数的分析性质转化为集合的拓扑性质，展现了上图概念的威力。

凸性与共轭函数

课程目标与结构

这一讲的核心目标包括四个方面：给出凸集和凸函数的定义，刻画可微凸函数的特征，定义函数的共轭，以及研究凸函数的共轭性质。这些概念构成了现代优化理论的基石，特别是在处理对偶问题和设计高效算法时不可或缺。

课程分为两大部分：第一部分是凸性，包括定义和可微凸函数的刻画；第二部分是Fenchel-Legendre共轭，这是凸分析中的核心变换工具。

凸集的定义

设 \mathcal{H} 是希尔伯特空间，C \subset \mathcal{H} 是一个凸集，当且仅当

这个定义的几何意义极其直观：凸集中任意两点之间的线段完全包含在该集合内。参数 \alpha \in [0,1] 描述了线段上点的位置。当 \alpha = 0 时得到点 y，当 \alpha = 1 时得到点 x，而 0 < \alpha < 1 时得到两点之间的内部点。这种线性组合 \alpha x + (1-\alpha)y 被称为凸组合，它保证了系数和为1且非负。

通过图形可以理解凸集的判别。第一个形状有凹陷部分，存在两个属于集合的点，但它们之间的线段部分在集合外部，因此不是凸集。第二个形状（半圆形）和第三个形状（矩形）都是凸集，因为任意两点间的连线都完全在集合内部。

凸集的基本性质

空集被认为是凸集。这个约定虽然看似琐碎，但在数学的完备性上很重要，它使得某些定理的表述更加简洁统一。

凸集有一个重要刻画：如果 C 是凸集，那么对任意 n \in \mathbb{N}^* 和任意 (x_1, \ldots, x_n) \in C^n，以及满足

的系数 (\alpha_1, \ldots, \alpha_n) \in [0, +\infty[^n，都有

这是凸集定义从两点推广到有限多点的情况，表明凸集对有限点的凸组合封闭。这个性质可以通过数学归纳法从两点的情况推导得出。具体来说，假设对 k 个点成立，考虑 k+1 个点的凸组合。如果最后一个系数 \alpha_{k+1} = 1，结论显然成立。否则，可以将前 k 个点的凸组合看作一个整体，然后应用两点的凸性。

每个向量（仿射）空间都是凸的。这是因为向量空间对线性组合封闭，自然也对凸组合封闭。这个性质说明了凸性是比线性更弱的条件。

如果 C 是凸集，那么 \text{int}(C)（内部）和 \bar{C}（闭包）也是凸集。这两个性质的证明都基于凸组合的连续性。对于内部，如果两点都在内部，它们都有邻域完全包含在 C 中，这些邻域的凸组合仍在 C 中。对于闭包，设 x, y \in \bar{C}，存在序列 (x_n)_{n \in \mathbb{N}} 和 (y_n)_{n \in \mathbb{N}} 分别收敛到 x 和 y。由于 C 是凸的

当 n \to \infty 时，由极限的线性性质

[0, +\infty[^N 是 \mathbb{R}^N 的一个凸锥。凸锥是同时满足凸性和锥性质（对正数倍封闭）的集合，在优化理论中用于描述可行方向和对偶锥等概念。

如果 (C_i)_{i \in I} 是一族凸集，那么

也是凸的。证明很直接：设 x, y \in \cap_{i \in I} C_i，则对所有 i \in I，都有 x \in C_i 且 y \in C_i。由于每个 C_i 都是凸的

对所有 i 成立，因此

这个性质在定义凸包时至关重要。

凸集的运算性质

如果 C 是凸集，那么对每个 \alpha \in \mathbb{R}，集合

也是凸的。这是因为凸组合与数乘运算可交换。设 x_1, x_2 \in C，则 \alpha x_1, \alpha x_2 \in \alpha C。对任意 \lambda \in [0,1]

由于 C 是凸的，\lambda x_1 + (1-\lambda)x_2 \in C，因此右边属于 \alpha C。

如果 C_1 和 C_2 是凸集，那么它们的笛卡尔积

和闵可夫斯基和

都是凸集。闵可夫斯基和的证明如下：设 (x_1 + x_2), (y_1 + y_2) \in C_1 + C_2，其中 x_1, y_1 \in C_1，x_2, y_2 \in C_2。对任意 \alpha \in [0,1]

由于 C_1 和 C_2 都是凸的，方括号中的项分别属于 C_1 和 C_2，因此它们的和属于 C_1 + C_2。

凸包

设 \mathcal{H} 是希尔伯特空间，C \subset \mathcal{H}。C 的凸包记为 \text{conv}(C)，是包含 C 的最小凸集。从集合论的角度，\text{conv}(C) 是所有包含 C 的凸集的交集。由于凸集的交集仍是凸集，这个定义是良好的。

有一个重要刻画：x \in \mathcal{H} 属于 \text{conv}(C) 当且仅当存在 n \in \mathbb{N}^*，点 (x_1, \ldots, x_n) \in C^n，以及满足

的系数 (\alpha_1, \ldots, \alpha_n) \in [0, +\infty[^n，使得

这个刻画表明凸包恰好是 C 中有限点的所有凸组合构成的集合。

证明分两个方向。首先证明 A \subset \text{conv}(C)，其中 A 是所有凸组合的集合。设

由于 x_i \in C \subset \text{conv}(C)，且 \text{conv}(C) 是凸集，根据凸集对凸组合封闭的性质，x \in \text{conv}(C)。

然后证明 \text{conv}(C) \subset A。由于 C \subset A（每个点可以看作自己的凸组合），且 A 是凸的（凸组合的凸组合仍是凸组合），而 \text{conv}(C) 是包含 C 的最小凸集，因此 \text{conv}(C) \subset A。

综合两个方向，得到 \text{conv}(C) = A。这个刻画在计算几何和优化算法中有重要应用，它将抽象的凸包概念转化为具体的代数表示。

凸函数的定义

函数 f: \mathcal{H} \to ]-\infty, +\infty] 是凸函数，当且仅当对所有 (x,y) \in \mathcal{H}^2 和所有 \alpha \in [0,1]，都有

这个不等式被称为Jensen不等式，它是凸性的核心。让我们深入理解这个定义的几何含义：等式右边 \alpha f(x) + (1-\alpha)f(y) 表示连接点 (x,f(x)) 和 (y,f(y)) 的线段上对应于横坐标 \alpha x + (1-\alpha)y 处的纵坐标值，而左边 f(\alpha x + (1-\alpha)y) 是函数在该点的实际值。凸性要求函数的图像始终位于任意两点连线的下方或重合。

定义域的重要性需要特别强调，条件应该明确写为 (x,y) \in (\text{dom} f)^2。这是因为在扩展实数系中，我们需要确保运算的良定义性——只有当 x 和 y 都在函数的定义域内时，不等式的两边才有意义。记住

所以这个限制确保了我们不会遇到无穷大的算术运算问题。

凸函数的例子

第一个是绝对值函数 f(x) = |x|。这是最经典的凸函数之一，它在原点处不可微但仍然是凸的。从几何上看，它形成一个V形，任意两点间的连线都在函数图像上方，这直观地展示了凸性。

第二个是 f(x) = \sqrt{|x|}。这个函数比绝对值函数更"平滑"，在原点附近增长更慢。尽管它在原点处的导数为无穷大，但它仍然满足凸性条件。这个例子说明凸函数可以有各种不同的增长率。

第三个是指示函数

这个函数展示了扩展值函数的重要性——通过允许函数取无穷值，我们可以将约束优化问题转化为无约束问题。

如何验证凸性？对于前两个函数，取任意两点间的连线，它们都在函数图像上方。对于第三个函数，由于它只在有限区间内取有限值，凸性验证主要关注该区间内的行为。

凹函数

函数 f: \mathcal{H} \to [-\infty, +\infty] 是凹函数，当且仅当 -f 是凸函数。这个对称性定义非常优雅，它意味着凹函数的所有性质都可以从凸函数的性质通过简单的符号变换得到。凹函数的图像位于任意两点连线的上方，与凸函数正好相反。

凸函数与上图凸性的等价关系

有一个深刻的定理：f: \mathcal{H} \to [-\infty, +\infty] 是凸函数当且仅当它的上图 \text{epi} f 是凸集。

这个等价关系将函数的分析性质（凸性）与集合的几何性质（凸性）联系起来，是凸分析的基石之一。通过图形可以直观看到：绝对值函数的上图是一个V形上方的区域，\sqrt{|x|} 的上图是一个更圆滑的凸区域，指示函数的上图是一个"半无限柱体"。所有这些上图都是凸集。

如果上图中存在两点，它们的连线部分在上图外部，那么对应的函数就不是凸的。

等价性定理的证明

正向证明：上图凸则函数凸

假设 \text{epi} f 是凸集。对任意 (x,y) \in (\text{dom} f)^2 和 (\eta,\rho) \in \mathbb{R}^2 满足 \eta \geq f(x) 和 \rho \geq f(y)，我们有

由于 \text{epi} f 是凸集，对任意 \alpha \in [0,1]

这意味着

关键步骤是让 \eta \to f(x) 和 \rho \to f(y)。由于不等式对所有 \eta \geq f(x) 和 \rho \geq f(y) 成立，取下确界得到

反向证明：函数凸则上图凸

假设 f 是凸函数。设 (x,\eta) \in \text{epi} f 和 (y,\rho) \in \text{epi} f，即 f(x) \leq \eta 和 f(y) \leq \rho。

对任意 \alpha \in [0,1]，由 f 的凸性

由于 f(x) \leq \eta 和 f(y) \leq \rho

因此

证明了 \text{epi} f 是凸集。

凸函数的重要性质

如果 f: \mathcal{H} \to [-\infty, +\infty] 是凸函数，那么 \text{dom} f 是凸集，并且对任意 \eta \in \mathbb{R}，下水平集

也是凸集。

这个性质在优化中极其重要。它告诉我们，凸函数的可行域（满足 f(x) \leq \eta 约束的点集）总是凸的，这保证了局部最优解就是全局最优解。下水平集的凸性是凸优化理论中许多算法收敛性的基础。

证明如下。设 x, y \in \text{lev}_{\leq\eta} f，即 f(x) \leq \eta 和 f(y) \leq \eta。对任意 \alpha \in [0,1]，由凸性

因此 \alpha x + (1-\alpha)y \in \text{lev}_{\leq\eta} f。

限制在直线上的凸性刻画

函数 f: \mathcal{H} \to ]-\infty, +\infty] 是凸的，当且仅当对所有 (x,y) \in (\text{dom} f)^2，函数

定义为

是凸的。

这个刻画将高维空间中的凸性问题简化为一维情形。它告诉我们，要验证一个函数的凸性，只需要检查它在所有可能的直线上的限制是否都是一维凸函数。这个性质在理论分析和算法设计中都有重要应用，因为一维凸函数的性质比高维情形简单得多。

证明的一个方向是显然的：如果 f 是凸的，那么它在任意直线上的限制自然满足一维凸性的定义。反过来，如果所有这样的限制函数都是凸的，那么对任意 x, y 和 \alpha \in [0,1]，函数 \varphi_{x,y} 在 \alpha 处满足凸性不等式，这正是 f 凸性的定义。

凸函数的高级性质

下水平集的凸性

凸函数的一个关键性质是其下水平集仍然是凸集。下水平集定义为

在优化理论中代表了满足某个阈值约束的所有可行点。为什么要研究这个性质？因为在实际优化问题中，我们经常需要在满足 f(x) \leq \eta 这样的约束条件下进行优化。如果这个可行域是凸的，那么局部最优解就是全局最优解，这大大简化了求解过程。

定理：如果 f: \mathcal{H} \to [-\infty, +\infty] 是凸函数，那么 \text{dom} f 是凸集，并且对任意 \eta \in \mathbb{R}，下水平集 \text{lev}_{\leq\eta} f 也是凸集。

证明：设 x, y \in \text{lev}_{\leq\eta} f，意味着 f(x) \leq \eta 且 f(y) \leq \eta。对于任意 \alpha \in [0,1]，凸性告诉我们

由于 f(x) 和 f(y) 都不超过 \eta，它们的凸组合满足

这里用到了 \alpha + (1-\alpha) = 1 这个恒等式。因此

即 \alpha x + (1-\alpha)y \in \text{lev}_{\leq\eta} f，证明了下水平集的凸性。

这个结果的深层含义在于，它建立了函数的分析性质（凸性）与几何性质（水平集的形状）之间的联系。在算法设计中，这保证了梯度下降等方法在约束集内移动时不会遇到局部陷阱。凸函数的所有下水平集都是凸的，这意味着可行域具有良好的几何结构。

凸函数族的运算性质

凸函数在某些运算下保持凸性，这些性质在构造新的凸函数和分析复杂优化问题时非常有用。

有限和的凸性

有限个凸函数的和仍是凸函数。设 f_1, \ldots, f_n 都是凸函数，定义 f = f_1 + \cdots + f_n。对任意 x, y 和 \alpha \in [0,1]

由于每个 f_i 是凸的

这个性质几乎是显然的，因为不等式的线性叠加保持了凸性条件。

上确界的凸性

但更深刻的是关于上确界的性质：如果 (f_i)_{i \in I} 是一族凸函数，那么

也是凸的。为什么这个结果如此重要？因为在对偶理论中，对偶函数往往表示为原始变量函数的上确界，这个性质保证了对偶函数的凸性，从而使对偶问题成为凸优化问题。

证明：证明采用了上图的方法，这体现了凸分析的一个基本技巧：将函数性质转化为集合性质。设 C_i 是 f_i 的上图，C 是 f = \sup_{i \in I} f_i 的上图。关键观察是

这是因为点 (x,t) 在 f 的上图中，当且仅当

这等价于对所有 i \in I，都有 t \geq f_i(x)，也就是说 (x,t) 在所有 C_i 中。由于每个 f_i 凸，每个 C_i 都是凸集，而凸集的交集仍是凸集，因此 C 是凸集，从而 f 是凸函数。

这个证明展示了上图概念的威力：它将一个关于函数的非线性运算（取上确界）转化为集合的线性运算（取交集），使得证明变得直观而优雅。

\Gamma_0(\mathcal{H}) 类函数

我们引入 \Gamma_0(\mathcal{H}) 这个函数类，它包含所有凸的、下半连续的、适当的函数。为什么要把这三个性质组合在一起？这不是随意的选择，而是优化理论发展过程中自然形成的"黄金组合"。

凸性保证了优化问题没有局部最优的困扰——任何局部最小值点都是全局最小值点。

下半连续性配合水平集的紧性可以保证最优解的存在性。这是Weierstrass定理的推广：下半连续函数在紧集上必能达到最小值。

适当性则排除了那些处处为无穷或取负无穷值的病态函数。适当函数要求 \text{dom} f \neq \emptyset 且 f(x) \neq -\infty 对所有 x 成立。

定义：

指示函数与闭凸集的等价性

特别地，当 C \subset \mathcal{H} 且 \iota_C \in \Gamma_0(\mathcal{H}) 时，C 必然是非空闭凸集。这个等价关系的证明基于

这个观察。要使 \iota_C 是凸的，需要 C 是凸的。要使 \iota_C 是下半连续的，等价于 \text{epi} \iota_C 是闭的，而

是闭的当且仅当 C 是闭的（因为 [0, +\infty[ 是闭的）。适当性要求 \text{dom} \iota_C = C \neq \emptyset。

为什么这很重要？因为它告诉我们，研究 \Gamma_0(\mathcal{H}) 中的指示函数等价于研究非空闭凸集，这在约束优化问题的分析中是基础性的。许多约束优化问题可以通过引入指示函数转化为无约束问题

如果 f 和 \iota_C 都在 \Gamma_0(\mathcal{H}) 中，右边的无约束问题也具有良好的性质。

严格凸函数

严格凸函数要求对于定义域内的不同点 x \neq y 和 \alpha \in ]0,1[，不等式

严格成立。注意这里是严格不等号 < 而不是 \leq。

这个严格不等号看似只是一个小改动，但它带来了质的变化：严格凸函数如果有最小值点，那么这个最小值点必然是唯一的。

定理：如果 f 是严格凸函数，且 \hat{x} 和 \hat{y} 都是最小值点，那么 \hat{x} = \hat{y}。

证明：假设 \hat{x} \neq \hat{y} 都是最小值点，即 f(\hat{x}) = f(\hat{y}) = \inf f。对 \alpha = 1/2，由严格凸性

这与 \inf f 是最小值矛盾。因此最小值点是唯一的。

唯一性的重要性

为什么唯一性如此重要？

在数值优化中，如果我们知道解是唯一的，那么不同的算法应该收敛到同一个点，这提供了算法正确性的检验标准。

在敏感性分析中，唯一性也简化了分析。当问题参数微小变化时，唯一的最优解会连续地变化，而不会出现解的"跳跃"。这使得最优解对参数的依赖关系更加可预测。

在理论分析中，唯一性保证了最优解的良定义性，使得后续的对偶理论、KKT条件等分析更加清晰。

严格凸与非严格凸的对比

通过图形可以直观理解差异。严格凸函数的共同特征是任意两点间的弦严格位于函数图像上方。而非严格凸函数虽然也是凸的，但包含线性段，在这些线性段上，弦与函数图像重合，失去了严格性。

例子：

绝对值函数 f(x) = |x| 是一个典型的凸但非严格凸的例子，它在原点两侧都是线性的。在 [0, +\infty[ 或 ]-\infty, 0] 上，函数是线性的，因此不满足严格凸性。

平方函数 f(x) = x^2 是严格凸的。对任意 x \neq y 和 \alpha \in ]0,1[

当 x \neq y 时严格不等号成立。

指示函数 \iota_C 除非 C 是单点集，否则不是严格凸的。如果 C 包含两个不同的点 x \neq y，那么在 C 内 \iota_C 恒为0，因此是线性的。

这些例子告诉我们，严格凸性是一个相当强的条件，许多常见的凸函数都不满足。但当它成立时，会带来许多好的性质，特别是在算法收敛性分析中。例如，对于严格凸函数，梯度下降法不仅收敛，而且收敛到唯一的全局最优点。

练习1：凸锥的性质

设 (a_k)_{1 \leq k \leq K} 是 \mathbb{R}^N 中的向量，定义集合

这个集合称为由向量族 (a_k) 生成的凸锥。我们需要证明 C 是 \mathbb{R}^N 的一个非空凸锥，并且当向量 (a_k)_{1 \leq k \leq K} 线性无关时，C 是闭的。

证明 C 是凸锥

非空性：显然 0 \in C（取所有 \xi_k = 0），所以 C 非空。

锥性质：如果 x \in C，存在 (\xi_k)_{1 \leq k \leq K} \in [0, \infty[^K 使得

对任意 \lambda > 0，有

因为 \lambda\xi_k \geq 0。这证明了 C 对正数倍封闭，满足锥的性质。

凸性：设

其中所有系数非负。对任意 \alpha \in [0,1]

因为 \alpha\xi_k + (1-\alpha)\eta_k \geq 0（非负数的凸组合仍非负），所以 \alpha x + (1-\alpha)y \in C。这证明了 C 是凸的。

线性无关时的闭性

当向量族 (a_k)_{1 \leq k \leq K} 线性无关时，C 中任何元素 x 在这个基下的分解是唯一的。定义映射

将 C 中的点映射到其系数向量。

由于 (a_k) 线性无关，这个映射是良定义的（每个 x 对应唯一的系数组）。更重要的是，这是一个线性映射。在有限维空间中，线性映射是连续的。

注意到

因此

由于 [0, \infty[^K 是 \mathbb{R}^K 中的闭集，而连续映射的原像保持闭性，所以 C 是闭的。

一般情形的闭性

即使对于任意向量族 (a_k)_{1 \leq k \leq K}（不一定线性无关），闭性结论仍然成立。这是因为 C 可以表示为有限个半空间的交集。

对于每个 k，定义半空间

其中 u_k 是适当选择的向量。通过这种构造，可以证明

而半空间是闭的，闭集的有限交仍是闭的，因此 C 是闭的。

这个结果在优化理论中很重要，因为许多约束优化问题的可行域可以表示为凸锥的形式。凸锥的闭性保证了最优解的存在性。

练习2：强凸性

范数平方的严格凸性

命题：函数 h(x) = \|x\|^2 是严格凸的。

证明：对任意 x \neq y 和 \alpha \in ]0,1[，定义

我们需要证明 \Delta_h < 0。

计算 h(\alpha x + (1-\alpha)y)，利用内积的双线性性

现在计算 \alpha h(x) + (1-\alpha)h(y)

因此

整理得

注意到 \alpha(\alpha - 1) = -\alpha(1-\alpha) 和 (1-\alpha)(-\alpha) = -\alpha(1-\alpha)

最后一步使用了恒等式 \|x-y\|^2 = \|x\|^2 + \|y\|^2 - 2\langle x|y \rangle。

由于 \alpha \in ]0,1[，我们有 \alpha(1-\alpha) > 0。当 x \neq y 时，\|x-y\|^2 > 0。因此

这证明了 \|\cdot\|^2 是严格凸的。

强凸函数的定义

函数 f: \mathcal{H} \to ]-\infty, +\infty] 是模为 \beta \in ]0, +\infty[ 的强凸函数，如果存在凸函数 g: \mathcal{H} \to ]-\infty, +\infty] 使得

强凸性是比严格凸性更强的性质。它不仅要求函数严格凸，还要求函数的"弯曲程度"有一个定量的下界。

强凸函数是严格凸的

命题：每个强凸函数都是严格凸的。

证明：如果 f = g + \frac{\beta}{2}\|\cdot\|^2 是强凸的，其中 g 是凸函数，对任意 x \neq y 和 \alpha \in ]0,1[

由于 g 是凸的，\Delta_g \leq 0。从前面的证明我们知道 \Delta_{\|\cdot\|^2} < 0。因此

由于 \beta > 0，不等号严格成立。这证明了 f 是严格凸的。

强凸性的等价刻画

定理：函数 f: \mathcal{H} \to ]-\infty, +\infty] 是模为 \beta \in ]0, +\infty[ 的强凸函数，当且仅当对所有 (x,y) \in \mathcal{H}^2 和所有 \alpha \in ]0,1[

证明 (*) 方向：如果 f 是模为 \beta 的强凸函数，则存在凸函数 g 使得 f = g + \frac{\beta}{2}\|\cdot\|^2。

对于凸函数 g

因此

这给出了所需的不等式。

反向证明：假设不等式成立。定义 g = f - \frac{\beta}{2}\|\cdot\|^2。我们需要证明 g 是凸的。

对任意 x, y 和 \alpha \in [0,1]，由假设

从前面的计算我们知道

因此

这证明了 g 是凸的，从而 f 是强凸的。

强凸性的意义

强凸性是比严格凸性更强的性质。它不仅保证了函数的唯一最小值点，还提供了关于函数增长率的定量信息。模 \beta 描述了这种"额外凸性"的强度——\beta 越大，函数越"陡峭"，优化算法的收敛速度也越快。

这个概念在优化理论中极其重要，因为强凸函数保证了许多优化算法（如梯度下降）的线性收敛率，而一般凸函数只能保证次线性收敛率。具体来说，对于强凸函数，梯度下降法的收敛速度可以表示为

其中 \mu 是强凸性模，L 是Lipschitz常数。这是指数收敛，远快于一般凸函数的 O(1/k) 收敛速度。