最优化理论

• 2024 研究生课程「最优化理论」笔记 & 复习要点。

1. 绪论

1.1. 概念

• 分类：可以根据不同属性的性质进行分类，如

  1. 目标函数：分为线性优化和非线性优化
  2. 约束条件：有约束（等式约束、不等式约束）和无约束
  3. 决策变量：离散型、连续型
  4. 最优解：单目标、多目标
  5. 优化问题：凸优化（通常为全局最优解）、非凸优化（多个局部最优解）

• 解：

  1. 最优解：目标函数取最值的变量
  2. 可行解：满足约束条件，但不一定最优
  3. 梯度：$g = \nabla f(x)$，目标函数的方向导数
  4. Hesse矩阵：$G = \nabla^2 f(x)$，目标函数的二阶方向导数

禁忌搜索算法

解决什么问题

• 启发式搜索算法——求解近似值

  解决无法找到精确解的复杂优化问题，例如背包问题、神经网络训练、调度问题、工程设计问题。（引入）

  特点是利用过去的经验解决具体问题。 有时候不能保证问题一定结局，却常常能有效解决问题。

• 分类

  1. 基于群体

     每次迭代搜索一组解，算法依赖于多个个体之间的信息交互。

  2. 基于个体

     关注单个解，从某个解出发迭代得到最优解。

• 核心思想

  给出多个迭代方向、逃离局部最优解