最速下降法（梯度下降法）

• 梯度下降法又称最速下降法。函数 在某点 的梯度 是一个向量， 其方向是 增长最快的方向。显然，负梯度方向是 减少最快的方向。在梯度下降法中，求某函数极大值时，沿着梯度方向走，可以最快达到极大点； 反之，沿着负梯度方向走，则最快地达到极小点。

• 对于任意点 ，可以定义 点的负梯度搜索方向的单位向量为:
从 点出发，沿着 方向走一步，步长为 , 得到新点 表示为：
因此，在新点 ，函数 的函数值为：
所有的 组成一个序列，该序列由迭代算法生成 。该序列在一定条件下收敛于使得 最小的解 。而迭代公式为 。

• 关键问题：如何设计步长？
如果选得太小，则算法收敛慢，如果选得太大，可能会导致发散。

• 梯度法的迭代过程
1. 选取初始点 ，给定允许误差 ，并令 ；
2. 计算负梯度 及其单位向量 ；
3. 检查是否满足条件 ，若满足则转 8，否则继续
4. 计算最佳步长 ；
5. 令：；
6. 计算并检验另一判据：，满足转 8，否则继续；
7. 令 ，转 2；
8. 输出结果，结束。

牛顿法

• 求解无约束极值问题得最古老算法之一，已发展成为一类算法：Newton 型方法。在局部，用一个二次函数近似代替目标函数 ，然后用近似函数的极小点作为 的近似极小点。

• 泰勒公式是把函数在 处计算该函数的 n 阶导数，则有 Taylor 展开：

• 若非线性目标函数 具有二阶连续偏导， 为 的一个近似极小点，则在 点泰勒展开：
对 求导得 ，并令 。 若 Hessian 矩阵 正定，即 ，则 ，此时有
上式则为 Newton 迭代公式。

• 算法过程
1. 给定初始点 ，精度 ，；
2. 计算 和 。当 可逆时，；
3. 由方程组 解出 ；
4. 若 ，停止，有 ；否则，令 ，转到 2。

DFP——拟牛顿法

• 拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的 海森矩阵的逆矩阵的缺陷，它使用正定矩阵来近似 海森矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化， 构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。

• 牛顿法的迭代公式：。所谓拟牛顿法，是指用梯度差分或一个近似矩阵 去代替 ，以克服 Newton 法中需计算 的缺点的一种计算方法，不同的构造 的方法，就产生不同的拟牛顿法。

• 我们有 ，如果令 ，，，则海森矩阵 ，或者 。

• 由于对于二次函数，上式精准成立，所以一般情况下，我们希望海森矩阵近似满足 或者 （拟牛顿条件）其中 ，。

• 个人理解：我们以梯度差分的方法去看，有 ，则

DFP

DFP算法原理

DFP 算法步骤

1. 令 , 选择初始点 , 任选一个对称正定实矩阵

2. 如果 停止迭代, 否则令 ，其中 表示梯度，雅各比矩阵

3. 使用一维搜索（只要一维搜索是精确的, 近似矩阵 就都是正定的）计算

1. 计算

1. 令 , 回到第2步

BFGS

BFGS 算法原理

凸集等一些前导知识

• 凸集定义：设集合 ，对任意的 与任意的 有 ，则称集合 是凸集。
凸集的几何意义是：若两个点属于此集合，则这两点连线上的任意一点均属于此集合。
assets/image-20220718152608-nlyrlay.png

• 梯度定义：设 元函数 对自变量 的各分量 的偏导数 都存在，则称函数 在 处一阶可导，并称向量
为函数 在 处的一阶导数或梯度，记为 （列向量）

• Hessian （海森）矩阵定义：设 元函数 对自变量 的各分量 的二阶偏导数 都存在，则称函数 在点 处二阶可导，并称矩阵
为 在 处的二阶导数或 Hessian （海森）矩阵，记为 ，若 对 各变元的所有二阶偏导数都连续，则 ，此时 为对称矩阵。

• 多元实值函数凹凸性判定定理：
设 是非空开凸集，，且 在 上二阶连续可微，如果 的 Hessian 矩阵 在 上是正定的，则 是 上的严格凸函数。

泰勒级数展开

• 一元函数 在点 处的泰勒展开式为:

• 二元函数 在点 处的泰勒展开式为:

• 元函数 在点 处的泰勒展开为:

Powell Method

基本搜索：包括从基点出发沿着已知的 个线性无关的搜索方向进行一维搜索,确定一个新的基点;加速搜索：指这将第一轮起点和新确定的基点相连构成新的方向，进行一维搜索使得函数值下降；调整搜索：将这一轮方向组的第一个方向去掉,新的方向补充在最后构成新的方向组，进行下一轮迭代。

• 共轭方向
• 共轭方向法是介于最速下降法与牛顿法之间的一类方法。 它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和 计算牛顿法所需要的二阶导数信息。
• 设 是 的对称正定矩阵，对于 中的两个非零向量 和 ，若有 ，则称 和 关于 共轭。
设 是 中一组非零向量，如果它们两两关于 共轭，即 ，，，则称这组方向是关于 共轭的，也是称他们是一组 的共轭方向。
如果 是单位矩阵，则 **** ，则可以认为共轭是正交的推广，正交是共轭的特殊形式。 ——不会相互影响的基方向。在优化中，构成优化空间的基不一定是两两正交的，例如与也能构成一个解空间，但是这两个基向量却不是正交的。因此，我们弱化正交的性质。而共轭则是这样的推广。在后续讲解的共轭梯度法，类似于“坐标下降法”，每次只优化一个变量，这在维的解空间中，我们经过次就能将问题优化完成。
• 我们把从点 出发，依次沿着某组共轭方向进行一维搜索 来求解无约束最优化问题的方法称为共轭方向法。
• 共轭方向法的几何意义
设有二次函数 ，其中 是 对称正定矩阵， 是一个定点。则函数 的等值面 是以 为中心的椭球面。由于 ，而 ，因为 正定，所以 ，因此 是 的极小值。
• 设 是在某个等值面上的一点， 是 中的一个方向， 沿着 以最优步长搜索得到点 ，则 是点 所在等值面的切向量。该等值面在点 处的法向量为 ，则 与 正交，即 ，令 ，所以 ，即等值面上一点处的切向量与由这一点指向极小点的向量关于 共轭。
• 性质
• 设 是正定矩阵， 中非零向量组 是 共轭的，则这 个向量线性无关的。
• 设 ， 是 中线性无关的向量组，若 与每个 都正交，则 。

PSO（粒子群优化）——Guided Random Search Methods

速度更新公式的参数定义

1. ：粒子群规模； ：粒子序号, ;

2. ：粒子维度； ：粒子维度序号， ;

3. ：迭代次数；

4. ：惯性权重;

5. ：个体学习因子; ：群体学习因子;

6. ：区间 内的随机数，增加搜索的随机性；

7. ：粒子 在第 次迭代中的前进位移向量，其形式为;

8. ：粒子 在第 次迭代中的位置向量，其形式为;

9. ：在第 次迭代后, 第 个粒子（个体）搜索得到的最优解（在解空间中的位置），其形式为;

10. ：在第 次迭代后, 整个粒子群体中的最优解，其形式为。

补充参数

1. 第 个粒子搜索到的最优位置的适应值 (优化目标函数的值) 为： （个体历史最优适应值）

2. 群体搜索到的最优位置的适应值为： （群体历史最优适应值）

算法流程图

算法参数的详细解释——参考上述提到的文章

粒子群规模：

粒子维度：

迭代次数：

惯性权重：

参数意义

改善惯性权重

学习因子： 、

• 表示粒子下一步动作来源于自身经验部分所占的权重，将粒子推向个体最优位置 的加速权重；

• 表示粒子下一步动作来源于其它粒子经验部分所占的权重，将粒子推向群体最优位置 的加速权重；

• ：无私型粒子群算法，"只有社会，没有自我"，迅速丧失群体多样性，易陷入局部最优而无法跳出；

• ：自我认知型粒子群算法，"只有自我，没有社会"，完全没有信息的社会共享，导致算法收敛速度缓慢；

• 、 都不为0：完全型粒子群算法，更容易保持收敛速度和搜索效果的均衡，是较好的选择。

Genetic algorithms（遗传算法）——Guided Random Search Methods

确定编码位长

适应值评估（Fitness Evaluation）

繁殖（reproduction）

1. 确定适应值是否有负值。如果有，将适应值进行放大，例如适应值为 放大为 ；

2. 适应下列式子，转换适应值
小思考：我觉得这个式子可以有其他的形式。书上的优化例子是最小化，因此将适应值放到分母，同时为了避免有除零的情况，在分母上加 。
然后根据转换后的值，计算每个适应值所在比例，例子如下：

3. 将我们得到的饼图，转换为下列的图样式。然后，生成10个随机数（对应于总体大小），并选择这些随机数位于插槽中的相应字符串。因此，如图，串S-2、S-7和S-8各复制两份，串S-4、S-5、S-6和S-10各复制一份。这些字符串将参与交叉和变异操作。

交叉和变异（Crossover and Mutation）

📎 参考