§3.7鲍威尔法

基本迭代公式仍旧是：Xk?1?Xk??kSk

基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上的一维搜索。

对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。

修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性。

注意掌握鲍威尔条件的表达式和应用！ 每环搜索方向组的生成：

1．第一环的搜索方向组就是各坐标轴方向

2．下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是：若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。 下一环搜索起点的确定：

下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件，则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。

kkk 这里需要注意的是反射点的计算：Xn?2?2Xn?X0

kkk 式中：Xn?2是本环起点X0相对于本环终点Xn沿新生成方向的反射点。

2?4x1?2x1x2，利用修正Powell法从例：对于无约束目标函数minf(X)?x12?2x2?1?X0???出发求最优解。

?1??1?1解：令X0?X0??? P1?P0?(e1,e2)

?1??1??1???11 X1?X0??????? 01?????3?11)?0 得：??2 则：X1 令f?(X1???

?1??0??3?11 X2?X1??????? 11???????3?11)?0 得：??0.5 则：X2 令f?(X2???

?1.5??3??1??2?11该环生成的新搜索方向为：S1?X2?X0?????????

?1.5??1??0.5? 对S1进行有效性判别：

?3??1??5?111 反射点X4?2X2?X0?2????????

?1.5??1??2?111)??3 f2?f(X2)??7 )??7.5 f3?f(X4 f1?f(X01111 ?1?f(X0)?f(X1)??3?(?7)?4，?2?f(X1)?f(X2)??7?(?7.5)?0.5

故最大下降量?m??1?4

故：f3?f1和(f1?2f2?f3)(f1?f2??m)2?方向S1可用

1

以X2为起点，沿S1方向作一维搜索：

1?m(f1?f3)2均成立 2?3??2??3?2??11X3?X2??S1?????????? 1.50.51.5?0.5???????11)?f(X2??S1)得??2/5?0.4 由minf(X3?3.8?1故，本轮寻优的终点为：X1?X3???

?1.7?做收敛性判别：

X1?X0?2.82?0.72，应继续搜索

?3.8?21下一轮寻优过程的起点为：X0?X3???

?1.7?下一轮寻优过程的搜索方向组为：(e2,S1) 继续依样搜索直至满足收敛精度

第4章 约束优化方法

约束优化方法要求大家重点掌握惩罚函数法，包括内点法、外点法、混合法。 一、外点法 构造惩罚函数：

min?(X,r)?f(X)?rkk??max[gu?1pu(X),0]??r2k?[h(X)]vv?1q2

外点法既可以处理不等式约束优化问题，又可以处理等式约束优化问题。 需要注意的是：惩罚因子rk随迭代次数的增加是递增的，当rk??时得到的解就是原问题的最优解。 例：用外点法求解

2minf(X)?x12?x2?2x1?1s.t.3?x2?0

22?2x1?1?rk?max[3?x2,0]? 解：构造惩罚函数?(X,rk)?x12?x222k2?x?x?2x?1?r(3?x)当3?x2?0时?1212k??(X,r)??2 2?当3?x2?0时?x1?x2?2x1?1令

???2x1?2?0 ?x1???2x2?2rk(x2?3)?0 ?x1

X为内点时无约束最优解

3rk**?1x2?limx2?3故得：x1?1x2? ?x1kk??1?rf(x*)?9

二、内点法

构造惩罚函数：

p1kk 或：?(X,r)?f(X)?r?ln[?gu(X)] ?(X,r)?f(X)?r?u?1u?1gu(X)kkp内点法只能处理不等式约束优化问题，不能处理等式约束优化问题。

需要注意的是：惩罚因子rk随迭代次数的增加是递减的，当rk?0时得到的解就是原问题的最优解。

例：用内点法求解约束优化问题 minf(X)?x1?x2

s.t.x12?x2?0?x1?0

解：构造惩罚函数?(X,rk)?x1?x2?rkln[x2?x12]?rklnx1

令

?2x1??1k?1?rk??r??0 2?x1x1x2?x1??1?1?rk??0 ?x2x2?x12

1?8rk?1(1?8rk?1)2?rk 得x1?，x2?416?0? 当rk?0时，得x*??? f(x*)?0

?0?三、混合法

构造惩罚函数：

q1k?(X,r)?f(X)?r??r2?[hv(X)]2

u?1gu(X)v?1kk1p或：?(X,r)?f(X)?rkk1?ln[?gu?1pu(X)]?rk2?[h(X)]vv?1q2

混合法的特点是：对于不等式约束按照内点法构造惩罚项，对于等式约束按照外点法构造惩罚项。混合法既可以处理不等式约束优化问题，也可以处理等式约束优化问题。 例：用混合惩罚函数法求解约束优化问题

2 minf(X)?x12?3x2?x2

s.t.1?x1?0x2?0

2解：构造惩罚函数?(X,rk)?x12?3x2?x2?rkln[1?x1]?12x2 kr1??k2x?r1?1?x1?k??0 令??(X,r)??2x2???3?2x?2?rk???1?1?2rk 得：x1?，x2?23 12(k?1)r