最优化理论与方法 - 期末考试回忆与解析
本文档基于2025年12月19日的考试回忆整理。内容涵盖凸分析基础、线性规划对偶理论、单纯形法细节以及非线性规划算法构造。
一、 判断题 (10题 × 1分)
本部分主要考察基本概念的辨析,重点在于对偶理论的性质和凸集的几何直观。
-
题目:两个不相交的集合的并一定不是凸集。
- 答案:
错误 (False) - 解析:这是一个常见的思维陷阱。例如集合 和 ,虽然它们不相交(),但它们的并集 是一个连通的区间,仍然是一个凸集。
- 答案:
-
题目:凸函数的定义域不一定是凸集。
- 答案:
错误 (False) - 解析:根据数学定义,函数 被称为凸函数的前提条件之一,就是其定义域必须是凸集。
- 答案:
-
题目:动态规划表格是二维的,且每次的计算是常数级,这个动态规划的时间复杂度是多项式时间。
- 答案:
正确 (True) - 解析:若表格大小为 ,总计算量为 。在算法复杂性理论中, 形式均属于多项式时间复杂度。
- 答案:
-
题目:用分支定界法求解一个极大的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界。
- 答案:
正确 (True) - 解析:对于最大化(Max)问题,最优解肯定是所有可行解中最大的。因此,任意一个“可行解”的值一定小于等于最优值,构成了下界(Lower Bound)。
- 答案:
-
题目:单纯形算法中利用最小比值法选转轴元的时候,如果能选的不止一个转轴元,则旋转后必然有一个基变量值为0。
- 答案:
正确 (True) - 解析:最小比值出现并列(Tie),意味着新顶点是多个约束边界的交点。旋转后,其中一个变量出基变为0,另一个并列的变量虽然留在基中,但其计算值也会变为0,这就是**退化(Degeneracy)**现象。
- 答案:
-
题目:所有线性规划都有对偶规划。
- 答案:
正确 (True) - 解析:任何线性规划问题都可以写出其形式上的对偶规划。至于它们是否有解(可行或无界),不影响对偶规划本身的存在性。
- 答案:
-
题目:原始线性规划可行解无界,则其对偶规划无可行解。
- 答案:
正确 (True) - 解析:根据弱对偶性:Max问题无界(),Min对偶问题必须不可行(否则对偶问题的任意可行解都会限制原问题的上界)。
- 答案:
-
题目: 和 关于 共轭, 和 关于 共轭,则 和 也关于 共轭。
- 答案:
错误 (False) - 解析:共轭性(A-Conjugate)类似于正交性,不具备传递性。例如在二维空间, 和 可能是同一个方向,它们之间不一定关于正定矩阵共轭。
- 答案:
-
题目: 在每一点处的黑塞矩阵(Hessian Matrix)正定,则 是凸函数。
- 答案:
正确 (True) - 解析:黑塞矩阵正定是严格凸函数的充分条件。既然是严格凸函数,那它必然也是凸函数。
- 答案:
二、 填空题 (10空 × 2分)
-
题目: 是凸函数, 是 ______ 函数? 是 ______ 函数?
- 答案:凸; 非凸非凹(或不一定)
- 解析:凸函数的逐点最大值仍然保持凸性(上方图交集);最小值通常呈“W”型,丧失凸性。
-
题目:线性规划中, 是 的一个子矩阵,若要选择 作为基,则 应该满足 ______,若此时的基本解为基本可行解,应满足 ______。
- 答案: 可逆 (或 );
- 解析:基必须满秩;可行解要求变量非负。
-
题目: 关于 求导的结果 ______。
- 答案:
- 解析:复合函数求导(链式法则),梯度与方向向量的内积。
-
题目:原始线性规划有3个功能约束,4个变量约束,则对偶线性规划有 ______ 个功能约束,______ 个变量约束?
- 答案:4; 3
- 解析:对称关系:原问题的变量数 对偶问题的约束数;原问题的约束数 对偶问题的变量数。
-
题目:等式约束二次规划中的拉格朗日法求解,实际上是求 ______ 和 ______ 组成的方程组。
- 答案:平稳性条件 (梯度方程); 原始可行性条件 (约束方程)
- 解析:即 KKT 系统,由 和 构成。
三、 计算与构造题 (核心考点)
1. 内惩罚函数法构造 (Barrier Method)
题目: 将以下最大化问题转化为利用内惩罚函数构造的最小化问题:
解析步骤:
- 目标转换:Max Min 。原目标变号为 。
- 障碍项选择:约束为 。内点法常用倒数形式 。
- 构造结果:
2. 对偶单纯形法
适用条件: 当单纯形表满足对偶可行(检验数 ,针对Max标准型),但不满足原始可行( 列有负数)时使用。
迭代逻辑:
- 选离基变量:看 列,选负得最厉害的那个(例如 )。
- 选入基变量:计算检验数与该行负系数的比值 ,取最小的那个。
- 旋转:高斯消元,直到 列全为非负。
3. 矩阵求逆技巧 (2阶)
对于 :
- 口诀:主对调,副变号,除以行列式。
- 公式:
4. 矩阵共轭计算
定义:向量 关于 共轭 。 计算例题: 已知 ,求 。
- 计算 。
- 求解 。
- 取 ,得 。
祝考试顺利! > 复习建议:重点回顾线性规划的标准型转化、对偶问题的书写规则以及凸函数的基本性质。
受保护的文章
请输入密码以继续阅读
部分内容可能已过时