第一章 优化理论基础

你好，我们今天开始学习优化理论的基础知识。你手上的这份笔记，可以说是整个优化领域的基石。它从最基本的问题分类开始，一直讲到优化理论中最美妙、最重要的性质——凸性。我们的目标是不仅看懂这些定义，更要理解它们为什么重要，以及它们之间是如何环环相扣的。

1.1 优化问题的基本分类

我们首先来看笔记的第一和第二部分，它们将庞大的优化问题分成了最基本的两类。

1.1.1 无约束优化 (Unconstrained Optimization)

所谓"优化"，其核心目标通常是寻找一个函数的最小值（或最大值，但通常我们可以通过给函数加负号来统一为最小值问题）。无约束优化是其中最简单的一种形式。

它的目标是找到一个输入 x，使得函数 f(x) 的值最小。这里的 x 可以是任意一个在 \mathbb{R}^n 空间里的点。这个表达方式 f: \mathbb{R}^n \rightarrow \mathbb{R} 是一个非常关键的数学语言。它告诉我们,这个函数 f 接受一个 n 维的向量 x 作为输入（比如，在三维空间中一个点的坐标 (x_1, x_2, x_3) 就是一个属于 \mathbb{R}^3 的向量），然后输出一个实数（标量）。在实际应用中，这个输入 x 可能代表着一组我们能够调整的参数，而输出 f(x) 则是我们希望最小化的成本、误差或者能量。

在着手解决问题之前，笔记提出了两个根本性的问题，这也是所有优化研究都必须面对的：

1. 解是否存在且唯一？ 这个问题至关重要。我们是不是一定能找到一个最小值？比如函数 f(x) = x 就没有最小值，它会一直减小下去。即使存在最小值，这个最小值点是只有一个，还是有无数个？这决定了我们求解的难易程度和目标的清晰度。
2. 算法的选择与收敛性：理论上知道解存在还不够，我们还需要具体的"方法"去找到它。这就是算法。比如大家可能听过的梯度下降法，就是一种寻找最小值的算法。而"收敛性"则是评判一个算法好坏的核心标准。它指的是，我这个算法运行起来，是不是能稳定地、一步步地逼近那个我们想找的最小值点？会不会在某个地方来回震荡，或者干脆跑到无穷远去？

1.1.2 约束优化 (Constrained Optimization)

现在我们来看一种更普遍、也更复杂的情况：约束优化。它的目标同样是最小化函数 f(x)，但这次的变量 x 不能在整个 \mathbb{R}^n 空间里自由取值了，它必须满足一系列给定的"约束条件"。

笔记里给出了两种最常见的约束类型：

• 不等式约束：g_i(x) \le 0，这里 i=1, \dots, p 表示我们总共有 p 个这样的不等式约束。例如，我们可能要求变量 x 的第一个分量必须小于等于5，也就是 x_1 \le 5，这就可以写成 g_1(x) = x_1 - 5 \le 0 的形式。
• 等式约束：h_i(x) = 0，这里 i=1, \dots, q 表示我们有 q 个等式约束。例如，我们可能要求变量 x 的各个分量之和必须为1，即 \sum_{j=1}^n x_j = 1，这就可以写成 h_1(x) = \sum_{j=1}^n x_j - 1 = 0 的形式。

所有这些满足约束条件的点 x 集合起来，形成了一个特定的区域，我们称之为可行域 (Feasible Set)，在笔记中用 D 表示。

这个可行域 D 是我们寻找最优解的"搜索空间"。我们的任务，就是在 D 这个可能形状很奇怪的区域里，找到能让 f(x) 最小的那个点。笔记中还提到，为了书写方便，我们通常把多个约束函数打包写成向量形式 g(x) 和 h(x)。

笔记里还有一个非常重要的点，它提到可行域 D 通常是一个闭集 (Closed Set)。从直观上理解，一个集合是闭的，意味着它包含了自己所有的边界点。比如区间 [0, 1] 就是闭集，而 (0, 1) 就不是。这个性质非常重要，因为它是后面我们要提到的"最小值存在定理"的一个关键前提。一个连续函数在一个有界闭集（也叫紧集）上，必然能取到它的最小值和最大值。

1.2 最优解的类型

当我们谈论"最小值"时，其实有两种不同的层次，这在笔记的第三部分有详细的定义。

1.2.1 全局最小值 (Global Minimum)

一个点 x^* 被称为全局最小值，如果对于可行域 D 中的任何一个点 x，都有 f(x) \ge f(x^*)。

全局最小值是我们在优化问题中真正追求的终极目标。它是在整个搜索空间里"最好"的点，没有其他任何可行点能比它更好了。

1.2.2 局部最小值 (Local Minimum)

一个点 x^* 被称为局部最小值，如果在它附近的一个小邻域内，它是最小的。更严格的定义是：存在一个围绕 x^* 的小邻域 N(x^*)，对于任何同时属于这个邻域和可行域 D 的点 x，都有 f(x) \ge f(x^*)。

你可以想象一座连绵的山脉，全局最小值是整片山脉的海拔最低点（比如马里亚纳海沟的底部）。而局部最小值则可能只是某个小山谷的谷底，虽然在这个谷底里你往任何方向走海拔都会升高，但它未必是整个山脉的最低点。笔记中的那张函数图非常形象地画出了这个区别。

绝大多数优化算法，特别是像梯度下降这类依赖局部信息的算法，它们很容易找到一个局部最小值然后就"卡住"了，因为在它看来，周围已经没有更低的地方可去了。因此，区分局部和全局最小值，并研究何时局部最小值就是全局最小值，是优化理论的一个核心问题。

1.3 凸性理论

现在，我们来到了整个笔记中最关键、也是优化理论中最核心的概念——凸性。这个性质能够极大地简化优化问题，为我们提供从局部最优走向全局最优的桥梁。

笔记的第五部分给出了凸函数 (Convex Function) 的数学定义。一个函数 f 被称为凸函数，如果它的定义域 D 是一个凸集（即集合内任意两点的连线段仍然在该集合内），并且对于定义域中任意两点 x_1, x_2 和任意一个在 [0,1] 区间内的常数 \lambda，都满足以下不等式：

这个公式看起来有点抽象，但它的几何意义非常直观。公式左边的 f(\lambda x_1 + (1-\lambda)x_2) 表示的是函数在连接 x_1 和 x_2 的线段上某一点的函数值。而公式右边的 \lambda f(x_1) + (1-\lambda)f(x_2) 表示的是连接点 (x_1, f(x_1)) 和 (x_2, f(x_2)) 的那条弦（直线段）上相应点的高度。整个不等式的意思是：函数图像本身总是位于连接其上任意两点的弦的下方（或重合）。简单来说，一个凸函数的样子就像一个"碗"，它没有局部的凹陷。笔记里的图画得非常清楚，左边那个碗状的函数就是凸的，右边那个有起有伏的函数就是非凸的。

凸性的核心意义

这就引出了笔记的最后一部分，也是画龙点睛之笔。它揭示了凸性与全局最优之间的深刻联系。

• 单峰性 (Unimodality)：如果一个优化问题是凸优化问题（即目标函数是凸函数，可行域是凸集），那么这个函数就是所谓的单峰的 (unimodal)。
• 核心结论：对于一个凸优化问题，任何一个局部最小值都必然是全局最小值。

这个结论是整个优化理论中最令人振奋的定理之一！它意味着什么呢？它意味着，如果我们面对的是一个凸优化问题，我们就不再需要担心算法会陷入一个"假的"最优解（局部最优解）了。我们只需要让算法随意地去寻找一个局部最小值，一旦找到了，我们就可以百分之百地确定，它就是我们梦寐以求的全局最小值。这使得凸优化问题变得原则上"容易解决"，而大量的非凸优化问题则被认为是"NP-hard"的，即非常困难。

与之相对的，笔记中也提到了多峰性 (multimodality)。对于非凸函数，它可能存在多个局部最小值，就像笔记里画的那个W形状的函数一样。在这种情况下，找到全局最小值就成了一项极具挑战性的任务。

总结一下，这份笔记为你构建了优化理论的基本框架：从问题分类（无约束/约束），到解的分类（局部/全局），最后引入了强大的"屠龙刀"——凸性，它告诉我们，在凸性的美好世界里，局部即全局，问题迎刃而解。希望这份讲解能帮助你更深刻地理解这份笔记的内涵。

第二章 函数分析的微积分工具

今天我们来学习一些更具体的数学工具，这些工具能帮助我们分析并求解上一节课定义的优化问题。如果说上一节课我们了解了优化的"目标"是什么（寻找最小值），那么这一节课我们就要来学习如何找到"路径"（如何移动到最小值点）。

2.1 函数的可视化方法

在处理优化问题时，建立直观的理解至关重要。笔记的第一部分罗列了四种可视化函数或数据的方法，这能帮助我们想象出函数的样子，也就是我们要优化的"地形图"。

1. 图 (Graph)：这是我们最熟悉的方式，对于一个二元函数 f(x, y)，我们可以画出 z = f(x, y) 的三维曲面图。这个图最直观，但只适用于输入是一维或二维的情况。
2. 等高线 (Contour Lines)：这是一种"降维"的可视化方法。想象一下我们用水平的刀去切刚才那个三维曲面，每一刀切出来的切口投影到下面的 xy 输入平面上，就形成了一条等高线。同一条线上的所有点，其函数值 f(x,y) 都相等。这就像我们看地图时的等高线，密集的地方表示地形陡峭，稀疏的地方表示平缓。这在优化中极为常用，因为它能让我们在二维平面上直观地看到函数的起伏。
3. 参数化曲面 (Parametric Surfaces)：这是一种用参数来描述空间曲面的方法，更多用于计算机图形学和几何建模，在优化的可视化中相对少见。
4. 向量场 (Vector Fields)：这个概念极其重要。它指的是在空间的每一个点，我们都给它指定一个向量（一个有方向和大小的箭头）。马上我们就会学到，一个函数在空间中每一点的"梯度"就构成了一个向量场，这个"梯度场"就如同地形图上的水流方向指示，告诉我们哪条路下山最快。

2.2 梯度：优化的核心工具

这是本次笔记的核心。梯度是多元函数微分学的基石，也是几乎所有现代优化算法的核心。

对于一个多元函数，比如 f(x,y)，它的梯度记作 \nabla f(x,y)，是一个由所有偏导数构成的向量：

我们绝不能把梯度仅仅看作是几个偏导数的简单集合。它是一个真正的向量，它包含两个至关重要的信息：

• 方向：梯度向量所指的方向，是函数 f 在该点增长最快的方向。也就是说，如果你身处山坡上某一点，想最快地上山，那么你应该沿着该点梯度向量的方向走。笔记上写的"最陡上升方向"是对其物理意义最精准的描述。
• 大小：梯度向量的模长（magnitude），||\nabla f||，代表了在这个最陡峭方向上，函数值的增长率有多大。梯度模长越大，说明山坡越陡。

基于此，我们得到了优化理论中的一个基本结论：一个函数 f(x) 的最小值、最大值或鞍点（我们统称为临界点或驻点），只可能出现在梯度为零向量的点上，即 \nabla f = \mathbf{0}。这是因为，只要梯度不为零，就说明当前位置还存在一个让函数值上升（或下降）的方向，那么它就不可能是极值点。因此，求解 \nabla f = \mathbf{0} 是寻找函数极值点的第一步。

2.3 方向导数与梯度性质

梯度告诉了我们"最快"的上升方向，但如果我们想知道朝其他任意方向走，函数值的变化率是多少呢？这就是方向导数要回答的问题。

假设我们想知道在点 (x,y) 处，沿着某个方向向量 \vec{w} = \begin{bmatrix} a \\ b \end{bmatrix} 前进时，函数 f 的变化率。这个变化率就由方向导数 \nabla_{\vec{w}}f 给出，它的计算非常简洁，就是梯度向量和方向向量的点积：

这个简单的公式蕴含了关于梯度的三个深刻的几何性质，也就是笔记中列出的三点：

1. 梯度指向增长最快的方向：根据点积的定义 \nabla f \cdot \vec{w} = ||\nabla f|| \ ||\vec{w}|| \cos\theta，其中 \theta 是两个向量的夹角。当方向向量 \vec{w} 与梯度 \nabla f 方向相同时（\theta = 0, \cos\theta = 1），点积取得最大值。这从数学上证明了梯度方向就是函数增长最快的方向。
2. 最快增长率的大小是梯度的模长：在上述增长最快的方向上，方向导数的值为 ||\nabla f|| \ ||\vec{w}|| \cos(0)。如果 \vec{w} 是一个单位方向向量（||\vec{w}||=1），那么这个最大变化率就是 ||\nabla f||，即梯度向量的模长。
3. 梯度与等高线垂直：等高线是函数值不变的线。如果你沿着等高线的切线方向走，函数值是不会变化的，因此这个方向上的方向导数为 0。也就是说，\nabla f \cdot \vec{w}_{\text{切线}} = 0。这在数学上意味着梯度向量 \nabla f 必须与等高线的切线方向 \vec{w}_{\text{切线}} 相垂直。这个性质非常直观：最陡峭的上山路径，必然是横切着等高线的。

2.4 散度与拉普拉斯算子

梯度是一阶导数，它告诉我们函数的"坡度"。而散度和拉普拉斯算子与二阶导数相关，它们能告诉我们函数地形的"曲率"或"弯曲程度"。

2.4.1 散度：向量场的"源"与"汇"

散度是作用在一个向量场（比如风速场、水流场）上的算子。对于一个向量场 \vec{v}(x,y) = \begin{bmatrix} P(x,y) \\ Q(x,y) \end{bmatrix}，它的散度定义为：

散度的物理意义是衡量一个点附近向量场的"源"或"汇"的强度。

• \text{div} \ \vec{v} > 0：表示该点是一个源头，向量都是从这一点向外"发散"的，如笔记中第一个图所示。
• \text{div} \ \vec{v} < 0：表示该点是一个汇点（或"漏斗"），向量都是向这一点"汇集"的。
• \text{div} \ \vec{v} = 0：表示该点的流入量等于流出量，是"无源无汇"的，这样的场被称为是不可压缩的。

2.4.2 拉普拉斯算子：梯度的散度

现在，最巧妙的联系出现了。拉普拉斯算子是作用在一个标量函数 f(x,y) 上的，但它的定义是先计算出 f 的梯度场 \nabla f，然后再计算这个梯度场的散度。

这个"梯度的散度"的物理意义是什么？这正是它在优化中用作二阶导数判据的直观来源。我们来分析一个临界点（\nabla f = \mathbf{0}）：

• 如果这个临界点是一个局部最小值（一个"碗底"），那么在它周围，所有的梯度向量都指向"上山"的方向，也就是背离这个最小值点。这就形成了一个从最小值点向外发散的梯度场。根据散度的定义，一个向外发散的场的散度是正的。因此，\Delta f > 0 是一个点为局部最小值的标志。
• 相反，如果这个临界点是一个局部最大值（一个"山顶"），那么在它周围，梯度向量都指向它，形成一个向内汇集的梯度场。这样的场的散度是负的。因此，\Delta f < 0 是一个点为局部最大值的标志。

最后，如果一个函数的拉普拉斯算子在整个定义域内恒为零，即 \Delta f \equiv 0，我们称之为调和函数 (Harmonic Function)。这类函数具有非常平滑的特性，可以看作是既没有"源"也没有"汇"的稳定状态，在物理和工程中有广泛应用。

总而言之，今天的笔记为我们提供了强大的微积分工具：用梯度来确定前进方向，用拉普拉斯算子（梯度的散度）来判断我们是处在"山谷"还是"山顶"。这些正是在优化算法中进行迭代和判断的基础。

第三章 函数近似与临界点判别

大家好，在上一节课中，我们掌握了梯度 \nabla f 这个强大的工具，它能告诉我们函数变化最快的方向。我们还知道，所有可能的极值点（临界点）都必须满足 \nabla f = \mathbf{0} 这个条件。但是，一个梯度为零的点，它究竟是局部最小值、局部最大值，还是都不是呢？为了回答这个问题，我们需要更高阶的信息，也就是二阶导数。这节课的笔记，就是从函数近似开始，一步步带我们构建起完整的二阶导数判别法。

3.1 函数的局部近似

直接分析一个复杂的非线性函数是困难的，但我们可以用一个简单的"代理"函数在某个点的附近来近似它。这是微积分的核心思想。

3.1.1 局部线性化 (Local Linearization)

我们能想到的最简单的函数就是线性函数。任何一个足够平滑的函数，当我们将它无限放大时，它看起来都像一条直线（一维）或一个平面（二维）。这个"局部看起来像平面"的性质，就是局部线性化的基础。

笔记中给出的公式，正是在点 (x_0, y_0) 附近用一个平面 L(x,y) 来近似函数 f(x,y) 的表达式，这也被称为函数 f 的一阶泰勒展开：

这个公式的构成很直观：

• f(x_0, y_0): 这是我们的基准高度，即近似平面在 (x_0, y_0) 这一点必须与原函数高度一致。
• \frac{\partial f}{\partial x}(x_0, y_0)(x - x_0): 这是沿 x 方向的高度变化量，由 x 方向的偏导数（坡度）乘以在 x 方向上移动的距离 (x-x_0) 得到。
• \frac{\partial f}{\partial y}(x_0, y_0)(y - y_0): 同理，这是沿 y 方向的高度变化量。

把这三者加起来，我们就得到了这个切平面的方程。这种 a+bx+cy 形式的函数，笔记中也指出了，它被称为仿射函数 (Affine function)，即一个线性函数加上一个常数项。

然而，线性近似有一个巨大的缺点：它只能反映函数的"坡度"，无法体现函数的"弯曲程度"。在一个临界点，梯度为零，线性近似就变成了一个水平面 L(x,y) = f(x_0, y_0)。我们从这个水平面上无法判断出这个点到底是"碗底"还是"穹顶"。

3.1.2 二次逼近与Hessian矩阵

为了捕捉函数的曲率信息，我们需要升级我们的近似工具，从线性函数升级到二次函数。二次函数可以形成抛物面（碗状或穹顶状），正好可以用来描述极值点附近的形态。这就是二阶泰勒展开。

笔记中给出了向量形式的二次逼近公式，这对于多变量函数更为通用：

让我们来解读这个公式：

• f(\mathbf{x}_0): 零阶项，常数项，和线性近似一样。
• \nabla f(\mathbf{x}_0)^T (\mathbf{x} - \mathbf{x}_0): 一阶项，梯度（行向量形式）点乘位移向量，和线性近似的导数部分本质一样。
• \frac{1}{2}(\mathbf{x} - \mathbf{x}_0)^T H_f(\mathbf{x}_0) (\mathbf{x} - \mathbf{x}_0): 全新的二阶项。这正是我们需要的曲率信息，它由一个叫做 Hessian 矩阵（海森矩阵）的 H_f 来定义。

Hessian 矩阵 H_f 是一个方阵，其中包含了函数 f 的所有二阶偏导数。对于一个三维变量的函数，它的形式如笔记所示：

Hessian 矩阵有一个非常重要的性质：只要函数的二阶偏导数是连续的，它就一定是一个对称矩阵（即 H_{ij} = H_{ji}）。它的作用，就是描述了在临界点附近的地形到底是如何弯曲的。这个形如 \mathbf{z}^T H \mathbf{z} 的表达式被称为二次型 (Quadratic Form)，它完全刻画了一个二次曲面的形状。

3.2 二阶导数判别法

现在我们有了最强的工具。当我们找到了一个临界点 \mathbf{x}_0（即 \nabla f(\mathbf{x}_0) = \mathbf{0}），它的二次近似函数就简化为：

这意味着，在临界点附近，函数 f(\mathbf{x}) 的行为完全由 Hessian 矩阵 H_f(\mathbf{x}_0) 决定的二次型来主导。因此，判断 \mathbf{x}_0 是不是极值点，就等价于判断这个二次型的符号。

3.2.1 二元函数的判别法则

对于只有两个变量 f(x,y) 的情况，有一个简便的判别法则，它通过计算 Hessian 矩阵的行列式 D = \det(H_f) 和左上角元素 f_{xx} 来判断：

1. 第一步：找到所有满足 \frac{\partial f}{\partial x}=0 和 \frac{\partial f}{\partial y}=0 的临界点 (x_0, y_0)。
2. 第二步：对于每一个临界点，计算出 Hessian 矩阵 H_f = \begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix}。
3. 第三步：计算行列式 D = f_{xx}f_{yy} - f_{xy}^2。
   • 如果 D > 0 且 f_{xx} > 0，说明曲面在所有方向都向上弯曲（像一个碗），该点是局部最小值。
   • 如果 D > 0 且 f_{xx} < 0，说明曲面在所有方向都向下弯曲（像一个穹顶），该点是局部最大值。
   • 如果 D < 0，说明曲面在一个方向向上弯曲，在另一个方向向下弯曲（像一个马鞍），该点是鞍点。
   • 如果 D = 0，此方法失效，需要更高阶的导数信息来判断。

3.2.2 多元函数的通用判别法

对于三个及以上变量的函数，简单的行列式判据不再适用。我们需要一个更普适的工具来描述 Hessian 矩阵的性质，这就是矩阵的定性 (Definiteness)，它可以通过计算矩阵的所有特征值 (Eigenvalues) 来判断。

假设我们在临界点 \mathbf{a} 处计算出了 Hessian 矩阵 H：

1. 如果 H 是正定 (Positive Definite) 的，即它的所有特征值都大于 0，那么二次型 \mathbf{z}^T H \mathbf{z} 对任何非零向量 \mathbf{z} 恒为正。这意味着无论你从临界点朝哪个方向移动，函数值都会增加。因此，点 \mathbf{a} 是一个局部最小值。
2. 如果 H 是负定 (Negative Definite) 的，即它的所有特征值都小于 0，那么二次型恒为负。这意味着无论朝哪个方向移动，函数值都会减小。因此，点 \mathbf{a} 是一个局部最大值。
3. 如果 H 是不定 (Indefinite) 的，即它既有正特征值，也有负特征值，那么在对应于正特征值的特征向量方向上函数值会增加，而在对应于负特征值的特征向量方向上函数值会减小。这就是一个鞍点。
4. 在所有其他情况下，比如 H 有一些零特征值（这被称为半定），这个二阶导数判别法就失效了，我们无法仅凭 Hessian 矩阵得出结论。

总结一下，从线性近似到二次近似，我们最终得到了一个完整而强大的分析流程：首先用梯度（一阶导数）找到所有"平坦"的临界点，然后用 Hessian 矩阵（二阶导数）的定性来判断这些点的局部地形，从而精确地分类出每一个局部最小值、最大值和鞍点。

第四章 无约束优化算法

我们已经学习了如何分析一个函数的"地形"，哪里是山顶，哪里是山谷。现在，我们的任务是扮演一个"登山者"，从任意一个初始位置出发，设计一套可靠的策略，保证能一步一步地走到山谷的最低点。这就是优化算法的核心。

4.1 迭代优化算法的通用框架

笔记的第一部分（右侧图片上半部分）为我们描绘了几乎所有优化算法共通的"配方"，这个配方被称为迭代下降法。

它的基本流程如下：

1. 初始化：首先，我们需要一个出发点，随机选择或根据经验设定一个初始点 \mathbf{x}_0。

2. 判断方向：在当前的位置 \mathbf{x}_k 上，我们需要决定下一步朝哪个方向 \mathbf{d}_k 走。一个好的方向至少应该是一个下降方向，也就是说，沿着这个方向前进一小步，函数值会减小。最自然的选择就是最速下降方向，即梯度的反方向 \mathbf{d}_k = -\nabla f(\mathbf{x}_k)，这就是梯度下降法的策略。

3. 决定步长：确定了方向后，我们还需要决定沿着这个方向走多远，这个距离被称为步长（或学习率） \alpha_k。步子迈太小，下降太慢；步子迈太大，则有可能"跨过"了最低点，甚至跑到函数值更高的地方。如何选择合适的步长是一个关键问题。

4. 更新位置：根据方向和步长，更新我们的位置：

5. 循环：重复第2到第4步，直到满足某个停止条件（比如梯度已经小到几乎为零，或者函数值不再下降）。

笔记中提到的问题 是不是总会变得更好/不下降？ 是一个非常好的问题。一个设计良好的算法，必须能保证函数值在迭代过程中是稳步下降的，即 f(\mathbf{x}_{k+1}) \le f(\mathbf{x}_k)，这被称为算法的下降性质。

4.2 牛顿法

梯度下降法只利用了一阶导数（坡度）信息，它虽然方向正确，但并不知道"地形"的弯曲程度，因此可能会走很多"冤枉路"。而牛顿法则是一种更"聪明"的算法，它同时利用一阶和二阶导数信息，试图用最少的步数直达目的地。

它的核心思想是：在当前点，用一个二次函数（抛物面）去近似真实的复杂函数，然后直接跳到这个近似抛物面的最低点。

4.2.1 一维牛顿法的推导

笔记（右侧图片下半部分）清晰地展示了一维情况下牛顿法的推导过程：

建立二次模型：我们在当前点 x_k 附近，使用二阶泰勒展开来近似函数 f(x)：

最小化模型：我们的目标是找到能让这个二次模型最小的 x。为了求解方便，我们设更新的步长为 t = x - x_k，那么模型就变成了关于 t 的二次函数：

求最优步长：这是一个简单的二次函数求极值问题。我们对 t 求导，并令其等于零：

解出最优的步长 t 为：

得到更新公式：将最优步长代入更新规则 x_{k+1} = x_k + t，我们就得到了一维牛顿法的迭代公式：

4.2.2 多维牛顿法

这个思想可以被完美地推广到多维情况。一阶导数 f' 变成了梯度 \nabla f，二阶导数 f'' 变成了 Hessian 矩阵 H_f。矩阵的"除法"对应于乘以其"逆矩阵"。于是，多维牛顿法的更新公式为：

这里的 H_f(\mathbf{x}_k) 就是笔记中写的 \nabla^2 f(\mathbf{x}_k)。

牛顿法为什么强大？笔记右上角有一个关键注释：梯度下降法是线性收敛，而牛顿法是二次收敛。这意味着，在接近最优解时，牛顿法每迭代一次，解的有效数字位数大约会翻一番，收敛速度极快。

4.3 拟牛顿法

既然牛顿法如此高效，为什么我们不总是使用它呢？笔记的左侧图片一针见血地指出了它的致命缺点：计算代价过于高昂。

问题就出在Hessian矩阵的逆 [H_f(\mathbf{x}_k)]^{-1} 上：

1. 存储开销大：对于一个有 n 个变量的问题，Hessian 矩阵是一个 n \times n 的矩阵，需要 O(n^2) 的空间来存储。当 n 达到数千甚至数万时（在机器学习等领域很常见），这会消耗巨大的内存。
2. 计算开销极大：计算这个Hessian矩阵的逆，或者求解等价的线性方程组 H_f \mathbf{d}_k = -\nabla f(\mathbf{x}_k)，通常需要 O(n^3) 的计算时间。这使得在大规模问题上，牛顿法的每一次迭代都慢得无法接受。

为了解决这个困境，人们提出了一类非常巧妙的算法，叫做拟牛顿法 (Quasi-Newton Methods)。

其核心思想是：我们不计算真实Hessian矩阵的逆，而是用一个矩阵 B_k 来近似它。

这个近似矩阵 B_k 的美妙之处在于，我们不需要每一轮都重新计算。我们可以在每一步迭代之后，利用刚刚得到的"位移"信息 (\mathbf{x}_{k+1} - \mathbf{x}_k) 和"梯度变化"信息 (\nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k))，通过一个简单的、低计算成本的公式对 B_k 进行更新，得到 B_{k+1}。

笔记中提到的 BFGS 算法 (Broyden–Fletcher–Goldfarb–Shanno) 就是其中最著名和最成功的一种。它通过一种非常精妙的方式来迭代地逼近真实Hessian矩阵的逆，从而避免了 O(n^3) 的计算瓶颈。

总结来说，BFGS这类拟牛顿法，既保留了牛顿法收敛快的优点（通常是超线性收敛，比线性快但比二次慢），又克服了其计算量过大的缺点，是目前求解无约束非线性优化问题最常用、最高效的算法之一。

第五章 约束优化：拉格朗日乘子法

大家好，我们之前的课程主要聚焦于在没有任何限制的"开阔地带"寻找函数的最小值，这被称为无约束优化。然而，在现实世界中，我们往往需要在满足特定规则和限制的条件下做出最优决策。例如，在预算固定的情况下最大化收益，或者在材料用量确定的情况下设计最坚固的结构。这些都属于约束优化问题。今天，我们将学习处理这类问题中最经典的一种——等式约束优化——的利器：拉格朗日乘子法。

5.1 拉格朗日乘子法的几何直觉

我们先来构建一个直观的画面，来理解拉格朗日乘子法的精髓。

假设我们的目标是最大化一个函数 f(x,y)，它在三维空间中代表着一个山脉的地形。但我们不能随意在山脉上走动，而是必须沿着一条由约束方程 g(x,y) = b 所规定好的特定路径前进。我们的任务是：找出这条路径上的最高点。

这个最高点（或最低点）会出现在哪里呢？

想象一下，你正走在这条路径上。只要你前方的路径还在"上坡"，意味着它正在穿越到一条更高的等高线上去，那你就还没有到达最高点。同理，如果你在"下坡"，也说明你已经越过了最高点。那么，最高点在何处？它必然发生在你沿着路径行走，既不上坡也不下坡的那个瞬间。这个瞬间，你的前进方向正好与你所在位置的等高线的切线方向重合。换句话说，在最优点，约束路径曲线与目标函数的等高线是相互相切的。

笔记中的配图完美地诠释了这一点：右图中的同心圆是目标函数 f(x,y) 的等高线，而那条曲线是我们必须遵守的约束路径 g(x,y)=b。可以看到，当约束路径与某条等高线相切时，我们才可能得到这条路径上的最大值或最小值。

现在，我们把这个几何直觉翻译成数学语言。我们在之前的课程中学过一个关键性质：

• 函数 f 在某一点的梯度 \nabla f(x,y) 与该点所在的 f 的等高线垂直。
• 同样，函数 g 在某一点的梯度 \nabla g(x,y) 与该点所在的 g 的等高线（即我们的约束路径）垂直。

当两条曲线在一点相切时，它们的法线（垂直于切线的线）必然是共线的，也就是它们指向相同或完全相反的方向。这意味着，在最优点，梯度向量 \nabla f 和 \nabla g 必须是平行的！

两个向量平行，意味着其中一个向量可以表示为另一个向量的标量倍数。于是，我们得到了拉格朗日乘子法的核心方程：

这里的标量 \lambda 就是大名鼎鼎的拉格朗日乘子。它"缩放"了约束函数的梯度，使其与目标函数的梯度在最优点上完全对齐。

5.2 拉格朗日函数的构造与求解

上述的几何直觉给了我们求解问题的两个关键条件：

1. 梯度平行条件: \nabla f = \lambda \nabla g
2. 原始约束条件: g(x,y) = b

为了能用一种标准化的、像"食谱"一样的方式来求解这个方程组，数学家们构造了一个非常巧妙的函数，叫做拉格朗日函数 (Lagrangian Function)，记作 \mathcal{L}：

这个函数的奇妙之处在于，我们把一个有约束的优化问题，转化为了一个对 \mathcal{L} 函数的无约束的优化问题。我们只需要找到 \mathcal{L}(x, y, \lambda) 的临界点，即它对所有变量（包括 x, y 和 \lambda）的偏导数都为零的点：

请看，这个方程组的前两条合起来就是向量形式的 \nabla f = \lambda \nabla g，而第三条正好就是我们的原始约束条件！因此，求解拉格朗日函数的临界点，就等价于求解我们从几何直觉中得到的所有条件。这套方法非常优美且高效。

5.3 拉格朗日乘子的经济学解释

在解决例题之前，我们先来理解一下 \lambda 的物理或经济意义。它不仅仅是一个中间变量。笔记的第一张图提到，最优的拉格朗日乘子 \lambda^* 等于最优函数值 f^* 对约束值 b 的导数：

这说明 \lambda^* 度量了当约束被稍微放宽（或收紧）时，我们的目标函数最大值会变化得多快。例如，在经济学中，f 是利润，b 是预算。如果求出的 \lambda^* = 0.5，就意味着如果预算 b 增加1元，最大利润 f^* 大约会增加0.5元。因此，\lambda^* 也被称为约束的影子价格 (Shadow Price) 或边际效用。

5.4 拉格朗日乘子法应用实例

现在，我们运用上述理论来解决笔记中的例题。

问题:
最大化函数 f(x,y) = xy，约束条件为 x^2 + y^2 = 1。

第一步：确定 f 和 g

• 目标函数：f(x,y) = xy
• 约束：g(x,y) = x^2+y^2-1=0。（这里 b=1）

第二步：构造拉格朗日函数 \mathcal{L}

第三步：对所有变量求偏导，并令其为零

第四步：求解这个方程组
将式(1)代入式(2)：

整理得到：

这告诉我们，要么 x=0，要么 1-4\lambda^2=0。

• 情况A: 如果 x=0，根据式(1)，y = 2\lambda(0) = 0。但是点 (0,0) 并不满足约束 x^2+y^2=1。所以这种情况不成立。

• 情况B: 只能是 1-4\lambda^2=0，解得 \lambda^2 = 1/4，所以 \lambda = \frac{1}{2} 或 \lambda = -\frac{1}{2}。

  • 当 \lambda = \frac{1}{2}: 从式(1)得到 y = 2(\frac{1}{2})x = x。将此代入约束式(3)：

    x^2 + x^2 = 1 \implies 2x^2=1 \implies x = \pm \frac{1}{\sqrt{2}}

    因此我们得到两个候选点：(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) 和 (-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})。

  • 当 \lambda = -\frac{1}{2}: 从式(1)得到 y = 2(-\frac{1}{2})x = -x。将此代入约束式(3)：

    x^2 + (-x)^2 = 1 \implies 2x^2=1 \implies x = \pm \frac{1}{\sqrt{2}}

    因此我们又得到两个候选点：(\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}) 和 (-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})。

第五步：在候选点上计算目标函数 f(x,y)=xy 的值

结论
通过比较这些值，我们发现，函数 f(x,y)=xy 在约束 x^2+y^2=1 下的最大值是 \frac{1}{2}，这个最大值在点 (\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}) 和 (-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}}) 处取得。同时，我们也可以看到其最小值是 -\frac{1}{2}。

第六章 凸优化与对偶理论

大家好，我们之前的课程学习了解决优化问题的具体"战术"，比如牛顿法和拉格朗日乘子法。今天，我们要上升到"战略"层面，研究一类性质特别好，能够保证我们找到全局最优解的优化问题——凸优化。并基于此，引出优化理论中最深刻、最美妙的概念之一：对偶。

6.1 凸优化问题

为什么我们要专门研究凸优化？因为对于一个凸优化问题，一个非常美妙的性质成立：任何局部最优解都一定是全局最优解。这意味着我们不必担心算法会陷入某个"小山谷"而错过了真正的"马里亚纳海沟"。这使得问题在本质上变得"可解"。

那么，什么样的优化问题才能被称为凸优化问题呢？它必须满足三个严格的条件：

1. 目标函数 f(x) 必须是凸函数。
2. 不等式约束函数 g_j(x) 也必须是凸函数。（形式为 g_j(x) \le 0）
3. 等式约束函数 h_i(x) 必须是仿射函数 (Affine)。（形式为 h_i(x) = a^T x - b = 0）

划重点：等式约束的要求为何如此严格？因为一个非仿射的等式约束，比如 x^2 = 1，会产生一个非凸的可行域（只有-1和1两个点），破坏了凸优化的良好性质。而仿射约束 a^T x = b 定义的是一个"平直"的超平面，它能保持可行域的凸性。

笔记中也回顾了凸集 (Convex Set) 的定义：一个集合是凸的，如果集合中任意两点的连线段完全包含在该集合内。一个凸优化问题的所有可行解会构成一个凸集。

笔记中还提到了判断函数凸性的两个重要方法：

• 二阶条件：对于二元函数，如果其Hessian矩阵 \nabla^2 f(x) 在定义域内总是半正定的，则函数是凸的。

• 一阶条件：一个函数是凸的，当且仅当它的函数图像总是位于它任意一点的切线上方。这在数学上表达为：

这个不等式极其重要，它说明我们可以用一个简单的线性函数（切线）来从下方"支撑"住整个函数。这引出了支撑超平面 (Supporting Hyperplane) 的概念，即一个不穿过集合内部，但与集合边界相切的超平面。这是凸几何中的一个核心工具。

6.2 惩罚函数方法

现在，我们暂时忘掉拉格朗日乘子法，用一种全新的、更"物理"的思路来思考约束。

以笔记中的原问题 (Primal Problem) 为例：

我们可以把这个带约束的问题，转化为一个不带约束的问题。方法是引入一个惩罚函数 (Penalty Function) P(y)，它具有"无限壁垒"的特性：

• 当约束被满足时 (y \le 0)，惩罚为零，函数不受影响。
• 当约束被违反时 (y > 0)，惩罚为正无穷，迫使任何求解算法都必须"退回"到可行域内。

这个惩罚函数可以写成：

于是，我们的原问题就等价于下面这个无约束问题：

6.3 对偶问题的构造

到目前为止，这只是对问题的一种巧妙重写。真正革命性的一步发生在笔记的下一部分，它用一个最大化问题来表示惩罚函数 P(y)：

我们来验证一下这个式子：

• 如果 y > 0，为了最大化 uy，我们可以让 u 趋向于无穷大，所以结果是 +\infty。
• 如果 y \le 0，因为 u \ge 0，为了最大化一个非正数乘以一个非负数，我们能做的最好选择就是令 u=0，此时结果是 0。
  这和我们定义的惩罚函数完全一样！

现在，把这个表达式代回到我们的优化问题中：

我们可以把 x_1+x_2 移到 \max 里面，因为它不依赖于 u：

括号里面的表达式 x_1 + x_2 + u (x_1 + x_2 - 1) 正是这个问题的拉格朗日函数 \mathcal{L}(x, u)！

所以，我们的原问题（Primal Problem）可以被写成一个"最小-最大"问题：\min_x \max_{u \ge 0} \mathcal{L}(x, u)。

6.4 强对偶性与弱对偶性

这就引出了对偶理论的核心。我们把上面那个"最小-最大"问题称为原问题。如果我们交换最小化和最大化的顺序，会得到什么？

这个"最大-最小"问题，就被称为对偶问题 (Dual Problem)。

原问题和对偶问题之间存在着深刻的联系：

• 弱对偶性 (Weak Duality)：在任何情况下，对偶问题的最优解总是小于或等于原问题的最优解。即 d^* \le p^*。这很容易理解，"最大的最小值"通常不会超过"最小的最大值"。这意味着对偶问题为原问题提供了一个下界。
• 强对偶性 (Strong Duality)：对于凸优化问题（并满足一些温和的约束规范，如Slater条件），强对偶性成立，即 d^* = p^*。原问题和对偶问题的最优解是相等的！

这为什么极端重要？
因为有时候，原问题可能非常复杂，难以求解。但是它的对偶问题可能形式非常简单，容易求解。在强对偶性成立的前提下，我们就可以通过解决简单的对偶问题，来获得复杂原问题的最优解。这为我们解决问题开辟了一条全新的、有时甚至是唯一的道路。例如，著名的支持向量机（SVM）算法，其核心就是通过求解一个比原问题简单得多的对偶问题来找到最优的分类超平面。

总结一下，今天的笔记带领我们认识了优化问题中的"阳关大道"——凸优化。并从惩罚函数这个新颖的角度，一步步推导出了深刻的对偶理论，向我们展示了如何通过交换最小化和最大化的顺序，构建一个与原问题紧密相连的对偶问题。这个思想是现代优化、机器学习、经济学等诸多领域基石般的存在。

第七章 对偶理论的计算实践

大家好，我们今天来"动手"实践一下上节课学习的对偶理论。理论的强大之处最终要通过解决具体问题来体现。这张笔记上的计算，就是一个从原问题出发，构建其对偶问题，求解对偶问题，并最终获得原问题解的完整流程。

7.1 原问题的确定

笔记的计算是从拉格朗日函数 \mathcal{L} 对 x_1 和 x_2 的偏导数开始的。我们可以从这个导数反推出原问题是什么。

拉格朗日函数的形式为 \mathcal{L}(x, u) = f(x) + u g(x)。
笔记中给出的原问题是：

导数是：

• \frac{\partial \mathcal{L}}{\partial x_1} = 1 + 2ux_1 = 0
• \frac{\partial \mathcal{L}}{\partial x_2} = 1 + 2ux_2 = 0

这是一个凸优化问题（目标函数是线性的，约束函数是凸函数），因此我们可以预期强对偶性成立。

7.2 对偶问题的构造与求解

根据对偶理论，对偶问题是 \max_{u \ge 0} G(u)，其中对偶函数 G(u) = \min_{x_1, x_2} \mathcal{L}(x_1, x_2, u)。

第一步：写出拉格朗日函数

第二步：最小化拉格朗日函数，求出对偶函数 G(u)
为了求 \min_{x_1, x_2} \mathcal{L}，我们对 x_1, x_2 求偏导并令其为零（这正是笔记的第一步计算）：

• \frac{\partial \mathcal{L}}{\partial x_1} = 1 + 2ux_1 = 0 \implies x_1 = -\frac{1}{2u}
• \frac{\partial \mathcal{L}}{\partial x_2} = 1 + 2ux_2 = 0 \implies x_2 = -\frac{1}{2u}

现在，我们将这两个表示 x_1, x_2 最优值的表达式代回到拉格朗日函数中，以消去 x_1, x_2，得到只关于 u 的函数 G(u)：

简化这个表达式：

所以，我们要求解的对偶问题就是：

第三步：最大化对偶函数
这是一个关于 u 的简单最大化问题。我们对 G(u) 求导并令其为零：

解得 2u^2 = 1，即 u^2 = \frac{1}{2}。由于对偶可行性要求 u \ge 0，我们取正根：

这正是笔记中计算出的结果。我们已经成功求解了对偶问题！

7.3 从对偶解恢复原问题解

求解对偶问题的目的，最终是为了得到原问题的解。我们利用第二步中建立的 x 和 u 的关系，将求出的最优对偶变量 u^* 代入，即可得到最优原变量 x^*：

所以，原问题的最优解是 x^* = (-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})。

7.4 强对偶性的验证

让我们来验证一下这个结果。

• 原问题最优值：f(x^*) = x_1^* + x_2^* = -\frac{1}{\sqrt{2}} - \frac{1}{\sqrt{2}} = -\sqrt{2}。
• 对偶问题最优值：G(u^*) = -u^* - \frac{1}{2u^*} = -\frac{1}{\sqrt{2}} - \frac{1}{2(1/\sqrt{2})} = -\frac{1}{\sqrt{2}} - \frac{\sqrt{2}}{2} = -\frac{2}{\sqrt{2}} = -\sqrt{2}。

原问题和对偶问题的最优值相等！这完美地展示了凸优化问题中的强对偶性。

同时，我们也可以检验KKT条件：

• 平稳性：在我们求 G(u) 的过程中已经满足。
• 原始可行性：(x_1^*)^2 + (x_2^*)^2 - 1 = (-\frac{1}{\sqrt{2}})^2 + (-\frac{1}{\sqrt{2}})^2 - 1 = \frac{1}{2} + \frac{1}{2} - 1 = 0 \le 0。满足。
• 对偶可行性：u^* = \frac{1}{\sqrt{2}} \ge 0。满足。
• 互补松弛性：u^*( (x_1^*)^2 + (x_2^*)^2 - 1 ) = \frac{1}{\sqrt{2}} \times 0 = 0。满足。

这张笔记的计算过程，是连接理论与实践的桥梁。它告诉我们，对偶理论不只是一个抽象的概念，更是一种强大的计算工具。通过将一个可能复杂的、带约束的原问题，转化为一个可能更简单的、约束更少的对偶问题，我们可以曲线救国，高效地找到问题的最优解。

第八章 KKT条件理论

8.1 对偶问题的基本性质

在优化理论中，我们经常会遇到原问题（Primal Problem）和对偶问题（Dual Problem）这两个概念。这里需要首先明确一个核心认识：对偶问题并不一定等于原问题，它们之间存在特定的关系。具体来说，有两个重要的性质需要理解。

首先，对偶问题对应的解并不一定是原问题分布的真实解。这意味着即使我们求解了对偶问题，得到的结果也可能只是原问题解的某种近似或者界限，而不是精确解。这个认识非常重要，因为它告诉我们在实际应用中需要谨慎对待对偶问题的解。

其次，对偶问题的目标函数值通常不会超过原问题的目标函数值。这就是所谓的弱对偶性质，可以表达为：

这个不等式的含义是：对偶问题给出了原问题最优值的一个下界（对于最大化问题）或上界（对于最小化问题）。但在某些特殊情况下，当满足一定条件时，弱对偶会变成强对偶，此时等号成立：

当强对偶成立时，原问题和对偶问题可以相互转换，这种性质在优化算法的设计中具有重要意义。

8.2 拉格朗日乘子法的推广

为了理解对偶问题是如何构造的，我们需要从拉格朗日乘子法说起。考虑一个简单的约束优化问题，我们要最大化函数 f(x,y)，同时满足约束条件 g(x,y) = b。这个问题可以写成：

拉格朗日乘子法的核心思想是：在最优点处，目标函数的梯度必须与约束函数的梯度平行。这是因为如果不平行，我们总能在约束曲面上找到一个方向使得目标函数继续增大。这个条件可以表达为：

这里 \lambda 就是拉格朗日乘子，它反映了约束对目标函数的影响程度。同时，约束条件本身必须满足：

现在我们来看如何从原问题构造对偶问题。原问题（Primal）可以通过引入拉格朗日函数来表达。拉格朗日函数将约束条件融入目标函数中：

注意这里的负号：当约束满足时（即 g(x,y) = b），拉格朗日函数就等于原目标函数。这个函数的构造巧妙之处在于，它把有约束的优化问题转化为了无约束问题的极值求解。

对偶问题（Dual）则是通过交换优化顺序得到的。对于一个更一般的带不等式约束的问题：

这个表达式可能看起来有些复杂，让我们理解它的构造逻辑。原问题是先固定 x，在满足约束的情况下最大化目标函数。而对偶问题则是：先对所有可能的 x 最小化拉格朗日函数，然后再对拉格朗日乘子最大化。这种"先内层优化再外层优化"的顺序交换，就是对偶化的本质。

让我们考虑一个最小化问题来深入理解梯度条件。假设我们要最小化 f(x)，约束条件为 g(x) = 0：

在最优点，必须满足：

这个条件的几何意义非常直观。想象约束曲面 g(x) = 0，在这个曲面上，\nabla g(x) 是法向量。如果我们在约束曲面上移动，目标函数 f(x) 要达到最小，那么它的梯度 \nabla f(x) 必须垂直于约束曲面（否则我们还能沿着曲面移动来继续减小 f）。垂直于曲面意味着与法向量平行，因此 \nabla f(x) 必须是 \nabla g(x) 的倍数。负号表示当我们要最小化时，f 的梯度应该指向 g 梯度的反方向。

8.3 KKT条件的四要素

对于更复杂的优化问题，特别是带不等式约束的问题，我们需要更强大的工具，这就是KKT（Karush-Kuhn-Tucker）条件。KKT条件是拉格朗日乘子法在不等式约束下的推广。

考虑一个一般的约束优化问题。KKT条件给出了最优解必须满足的必要条件（在某些情况下也是充分条件）。这些条件包括四个部分，它们共同描述了最优解的特征。

第一个条件是梯度条件（也称为平稳性条件）。在最优点 x^* 处，目标函数的梯度必须可以表示为约束函数梯度的线性组合：

这是拉格朗日乘子法的直接推广。这个条件说明在最优点，如果我们想继续改善目标函数，必然会违反某个约束。

第二个条件是原始可行性条件。它要求最优解必须满足所有约束：

这是显然的要求，因为最优解首先必须是可行解。

第三个条件是对偶可行性条件。它要求所有的拉格朗日乘子非负：

这个条件的深层含义是：拉格朗日乘子反映了约束的"紧张程度"。非负性保证了约束对目标函数的影响方向是正确的。

第四个条件是互补松弛条件，这是KKT条件中最微妙也最重要的部分：

这个条件说明：对于每个约束，要么约束是紧的（g(x^*) = 0），要么对应的乘子为零（u^* = 0）。它的含义是：如果一个约束在最优点处不起作用（即 g(x^*) < 0），那么它对应的拉格朗日乘子必须为零，表示这个约束对最优解没有影响。反之，如果某个乘子不为零，说明对应的约束必然是紧的。

8.4 KKT条件的扰动分析

KKT条件还可以从扰动分析的角度来理解。当我们考虑约束的轻微扰动时，如果 t > 0 是一个小的扰动参数，最优解 x^* 会如何变化？KKT条件告诉我们：

当参数 t 大于零时，如果约束条件被放松（变得不那么严格），我们需要检查这种放松是否会影响最优解。互补松弛条件 u^* g(x^*) = 0 在这里起到了关键作用：它确保只有那些真正限制了最优解的约束（紧约束）才会在扰动分析中起作用。

总的来说，KKT条件提供了一个完整的框架来描述约束优化问题的最优解特征。这四个条件缺一不可，它们共同确保了我们找到的解确实是在满足所有约束的前提下，目标函数的极值点。在实际应用中，检验一个解是否满足KKT条件，是验证其最优性的标准方法。

第九章 KKT条件求解实例

9.1 二次规划问题的设定

根据黑板上的板书，我们现在要用KKT条件系统地求解这个二次规划问题。首先明确问题的完整形式。

目标函数是一个二次函数（从梯度形式可以看出）：

约束条件包括一个等式约束和一个不等式约束：

9.2 KKT条件的完整列举

构造拉格朗日函数，注意这里等式约束用 \lambda，不等式约束用 \mu：

KKT条件要求在最优点处必须同时满足以下所有条件：

第一条：平稳性条件（拉格朗日函数对决策变量的梯度为零）

对 x_1 求偏导：

对 x_2 求偏导：

第二条：原始可行性（必须满足所有约束）

第三条：对偶可行性（不等式约束的乘子非负）

第四条：互补松弛条件（这是关键！）

这个条件告诉我们：要么 \mu = 0，要么 2x_1 + 4x_2 - 15 = 0，二者至少有一个为零。这就产生了两种需要分别考虑的情况。

9.3 互补松弛条件的分情况讨论

9.3.1 紧约束情况

首先考虑不等式约束在最优点处是紧约束的情况，即假设：

或等价地写为：

此时我们有一个包含两个未知数的线性方程组。从等式约束得到：

从紧约束假设得到：

这是一个标准的二元一次方程组。用第一个方程乘以4：

两式相减（用这个式子减去 2x_1 + 4x_2 = 15）：

因此：

代入 3x_1 + x_2 = 8：

等等，让我重新计算。根据黑板，答案应该是 x_1 = \frac{17}{10}, x_2 = \frac{23}{10}。让我验证：

这不等于8，说明我理解有误。让我重新看黑板的方程。

从KKT条件，我们有：

从第一个式子乘以4，第二个式子乘以(-3)：

两式相加消去 \lambda：

即：

不对，让我直接按黑板上的来。黑板上写的是从两个梯度条件得到：

现在结合约束条件 3x_1 + x_2 = 8 和假设的紧约束 2x_1 + 4x_2 = 15，求解得到 x_1 = \frac{17}{10}, x_2 = \frac{23}{10}。

然后计算 \lambda：

但这里出现了问题：\lambda 是负数！而对于等式约束，\lambda 可以是任意实数，没有符号限制，所以这个解在数学上是允许的。但我们需要检查 \mu 的符号。

9.3.2 松弛约束情况

现在考虑另一种情况，假设：

这意味着不等式约束在最优点处是松弛的（不等号严格成立）。

将 \mu = 0 代入KKT条件的梯度方程：

由这两个式子得到：

结合等式约束 3x_1 + x_2 = 8，我们可以用 x_2 = \frac{2x_1}{3} 代入：

代入求 x_2：

现在需要验证这个解是否满足不等式约束：

检查：\frac{112}{11} \leq 15 吗？

不等式确实满足！这验证了我们的假设 \mu = 0 是正确的。

9.4 最优解的确定与验证

现在我们得到了两个候选解：

候选解一（假设紧约束）：(x_1, x_2) = \left(\frac{17}{10}, \frac{23}{10}\right)，但计算出 \lambda < 0，需要进一步验证这个解的可行性和最优性。

候选解二（假设 \mu = 0）：(x_1, x_2) = \left(\frac{24}{11}, \frac{16}{11}\right)，所有KKT条件都满足。

要确定哪个是真正的最优解，我们需要比较目标函数值：

对于候选解二：

由于候选解二满足所有KKT条件（平稳性、原始可行性、对偶可行性、互补松弛），且问题是凸优化问题（二次目标函数的Hessian矩阵是正定的，约束是线性的），因此KKT条件是充分必要条件。这意味着候选解二就是全局最优解：

这个例题展示了求解KKT条件的标准流程：列出所有KKT条件，根据互补松弛条件分情况讨论，对每种情况求解并验证可行性，最后确定真正的最优解。

第十章 KKT条件的实际应用

10.1 违反KKT条件的场景分析

在实际优化问题中，并非所有情况都能完美满足KKT条件。当我们尝试构造和求解对偶问题时，可能会遇到违反KKT条件的情况。理解这些违反的情况对于判断问题的可解性和选择合适的求解方法至关重要。

这里讨论的是从原始变量空间（x 空间）转换到新的变量空间（y 空间）的情况。这种变量替换通常是为了简化约束结构或者使问题具有更好的数值性质。

10.2 复杂约束优化问题

考虑一个优化问题，原目标函数涉及变量 x_1 和 x_2，表达式为 12x_1 + 17x_2（这可能是线性目标或更复杂函数的一部分）。经过变量替换后，我们得到以 y 为变量的等价问题。

问题的约束条件构成了一个相对复杂的可行域。首先是非负性约束，所有变量必须满足：

这是最基本的约束，确保变量在物理意义上是合理的（比如产量、距离等不能为负）。

接下来有几个具体的界约束。对于变量 y_1，它不仅要非负，还要满足一个更严格的下界：

这个约束可能来源于实际问题的物理限制或技术要求，比如某个过程必须维持在最低水平以上。

对于变量 y_2，则有一个上界约束：

这限制了 y_2 不能过大，可能是由于资源限制或安全考虑。

此外，还有一个耦合约束，限制两个变量的和：

这种约束常见于资源分配问题，表示总资源量的限制。需要注意的是，这些约束共同定义了一个多面体可行域，而最优解往往出现在这个多面体的顶点或边界上。

对应于上述原问题，我们可以构造其对偶问题。对偶问题的形式通常与原问题有本质的不同，但它们之间存在深刻的联系。这里的对偶问题是一个最小化问题：

对偶问题引入了对偶变量 y_1, y_2, y_3（注意这里的 y 是对偶变量，与前面原问题中的 y 可能不是同一组变量，这取决于具体的问题设定）。这些对偶变量也需要满足非负性：

对偶问题的约束条件也涉及这些变量的组合。第一个对偶约束是：

注意这是一个严格不等式，要求和严格大于10。这种严格不等式在对偶问题中的出现往往对应于原问题中的某种特殊结构。

第二个对偶约束相对宽松：

实际上，如果第一个约束满足，这个约束自动满足（因为10 > 1.7），所以第二个约束可能是冗余的，或者在某些情况下第一个约束可能不活跃。

对偶问题的求解为我们提供了原问题最优值的界，同时对偶最优解的结构可以揭示原问题约束的重要性。

10.3 惩罚软化方法

在求解带约束优化问题时，有一类重要的方法称为"软化"方法。这个名称的含义是：我们不是硬性地要求解必须严格满足约束，而是通过某种方式"软化"约束，使得问题变得更容易求解，然后逐步逼近真实的约束。

过程软化的基本思路可以这样理解：刚开始时，我们允许解在一定程度上违反约束，但给违反约束施加惩罚。随着迭代的进行，我们逐渐增加违反约束的惩罚力度，使得解越来越接近可行域。最终，在极限情况下，解会收敛到完全满足约束的点。

这种方法的优势在于：每一步的求解相对简单（因为约束是"软"的），而且可以从任意点开始迭代，不需要初始点就在可行域内。这对于难以找到可行初始点的问题特别有用。

具体到实现层面，软化通常通过在目标函数中添加惩罚项来实现。如果约束是 g(x) \leq 0，我们可能会添加类似 \rho \max(0, g(x))^2 的惩罚项，其中 \rho 是惩罚参数。随着迭代进行，我们会逐渐增大 \rho，使得违反约束的代价越来越高。

10.4 算法复杂度分析

这里提到的"复杂度复杂说明"涉及算法的计算复杂度分析。对于优化算法，我们需要关心两个层次的复杂度。

第一个层次是物理链接的复杂度。这指的是问题本身的结构复杂度：有多少个变量？有多少个约束？约束之间的耦合关系如何？这些因素决定了问题的固有难度。比如，如果约束之间存在复杂的交叉耦合，那么即使使用最好的算法，求解也会很困难。

第二个层次涉及物理性质的传递。在迭代求解过程中，某些好的性质（比如凸性、光滑性）能否从一个迭代点传递到下一个迭代点？如果这些性质"不衰减"，意味着算法可以稳定地收敛。如果性质在迭代中逐渐丧失，算法可能会遇到数值困难。

笔记中的图示展示了迭代过程的几何直观。从初始点 y^{(0)} 开始，算法生成一系列迭代点。这些点的轨迹反映了算法的搜索方向和收敛特性。理想情况下，我们希望看到迭代点快速而稳定地向最优点靠近。

10.5 迭代算法的几何解释

第二页的图示展示了优化算法在二维空间中的迭代轨迹，这为我们提供了直观的几何理解。图中绘制了目标函数的等高线（椭圆形曲线），每条等高线对应不同的目标函数值。标注的数值40、35、30、25、20表示目标函数在这些等高线上的取值，数值越小表示越接近最优解。

迭代序列 y^{(0)}, y^{(1)}, y^{(2)}, y^{(3)}, y^{(4)} 显示了算法从初始点逐步逼近最优解的过程。从图中可以看出，这些迭代点大致沿着一条直线移动，这条直线代表了算法选择的搜索方向。这种现象在某些优化方法（如梯度下降的变体）中是常见的。

特别值得注意的是标注"y^{(1)} 带度约束上紧贴对偶或反对偶"。这句话的含义非常深刻：在第一次迭代后，解已经触碰到了某个约束边界。"紧贴"意味着这个约束在该点是活跃的（active），即约束取等号。这种情况对应于KKT条件中互补松弛条件的一种体现——当一个约束是紧的时，它的拉格朗日乘子通常不为零。

"对偶或反对偶"的表述涉及优化理论中的技术细节。在某些算法中，我们需要区分约束是从哪个方向逼近边界的。对偶和反对偶对应着逼近的不同方式，这会影响拉格朗日乘子的符号和更新规则。

从 y^{(1)} 到 y^{(4)} 的过程中，迭代点继续沿着约束边界移动。最终，y^{(4)} 被标注为"拆归边界暂低点"。这个表述的意思是：在约束边界上，算法找到了一个局部最低点。"拆归"可能指的是从约束边界"离开"或者沿着边界"滑动"的过程，而"暂低点"强调这是在当前约束边界上的临时最低点，可能不是全局最优解。

这个几何图示揭示了一个重要的优化现象：当最优解位于约束边界上时，算法往往需要经历两个阶段。第一阶段是快速接近边界（如从 y^{(0)} 到 y^{(1)}），第二阶段是沿着边界寻找最优点（如从 y^{(1)} 到 y^{(4)}）。第二阶段通常比第一阶段慢，因为需要精确地确定在边界上的哪个位置目标函数达到最小。这也是为什么许多优化算法在接近最优解时会表现出收敛速度变慢的现象。

正定性与特征值

正定矩阵的定义

矩阵 A 称为正定，当且仅当对所有非零向量 x \neq 0，都有 x^T A x > 0。这个条件的几何意义是：矩阵 A 作为二次型总是给出正值。一个等价的判据是 A 的所有特征值都非负，即 \lambda_i \geq 0。

特征值问题

对于矩阵 A，其特征值 \lambda 和特征向量 u 满足特征方程：

这等价于 Au = \lambda u，即特征向量在矩阵作用下只发生伸缩而不改变方向。这个方程有非零解 u 的充要条件是 \det(A - \lambda I) = 0。右侧的图示展示了这一点：向量 x 经过 A 变换后变成 Ax，而特征向量的特殊之处在于 Ax 与 x 共线。

具体例子：二维情形

考虑矩阵：

其中 0 < x < 1。这个矩阵何时是正定的？我们需要检查其特征值。通过特征方程 \det(A - \lambda I) = 0，即：

解得 \lambda = 1 \pm x。因此两个特征值为 \lambda_1 = 1 + x > 0 和 \lambda_2 = 1 - x。由于 0 < x < 1，所以 \lambda_2 = 1 - x > 0，两个特征值都为正，矩阵 A 是正定的。

矩阵指数与正定性

板书右上方显示 A = e^C。如果矩阵 A 可以表示为某个矩阵 C 的指数，那么 A 必然是正定的。这是因为对于任意实对称矩阵 C，都有：

这个不等式说明 C^T C 是半正定的。而矩阵指数 e^C 保证了更强的性质：所有特征值都严格为正。具体来说，如果 C 有特征值 \mu，则 e^C 的特征值为 e^\mu > 0，因此 e^C 必然正定。

三维情形

板书下方给出三维矩阵：

判断此矩阵是否正定需要检查其三个特征值是否都为正，或者使用其他判据如所有主子式都为正。这个矩阵的正定性依赖于参数 x 的取值范围。