最优化理论与方法 袁亚湘_芝麻006| 最优化理论与方法系列3

嘿，你喜欢小芝麻吗？听说攒的多了，就能芝麻开门了哦

写在前面 没有记录就等于没有发生，我要用自己的方式，去诉尽这平凡而可贵的旅途！本系列旨在复习回顾，无法面面俱到，也不可能普适，系统梳理真的比较吃力，也可能是笔者功力尚浅。不过还好，我在路上！复习时需要比对公式理解，这样概念才能不断深化，笔者仅仅做到了概括要点。不管怎样，于你于我，都希望有所收获。 特此声明，文中大部分图片及文字叙述源自任课焦老师课件。感谢老师一学期以来的悉心讲解 文中不当之处欢迎指正！

【目录】

• 一维搜索法概述

• 搜索区间的确定

• 对分法

• 牛顿切线法

• 黄金分割法

• 抛物线插值法

• 综合

• 习题演练

【一维搜索法概述】

• 概念

求解一维目标函数的极小点和极小值所用的数值迭代方法称为一维搜索方法。拓：在多维优化问题中，也可以用于在确定方向上寻求最优步长的一维搜索。对于常见的二次函数，要求无约束可微函数的最优解，无疑求导令梯度等于零即可求出驻点。但是 对于n次函数，由梯度等于零会得到非线性方程组，求解困难(注意我们讨论的X已不再是一个数，而是向量)。 因此，常使用迭代法。

• 步骤

• 确定初始搜索区间[a,b]

该区间需包含一维优化目标函数的极小点，且为单峰区间。

• 在搜索区间寻找极小点

其中α为步长， S为搜索方向。多维优化问题中，一维优化是寻找合适的步长，使得新的迭代点对应的函数值最小。

• 迭代法

• 基本思想

为了求解函数f(x)的最优解，首先给定初始点x^0，根据某种算法寻找比x^0更好的解x^1，不断重复可得解序列{x^k}，若解序列有极限x*，则该序列收敛于x*。由于计算机只能有限次迭代，所以我们一般得到的是近似解，只要符合工程上的精度要求即可。

• 终止条件类别

1.相继两次迭代的绝对误差

2.相继两次迭代的相对误差

3.目标函数梯度的模足够小

图源任课焦老师课件

• 分类

根据是否计算目标函数和约束函数的导数： 直接法(仅利用函数值)、 非直接法(利用导数，收敛性结果更强)。根据迭代点是否沿某个方向产生： 线搜索法、 信赖域法(在某个区域内搜索迭代点)。

【搜索区间的确定】

常见的一维直接法有消去法、近似法，均从某个初始搜索区间出发，利用单谷函数消去性质逐步缩小区间，直到满足精度要求。 进退算法求初始区间

• 基本思想

从某点出发，沿函数下降方向前进，直到发现函数值上升为止。由 高低高三点确定极小点所在初始区间。

• 说明

效率低；步长h选取不能太小。

【对分法】

• 基本思想

利用导数判断区间点处于上升还是下降段，若区间端点导数一正一负，则区间内必存在极小点。取中值x0，若该点处导数值为正，该点处于上升段，去掉[x0,b]；若该点处导数值为负，该点处于下降段，去掉[a,x0]；若为0，则为最小点。

不断重复上述过程，直到区间充分小，此时可取中点作为极小点的近似点。

• 说明

优点：计算量少，总能收敛到局部极小点。

缺点：收敛速度慢。

【牛顿切线法】

• 基本思想

极小点处用函数的二阶泰勒多项式代替目标函数，从而求得目标函数的极小点的近似值。迭代公式如下，终止条件为一阶导模值足够小。

• 说明

特点：收敛速度快，局部二阶收敛。缺点：需要计算二阶导数，计算量大；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点；局部收敛。

【黄金分割法】

• 基本思想

每次去掉区间后，保留的区间长度与原长度比值不变， 遵循对称原则和保持缩减比原则。终止条件为区间端点的绝对误差足够小。

• 说明

优点：不要求函数可微，每次迭代只需计算一个函数值，程序简单。缺点：收敛速度慢。

【抛物线插值法】

• 基本思想

利用两个试探点来寻找极小点，其中试探点1可根据 进退法求得(即高低高中的低)，试探点2利用 插值法寻找。比较两点函数值(或者计算两点的绝对误差)，可终止迭代或继续迭代(继续迭代时区间端点和试探点的物理意义不能改变，即区间端点是新的试探点1近旁的左右两点)。

【综述】

• 如果目标函数能求二阶导：用牛顿切线法，收敛快

• 如果目标函数能求一阶导：用二分法，收敛速度慢但可靠

• 只需计算函数值的方法：首先考虑二次插值法，收敛快；黄金分割法收敛慢，但可靠

【习题演练】

点击图片给我留言，我们聊聊芝麻叭好不好