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 ，寻找改善方向S0
Step1 取沿改善方向S0所跨过步长为0
（保持可行改善）求X1= X0+ 0 S0
Step2 对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,进入Step1
Step1
若 bk- ak<l,则停算，极小点 [ ak,bk ]否则求：
a1
(a1 + b1)/2
f(a1)
b1
f(b1)
uk
vk
f(uk)
f(vk)
uk=ak+(bk-ak)/2-
vk=ak+(bk-ak)/2+
若f(uk) f(vk),则令
ak+1 =ak和 bk+1= vk
否则令 ak+1 = uk和 bk+1= bk
Step2令k+1 k,转Step1
a
(a+b)/2
f(a)
b
f(b)
uk
vk
f(uk)
f(vk)
a2
f(a2)
b2
f(b2)
黄金分割法（法）
Step0 给定容许最终不确定区间长度为l >0，初始区间[a1,b1 ],令k=1,进入Step1
Step1 若 bk- ak<l,则停算,极小点x* [ ak,bk ] 否则计算 f 在
uk=ak+(bk-ak)
vk=ak+(bk-ak) 的值。
a1
f(a1)
b1
f(b1)
uk
vk
f(uk)
f(vk)
uk=ak+(bk-ak)
a1
f(a1)
b1
f(b1)
uk
vk
f(uk)
f(vk)
uk=ak+(bk-ak)
Step2 若f(uk)>f(vk),则令
ak+1 = uk和bk+1= bk
否则令 ak+1 = ak和bk+1= vk
Step3 令k+1 k,转Step1
分数法（Fibonacci法）
Fibonacci数列：F0=F1=1,Fk+2=Fk+1+Fk
Fn = 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,进入Step1
a1
f(a1)
b1
f(b1)
uk
vk
f(uk)
f(vk)
u1=a1+ (Fn-2/ Fn) (b1-a1)
a1
f(a1)
b1
f(b1)
uk
vk
f(uk)
f(vk)
v1=a1+ (Fn-1/ Fn) (b1-a1)
Step1 若 f(uk)>f(vk) 转Step2
若 f(uk)f(vk) 转Step3
Step2 令 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 ) 且
转Step4
Step3 令 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 ) 且
转Step4
Step4 令k+1k,转Step1
Step5 令 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为缩减比。
Fn (b1-a1)/l
=Fn-k/Fn-k+1
分数法
-1 l/(b1-a1)
=-1
黄金分割法
l/(b1-a1)
<
二分法
计算次数n
缩减比
搜索方法
三种搜索方法效率的比较
例6-5 f(X)= 在[0，10]内的极小值，要求精度不超过1。
解： f(X)= 在[0，10]内为凸函数，即单峰函数。
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/13
v1=a1+ (Fn-1/ Fn) (b1-a1)=0+(8/13)*10=80/13
令k=1,进入Step1
0
10
f(10)
f(uk)
f(vk)
u1=0+ (5/13) (10-0)
v1=0+ (8/13) (10-0)
f()
Step1 计算 f(u1) = f(50/13)=
f(v1) = f(80/13)=
因为 f(u1)<f(v1) 转Step3
Step3 令 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
因为 kn-2, 估计 f(u2) = f(30/13) =
转Step4
Step4 令1+11,k=2 转Step1
Step1 计算 f(u2)= f(30/13)=
f(v2) = f(50/13)=
因为 f(v2)<f(u2) 转Step2
Step2 令 a3 = u2= 30/13 和
b3 = b2 = 80/13
u3 = 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 ) =
转Step4
Step4 令2+11,k=3转Step1
Step1 计算 f(u3) = f(50/13)=
f(v3) = f(60/13) =
因为 f(u3)<f(v3) 转Step3
Step3 令 a4 = a3 = 30/13 和
b4 = v3 = 60/13
v4 = 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) = -
转Step4
Step4 令3+11, k=4 转Step1
Step1 计算 f(u4) = f(40/13) =
f(v4) = f(50/13) =
因为 f(v4)<f(u4) 转Step2
Step2 令 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, 转Step5
Step5 令 u6 = u6-1 = 50/13 和
v6= u6-1+ ，取 =2/13，v6= 4
计算 f(u6)= f(50/13) =
f(v6)= f(4) =
因为 f(u6) f(v6)
令 a6 = a6-1 = 40/13 和 b6 = u6 = 50/13，
停止,则最优解落在区间[40/13,50/13] 中。
[40/13,50/13]= [,]
精确度小于1。
计算：
Xa = f() =
Xb = f() =
取近似最优解为：
X = (Xa + Xb)/2=
f() =
可以计算其精确最优解为：
X = f() =
用导数的搜索方法:
最速下降法(梯度法)
引理: 设 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,进入Step1
Step1若 ||f(Xk)|| 2 < 则停止计算.
否则令 Sk= - f(Xk) 进入Step2
Step2 作一维搜索:Min f (Xk+Sk)
得解为k,,令
Xk+1= Xk+k Sk
Step3 令k+1 k,转Step1
例6-6 用梯度法求解
Min f(x1,x2)=3x12+2x1x2+x22+2x1-2x2 +1
精度 =。
解：
Step0 = >0, 初始点X0=(0,0) T
令k=0, 进入Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
f(X0)=(2 ,–2)T ,|| f(X0) || 2 =8>
令S0= - f(X0)=(-2 ,2)T 进入Step2
Step2 作一维搜索:Min f (X0+S0)
= Min f (-2, 2) = Min (82 -8+1)
得解为0 =1/2,令 X1= X0+0 S0 =(-1 ,1)T
Step3 令0+1 k, k=1,转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
f(X1)=(-2 ,–2)T,|| f(X1)|| 2 =8>
令S1= - f(X1)=(2 ,2)T 进入Step2
Step2 作一维搜索:Min f (X1+S1)
= Min f (-1+2, 1+2) = Min (242 -8+1)
得解为1=1/6,令 X2= X1+1 S1 =(-2/3 ,4/3)T
Step3 令1+1 k, k=2,转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
f(X2)=(2/3 ,-2/3)T ,||f(X2)|| 2 =(8/9)>
令S2= - f(X2)=(-2/3 ,2/3)T 进入Step2
Step2 作一维搜索:Min f (X2+S2)
= Min ((8/9)2 –(8/9)-5/3)
得解为2=1/2,令 X3= X2+2 S2 =(-1 ,5/3)T
Step3 令2+1 k, k=3,转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
f(X3)=(-2/3 ,-2/3)T ,||f(X3)||2 =(8/9)>
令S3= - f(X3)=(2/3 ,2/3)T 进入Step2
Step2 作一维搜索:Min f (X3+S3)
= Min ((8/3)2 –(8/9)-17/9)
得解为3 =1/6,令 X4= X3+3 S3=(-8/9 ,16/9)T
Step3 令3+1 k, k=4,转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
f(X4)=(2/9 ,-2/9)T
|| f(X4) ||2= (8 / 81 ) <
停止计算.
则 X4= (-8/9 ,16/9)T 作为近似解
f(X4) = f(-8/9 ,16/9)= -161/81= 而精确解 X = (-1 ,2)T f(X)= f(-1 ,2)= -2
共轭梯度算法
Step0 给定终止允许误差为>0, 初始
点X0,y0=X0 S0=- f(y0)
令k=j=0,进入Step1
Step1若 ||f(yj)|| 2 < 则停止计算.
否则进入Step2
Step2 作一维搜索:Min f (yj+Sj)
得解为j,令 yj+1= yj+j Sj
当j<n-1,转Step3,否则转Step4
Step3 令
Sj+1= - f(yj+1) +{|| f(yj+1) || 2 / || f(yj) || 2} Sj
令j+1 j,转Step1
Step4 令y1=Xk= yn, S1= - f(y1)
j=1 , k+1 k ,转Step1
例6-7 用共轭梯度法求解
Min f(x1,x2)=3x12+2x1x2+x22+2x1-2x2 +1
精度 =。
解：
Step0 = >0, 初始点X0=(0,0) T y0=X0=(0,0) T, S0= - f(y0)=(-2 ,2)T
令k=j=0, 进入Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
|| f(y0) || 2 = 8 > 进入Step2
Step2 作一维搜索:Min f (y0+S0)
= Min f (-2, 2) = Min (82 -8+1)
得解为0=1/2,令 y1= y0+0 S0 =(-1 ,1)T
j=0<n=2-1 转Step3
Step3
S1= - f(y1) +{|| f(y1) || 2 / || f(y0) || 2} S0
= (0 ,4)T
令0+1 j, j=1,转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
|| f(y1) || 2 = 8 > 进入Step2
Step2 作一维搜索:Min f (y1+S1)
= Min (162 -8-1)
得解为1 =1/4,令 y2= y1+1 S1 =(-1,2)T
j=1=n=2-1 转Step4
Step4 令y1=X2=y2=(-1,2)T
S1= - f(y1) = (2,2)T
j=1,k+1=0+1=1
转Step1
Step1 f(X)=(6x1+2x2+2 ,2x1+2x2 –2)T
|| f(y2) || 2 = 0 <
则 X2= (-1 ,2)T 作为近似解
f(X2)= f(-1 ,2) = -2
也是精确解
X = (-1 ,2)T
f(X)= f(-1 ,2) = -2
