一维搜索方法type
status
date
slug
summary
tags
category
icon
password
Property
目标函数为一元单值函数 时的最小优化问题的迭代求解方法，称为一维搜索法，也称为线性搜索法。
迭代算法从初始搜索点 出发，产生一个迭代序列 。在第 次迭代中，通过当前迭代点 和目标函数 构建下一个迭代点 。算法可能只需要迭代点处的目标函数值，还可能用到目标函数的一阶导数，甚至二阶导数。
一维搜索算法包括（但不限于）：
- 黄金分割法（只使用目标函数值）
- 斐波那契数列法（只使用目标函数值）
- 二分法（只使用目标函数的一阶导数）
- 割线法（只使用目标函数的一阶导数）
- 牛顿法（同时使用目标函数的一阶导数和二阶导数）
黄金分割法
黄金分割法可用于求解一元单值函数在区间上的极小点。前提是目标函数在区间上是单峰的，即存在唯一的局部极小点。
方法思路：选择区间 中的点，计算对应的目标函数值，通过比较不断缩小极小点所在的区间。利用尽可能少的计算次数来找出函数的极小点，即不断的压缩极小所在的区间，直到达到足够的精度水平。
如果在每次迭代中只计算一个点的目标函数，将无法开展比较并压缩极小点所在的区间。因此每次需要计算两个点处的目标函数值。可以按照对称压缩方式来缩小极小点所在区间，即
其中，
计算目标函数在中间点 和 处的值，如果，则极小点应该位于区间 中；否则，如果 ，则极小点应该位于区间中。
按以上方式，对区间压缩后，可利用之前一样的 重复以上过程并确定两个新的中间点。如此往复，即可得到精度水平足够的区间。由于已经位于区间 中，且 已知，可令 作为 ，只需计算 及其对应的目标函数值 即可。为此，需要确定合适的参数 ，使得每次迭代只需计算一次目标函数的值。
不失一般性地，可认为初始区间 的长度为1，可知
由，可得
整理，得：
解得：
由于 ，得：
注意
故有
即以 的比例划分区间，能够使得短区间与长区间长度之间的比值等于长区间与整个区间的长度的比值。
这种划分方式服从古希腊几何学家提出的著名的黄金分割法则。
利用黄金分割法开展区间压缩，意味着每一步只需要确定一个新点并计算一次目标函数的值（第一步除外）。经过步压缩之后，极小点所在区间长度将压缩到初始区间长度的，称为总压缩比。
斐波那契数列法
黄金分割法进行区间压缩过程中，参数始终保持不变；斐波那契数列法区间压缩过程中，允许参数 不断调整。
确定一个参数序列，使得每次迭代中只需计算一次目标函数值。两次迭代的参数 应满足
整理后，得
假设序列满足上述条件，则经过 次迭代后，总压缩比为。
序列 的选择问题，可采用有约束优化问题描述为
斐波那契数列：令 对于 有
上述优化问题的最优解可采用斐波那契数列表示，即
表示斐波那契数列中的第个元素
斐波那契数列法的总压缩比为
二分法
求解单值函数 在单峰区间 的极小点
二分法要求函数是连续可微的，这样可使用函数的一阶导数 ：
- 确定区间 的中点 ；
- 如果，则极小点位于左侧，新区间为，转1；
- 如果，则极小点位于右侧，新区间为，转1；
- 如果，则为极小点。算法结束。
二分法的总压缩比为。
二分法与黄金分割法和斐波那契数列法存在两个明显的区别：
- 二分法使用的是目标函数的导数 ， 而不是黄金分割法和斐波那契数列法所使用的函数值
- 在每次迭代中，区间的压缩比为 ，因此，经过步迭代之后，整个区间的总压缩比为 。这一总压缩比比黄金分割法和斐波那契数列法的总压缩比要小。
牛顿法
假设函数连续二阶可微，可构造经过点 处的二次函数
显然，有
可认为是函数的近似，因此求函数的极小点可近似于求解的极小点。
函数 的极小点应满足一阶必要条件：
令 ，可得
当对区间内所有点都成立时，牛顿法可收敛到极小点；但是，如果在某些点处，有，牛顿法可能收敛到极大点：
牛顿法能够不断地迫使目标函数的一阶导数趋向于零，实际上，令令，可得迭代公式
用于求解方程，称为牛顿切线法
割线法
牛顿法需要用到目标函数的二阶导数，如果函数的二阶导数不存在，可用不同点处的一阶导数对其近似得到。
将近似值
带入牛顿法迭代公式，可得
该方法需要两个初始点和。割线法使用第和第 个迭代之间的割线确定第个迭代点。
割线法也可用于解方程 ，其迭代公式为
划界法
前面讨论的方法有一个应用前提即需要提供目标函数极小点所在的初始区间。这一区间确定是极小点所在的上下边界，因此，寻找这一初始区间的方法称为划界法。
任选3点 ，如果 ，则极小点在区间 。否则，如果 ，则选一点 ，检查 是否成立，如果成立，极小点在区间 ，否则，重复该过程，直到能够找到一个 ，使得 成立。
新点选择应保证其与前一个相邻点的距离超过其与前两点之间距离，可令相邻各点之间的距离倍增。
根据以上流程，最后的到3个点、 、 ，满足 ，极小点所在区间是。接下来就可以利用前面讨论的方法，如黄金分割法、斐披那契数列法和二分法等对区间进行压缩，求出目标函数的极小点了。
需要注意：在划界法中，已经得到目标函数值 、 、 。如果求取目标函数值涉及的计算量比较大或存在一定的困难，那么可以直接将 作为迭代过程中的一个点。如使用黄金分割法，可令 ，这样就是把 作为黄金分割法中的一个起始点了。为了达到这一目的，在划界法中应按照的方式来选择新点，即相邻点之间距离的扩展倍数为
多维优化问题中的一维搜索
一维搜索方法在多维优化问题中发挥着重要作用，特别是对于多维优化问题的迭代求解算法而言，通常每次迭代都包括一维搜索的过程。
多维优化问题中的一维搜索过程:
令目标函数为 ，求其极小点的迭代算法中迭代公式为
其中， 为给定的初始搜索点， 为步长，其确定方式为使函数
达到最小；向量 称为搜索方向。这就是多维优化问题中的一维搜索过程
通过开展一维搜索，可以保证在某些条件下， 。前面所有一维搜索方法(包括划界法)都可以
用于求取函数 的极小点。比如，可以使用割线法来确定 。利用链式法则计算函数的一阶导数：
一维搜索方法在实际应用中存在一些问题。首先，精确地求解函数的极小点可能需要非常大的计算量；在某些极端情况下，甚至并不存在。其次，实际应用经验表明，应该将更多的计算资源配置到多维优化算法而不是追求高精度的一维搜索上。这意味着应为一维搜索算法设计合适的停止条件，并使得即使一维搜索结果精度偏低，仍然能保证目标函数在两次迭代中得到足够程度的下降。一个最基本的理念是要保证步长 不要太小或太大。
实际应用中存在一些常用的停止条件：
Armijo条件
选定3个常数， 。
通过要求 保证 不会太大；通过要求 保证 不会太小。
Goldstein条件
Armijo条件中第二个不等式调整为
Armijo-Goldstein条件
Armijo条件中的第一个不等式和Goldstein条件联合
Wolfe条件：
强Wolfe条件：
Armijo划界法是一种简单实用的(非精确)一维搜索方法：
- 选定备选值；
- 如果满足预定停止条件（通常是Armijo条件中的第一个不等式），则其为步长，算法结束；
- 否则，乘以，步长为转2