第四章 非线性规划 山大刁在筠 运筹学讲义

minFck(x),????k?1,2,

用解析方法求解： 令

dFck(x)dx?0，求得

xk?k,????k?1,2,1?k

可以看到，当k无限增大时xk是从问题（4.5.31）可行域外部趋于它的最优解

x*?1的。图见

障碍函数法

在可行区域的边界上筑起一道“墙”，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被“挡”在可行区域内部了。

?min f(x) ?s.. tg(x)?0,i?1,...,pi?令g(x)?(g1(x),g2(x),...,gp(x))T， 可行域X的内部记为

Xo?{x?Rn| g(x)?0}

构造障碍函数 当x?Xo时，

p1或Bdk(x)??dk?ln[?gi(x)] Bdk(x)??dk?i?1i?1gi(x)p其中，dk为罚参数或罚因子

Fdk(x)?f(x)?Bdk(x) min Fdk(x), k?1,2,...

障碍函数法步骤

第1步 选取初始点x0?Xo，罚参数列{dk}(k?1,2,...)，给出检验终止条件

??0，令k:=1；

第2步 做障碍函数Bdk(x)，构造增广目标函数Fdk(x)?f(x)?Bdk(x) 第3步 选用某种无约束最优化方法，以xk?1为初始点求解

min Fdk(x), x?Xo

得到最优解xk。若xk已满足某种终止条件，停止迭代，输出xk。否则，令k:=k+1，转第2步。

例4.5.4 用障碍函数法求解例4.5.3取 采用对数形式的障碍函数 解: 取

1Bdk??dkln(x?1)??ln(x?1),????x??

k相应的增广目标函数为：

1Fdk(x)?x2?ln(x?1),????x??

k用解析方法求得minFdk(x)的最优解为

k?k2?2kx?,??????k?1,2,2kk

由上式可见，当k无限增大，即dk无限减小时，xk从问题（4.5.31）的可行域内部趋于最优解x*?1

两类方法的优缺点比较： 优点：

罚函数法：结构简单初始点选取比较自由

障碍函数法：结构简单但初始点必须是可行内点，由此产生的迭代点均为可行内点 缺点：

1、收敛速度慢

2、工作量大，每次迭代都要求解一个无约束优化问题 3、方法本身造成数值困难性