第7章 约束问题的优化方法.doc

1、90第 7 章 约束问题的优化方法7.1 可行方向法7.1.1 可行方向法的基本思想可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点考虑只含线性约束的非线性规划问题：（1）eExbAf s.t)( min为非线性函数， ， ， ， .)(xf nmRAnlRl注 1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。目前已经提出许多可行方向法，用来处理具有线性约

2、束的非线性规划问题。搜索方向选择方式不同形成不同的可行方向法：（1）Zoutendijk 可行方向法（2）Rosen 梯度投影法（3）Wolfe 既约梯度法可行方向的判定：定理 1：设 是问题（1）的可行解，在点 处有 ， ，其中x x1bA2x，212则非零向量 为 处的可行方向的充要条件是dx，01dAE证明：必要性：设非零向量 是 处的可行方向根据可行方向的定义， ，使得对每x 0个 有 为可行点，即 ， .),0(dx b)(edx)(212121)( dAxbA由于 ，由上式得到 01又由 得到 . edxE)(E91充分性：设 ， .01dAE由于 ，则 ，使得对于所有的 ,成立

3、.2bx)0(22)(bdxA根据假设及 ，得到 .111)(bdx上述两式组合起来就是 .又由 及 可知0Edex exE)(表明 是可行点，因此 是 处的可行方向xd7.1.2 Zoutendijk 可行方向法Zoutendijk 子问题：根据定理 1，如果非零向量 同时满足 , ， ,则 是d0)(dxfT01dAEd处的下降可行方向xZoutendijk 可行方向法把确定搜索方向归结为求解线性规划问题（2）nj | dEAfjT,21,0 s.t)(min1在（2）式中，显然 是可行解，可推知目标函数最优值必定小于或等于零如果0d目标函数最优值小于零，则得到下降可行方向 ；否则，如果目

4、标函数最优值为零，则 x是 K-T 点定理 2：考虑问题（1），设 是可行解，在点 处有 ， ，其中xx1bA2x，21A21b则 为 K-T 点的充要条件是问题（2）的目标函数最优值为零x一维搜索步长的确定：设 为 处一个下降可行方向后继点迭代公式：)(kd)( )()()1( kkkdx的取值原则：k(l)保持迭代点 的可行性；)()()1( kkkdx(2)使目标函数值尽可能减小根据上述原则，可以通过求解一维搜索问题来确定步长：（3）0 )( s.tmin()()edxEbAfkkkk由于 是可行方向，因此，(3)式中第 2 个约束是多余的)(kd92在点 处，把不等式约束区分为起作用约

5、束和不起作用约束： ，)(kx 1)(bxAk2)(2bA(3)式中第 1 个约束可以写成（4）21)(2)(211bdAxkk由于 为可行方向， ， ，以及 ，因此 自)(kd0)(1kdA1x1)(1)(1bdAxkk然成立约束条件（4）简化为 2)(2)(2xkk问题（3）简化为（5）0 s.t)( min2(2)2bdAxfkk根据（5）式的约束条件，容易求出 的上限，令)(2kxb)(2k由 知 . 2)(2bxAk0(5)式的约束条件写成： d由此得到 的上限：0 ,|minax d，dbi不 大 于问题（3）最终简化成： （6）max)()(0 s.tinkkf给定问题（1）和一

6、个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长初始可行点的确定：为求（1）式的一个可行点，引入人工变量（向量） 和 ，解辅助线性规划（7）0, s.t)(in1eExbAlimi如果（7）式的最优解 ，那么 就是（1）式的一个可行解)(),(x可行方向法的计算步骤：93(l)给定初始可行点 ，置 .)1(xk(2)在点 处把 A 和 b 分解成 和 ，使得)(k 21b，1)(xk2)(2xAk计算 )(kxf(3)求解线性规划问题 n j | dEfjTk,21,0 s.t)(min1得到最优解 . )(kd(4)如果 ，则停止计算，

7、为 K-T 点，否则，进行步骤（5）.0)(kTxf )(kx(5)计算 的上限 ，在 上作一维搜索：max,axmax)()( s.tinkkdf得到最优解 ，令k )()()1( kkkx(6)置 ，返回步骤（2）.1:例：用 Zoutendijk 可行方向法解下列问题： 0, 21 s.t 64in121x取初始可行点 .Tx)0,()1第 1 次迭代： ，在 处，起作用约束和不起作用约束的系数矩Tf)4,2(1)(阵及右端分别为， ； ，01A120b21先求在 处的下降可行方向：)(x即 j |dxfjT2,1 0s.t)( min11 , s.t4min221d-由单纯形方法求得最

8、优解： )1(再求步长 : 1942112)(2dA0)(2xb12,minax解一维搜索问题 10 s.t 62)(i()dxf得到： 1令 )1()()2(dx第 2 次迭代： ，在 处，起作用约束和不起作用约束的系数矩阵Tf)2,0)2()2(x及右端分别为， ； ，11A102A2b0求在 处的下降可行方向：)2(x 1 0 s.t min221d-d由单纯形方法求得最优解： 1)2(d沿 搜索，求步长 : )2(d201)(2A1)(2xb1ma解一维搜索问题 10 s.t 2)(in2()2dxf得到： .2195令 2/31)(2)()3(dx第 3 次迭代： Tf),)(， ；

9、 ，11A102A)2(b01求在 处的下降可行方向：)3(x 1 s.tmin221d-由单纯形方法求得最优解： 0)3(d根据定理 1， 是 K-T 点。Tx)2,()3该例是凸规划， 是最优解，目标函数最优值 .)( 2/3minf将可行方向法推广到非线性约束情形：考虑不等式约束问题（8）ix gfi ,1 ,0)(s.t定理 3：设 x 是问题（8）的可行解， 是在 处起作用约束下标集，|Ii x又设函数 , 在 处可微，函数 在 处连续，如果)(f)(Iigi)(Ii，0dT IidTi ,0则 d 是下降可行方向根据定理 3，求下降可行方向归结为求解 LP 问题（9）njdIizx

10、gf zjTi,1,| 0)(s.tmin设（9）式的最优解为 如果 ，则 是在 x 处的下降可行方向；如果 ，相),(dz0z 0z应的 x 必为 Fritz John 点定理 4：设 x 是问题（9）的可行解， ，则 x 是 Fritz John 点的充要0)(|giI条件是问题（9）的目标函数最优值等于零步长 的确定，仍然需要求解一维搜索问题kmax)()(0 s.tinkkdf96其中（10）,1 ,0)(|sup()max midxgkki 计算步骤：(l)给定初始可行点 ，置 . )1(k(2)令 ，解线性规划问题0|kixgI njdIizxgf zjTki,1,| 0)(s.t

11、in)(得最优解 ，若 ，则停止计算， 为 Fritz John 点；否则，进行步骤（3）.),(kdz0kz)(k(3)求解一维搜索问题 max)()( s.tinkkf其中 由（10）式确定，得到最优解 maxk（4）令 ，置 ，返回步骤（2）.)()()1( kkkdx 1:Zoutendijk 算法的收敛问题：不能保证 Zoutendijk 方法迭代产生的序列收敛于 K-T 点Topkis-Veinott 修正Topkis 和 Veinott 把求方向的线性规划改成 njdmixgzxgf j iTi,1,| ,1 )()(0s.t mi 紧约束和非紧约束在确定下降可行方向中均起作用，

12、并且在接近非紧约束边界时，不至发生方向突然改变修正方法计算步骤：(l)给定初始可行点 ，置 . )1(xk(2)解线性规划问题 njdmixgzxgf j kiTki,1,| ,1 ),()(0s.t mi)( 得最优解 .),(kdz(3)若 ，则停止计算， 为 Fritz John 点；否则，进行步骤（4）.0)(kx(4)求解一维搜索问题97max)()(0 s.tinkkdf其中 由（10）式确定，得到最优解 maxk（5）令 ，置 ，返回步骤（2）.)()()1( kkkdx 1:Topkis-Veinott 修正方法的收敛性:定理 5: 考虑问题（8），设函数 连续可微，又设 是)

13、,( ),(ixgfi )(kxTopkis-Veinott 算法产生的序列，则 的任一聚点是 Fritz John 点)kx7.2 惩罚函数法7.2.1 惩罚函数法的基本思想惩罚函数法的基本思想：借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解考虑约束问题（1）ljxhmigfji ,1 ,0)( s.t n 求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题对于等式约束问题：（2）ljxhfj ,1 ,0)( s.tmin可定义辅助函数 ljxhfF121 )()(,(参数 是很大的正数（2）式转化为无约束问题（3）),(

14、min1xF求解问题（3）能够得到问题(2)的近似解对于不等式约束问题：（4）mixgfi ,1 ,0)( s.t定义辅助函数 mi ixfF122 )(,a)(,(98（4）式转化为无约束问题（5）),( min2xF通过（5）式求得（4）式的近似解一般情形（1）式）：可定义辅助函数 )(),(xPfx其中 mi ljjihgP11)()()(连续函数 和 满足条件：0 ,)( ,y函数 和 的典型取法： )(,0maxgi|hj为给定常数通常取作 . 1,2约束问题（1）转化为无约束问题（6）)(),(minxPfxF称为罚项， 称为罚因子，而 称为罚函数。)(xP,当 x 为可行点时，

15、，有 ；0)(xP)(,(f当 x 不是可行点时， 是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域求解问题（6）能够得到约束问题（1）的近似解。越大，近似效果越好。7.2.2 乘子法1 乘子法的基本思想考虑只有等式约束问题（2）.运用乘子法事先需要定义增广 Lagrange 函数（乘子罚函数）: (7)(2)( ),( 121xhxhvffvxTTljljj99与 Lagrange 函数的区别在于增加罚项 ;与罚函数的区别在于增加了),(vx )(2xhT乘子项 (hT注 1：增广 Lagrange 函数与 Lagrange 函数及罚函数具有不同的性

16、态，即对于 ，只要取足够大的罚因子 ，不必趋向无穷大，就可通过极小化),vx，求得问题（2）的局部最优解,(为证明上述结论，先给出如下假设：设 是等式约束问题（2）的一个局部最优解，且满足二阶充分条件，即存在乘子x，使得Tlv),(1 0)(vAxfljhj ,1 ,且对每一个满足 的非零向量 d ，有),1(0)lxhdjT0(2vxLdT其中，),)(1hxAl )(),xhfT定理 1：设 和 满足问题（2）的局部最优解的二阶充分条件，则存在 ，使得v 0对所有的 ， 是 的严格局部极小点反之，若存在点 ，使得, )(ljxj ,1 ,0)(且对于某个 ， 是 的无约束极小点，又满足极小

17、点的二阶充分条件，则)0(v)(x,)0(v是问题（2）的严格局部最优解)0(x证明：需要用到矩阵理论的相关知识和二阶充分条件的定义。注 2：根据定理 1，如果知道最优乘子 ，那么只要取充分大的罚因子 ，不需趋向v无穷大，就能通过极小化 求出问题（2）的解),(vx注 3：确定最优乘子 一般方法：先给定充分大的 和 Lagrange 乘子的初始估计 v，然后在迭代过程中修正 v，力图使v 趋向 .修正 v 的公式：设在第 k 次迭代中，Lagrange 乘子向量的估计为 ，罚因子取 ，得到)(kv的极小点 这时有),(x)(kx lj kjkjkjk xhvfv1 )()()()( 0对问题（2）最优解 ，当 线性无关，应有x,xhl jjvf1)()(假如 ，则必有xk)(