最优化理论与方法 - 期末考试回忆与解析

本文档基于2025年12月19日的考试回忆整理。内容涵盖凸分析基础、线性规划对偶理论、单纯形法细节以及非线性规划算法构造。

一、判断题 (10题 × 1分)#

本部分主要考察基本概念的辨析，重点在于对偶理论的性质和凸集的几何直观。

题目：两个不相交的集合的并一定不是凸集。
- 答案：错误 (False)
- 解析：这是一个常见的思维陷阱。例如集合 $A=(0, 1)$ 和 $B=[1, 2)$ ，虽然它们不相交（ $A \cap B = \emptyset$ ），但它们的并集 $A \cup B = (0, 2)$ 是一个连通的区间，仍然是一个凸集。
题目：凸函数的定义域不一定是凸集。
- 答案：错误 (False)
- 解析：根据数学定义，函数 $f$ 被称为凸函数的前提条件之一，就是其定义域必须是凸集。
题目：动态规划表格是二维的，且每次的计算是常数级，这个动态规划的时间复杂度是多项式时间。
- 答案：正确 (True)
- 解析：若表格大小为 $N \times N$ ，总计算量为 $O(N^2)$ 。在算法复杂性理论中， $N^k$ 形式均属于多项式时间复杂度。
题目：用分支定界法求解一个极大的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。
- 答案：正确 (True)
- 解析：对于最大化（Max）问题，最优解肯定是所有可行解中最大的。因此，任意一个“可行解”的值一定小于等于最优值，构成了下界（Lower Bound）。
题目：单纯形算法中利用最小比值法选转轴元的时候，如果能选的不止一个转轴元，则旋转后必然有一个基变量值为0。
- 答案：正确 (True)
- 解析：最小比值出现并列（Tie），意味着新顶点是多个约束边界的交点。旋转后，其中一个变量出基变为0，另一个并列的变量虽然留在基中，但其计算值也会变为0，这就是**退化（Degeneracy）**现象。
题目：所有线性规划都有对偶规划。
- 答案：正确 (True)
- 解析：任何线性规划问题都可以写出其形式上的对偶规划。至于它们是否有解（可行或无界），不影响对偶规划本身的存在性。
题目：原始线性规划可行解无界，则其对偶规划无可行解。
- 答案：正确 (True)
- 解析：根据弱对偶性：Max问题无界（ $+\infty$ ），Min对偶问题必须不可行（否则对偶问题的任意可行解都会限制原问题的上界）。
题目： $d_1$ 和 $d_2$ 关于 $A$ 共轭， $d_2$ 和 $d_3$ 关于 $A$ 共轭，则 $d_1$ 和 $d_3$ 也关于 $A$ 共轭。
- 答案：错误 (False)
- 解析：共轭性（A-Conjugate）类似于正交性，不具备传递性。例如在二维空间， $d_1$ 和 $d_3$ 可能是同一个方向，它们之间不一定关于正定矩阵共轭。
题目： $f(x)$ 在每一点处的黑塞矩阵（Hessian Matrix）正定，则 $f(x)$ 是凸函数。
- 答案：正确 (True)
- 解析：黑塞矩阵正定是严格凸函数的充分条件。既然是严格凸函数，那它必然也是凸函数。

二、填空题 (10空 × 2分)#

题目： $f, g$ 是凸函数， $\max\{f, g\}$ 是 ______ 函数？ $\min\{f, g\}$ 是 ______ 函数？
- 答案：凸； 非凸非凹（或不一定）
- 解析：凸函数的逐点最大值仍然保持凸性（上方图交集）；最小值通常呈“W”型，丧失凸性。
题目：线性规划中， $B$ 是 $A$ 的一个子矩阵，若要选择 $B$ 作为基，则 $B$ 应该满足 ______，若此时的基本解为基本可行解，应满足 ______。
- 答案： $B$ 可逆 (或 $|B| \neq 0$ )； $B^{-1}b \ge 0$
- 解析：基必须满秩；可行解要求变量非负。
题目： $f(x+\alpha d)$ 关于 $\alpha$ 求导的结果 ______。
- 答案： $\nabla f(x+\alpha d)^T d$
- 解析：复合函数求导（链式法则），梯度与方向向量的内积。
题目：原始线性规划有3个功能约束，4个变量约束，则对偶线性规划有 ______ 个功能约束，______ 个变量约束？
- 答案：4； 3
- 解析：对称关系：原问题的变量数 $\leftrightarrow$ 对偶问题的约束数；原问题的约束数 $\leftrightarrow$ 对偶问题的变量数。
题目：等式约束二次规划中的拉格朗日法求解，实际上是求 ______ 和 ______ 组成的方程组。
- 答案：平稳性条件 (梯度方程)； 原始可行性条件 (约束方程)
- 解析：即 KKT 系统，由 $\nabla L = 0$ 和 $Ax=b$ 构成。

三、计算与构造题 (核心考点)#

1. 内惩罚函数法构造 (Barrier Method)#

题目：将以下最大化问题转化为利用内惩罚函数构造的最小化问题：

\begin{aligned} \max \quad & -x_1 + x_2 \\ \text{s.t.} \quad & x_1^2 + x_2^2 \le 5 \end{aligned}

解析步骤：

目标转换：Max $z \iff$ Min $-z$ 。原目标变号为 $x_1 - x_2$ 。
障碍项选择：约束为 $g(x) = 5 - x_1^2 - x_2^2 \ge 0$ 。内点法常用倒数形式 $\frac{1}{g(x)}$ 。
构造结果： $\min \quad P(x, r) = (x_1 - x_2) + r \cdot \frac{1}{5 - x_1^2 - x_2^2} \quad (r > 0)$

2. 对偶单纯形法#

适用条件：当单纯形表满足对偶可行（检验数 $\sigma_j \le 0$ ，针对Max标准型），但不满足原始可行（ $b$ 列有负数）时使用。

迭代逻辑：

选离基变量：看 $b$ 列，选负得最厉害的那个（例如 $b_i = -4$ ）。
选入基变量：计算检验数与该行负系数的比值 $\theta = |\sigma_j / a_{rj}|$ ，取最小的那个。
旋转：高斯消元，直到 $b$ 列全为非负。

3. 矩阵求逆技巧 (2阶)#

对于 $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ ：

口诀：主对调，副变号，除以行列式。
公式： $A^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}$

4. 矩阵共轭计算#

定义：向量 $d_1, d_2$ 关于 $A$ 共轭 $\iff d_1^T A d_2 = 0$ 。 计算例题：已知 $A = \begin{pmatrix} 4 & 2 \\ 2 & 2 \end{pmatrix}, d_1 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$ ，求 $d_2$ 。

计算 $d_1^T A = (1, 0) \begin{pmatrix} 4 & 2 \\ 2 & 2 \end{pmatrix} = (4, 2)$ 。
求解 $(4, 2) \cdot \begin{pmatrix} x \\ y \end{pmatrix} = 4x + 2y = 0 \implies y = -2x$ 。
取 $x=1$ ，得 $d_2 = (1, -2)^T$ 。

祝考试顺利！ > 复习建议：重点回顾线性规划的标准型转化、对偶问题的书写规则以及凸函数的基本性质。

🔒

受保护的文章

请输入密码以继续阅读

A Good Day!

最优化理论与方法 - 期末考试回忆与解析

一、判断题 (10题 × 1分)#

二、填空题 (10空 × 2分)#

三、计算与构造题 (核心考点)#

1. 内惩罚函数法构造 (Barrier Method)#

2. 对偶单纯形法#

3. 矩阵求逆技巧 (2阶)#

4. 矩阵共轭计算#

受保护的文章

评论区

目录

A Good Day!

最优化理论与方法 - 期末考试回忆与解析

一、 判断题 (10题 × 1分)#

二、 填空题 (10空 × 2分)#

三、 计算与构造题 (核心考点)#

1. 内惩罚函数法构造 (Barrier Method)#

2. 对偶单纯形法#

3. 矩阵求逆技巧 (2阶)#

4. 矩阵共轭计算#

受保护的文章

评论区

目录

一、判断题 (10题 × 1分)#

二、填空题 (10空 × 2分)#

三、计算与构造题 (核心考点)#