结构优化设计第4章 无约束最优化方法

《机械优化设计》§4-8 鲍威尔(Powell)方法¾基本思想：把n维无约束优化问题转化为n个沿坐标轴方向e 1,e 2……e n 的一维优化问题来求解。

坐标轮换法坐标轮换法：1e s x¾特点：z 方法简单，思路简明z 收敛速度太慢，效率太低鲍威尔算法的流程图{n次搜索判定并确定下轮方向组{构造新方向并一维搜索{计算条件参数准备信息判断终止条件5. 鲍威尔法的特点：（1）收敛速度快，可靠性高；（2）对非正定函数，也很有效；（3）计算步骤较复杂。

6. 鲍威尔法与坐标轮换法的主要区别：（1）每轮的搜索次数；（2）每轮的搜索方向组的构造方式。

0.01ε=的最优解。

迭代精度。

z例题（书P85）：用改进的鲍威尔法求目标函数22121212(,)10(5)()f x x x x x x =+−+−解：（一）第1轮迭代计算1）从出发，沿e 1方向进行一维搜索：(1)1100/22 4.5455α==得：(1)1[4.54550]T=x 初始点(1)0[00]T=x 12[10];[01]T T ==e e (1)(1)1120(5)20f ααα′=−+=min :(1)1()f x (1)0x (1)(1)(1)1011α=+x x e (1)2(1)2(1)11110(5)()()f ααα=−+=选取基本搜索方向组：(1)(1)1101;000αα⎡⎤⎡⎤⎡⎤=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦2）从出发，沿e 2方向进行一维搜索：(1)20.826α=得：(1)2[4.54550.826]T=x (1)(1)2220(0.455)2( 4.545)0f ααα′=−+−=min :(1)(1)2(1)2(1)2222()10(4.5455)(4.545)()f f ααα=+−+−=x (1)1x (1)(1)(1)(1)21222(1)24.5454.5450;01ααα⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦xx e (1)2()15.215f =x (1)(1)212()()22.72715.2157.512f f Δ=−=−=x x 3）计算函数值以及下降量(1)0()250f =x (1)1()22.727f =x (1)(1)101()()25022.727227.27f f Δ=−=−=x x (1)()if x i Δ4）求最大下降量121max{,}227.723m Δ=ΔΔ=Δ=mΔ5）计算映射点及其函数值(1)()f x (1)x (1)(1)(1)24.545509.09220.82640 1.653⎡⎤⎡⎤⎡⎤=−=−=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦x x x (1)00()250F f ==x (1)()385.239f =x 6）计算判别条件式(1)22()15.215F f ==x (1)3()385.239F f ==x 30?F F <故不满足鲍威尔条件，则下一轮仍用原方向组。

当limr(k) 0 k
则(x, r(k) ) f (x) , xk * x *
例： 用内点法求
min
f
(x)

x2 1

x2 2
s.t. g( x) 1 x1 0 的约束最优解。
解:
首先构造内点惩罚函数: (
x,
r)

x2 1

x2 2

rk
ln(x1
1)
用解析法求函数的极小值，运用极值条件：
二. 直接解法：
基本思想：合理选择初始点，确定搜索方向，以迭代公式 x(k+1)= x(k)+α(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。 适用范围：只能求解不等式约束优化问题的最优解。
基本要点：选取初始点、确定搜索方向及适当步长。
搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。 可行性：迭代点必须在约束条件所限制的可行域内，即满足
1
u1 gu (x)
② .(x, r(k) )
m
f (x) r(k)
1
u1 gu (x)
③ .(x, r (k) )
f (x)
m
r (k) u u 1
1 gu (x)
其中：gu (x) 0,u 1,2,...m
其中：gu (x) 0,u 1,2,...m
gu(x)0, u=1,2,…,p
适用性：当前迭代点的目标函数值较前一点是下降的，即满足 F(xk+1)<F(xk)
收敛条件：
• 边界点的收敛条件应该符合 K-T 条件；
• 内点的收敛条件为： xk1 xk 1
和

将上式右边极小化, 即令
q(k) (s) f (xk ) 2 f (xk )s 0
得:
xk1 xk [ 2 f (xk )]1 f (xk )
(4.2.2) (4.2.3)
这就是牛顿法迭代公式.相应的算法称为牛顿法


令 Gk 2 f (xk ), gk f (xk ) , 则(4.2.3)也可写成
事实上, 由于精确线性搜索满足gkT1dk 0则
gT k 1
g
k
dkT1dk
0
(4.1.11)
这表明最速下降法中相邻两次的搜索方向是相互直
交的, 这就产生了锯齿形状.越接近极小点, 步长越
小, 前进越慢.
最速下降法的锯齿现象
x2 x1

x*
x3
最速下降法的收敛速度
精确线性搜索的最速下降法的收敛速度是线性的
dk
o(
x xk
)
(4.1.2)
显然, 若dk 满足 gkT dk 0 , 则是下降方向, 它使得
f (xk dk ) f (xk )
当
取定后,
g
T k
d
的值越小,
k
即

g
T k
dk
的值越大,
函
数f(x)在xk处下降量越大.
由Cauchy-Schwartz(柯西-施瓦)不等式
二次型 f (x1, x2 ,, xn ) 如果对于任意一组不全为零的 实数 c1 , c2 ,, cn都有 f (c1, c2 ,, cn ) 0 就称为正定的.
A是一个实对称矩阵，如果 实二次型
xT Ax
是正定的，则A称为正定矩阵.

3 函数的泰勒级数展开
在高数里我们学过一维泰勒级数的展开式，这里我们需要用 到二维泰勒公式的展开式。
首先我来引进一维泰勒公式。设f(x)在开区间（a,b）内具有 直到（n+1）阶的导数，x0是区间（a,b)内一点，x是以x0为中 心的某个领域内的点，则f(x)在x0处的泰勒级数展开为：
函数的泰勒级数展开
解.������f(x)=(������������������ − ������, ������������������ − ������)������
令
������f(x)=0
，得x1=1,x2=3。而������������f(x)=
������ ������
������ 说明海 ������
迭代算法及其收敛性
那迭代到什么时候停呢？一般给定一个精度要求ε，其值 一般为������������−������~������������−������,再用下式来确定迭代完毕与否。
||������f(xk)||≤ε
无约束的最优性条件
5.无约束最优性条件
定理1. （无约束极小点的一阶必要性） 设函数f(x)在x0处可微。若x0是f(x)的 无约束局部极小点，则必有
无约束的最优性条件
定理3
（严格的无约束局部极小点充分条件） 设f(X)具有连续的二阶偏导数，在点X处������f(x)=0,且其 海辛矩阵 ������������f(x)正定，则可断言X是f(X）的严格局部 极小点。
无约束的最优性条件
例1. f(x)=(������������ − ������)������+(������������ − ������)������ ,试讨论这个多元函数的 极小值点
f(x)=f(x0)+������(���ሖ���������)(x-x0)+������������ ������������(������������)(������ − ������������)������