最优化理论期末复习

复习课大纲

1. 线性优化 LP 建模
2. 二维的图解法 LP
3. 单纯形表 LP（大M法）闭合、位势 $(u,v)$
4. 运输问题（建模，初始值，检验数，负的检验数用闭回路调整）
5. 指派问题（匈牙利算法）
6. 相关概念、定理（凸集、凸函数、性质、定理）
7. 无约束（最速下降法、牛顿法）
8. 最优性定理（有、无约束，一阶、二阶、KKT条件）
9. 罚函数法、障碍函数的构造
10. 遗传算法

22～23最优化理论真题

一、用图解法求解线性规划问题

题目： 用图解法求解线性规划问题（$10$ 分）

$$\min \quad f = x_1 + x_2 \quad s.t. \begin{cases} x_1 + x_2 \leq 3 \\ x_1 \leq x_2 \\ x_1 \geq 1 \end{cases}$$

第一步：将约束条件转化为等式直线方程

将各不等式约束取等号，得到三条约束直线：

• $x_1 + x_2 = 3$，该直线过点 $(0, 3)$ 和 $(3, 0)$，可行域位于直线下方；
• $x_1 = x_2$，该直线为过原点的 $45^\circ$ 直线，可行域位于直线上方（即 $x_2 \geq x_1$）；
• $x_1 = 1$，该直线为垂直于 $x_1$ 轴的直线，可行域位于直线右侧（即 $x_1 \geq 1$）。

第二步：求各约束直线的交点（可行域顶点）

联立各约束直线方程，求可行域的顶点坐标：

• $x_1 = 1$ 与 $x_1 = x_2$ 联立：$x_1 = 1$，代入得 $x_2 = 1$，得交点 $A(1, 1)$；
• $x_1 = 1$ 与 $x_1 + x_2 = 3$ 联立：$1 + x_2 = 3$，解得 $x_2 = 2$，得交点 $B(1, 2)$；
• $x_1 = x_2$ 与 $x_1 + x_2 = 3$ 联立：$2x_1 = 3$，解得 $x_1 = \dfrac{3}{2}$，$x_2 = \dfrac{3}{2}$，得交点 $C\left(\dfrac{3}{2}, \dfrac{3}{2}\right)$。

三条直线围成的三角形区域 $ABC$ 即为可行域。

第三步：绘制图形并分析目标函数

第四步：分析目标函数等值线

目标函数 $f = x_1 + x_2$ 的等值线方程为 $x_1 + x_2 = c$（$c$ 为常数），即 $x_2 = -x_1 + c$。这是一族斜率为 $-1$ 的平行直线。最小化 $f$ 等价于使等值线沿目标函数梯度方向 $(1, 1)$ 的反方向移动，即让常数 $c$ 不断减小。

第五步：确定最优解与最优值

将可行域的三个顶点分别代入目标函数计算：

• 在点 $A(1, 1)$ 处：$f = 1 + 1 = 2$；
• 在点 $B(1, 2)$ 处：$f = 1 + 2 = 3$；
• 在点 $C\left(\dfrac{3}{2}, \dfrac{3}{2}\right)$ 处：$f = \dfrac{3}{2} + \dfrac{3}{2} = 3$。

当等值线 $x_1 + x_2 = 2$ 移动到点 $A(1, 1)$ 时，$c$ 取到最小值 $2$。若继续沿反方向移动，等值线将完全离开可行域。因此，最优解在顶点 $A$ 处取得。

结论：

最优解为 $(x_1^*, x_2^*) = (1, 1)$，最优值为 $f^* = 2$。

评分标准对应：

• 正确画出 $3$ 条约束直线各 $1$ 分；
• 正确画出可行域 $2$ 分；
• 正确求出约束直线的交点 $2$ 分；
• 正确求出最优值和最优解 $3$ 分。

叙述并证明无约束最优化问题的一阶必要条件

无约束最优化问题的一般形式为：

$$\min_{x \in \mathbb{R}^n} f(x)$$

其中 $f: \mathbb{R}^n \to \mathbb{R}$ 为连续可微的目标函数。所谓”无约束”，是指决策变量 $x$ 在整个 $n$ 维欧氏空间 $\mathbb{R}^n$ 中自由取值，不受到任何等式或不等式约束的限制。

一阶必要条件（定理3）

设 $f(x)$ 在 $x^*$ 的某个邻域内有连续的偏导数（即 $f$ 在 $x^*$ 附近连续可微），若 $x^*$ 是 $f(x)$ 的局部最优解，则

$$\nabla f(x^*) = 0$$

也就是说：若 $x^*$ 是局部最优解，则它在该点处的梯度必须为零向量。

满足 $\nabla f(x^*) = 0$ 的点称为驻点（Stationary Point）或临界点（Critical Point）。驻点可能为局部极小点、局部极大点或鞍点，因此梯度为零只是极值点的必要条件，而非充分条件。

预备知识

在正式证明之前，先回顾几个关键概念和运算规则：

（1）梯度（Gradient）的定义

对于多元函数 $f(x_1, x_2, \dots, x_n)$，它在点 $x$ 处的梯度是一个列向量，由所有一阶偏导数组成：

$$\nabla f(x) = \begin{pmatrix} \dfrac{\partial f}{\partial x_1} \\ \dfrac{\partial f}{\partial x_2} \\ \vdots \\ \dfrac{\partial f}{\partial x_n} \end{pmatrix}$$

例如 $f(x_1, x_2) = x_1^2 + x_2^2$，则 $\dfrac{\partial f}{\partial x_1} = 2x_1$，$\dfrac{\partial f}{\partial x_2} = 2x_2$，于是：

$$\nabla f(x) = \begin{pmatrix} 2x_1 \\ 2x_2 \end{pmatrix}$$

（2）可微的定义

函数 $f$ 在点 $x^*$ 处可微（Differentiable），是指存在向量 $g \in \mathbb{R}^n$，使得对任意方向 $d \in \mathbb{R}^n$，有：

$$f(x^* + d) = f(x^*) + g^T d + o(\|d\|)$$

其中 $o(\|d\|)$ 表示高阶无穷小，即满足 $\lim\limits_{\|d\| \to 0} \dfrac{o(\|d\|)}{\|d\|} = 0$。直观理解就是：当 $d$ 很小时，$o(\|d\|)$ 比 $\|d\|$ 衰减得更快，可以忽略不计。

可以证明这个向量 $g$ 就是梯度 $\nabla f(x^*)$，因此上式也常写为：

$$f(x^* + d) = f(x^*) + \nabla f(x^*)^T d + o(\|d\|)$$

（3）向量内积的运算规则

对于两个 $n$ 维列向量 $a = (a_1, a_2, \dots, a_n)^T$ 和 $b = (b_1, b_2, \dots, b_n)^T$，它们的内积（点积）为：

$$a^T b = \sum_{i=1}^{n} a_i b_i = a_1 b_1 + a_2 b_2 + \dots + a_n b_n$$

特别地，一个向量与自身的内积等于它的模长平方：

$$a^T a = \sum_{i=1}^{n} a_i^2 = \|a\|^2$$

（4）方向导数

函数 $f$ 在点 $x^*$ 沿方向 $d$ 的方向导数，衡量了 $f$ 在该方向上的瞬时变化率。当 $f$ 可微时：

$$\lim_{t \to 0} \frac{f(x^* + td) - f(x^*)}{t} = \nabla f(x^*)^T d$$

若 $\nabla f(x^*)^T d < 0$，说明沿方向 $d$ 移动时，函数值会下降。

证明：

采用反证法。设 $x^*$ 为 $f(x)$ 的局部最优解，假设 $\nabla f(x^*) \neq 0$。

由于 $f(x)$ 在 $x^*$ 的某个邻域内有连续的偏导数，根据一阶泰勒展开公式，对 $x^*$ 附近的任意点 $x$，有：

$$f(x) = f(x^*) + \nabla f(x^*)^T (x - x^*) + o(\|x - x^*\|)$$

移项得到函数值的增量：

$$f(x) - f(x^*) = \nabla f(x^*)^T (x - x^*) + o(\|x - x^*\|)$$

其中 $x - x^*$ 表示从 $x^*$ 指向 $x$ 的位移向量，$\|x - x^*\|$ 为该位移的模长（距离），$o(\|x - x^*\|)$ 为比 $\|x - x^*\|$ 更高阶的无穷小。

为什么要取负梯度方向？

我们的目标是找到一个方向 $d = x - x^*$，使得沿该方向移动时，函数值 $f(x)$ 能够下降（这样才能与”$x^*$ 是局部最优解”产生矛盾）。

由于 $f$ 可微，函数值的一阶近似增量为 $\nabla f(x^*)^T (x - x^*)$。我们希望这个一阶项是负的（即函数值下降）。

为什么 $x - x^*$ 能直接等于 $-\nabla f(x^*)$？

首先明确各量的维度：

• $x$ 和 $x^*$ 都是 $n$ 维欧氏空间 $\mathbb{R}^n$ 中的点（也就是 $n$ 维向量）；
• $\nabla f(x^*)$ 是 $f$ 在 $x^*$ 处的梯度，也是 $\mathbb{R}^n$ 中的一个 $n$ 维向量。

因此：

• $x - x^*$ 是两个 $n$ 维向量的差，结果仍然是 $\mathbb{R}^n$ 中的 $n$ 维向量（表示从 $x^*$ 指向 $x$ 的位移向量）；
• $-\nabla f(x^*)$ 也是 $\mathbb{R}^n$ 中的 $n$ 维向量（表示负梯度方向向量）。

既然两者都是同维度的向量，就可以直接令它们相等。这相当于在说：我主动构造一个新的点 $x$，使得从 $x^*$ 到 $x$ 的位移恰好是负梯度方向，即：

$$x = x^* - \nabla f(x^*)$$

由于这是无约束优化问题，$x$ 的取值范围是整个 $\mathbb{R}^n$，所以上面的 $x$ 当然是一个合法的点。

验证：代入后一阶项的符号

现在把 $x - x^* = -\nabla f(x^*)$ 代入一阶项 $\nabla f(x^*)^T (x - x^*)$：

$$\begin{aligned} \nabla f(x^*)^T (x - x^*) &= \nabla f(x^*)^T \bigl(-\nabla f(x^*)\bigr) \\[8pt] &= -\nabla f(x^*)^T \nabla f(x^*) \\[8pt] &= -\|\nabla f(x^*)\|^2 \end{aligned}$$

这里一步步来：

• 第一步：将 $x - x^* = -\nabla f(x^*)$ 代入括号内；
• 第二步：利用内积对负号的分配律：$a^T(-b) = -(a^T b)$，提出负号；
• 第三步：利用自身内积等于模长平方的性质：$a^T a = \|a\|^2$，得到 $\nabla f(x^*)^T \nabla f(x^*) = \|\nabla f(x^*)\|^2$。

由于反证法假设了 $\nabla f(x^*) \neq 0$，所以 $\|\nabla f(x^*)\|^2 > 0$，于是：

$$\nabla f(x^*)^T (x - x^*) = -\|\nabla f(x^*)\|^2 < 0$$

这说明沿负梯度方向移动时，一阶项严格小于零，函数值有下降的趋势。

从几何上看：梯度 $\nabla f(x^*)$ 指向函数值增长最快的方向，那么负梯度方向 $-\nabla f(x^*)$ 自然就是函数值下降最快的方向。

为什么需要引入步长参数 $t$？

上面的分析只说明了”方向正确”，但还有一个关键问题：如果我们直接令 $x - x^* = -\nabla f(x^*)$，一步跨过去的距离 $\|\nabla f(x^*)\|$ 可能太大，导致 $x = x^* - \nabla f(x^*)$ 已经跳出了 $x^*$ 的局部最优邻域（局部最优只保证邻域内最优，远处可能更大也可能更小）。

因此，我们需要引入一个很小的正数 $t$ 作为步长，控制移动距离：

$$x - x^* = -t \nabla f(x^*)$$

也就是：

$$x = x^* - t \nabla f(x^*)$$

这样，位移的大小为 $\|x - x^*\| = t \|\nabla f(x^*)\|$。只要取 $t > 0$ 充分小，就能保证 $x$ 仍然落在 $x^*$ 的局部最优邻域内（因为局部最优要求在 $x^*$ 的某个邻域内 $f(x^*)$ 最小）。

验证：把负梯度方向代入增量公式

在正式展开之前，先做一个快速验证——将 $x - x^* = -\nabla f(x^*)$（即 $t = 1$ 的特殊情况）直接代入一阶泰勒展开的增量公式：

$$\begin{aligned} f(x) - f(x^*) &= \nabla f(x^*)^T (x - x^*) + o(\|x - x^*\|) \\[8pt] &= \nabla f(x^*)^T \bigl(-\nabla f(x^*)\bigr) + o(\|\nabla f(x^*)\|) \\[8pt] &= -\|\nabla f(x^*)\|^2 + o(\|\nabla f(x^*)\|) \end{aligned}$$

其中 $-\|\nabla f(x^*)\|^2$ 是一个固定的负数（因为 $\nabla f(x^*) \neq 0$），而 $o(\|\nabla f(x^*)\|)$ 在步长固定时只是某个有限值。这直观地说明：沿负梯度方向移动，一阶项的贡献是使函数值下降的。

为了使论证更加严谨（确保 $x$ 落在局部邻域内，且高阶无穷小项不至于抵消负项），我们回到带步长 $t$ 的一般形式。

将 $x - x^* = -t \nabla f(x^*)$ 代入增量公式：

$$\begin{aligned} f(x) - f(x^*) &= \nabla f(x^*)^T \bigl(-t \nabla f(x^*)\bigr) + o(\|t \nabla f(x^*)\|) \\[8pt] &= -t \cdot \nabla f(x^*)^T \nabla f(x^*) + o(t \|\nabla f(x^*)\|) \\[8pt] &= -t \|\nabla f(x^*)\|^2 + o(t) \end{aligned}$$

这里详细说明每一步的运算规则：

• 第一步：将 $x - x^* = -t \nabla f(x^*)$ 整体代入 $\nabla f(x^*)^T (x - x^*)$，同时 $\|x - x^*\| = \|-t \nabla f(x^*)\| = t \|\nabla f(x^*)\|$；
• 第二步：利用内积对常数因子的齐次性：$a^T (tb) = t \cdot a^T b$，将 $-t$ 提至内积外面；
• 第三步：利用自身内积等于模长平方：$\nabla f(x^*)^T \nabla f(x^*) = \|\nabla f(x^*)\|^2$。同时，由于 $\|\nabla f(x^*)\|$ 是一个固定的正数，高阶无穷小满足 $o(t \cdot c) = o(t)$（$c$ 为非零常数），因此 $o(t \|\nabla f(x^*)\|) = o(t)$。

由于假设了 $\nabla f(x^*) \neq 0$，所以 $\|\nabla f(x^*)\|^2 > 0$，于是 $-t \|\nabla f(x^*)\|^2$ 是一个严格小于零、且与 $t$ 同阶的量。而 $o(t)$ 是比 $t$ 更高阶的无穷小，即满足 $\lim\limits_{t \to 0} \dfrac{o(t)}{t} = 0$。

因此，当 $t > 0$ 充分小时（即 $x$ 充分接近 $x^*$ 时）：

$$-t \|\nabla f(x^*)\|^2 + o(t) < 0$$

这是因为负项 $-t \|\nabla f(x^*)\|^2$ 与 $t$ 同阶，而 $o(t)$ 在 $t \to 0$ 时趋于零的速度更快，所以负项占主导，总和为负。

于是：

$$f(x) - f(x^*) < 0 \quad \Longrightarrow \quad f(x) < f(x^*)$$

这意味着在 $x^*$ 的任意小邻域内，总存在点 $x = x^* - t \nabla f(x^*)$ 使得 $f(x) < f(x^*)$，这与”$x^*$ 是局部最优解”矛盾。

故假设错误，必有 $\nabla f(x^*) = 0$。

几何解释：

梯度 $\nabla f(x)$ 指向函数值增长最快的方向。若在某点梯度不为零，则沿负梯度方向移动可以使函数值下降，因此该点不可能为极小点。只有在梯度为零的点，函数在各个方向上的一阶变化均为零，才有可能成为极值点。

二阶必要条件（定理4）

设 $f: \mathbb{R}^n \to \mathbb{R}$ 在 $x^*$ 处有二阶连续偏导数，若 $x^*$ 是 $f$ 的局部极小点，则

$$\nabla f(x^*) = 0 \quad \text{且} \quad \nabla^2 f(x^*) \succeq 0 \; (\text{半正定})$$

其中 $\nabla^2 f(x^*)$ 为 $f$ 在 $x^*$ 处的Hesse矩阵（二阶偏导数矩阵）。该条件说明：局部极小点不仅梯度为零，而且函数在该点的二阶曲率必须”向上开口”（半正定）。

二阶充分条件（定理5）

设 $f: \mathbb{R}^n \to \mathbb{R}$ 在 $x^*$ 的某邻域内有连续的二阶偏导数，若

$$\nabla f(x^*) = 0 \quad \text{且} \quad \nabla^2 f(x^*) \succ 0 \; (\text{正定})$$

则 $x^*$ 是 $f$ 在该邻域内的严格局部极小点。

三者关系总结如下：

条件类型	前提	结论
一阶必要	$f$ 在 $x^*$ 可微	$x^*$ 为局部极小点 $\Rightarrow \nabla f(x^*) = 0$
二阶必要	$f$ 在 $x^*$ 二阶连续可微	$x^*$ 为局部极小点 $\Rightarrow \nabla f(x^*) = 0, \nabla^2 f(x^*) \succeq 0$
二阶充分	$f$ 在 $x^*$ 邻域二阶连续可微	$\nabla f(x^*) = 0, \nabla^2 f(x^*) \succ 0$ $\Rightarrow x^*$ 为严格局部极小点