【凸优化】谈非线性规划的一维搜索各种方法！

一维搜索

一维搜索就是目标变量只有一个的时候的最优化问题，又称为单变量函数寻优法。

求解这类问题一般有两种方法，一类是区间收缩法（如黄金分割法），一类是函数逼近法（如三点二次插值法、牛顿法）。下面分别介绍：

2

 单谷函数

定义：如果函数f(x)在区间[a,b]上只有一个极小值点, 则称f(x)为[a,b]上的单谷函数。

单谷函数具有一个重要的消去性质

3

 外推内插法

在一维搜索中的区间收缩法中需要用到单谷区间，而寻找单谷区间的方法就是下面要介绍的外推内插法。

其思路为从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。而由两边高，中间低的三点，可确定极小点所在的初始区间。

4

黄金分割法

黄金分割法的思想是：反复使用单谷函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。

该方法的优点是需计算函数值，通用性强。

转自：机器学习算法与自然语言处理

完整内容请点击“阅读原文”