无约束问题的优化方法

4

无约束问题的优化方法（P1）Min

f(X)X

En研究意义：许多问题可转变为无约束问题求解。通常一个算法总包括一维搜索，而一维搜索实质就是一个无约束问题。搜索的基本思想是通过逐次循环，来求得问题的最优解或近似最优解。定义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即为近似最优解。否则，k

+1

k,转Step2二分法Step0

给定

>0,容许最终不确定区间

长度为l

>0，初始区间[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

给定容许最终不确定区间长度

为l

>0，初始区间[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分数法（Fibonacci法）Fibonacci数列：F0=F1=1,Fk+2=Fk+1+FkFn

=

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

给定最终不确定区间长度l

>0，初始区间[a1,b1

],根据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，

停止，则最优解落在区间[an,bn

] 中。为了衡量搜索的效率，引进“缩减比”的概念：给定最终不确定区间长度l1

>0，在

进行了p 个点的函数计算以后，缩短为lp，称

=lp/

l1为缩减比。搜索方法缩减比计算次数n二分法

<0.5p/20.5n/2

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

=0.618p-10.618n-1

l/(b1-a1)分数法

=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数，即单峰函数。Step0

l

=1，

[a1,b1

]=

[0，10]，根据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，停止,则最优解落在区间[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取近似最优解为：X

=

(Xa

+

Xb)/2=

3.4616f(3.4616)

= -39.82可以计算其精确最优解为：X

=

3.6

f(3.6)

= -39.86用导数的搜索方法:最速下降法(梯度法)引理:

设

f(X)

在

X*

点可微，如果

f(X*)

0,

则S=

-

f(X*)为

f(X)

在

X*

点一个下降方向.命题:设f(X)在X*点可微，

f(X*)

0,则(寻找最快下降方向)

Min

f

(X*,S)/

S

其最优解为: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