無約束問題的優(yōu)化方法

4

無約束問題的優(yōu)化方法（P1）Min

f(X)X

En研究意義：許多問題可轉變?yōu)闊o約束問題求解。通常一個算法總包括一維搜索，而一維搜索實質就是一個無約束問題。搜索的基本思想是通過逐次循環(huán)，來求得問題的最優(yōu)解或近似最優(yōu)解。定義1：令S

En

，S

0

X*

∈D

稱S為D在X* 點的一個可行方向，如果存在某個

>0使得：

X*

+

S∈D

，

∈（0，

）。定義2：令S

En

，S

0

X*

∈D

稱S為f在X* 點的一個下降（改善）方向，如果存在某個

>0，使得：f(

X*

+

S)

<f

(

X*

)，

∈（0，

）。定義3：稱S為可行下降方向，如果它既

是可行又是下降的方向。搜索法的算法步驟：Step0

取初始點X0

，尋找改善方向S0Step1

取沿改善方向S0所跨過步長為

0（保持可行改善）求X1=

X0+

0

S0Step2

對Xk-1,尋找改善方向Sk-1

及f(x)，沿改善方向Sk-1所下降最多的步長為

k-1

,求Xk=

Xk-1+

k-1

Sk-1下降最多的步長指求

k-1

滿足Min

f(

Xk-1+

k-1

Sk-1

)Step3對

>0,如果

Xk-

Xk-1

/

Xk

<=

則停算，Xk即為近似最優(yōu)解。否則，k

+1

k,轉Step2二分法Step0

給定

>0,容許最終不確定區(qū)間

長度為l

>0，初始區(qū)間[a1,b1

],令k=1,進入Step1Step1o

若

bk-

ak<l,則停算，極小點

[

ak,bk

]否則求：a1b1f(b1)uk

vk(a1

+

b1)/2f(a1)f(u

f(vk)k)uk=ak+(bk-ak)/2-

vk=ak+(bk-ak)/2+

o

若f(uk)

f(vk),則令ak+1

=ak和

bk+1=vk否則令ak+1

=

uk和

bk+1=

bkStep2令k+1

k,轉Step1abf(b)uk

vk(a+b)/2f(a)f(u

f(vk)k)a2f(a2)b2f(b2)黃金分割法（0.618法）Step0

給定容許最終不確定區(qū)間長度

為l

>0，初始區(qū)間[a1,b1],令k=1,進入Step1Step1

若

bk-

ak<l,則停算,極小點x*

[

ak,bk

] 否則計算

f

在uk=ak+0.382(bk-ak)vk=ak+0.618(bk-ak)的值。a1f(a1)b1f(b1)uk

vkf(vk)f(uk)uk=ak+0.382(bk-ak)a1f(a1)b1f(b1)uk

vkf(vk)f(uk)uk=ak+0.618(bk-ak)Step2

若f(uk)>f(vk),則令ak+1

=

uk和bk+1=

bk

否則令

ak+1

=

ak和bk+1=

vkStep3

令k+1

k,轉Step1分數(shù)法（Fibonacci法）Fibonacci數(shù)列：F0=F1=1,Fk+2=Fk+1+FkFn

=

1,1,2,3,5,8,13,….Step0

給定最終不確定區(qū)間長度l

>0，初始區(qū)間[a1,b1

],根據(jù)Fn

(b1-a1)/l,確定

n, 計算

u1=a1+

(Fn-2/

Fn) (b1-a1)v1=a1+

(Fn-1/

Fn) (b1-a1)令k=1,進入Step1a1f(a1)b1f(b1)uk

vkf(vk)f(uk)u1=a1+

(Fn-2/

Fn)

(b1-a1)a1f(a1)b1f(b1)uk

vkf(vk)f(uk)v1=a1+

(Fn-1/

Fn)

(b1-a1)Step1

若

f(uk)>f(vk) 轉Step2Step2若

f(uk)

f(vk) 轉Step3

令

ak+1

=

uk和bk+1=

bk，uk+1=

vk進一步令

和vk+1

=

ak+1

+

(Fn-k-1/

Fn-k)

(bk+1

-

ak+1)

若k=n-2,轉Step5

否則估計

f(vk+1

)

且轉Step4Step3

令

ak+1

=

ak和bk+1=

vk，vk+1=

uk進一步令

和uk+1=ak+1

+(Fn-k-2/Fn-k)

(bk+1

-ak+1)若k=n-2,轉Step5

否則估計

f(uk+1

)

且轉Step4Step4

令k+1

k,轉Step1Step5

令

un

=un-1

和

vn=un-1+

，若

f(un) >f(vn)

令an

=

vn和bn=

bn-1，否則若

f(un)

f(vn) 令an

=

an-1

和bn=

un，

停止，則最優(yōu)解落在區(qū)間[an,bn

] 中。為了衡量搜索的效率，引進“縮減比”的概念：給定最終不確定區(qū)間長度l1

>0，在

進行了p 個點的函數(shù)計算以后，縮短為lp，稱

=lp/

l1為縮減比。搜索方法縮減比計算次數(shù)n二分法

<0.5p/20.5n/2

l/(b1-a1)黃金分割法

=0.618p-10.618n-1

l/(b1-a1)分數(shù)法

=Fn-k/Fn-k+1Fn

(b1-a1)/l三種搜索方法效率的比較例6-5f(X)=3x2-21.6x-1.0在[0，10]內的極小值，要求精度不超過1。在[0，10]內為凸函解：

f(X)=3x2-21.6x-1.0數(shù)，即單峰函數(shù)。Step0

l

=1，

[a1,b1

]=

[0，10]，根據(jù)Fn

(b1-a1)/l=10,確定

n=6,

F6=13>10計算u1=a1+(F6-2/F6)(b1-a1)=0+(5/13)*10=50/13v1=a1+(Fn-1/Fn)(b1-a1)=0+(8/13)*10=80/13令k=1,進入Step1010f(10)3.8462f(vk)u1=0+

(5/13)

(10-0)6.1538v1=0+

(8/13)

(10-0)f(uk)f(3.6)-39.86-20.3Step1

計算

f(u1)

=f(50/13)=

-39.7f(v1)

=

f(80/13)=

-20.3因為

f(u1)<f(v1)

轉Step3Step3

令

a2

=

a1=

0

和

b2

=

v1=

80/13，

進一步令

v2

=

u1

=

50/13

和u2

=

a2+

(F6-3/

F6-1)

(b2

–a2)=0+(3/8)(80/13)=30/13因為

k

n-2,

估計

f(u2)

= f(30/13)

=-34.9轉Step4Step4Step1令1+1

1,k=2

轉Step1計算

f(u2)=

f(30/13)=

-34.9f(v2)

=

f(50/13)=

-39.7因為

f(v2)<f(u2)

轉Step2Step2

令

a3

=

u2=

30/13和b3

=

b2

=80/13u3

=

v2

=50/13和v3

=

a3+

(F6-3/

F6-2)

(b3–

a3)=

30/13+(3/5)(80-30)/13

=

60/13因為

k

n-2,

估計

f(v3

)

= -34.8

轉Step4Step4

令2+1

1,k=3轉Step1Step1

計算

f(u3)

=

f(50/13)= -39.7f(v3)

=

f(60/13)

=因為

f(u3)<f(v3)-34.8轉Step3Step3

令

a4

=

a3

=

30/13

和b4

=

v3

=

60/13v4

=

u3

=50/13

和u4

=

a4

+

(F1/

F3)

(b4

–

a4)=

30/13+(1/3)

(60-30)/13=

40/13因為

k

n-2,

估計f(u4

)

=

f(40/13)

=

-

39.1轉Step4Step4

令3+1

1,

k=4

轉Step1Step1

計算

f(u4)

=

f(40/13)

=

-39.1f(v4)

=

f(50/13)=

-39.7因為

f(v4)<f(u4)

轉Step2Step2

令

a5

=

u4

=40/13

和b5

=

b4

=60/13進一步令u5

=

v4

=50/13和v5

=

a5

+

(F6-4-1/

F6-4)

(b5

–

a5)=40/13+(1/2)(60-40)/13=

60/13因為

k=n-2, 轉Step5Step5

令

u6=u6-1= 50/13和v6=

u6-1+

，取

=2/13，v6=

4計算

f(u6)=

f(50/13)

=

-39.7f(v6)=

f(4) =

-39.4因為

f(u6)

f(v6)令

a6=

a6-1

=

40/13

和

b6

=

u6

=

50/13，停止,則最優(yōu)解落在區(qū)間[40/13,50/13] 中。[40/13,50/13]=

[3.0769,3.8462]精確度小于1。計算：Xa

=

3.8462Xb

=

3.0769f(3.8462)

=

-39.7f(3.0769)

=

-39.42取近似最優(yōu)解為：X

=

(Xa

+

Xb)/2=

3.4616f(3.4616)

= -39.82可以計算其精確最優(yōu)解為：X

=

3.6

f(3.6)

= -39.86用導數(shù)的搜索方法:最速下降法(梯度法)引理:

設

f(X)

在

X*

點可微，如果

f(X*)

0,

則S=

-

f(X*)為

f(X)

在

X*

點一個下降方向.命題:設f(X)在X*點可微，

f(X*)

0,則(尋找最快下降方向)

Min

f

(X*,S)/

S

其最優(yōu)解為:S*=

-

f(X*)/

||

f(X*)||

為

f(X)

在X*點最速下降方向.即:

-

f(X*)/

||

f(X*)||

(負梯度方

向)為

f(X)

在

X*

點最速下降方向.梯度算法Step0

給定終止允許誤差為

>0, 初始點X0,令k=0,進入Step1Step1若

||

f(Xk)||

2

<

否則令

Sk=

-

f(Xk)則停止計算.

進入Step2Step2

作一維搜索:Min

f

(Xk+

Sk)得解為

k,,令Xk+1=

Xk+

k

SkStep3

令k+1

k,轉Step1例6-6

用梯度法求解2

1

1

2

2

1

2Min

f(x1,x2)=3x

2+2x1x2+x

2+2x1-2x2

+1精度

=0.1。

解：TStep0

=0.1

>0, 初始點X0=(0,0)令k=0, 進入Step1Step1

f(X)=(6x1+2x2+2

,2x1+2x2

–2)T

f(X0)=(2

,–2)T

,||

f(X0)

||

2

=8>0.1令S0=

-

f(X0)=(-2

,2)T

進入Step2Step2

作一維搜索:Min

f

(X0+

S0)=

Min

f

(-2

,

2

)

=

Min

(8

2

-8

+1)

得解為

0

=1/2,令

X1=

X0+

0

S0

=(-1

,1)TStep3

令0+1

k,

k=1,轉Step1Step1

f(X)=(6x1+2x2+2

,2x1+2x2

–2)T

f(X1)=(-2

,–2)T,||

f(X1)||

2

=8>0.1令S1=

-

f(X1)=(2

,2)T

進入Step2Step2

作一維搜索:Min

f

(X1+

S1)=

Min

f

(-1+2

,

1+2

)

=

Min

(24

2

-8

+1得解為

1=1/6,令

X2=

X1+

1

S1

=(-2/3

,4/3)TStep3

令1+1

k,

k=2,轉Step1Step1

f(X)=(6x1+2x2+2

,2x1+2x2

–2)T

f(X2)=(2/3

,-2/3)T

,||

f(X2)||

2

=(8/9)>0.1令S2=

-

f(X2)=(-2/3

,2/3)T

進入Step2Step2

作一維搜索:Min

f

(X2+

S2)=

Min

((8/9)

2

–(8/9)

-5/3)得解為

2=1/2,令

X3=

X2+

2

S2

=(-1

,5/3)TStep3

令2+1

k,

k=3,轉Step1Step1

f(X)=(6x1+2x2+2

,2x1+2x2

–2)T

f(X3)=(-2/3

,-2/3)T

,||

f(X3)||2

=(8/9)>0.1令S3=

-

f(X3)=(2/3

,2/3)T

進入Step2Step2

作一維搜索:Min

f

(X3+

S3)=

Min

((8/3)

2

–(8/9)

-17/9)得解為

3

=1/6,令

X4=

X3+

3

S3=(-8/9

,16/9)TStep3

令3+1

k,

k=4,轉Step1Step1

f(X)=(6x1+2x2+2

,2x1+2x2

–2)T

f(X4)=(2/9

,-2/9)T||

f(X4)

||2=

(8

/

81

)

<

0.1停止計算.X4=

(-8/9

,16/9)T則 作為近似解f(X4)

=

f(-8/9

,16/9)=

-161/81=

-1.9630而精確解X

=

(-1

,2)T

f(X)=

f(-1

,2)=

-2共軛梯度算法Step0

給定終止允許誤差為

>0, 初始

點X0,y0=X0

S0=-

f(y0)令k=j=0,進入Step1Step1若

||

f(yj)||

2

<

則停止計算.否則進入Step2Step2

作一維搜索:Min

f

(yj+

Sj)

得解為

j,令

yj+1=

yj+

j

Sj當j<n-1,轉Step3,否則轉Step4Step3

令Sj+1=

-

f(yj+1)

+{||

f(yj+1)

||

2

/

||

f(yj)

||

2}

Sj令j+1

j,轉Step1Step4

令y1=Xk=

yn,S1=

-

f(y1)j=1

, k+1

k

,轉Step1例6-7

用共軛梯度法求解2

1

1

2

2

1

2Min

f(x1,x2)=3x

2+2x1x2+x

2+2x1-2x2

+1精度

=0.1。解：Step0

=0.1

>0, 初始點X0=(0,0)Ty0=X0=(0,0)

T,

S0=

-

f