最优化算法复习问题清单

线搜索

一维搜索

1. 黄金分割法的原理是什么？对函数的要求是什么？如何操作？

2. 二分法的原理是什么？对函数的要求是什么？如何操作？

3. 牛顿法的原理是什么？对函数的要求是什么？如何操作？

   1. 牛顿法除了求解极小值点，还可以用来求解什么？

4. 割线法的原理是什么？对函数的要求是什么？如何操作？

多维搜索

1. 多元函数求极值的基本格式是什么？

2. 精确步长公式是什么？

3. 信赖域法的原理是什么？

   • while $f\left( x_{k} + \alpha p_{k} \right) > f\left( x_{k} \right) + c\alpha p_{k}^{\top}\nabla f\left( x_{k} \right)$ do $\alpha \leftarrow \rho\alpha$

无约束优化

1. 梯度下降法的迭代格式是什么？

2. 牛顿法的迭代格式是什么？

3. 共轭梯度法迭代格式是什么？

   1. 共轭方向是什么？

   2. 有限步终止的原因是什么？

4. 拟牛顿法的迭代格式是什么？

   1. 拟牛顿法怎么来的？

   2. 秩一矫正的推导？

   3. DFP、BFGS 分别是什么？怎么推导？

   4. Sherman-Morrison 公式是什么？（*）

      • $A + uv^{\top}$ 可逆$\Rightarrow \left( A + uv^{\top} \right)^{- 1} = A^{- 1} - \frac{A^{- 1}uv^{\top}A^{- 1}}{1 + v^{\top}A^{- 1}u}$

线性规划

1. 标准格式是什么？

2. 基本解是什么？基本可行解是什么？

3. 单纯形法的矩阵形式？操作步骤？

4. 两阶段法是什么?

5. 大 M 法是什么？

6. 线性规划的对偶怎么写？

整数规划

1. 割平面法的原理是什么？

2. 分支定界法的原理是什么？

约束优化

理论知识

1. Lagrange 函数？

2. 二次规划的标准型是什么？其最优性条件是什么？

3. KKT 条件是什么？

4. 对偶定理？弱对偶理论？强对偶理论？鞍点理论？

5. 约束优化的二阶条件？

求解方法

1. 投影类方法的迭代格式？常见约束的投影表达式？

2. 拉格朗日法的迭代格式？

3. 罚函数法的罚函数是什么？迭代格式是什么？

4. 增广拉格朗日函数是什么？迭代格式是什么？

多目标规划

1. 多目标规划有哪些求解方法？

   1. 帕累托最优解？

   2. 各种单目标优化方法的优缺点和使用条件？线性加权法、极小极大法、范数法、转换为约束问题