第4章一维搜索法

第四章

一维搜索法求目标函数极值的方法和函数极值点存在的条件，都离不开求目标函数的一、二阶导数或偏导数。但有时函数的导数不易求得，甚至根本就不存在。这时，上述方法就无法应用。直接探索

(或称搜索)方法就是在这神情况下形成与发展起来的，并且在工程实践中得到了广泛应用。对于单个变量(一维问题)的直接探索，通常称为一维探索(或一维搜索、寻查)或线性探索。它是一维最优化问题的常用方法。求多维目标函数的极值问题，可以处理为从选定的初始点出发，X

(0)沿着某一使函数值下降的待定方向S

(0)求出目标函数在此方向上的极值点X

(1)，然后再从点X

(1)出发沿使目标函数值继续下降的另一个特定方向S

(1)求目标函数新的极值点X

(2)。如此逐步迭代下去，直到满足迭代终止判据并求出近似的最优解X

*

为止。第四章 一维搜索法第四章 一维搜索法X

(k

+1)下降的规定方向S

(k

)

找出在此方向的极值点

。这一过程是最优化方法中的一种基本过程，在此过程中因出发点探索方向均暂时为定值，因此，为了使目标函数值为最小，只要找到合适的步长就可以了。也就是说，在任何一次迭代计算过程中，当起步点 和X

(方k

)

向 S确(

k定)

之后，就把求多维目标函数的极小值这个多维问题，变成求一个变量即步长 的a(最k

)

优值的一维问题了。即:以上每一步的格式都是从某一定点X

(k

)出发，沿着某一使函数值f

(

X

(k

)

+

aS

(k

)

)

=

f

(

X

(k

)

+

a(k

)

S

(k

)

)X

(k

+1)

=

X

(k

)

+

a(k

)

S

(k

)min第四章 一维搜索法一维优化需要解决两个方面的问题：确定极小点存在的区间，即搜索区间（初始区间）。（加步探索法，进退法，或叫外推法）在搜索区间上寻优。（试探法：对分法、黄金分割法，插值法：抛物线法）第四章 一维搜索法由单谷函数的性质可知，在极小点左边函数值应一直下降，而在极小点右边则函数值应严格上升，函数值具有的特征是：“高－低—方向上的三x1个<

点x2

<

x3

，以，便可通过比较三个函数值的及其函f

(数x1值)f

(x2，)f

(x3和)高”。根据这一特点，S若(k已)知大小估计极小点所在[的a,区b]间4-1

确定初始区间的进退法xf

(x1)f

(x2

)

f

(x3

)f

(x)0x1x2x34-1

确定初始区间的进退法f

(x1)

>

f

(x2

)

>

f

(x3

)极小点在右端点的x3

右侧f

(x2

)f

(x1)f

(x)x0x1

x2x33-1

确定初始区间的进退法f

(x1)

<

f

(x2

)

<

f

(x3

)极小点在左端点的

x1

左侧f

(x3

)f

(x2

)f

(x3

)f

(x)f

(x1)x0x1

x2x34-1

确定初始区间的进退法f

(x1)

>

f

(x2

)

<

f

(x3

)极小点在

x1

与

x3

之间[x1,

x3

]称为初始区间，记为：[a,

b]4-1

确定初始区间的进退法探测初始空间的进退法步骤:给定初始点

x0

,初始步长h

,令

x1

=

x0

,记:

f1

=

f

(x1)产生新的探测点x2

=x1

+h，记f2

=f

(x2

)比较函数值f1

和f2

的大小,确定向前或向后探测的策略若:若:f1

>

f2f1

<

f2则加大步长,令

h

=

2h

,转(4)向前探测则调转方向,令

h

=

-h

,转(4)向后探测(4)产生新的探测点x3

=x0

+h

,令f3

=f

(x3

)(5)比较函数值f2

和f3

的大小若:则初始区间已经找到,令c

=x2

,fc

=f2当

h

>

0

时,

[a,

b]=

[x1,

x3

]当

h

<

0

时,

[a,

b]=

[x3,

x1

]f2

<

f34-1

确定初始区间的进退法若:则继续加大步长,令h=

2h

,

x1

=

x2

,

x2

=

x3转(4)继续探测。f2

>

f3例题:求f

(x)=3x2

-4x

+2

的极小点的初始区间4-1

确定初始区间的进退法%f.mfunction

f=f(x)f=3*x^3-4*x+24-1

确定初始区间的进退法c=f2,fc=f2if

h>0a=x1,b=x3fa=f1,fb=f3elsea=x3,b=x1fa=f3,fb=f1enda,b,c,fa,fb,fc%initial_space.mfunction

[a,b,c,fa,fb,fc]=initial_space(x0,h)x1=x0；f1=f(x1)；x2=x0+h；f2=f(x2)；if

f1>f2x3=x0+2*h；f3=f(x3)；elseh=-h；x2=x0+h；f2=f(x2)；Endwhile

f2>f3h=2*h；x1=x2；x2=x3；f1=f2；f2=f3；x3=x2+h；f3=f(x3)；Endc=f2；fc=f2；if

h>0a=x1；b=x3；

fa=f1；fb=f3；elsea=x3；b=x1；

fa=f3,；b=f1；end[a

b

c

fa

fb

fc]Matlab函数文件：三、单谷区间与单谷函数由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念．a

=

2三、单谷区间与单谷函数由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念．定义4.2

设j

:

R1

fi

R1，闭区间

[a,

b]

R1．若存在点t

*

˛

[a,

b]，使得j(t)在[a,

t*

]上严格递减，j(t)

在[t*,b上]严格递增，则称[a,b]是函数j

(t)的单谷区间，j

(t)是[a,b]上单谷函数．由定义4.2易知，一个区间是某函数的单谷区间意味着，在该区间中函数只有一个“凹谷”（极小值）．例如，图4.3中不是 的单谷区间，上的单谷函数．[的a,b]是

的单谷区[间a,

，b]也即j

(t)是

上的单谷j函即 不是(t数)

．图[a4,

.b4]中的j

(t)

j

(t)[a,

b]图4.2开始选取初始点t0

,初始步长

h0

>0,加步系数a

>1

,令k=0j0

=j(t0

),比较目标函数值tk

+1

=

tk

+

hk

,jk

+1

=

j(tk

=1)a

=

min{t,

tk

+1

}结束hk

+1

=

a

hk

,t

=

tk

,tk

=

tk

+1

,jk

=

jk

+1

,k=k+1h

k

=

-

h

k

t=k+1Nk=0YNj

k

+

1

<

j

kY另外，从定义4.2还可知，某区间上的单谷函数在

该区间上不一定是连续函数，而凸函数在所给

区间上必然是单谷函数（如图4.3所示）．由定

义4.1和定义4.2知，函数的单谷区间总是相应问题（4.3）的一个搜索区间（如图4.3所示），但反之不然（如图4.4所示）．单谷区间和单谷函数有如下有用的性质：定理4.1

设j

:R1

fi

R1

,[a,b]是的单谷区间，任取t1

,

t2

˛

[a,

b]并且

t2

<

t1

．（1）若有j

(t2

)£

j

(t1

)间．（2）若有j

(t2

)‡j

(t1

)间．，则[a,t1

]是j

(t)的单谷区，则[t2

,b]是j

(t)的单谷区图4.3图4.4证明略．定理4.1说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间．换句话说利用这个定理可以把搜索区间无限缩小，从而求到极小点．以下介绍的几种一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解．§4.2

对分法一、对分法基本原理求解一维最优化问题minj(t)一般可先确定它的一个有限搜索区间

[a,

b]

，把问题化为求解问题min

j

(t)，然后通过不断缩短区间的长度，最a£t

£b后求得最优解．设j：R1

fiR1

在已获得的搜索区间

[a,

b]

内具有连续的一阶导数．因为j

(t)在[a,b]上可微，故j

(t)在[a,b]上连续，由此知j

(t)在[a,b]上有最小值．令

j

(t)

=

0

，总可求得极小点

t

*

．不妨设j

(t)在

(a,

t

*

)上是单减函数；在(t

*

,b)上是单增函数．所以t

˛

(a,

t*

)时，j

(t)

<

0

，故

j

(a)

<

0

；当t

˛

(t*

,b)时，j

(t)>0

，亦即j

(b)>0．对分法的原理如图4.5所示．图4.5二、对分法迭代步骤已知j

(t)，j

(t)表达式，终止限

．(1)确定初始搜索区间[a,b]，要求j

'(a)

<

0，j

'(b)

>

0．．t

*

=c，转(5)；若j

(c)>0，则b

=c

，转(4)．(4)若|

a

-b

|<e转(2)．(5)打印t

*，停机．对分法的计算流程如图4.6所示．2(2)计算[a,b]的中点c

=1

(a

+b)(3)若j

(c)，<0则a

=c，转(4)；若j

(c)=0

，则2，则t

*

=

1

(a

+

b)

，转(5)；否则三、对分法有关说明对分法每次迭代都取区间的中点，若这点的导数值小于零，说明的根位于右半区间中（如图4.5所示），因此去掉左半区间；若中点导数值大于零，则去掉右半区间；若中点导数值正好等于零，则该点就是极小点．因为每次迭代都使原区间缩短一半，所以称为对分法或二分法．开始确定[a

b],要求c=(a+b)/2b=ct*=(a+b)t*=cNYa=cNYNY/2输出t*结束图4.6§4.3

Newton一、Newton切线法基本原理设j

:

R1

fiR1在已获得的搜索区间[a,b]内具有连续二阶导数，求min

j

(t)

．a£t

£b因为j

(t)

在

[a,

b]

上可微，故j

(t)

在[a,b]

上有最小值，令

j

(t)

=

0

．下面不妨设在区间[a,b]中经过k

次迭代已求得方程j

(t)=0

的一个近似根tk

．过(tk

,j

(tk

))作曲线的切线y

=j

(t),其方程是y

-

j

(tk

)

=

j

(tk

)(t

-

tk

)

（4.4）一、牛顿法切线法基本原理设f(x)为一个连续可微的函数，则在x0附近，该函数应该与一个二次函数接近，即可在点x0附近用一个二次函数φ(x)来逼近函数f(x)，即：212f

(x)»

f(x)

=

f

(x0

)

+

f

'(x0

)(x

-

x0

)

+f

"(x0

)(x

-

x0

)用二次函数的φ(x)极小点x1作为f(x)极小点的一个近似点。根据极值必要条件:f

'(x1

)

=

0§4.3

Newton切线法f

'(x0

)

+

f

"(x0

)(x1

-

x0

)

=

0即0f

'(x0

)f

"(x

)x1

=

x0

-依次继续下去，可得牛顿迭代公式：kkf

'(x

)f

"(x

)xk

+1

=

xk

-在图中，在a0

处用一抛物线φ0(a)代替曲线f(a)，相当于用一斜直线φ0′(a)代替曲线f'(a)。这样各个近似点是通过对作f'(a)切线求得与轴的交点找到的，所以，

有时，牛顿法又称作切线法。牛顿法的几何解释然后用这条切线与横轴交点的横坐标tk

+1

作为根的新的近似（如图4.7所示）．它可由方程（4.4）在令y

=0

的解出来，即．j

¢(tk

)j

(t

)tk

+1

=

tk

-

k这就是Newton切线法迭代公式．二、Newton切线法迭代步骤已知j

(t)

，j

(t)

表达式，终止限

．确定初始搜索区间[a,b]，要求j

'(a)

<

0，j

'(b)

>

0

．选定t0

．(3)计算t

=t0

-j

'(t0

)/j

"(t0

)．(4)若|

t

-t0

|‡e（5）．，则

t0

=

t

，转（3）；否则转(5)打印t，j(t)，停机．Newton切线法的计算流程如图4.8所示．图4.7三、Newton切线法有关说明这种方法一旦用好，收敛速度是很高的．如果初始点选得适当，通常经过几次迭代就可以得到满足一般精度要求的结果，但是它也有缺点．第一，需要求二阶导数．如果在多维最优化问题的一维搜索中使用这种方法，就要涉及

Hesse矩阵，一般是难于求出的．第二，当曲线y

=j

(t)在[a,b]上有较复杂的弯曲时，这种方法也往往失效．如图4.9所示的迭代：t2

，结果t2

跳出[a,b]．t0

fi

t1

fit

=

t

-

j

'

(t

)

/

j

''

(t

)0

0

0输出t*,j*开始t0

=

tNt

-

t0

£Yt*

=

t

,j*

=

j(t

)0

0选定t0,确定[a

b],要求j

'(a)<0,j(b)>0结束图4-8图4.9图4.10§4.4

黄金分割法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题．所谓黄金分割就是将一线段分为二段的方法．这样分后，要求整段长L与较长段x的比值正好等于较长段x与较短段L

-x

的比值（如图4.11所示），即．．x L

-

x于是有

x

2

+

Lx

-

L2

=

0，解出其正根L

=

x2x

=

5

-1

L

»

0.618L由此可见长段的长度应为全长的0.618倍，而短段的长度应为全长的0.382倍．因为古代的人们认为按0.618的比率来分割线段是最协调，胜似黄金，故称之为黄金分割．图4.114-4

黄金分割法一维搜索试探方法的基本思想：在确定了搜索区间的前提下，不断缩小搜索区间，同时保持搜索区间内函数值

“大-小-大”的走势，直到区间的宽度小于预定的精度。黄金分割法基本思想：在搜索区间内插入两个黄金分割点，将区间分成三段。利用函数的单谷性质，通过函数值大小的比较，删去其中一段。在保留下来的区间上作同样的处置，如此往复送代，使搜索区间缩小到精度范围内，得到极小点的近似解。4-4

黄金分割法4-4

黄金分割法黄金分割法是按照对称的原则选取中间插入点而缩小区间的。具有每次达代计算时缩短率不变的特点。LlL(1

-

l)Llllaabx1x2x1x2bx2x14-4

黄金分割法2l

=

5

-1

»

0.618l2

+

l

-1

=

0+

-1

=

0Ll

=

l

=

L

-

lL

ll

2

-

L(L

-

l)

=

0

L

l

2lLlL(1

-

l

)

Llllaabx1x2x1x2b21x

x缩短率不变4-4

黄金分割法黄金分割法的收敛准则：区间长度达到充分小当：

时b

-

a

£

e2x*

=

a

+

b

b

-

a

ln

0.618n‡

由于黄金分割法每次区间收缩比率是完全相等的，如果给定收敛精度和初始区间长度，则完成一维收缩所需缩小区间的次数为：0.618n

(b

-

a)

£

eln

e

4-4

黄金分割法二、黄金分割法的计算步骤：给定初始区间[a,b]和收敛精度产生中间插入点并计算其函数值x1

=

a

+

0.382(b

-

a),

f1

=

f

(x1

)x2

=

a

+

0.618(b

-

a),

f2

=

f

(x2

)比较函数值f1

和f2

，确定区间的取舍：若f1

<f2

，则新区间[a,b]=[a,x2

]令b

=x2

,x2

=x1

,f2

=f1记N0

=0若f1

>f2

，则新区间[a,b]=[x1

,b]令a

=x1

,x1

=x2

,f1

=f2记N0

=14-4

黄金分割法否则转（5）2（4）收敛判断：若

b

-

a

£

e，令：x*

=

a

+

b

，结束搜索，（5）产生新的插入点若N0

=0

，则取若N0

=1

，则取x1

=

a

+

0.382(b

-

a),

f1

=

f

(x1

)x2

=

a

+

0.618(b

-

a),

f2

=

f

(x2

)转（3）进行新的区间缩小。t*

,j*开始确定[a,b]b

=

(

5

-1)

/

2t2

=

a

+

b(b

-

a)j2

=

j

(2

)t1

=

a

+

b

-

t

2j1

=

j

(t1

)1

2t*

=

(t

+

t

)

/

2j*

=

j(t*

)结束Nb

=

t2

t2

=

t1

j2

=

jNY1

2t

-

t

<

ea

=

t1

,

t1

=

t

2

,

j

1

=

jt2

=

a

+

b

(b

-

a),

j2

=

j

(t2

)j

1

<

j

2Y图4.134-4

黄金分割法例题:求

f

(x)

=

3x2

-

4x

+

2

的极小点，给定

x

=

0

，

h

=10e

=

0.2（1）确定初始区间[a,b]=[0,2]（2）用黄金分割法缩小区间Matlab函数文件：%golden_setion_methodfunction

goldensection(a0,b0,eps)a=a0;b=b0;x1=a+0.382*(b-a);f1=f(x1);x2=a+0.618*(b-a);f2=f(x2);if

f1<f2n0=0;b=x2;x2=x1;f2=f1;elsen0=1;a=x1;x1=x2;f1=f2;Endwhile

abs(b-a)>epsif

n0==0x1=a+0.382*(b-a);f1=f(x1);elsex2=a+0.618*(b-a);f2=f(x2);endiff1<f2n0=0;b=x2;x2=x1;f2=f1;4-4

黄金分割法elsen0=1;a=x1;x1=x2;f1=f2;endenda,b,x=(a+b)/2,f=f(x)三、黄金分割法有关说明黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点．该方法适用于单谷区间上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛．§4.5

抛物线插值法一、抛物线插值法基本原理考虑一维搜索问题min

j

(t)，．t1

£t£t2假设其中j

(t)是定义在区间[t1

,t2

]上的单峰函数．首先用试探法在[t1

,t2

]上找一点t0

，使之满足j(t1

)

‡

j(t0

)，j(t2

)

‡

j(t0

)通过目标函数曲线上的三个点(t1

,j

(t1

)),(t0

,j

(t0

)),(t2

,j

(t2

))，作它的二次拟合曲线（如图4.14所示）．P(t)

=

a0

+

a1t

+

a2

t

2图4.14由于上述三个点既是目标函数曲线j

(t)上的点，又是二次拟合曲线P(t)上的点，故有方程组（4.5）（4.6）+

a

t

+

a t

2

=

j(t

)．1

2

2

2

2+

a

t

+

a t

2

=

j(t

)，1

0

2

0

0+

a

t

+

a t

2

=

j(t

)，1

1 2

1

12

0P(t

)

=

a将方程组（4.5）中的a0

消去，得0

01

0P(t

)

=

aP(t

)

=

a2

21

1

0

2

11020202-j(t

)，=

j(t

)-j(t

)．a

(t

-

t

)

+

a

(t-

t

)

=

j(t

)a

(t

-

t

)

+

a

(t

-

t

)

1

0

2

2

0

2从方程组（4.6）可解出待定系数，（4.7）即（4.9）即为二次拟合函数的极小值点．a1

=(t

2

-

t

2

)j

(t1

)

+

(t

2

-

t

2

)j

(t0

)

+

(t

2

-

t

2

)j

(t2

)0

2

2

1

1

0(t1

-

t0

)(t0

-

t2

)(t2

-

t1

)(t

-

t

)j

(t

)

+

(t

-

t

)j

(t

)

+

(t

-

t

)j

(t

)a2

=

0

2

1

2

1

0

1

0

2

．（4.8）(t1

-

t0

)(t0

-

t2

)(t2

-

t1

)对于二次拟合函数P(t)

=

a0

+

a1t

+

a2t

2，我们很容dt易求得它的极小值点．令dP(t)=0a1

+2a2

t

=0，从中解出

2a2at

=

-

1

即为二次拟合函数P(t)的极小值点．将式（4.7）与式（4.8）代入式（4.9）得（

4.11）2（．4.10）0

2

1

2

1

0

1

0a2a2

2

(t0

-

t2

)j

(t1

)

+

(t2

-

t1

)j

(t0

)

+

(t1

-

t0

)j

(t2

)1

(t

2

-

t

2

)j

(t

)

+

(t

2

-

t

2

)j

(t

)

+

(t

2

-

t

2

)j

(t

)t

=

-

1

=用区间[t1

,t2

]上二次拟合函数P(t)的这个极小值点t

作为目标函数

j

(t)

在该区间极小值点的一个估计值．若

t

和

t0已充分接近，即对给定的允许误差e

>0使|

t0

-

t

|<

e成立时，t

就可被看作是j

(t)在区间[t1

,t2

]内近似最优解；否则应缩短区间，按照j

(t)值保持两头大、中间小的原则构成新的三点，继续上述过程，直至不等式（4.11）成立为止．二、抛物线插值法迭代步骤下面具体介绍一下缩短区间，构成新三点的方法．由式（4.15）得到的点

t

，在区间[t1

,

t2

]内既可能在点

t0

的左侧（即

t

<

t0），又可能在

t0

的右侧（即

t

>

t0

），分别对应这两种情形比较j

(t

)和j

(t0

)的大小，又有j

(t

)<j

(t0

)，j

(t

)>j

(t0

)及j

(t

)=j

(t0

)等三种情形，故共有如下六种情况（如图4.15与图4.16所示）：图4.15图4.16，，保留[t1

,t0

]为新区间，故置t2=

t0，j(t2

)

=

j(t0

)，（1）对于图4.15（a）的情况：因j

(t

)<j

(t0

)，所以相对t0为说t

是好点，故划掉区间[t0

,

t2

]t0

=t

，j

(t0

)=j

(t

)，t1保持不变；（2）对于图4.15（b）的情况：因j

(t

)>j

(t0

)，所以相对t

来说t0是好点，故划掉[t1

,t

]，保留[t

,t2

]为新区间，故置t1

=t

，j

(t1

)=j

(t

)t0与t2

保持不变；（3）对于图4.15（c）的情况：因j

(t

)<j

(t0

)，所以相对t0

来说t

是好点，故划掉[t1

,t0

]，保留为新区间[t0

,t2

]，故置t1

=t0，j

(t1

)=j

(t0

)，t0

=t，j

(t0

)=j

(t

)，t2

保持不变；，

2

0

，0；通过上述讨论，我们可直接给抛物线插值法的迭代流程图（图4.17）．（4）对于图4.15（d）的情况：因j

(t

)>j

(t0)，所以相对t

来说t0是好点，故划掉[t

,t2

]保留[t1

,

t

]，故置t2

=

t

，j

(t2

)=

j

(t)

，t0

与t1保持不变．（5）对于图4.16（a）的情况：一般同时划掉[t1

,t

]及[t0

,t2

]仅留中间的[t

,t0

]，故置11t

=

t

j

(t

)

=

j

(t

)0， ，

2t

=

tj

(t

)

=

j

(t

)

t2t

+

t=

1

2

2210t

+

tj(t

)

=

j（6）对于图4.16（b）的情况：一般同时划掉[t1

,

t0

]及[t

,

t2

]

，仅留中间

[t0

,

t

]，故1

01

0置t

=

t

，j

(t

)

=

j

(t

)，t22

0=

t

，j

(t

)

=

j

(t

)

，t2=

t1

+

t2

2

t1

+t2

．j(t0

)

=j三、抛物线插值法有关说明抛物线插值法是多项式逼近法的一

种．所谓多项式逼近，是利用目标函数在若干点的函数值或导数值等信息，构成一个与目标函数相接近的低次插值多项式，用该多项式的最优解作为目标函数的近似最优解．开始确定t0,t1,t2,要求j

(t1

)

‡

j

(t0

),

j

(t2

)

‡

j

(t0

)按(4.10)计算tt1

=

tj(t1

)

=j(t)t

2

=

t

1t

0

=

tj(t2

)

=

j(t0

)j(t1

)

=

j(t)t

1

=

t

1t

0

=

tj

(t1

)

=

j(t0

)j

(