常用的一维搜索方法

无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。

这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。

（直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。

间接法：又称解析法，是应用数学极值理论的解析方法。

首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。

）在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。

根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。

一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。

一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。

由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。

在多变量函数的最优化中,迭代格式X k+1=X k+a k d k其关键就是构造搜索方向d k和步长因子a k设Φ(a)=f(x k+ad k)这样从凡出发,沿搜索方向d k,确定步长因子a k,使Φ(a)<Φ(0)的问题就是关于步长因子a的一维搜索问题。

其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。

一维搜索通常分为精确的和不精确的两类。

如果求得a k使目标函数沿方向d k达到极小,即使得f (x k+a k d k)=min f (x k+ ad k) ( a>0)则称这样的一维搜索为最优一维搜索,或精确一维搜索,a k叫最优步长因子;如果选取a k使目标函数f得到可接受的下降量,即使得下降量f (x k)一f (x k+a k d k)>0是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维搜索。

凸优化之⽆约束优化（⼀维搜索⽅法：⼆分法、⽜顿法、割线法）1、⼆分法（⼀阶导）⼆分法是利⽤⽬标函数的⼀阶导数来连续压缩区间的⽅法，因此这⾥除了要求 f 在 [a0,b0] 为单峰函数外，还要去 f(x) 连续可微。

（1）确定初始区间的中点 x(0)=(a0+b0)/2 。

然后计算 f(x) 在 x(0) 处的⼀阶导数 f'(x(0))，如果 f'(x(0)) >0 , 说明极⼩点位于 x(0)的左侧，也就是所，极⼩点所在的区间压缩为[a0,x(0)]；反之，如果 f'(x(0)) <0，说明极⼩点位于x(0)的右侧，极⼩点所在的区间压缩为[x(0)，b0]；如果f'(x(0)) = 0，说明就是函数 f(x) 的极⼩点。

（2）根据新的区间构造x(1)，以此来推，直到f'(x(k)) = 0，停⽌。

可见经过N步迭代之后，整个区间的总压缩⽐为（1/2）N，这⽐黄⾦分割法和斐波那契数列法的总压缩⽐要⼩。

1 #ifndef _BINARYSECTION_H_2#define _BINARYSECTION_H_34 typedef float (* PtrOneVarFunc)(float x);5void BinarySectionMethod(float a, float b, PtrOneVarFunc fi, float epsilon);67#endif1 #include<iostream>2 #include<cmath>3 #include "BinarySection.h"45using namespace std;67void BinarySectionMethod(float a, float b, PtrOneVarFunc tangent, float epsilon)8 {9float a0,b0,middle;10int k;11 k = 1;12 a0 = a;13 b0 = b;14 middle = ( a0 + b0 )/2;1516while( abs(tangent(middle)) - epsilon > 0 )17 {18 #ifdef _DEBUG19 cout<<k++<<"th iteration:x="<<middle<<",f'("<<middle<<")="<<tangent(middle)<<endl;20#endif2122if( tangent(middle) > 0)23 {24 b0 = middle;25 }26else27 {28 a0 = middle;29 }30 middle =( a0+b0)/2;31 }3233 cout<<k<<"th iteration:x="<<middle<<",f'("<<middle<<")="<<tangent(middle)<<endl;34 }1 #include<iostream>2 #include "BinarySection.h"345float TangentFunctionofOneVariable(float x)6 {7return14*x-5;//7*x*x-5*x+2;8 }910int main()11 {12 BinarySectionMethod(-50, 50, TangentFunctionofOneVariable, 0.001);13return0;14 }1th iteration:x=0,f'(0)=-52th iteration:x=25,f'(25)=3453th iteration:x=12.5,f'(12.5)=1704th iteration:x=6.25,f'(6.25)=82.55th iteration:x=3.125,f'(3.125)=38.756th iteration:x=1.5625,f'(1.5625)=16.8757th iteration:x=0.78125,f'(0.78125)=5.93758th iteration:x=0.390625,f'(0.390625)=0.468759th iteration:x=0.195312,f'(0.195312)=-2.2656210th iteration:x=0.292969,f'(0.292969)=-0.89843811th iteration:x=0.341797,f'(0.341797)=-0.21484412th iteration:x=0.366211,f'(0.366211)=0.12695313th iteration:x=0.354004,f'(0.354004)=-0.043945314th iteration:x=0.360107,f'(0.360107)=0.041503915th iteration:x=0.357056,f'(0.357056)=-0.001220716th iteration:x=0.358582,f'(0.358582)=0.020141617th iteration:x=0.357819,f'(0.357819)=0.0094604518th iteration:x=0.357437,f'(0.357437)=0.0041198719th iteration:x=0.357246,f'(0.357246)=0.0014495820th iteration:x=0.357151,f'(0.357151)=0.0001144412、⽜顿法（⼆阶导）前提：f 在 [a0,b0] 为单峰函数，且[a0,b0] 在极⼩点附近，不能离的太远否则可能⽆法收敛。

常用一维搜索算法常用一维算法一维算法是解决一维问题的常用方法。

一维算法主要通过在一维数据集中查找目标元素来解决问题。

以下是一些常用的一维算法：1. 线性（Linear Search）：线性算法是一种最简单的算法，也是最基本的一维算法。

它从头到尾依次检查数据集中的每个元素，直到找到目标元素或遍历完整个数据集。

线性算法的时间复杂度为O(n)。

2. 二分（Binary Search）：二分算法是一种高效的算法，但它要求数据集必须是有序的。

算法通过将数据集分成两半，并与目标元素进行比较，从而确定目标元素在哪个半部分中。

然后，它将重复这个过程，直到找到目标元素或数据集被划分为一个元素。

二分算法的时间复杂度为O(log n)。

3. 插值（Interpolation Search）：插值算法是改进的二分算法，它根据目标元素与数据集中元素的相对位置来确定的起始位置。

它使用目标元素与数据集首尾元素之间的比例来估计目标元素的位置。

插值算法在数据集分布均匀的情况下具有较好的性能。

4. 斐波那契（Fibonacci Search）：斐波那契算法基于斐波那契数列来确定的起始位置。

它通过比较目标元素与斐波那契数列中的元素来确定的范围，并将数据集划分成两部分。

然后，它在适当的部分中重复这个过程，直到找到目标元素。

斐波那契算法的时间复杂度为O(log n)。

5. 插入（Interpolation Search）：插入算法是一种改进的线性算法，它使用了数据集中元素的顺序信息来提高效率。

与线性算法一样，它从头到尾依次检查数据集中的每个元素，但是当元素不满足条件时，它会根据元素的顺序信息来确定的方向，从而减少的次数。

6. 哈希（Hash Search）：哈希算法使用哈希函数将数据集中的元素映射到哈希表中的索引。

然后，它通过查找哈希表中的索引来确定目标元素的位置。

哈希算法通常具有很高的效率，但是它需要额外的内存空间来存储哈希表。

上述算法是一维问题的常用解决方法。

§4.3 一维搜索方法一维搜索问题：目标函数为单变量的非线性规划问题，即)(min max00t t t t ϕ≤≤≥ （4.3.1）对t 的取值为0≥t 的（4.3.1）称为一维搜索问题，即 )(min 0t t ϕ≥ ；对t 的取值为max 0t t ≤≤的（4.3.1）称为有效一维搜索问题，即 )(minmax0t t t ϕ≤≤。

1、0.618法（近似黄金分割法）单谷函数：称函数)(t ϕ是区间],[b a 上的单谷函数，若存在 ],[*b a t ∈，使得)(t ϕ在],[*t a 上严格递减，且在],[*b t 上严格递增。

区间],[b a 称为)(t ϕ的单谷区间。

求解一维搜索问题的方法：先设法给出一个搜索区间],[b a ，然后通过迭代不断缩小搜索区间，当区间的长度充分小是，可取这个区间中的任一点作为一个近似极小点。

考虑问题)(min t bt a ϕ≤≤ （4.3.2）其中],[b a 是)(t ϕ的单谷区间， 下面将通过迭代不断缩小搜索区间， 获得)(t ϕ的唯一极小点 *t 的近似解。

在],[b a 内任取两点 21,t t ，设 21t t <，由于)(t ϕ是区间],[b a 上的单谷函数，所以有<1> 若)()(21t t ϕϕ≤，则 ],[2*t a t ∈；<2> 若)()(21t t ϕϕ≥，则 ],[1*b t t ∈。

证<1>：若],[2*t a t ∉，则 2*t t >，所以*21t t t a <<<，因为)(t ϕ在],[*t a 上严格递减，所以)()(21t t ϕϕ>，矛盾。

同理可证 <2>。

通过比较)(1t ϕ和)(2t ϕ的大小，可将搜索区间缩小为],[2t a 或],[1b t 。

不妨设为],[2t a ，则在],[2t a 只需另找一个点 2t '，比较 1t 和2t '的目标函数值，又可以进一步缩小搜索区间。