最优化方法及其Matlab程序设计 第十章可行方向法 Back Close
1/78 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1õŸ å1êï{
本章介绍的可行方向法是一类直接处理约束优化问题的方法，其 基本思想是要求每一步迭代产生的搜索方向不仅对目标函数是下降 方向，而且对约束函数来说是可行方向，即迭代点总是满足所有的约 束条件.各种不同的可行方向法的主要区别在于选取可行方向d,的 策略不同，我们主要介绍Zoutendijk可行方向法、投影梯度法和简约 梯度法三类可行方向法 §10.1 Zoutendijk可行方向法 Zoutendijk可行方向法是用一个线性规划来确定搜索方向一下 降可行方向的方法，它最早是由Zoutendijk于1960年提出来的.我们 分线性约束和非线性约束两种情形来讨论其算法原理 Back Close
2/78 JJ II J I Back Close Ÿ0 å1êï{¥òaÜ?nÂ`zØKê{, Ÿ ƒ gé¥á¶zò⁄Sì)|¢êïÿ=È8IºÍ¥e¸ êï, ÖȺÍ5`¥å1êï, =Sì:o¥˜v§k Â^á. à´ÿ”å1êï{Ãá´O3u¿å1êï dk ¸—ÿ”, ·ÇÃá0 Zoutendijk å1êï{!›KF›{⁄{ F›{naå1êï{. §10.1 Zoutendijk å1êï{ Zoutendijk å1êï{¥^òáÇ55y5(½|¢êï—e ¸å1êïê{, ßÅ@¥d Zoutendijk u 1960 cJ—5. ·Ç ©Ç5Â⁄öÇ5¸´ú/5?ÿŸé{n
§10.1.1线性约束下的可行方向法 1.基本原理 考虑下面的非线性优化问题 min f(x), s.t.Ax≥b, (10.1) Ex=e, 其中f(x)连续可微，A是m×n矩阵，E是l×n矩阵，x∈R”,b∈Rm, e∈R'.即(10.1)中有m个线性不等式约束和l个线性等式约束 下面的引理指出了问题(101)的下降可行方向d应满足的条件. 引理10.1设元是问题(10.1)的一个可行点，且在元处有A1元= Back Close
3/78 JJ II J I Back Close §10.1.1 Ç5Âeå1êï{ 1. ƒ n ƒe°öÇ5`zØK min f(x), s.t. Ax ≥ b, Ex = e, (10.1) Ÿ• f(x) ÎYåá, A ¥ m×n › , E ¥ l×n › , x ∈ R n , b ∈ R m , e ∈ R l . = (10.1) •k m áÇ5ÿ ™Â⁄ l áÇ5 ™Â. e°⁄nç— ØK (10.1) e¸å1êï d A˜v^á. ⁄n 10.1 x¯ ¥ØK (10.1) òáå1:, Ö3 x¯ ?k A1x¯ =
b1,A2元>b2,其中 则d∈Rm是点元处的下降可行方向的充要条件是 A1d≥0，Ed=0,7f()'d<0. 证不难发现d是f(x)在元处的下降方向的充要条件是Vf(⑦)'d< 0.另外，注意到条件A1元=b1表明约束条件A1x≥b1是点元出的有 效约束，而条件A2元>b2表明约束条件A2x≥b2是点元处的非有效 约束.因此，在可行点元处将约束矩阵A分裂为相应的A1和A2两部 分 Back Close
4/78 JJ II J I Back Close b1, A2x > b ¯ 2, Ÿ• A = A1 A2 , b = b1 b2 . K d ∈ R n ¥: x¯ ?e¸å1êïøá^ᥠA1d ≥ 0, Ed = 0, ∇f(x¯) T d < 0. y ÿJuy d ¥ f(x) 3 x¯ ?e¸êïøá^ᥠ∇f(¯x) T d < 0. , , 5ø^á A1x¯ = b1 L²Â^á A1x ≥ b1 ¥: x¯ —k Â, ^á A2x > b ¯ 2 L²Â^á A2x ≥ b2 ¥: x¯ ?ök Â. œd, 3å1: x¯ ?Ú› A ©èÉA A1 ⁄ A2 ¸‹ ©
充分性.设A1d≥0，Ed=0.因元是可行点，且A元=b1,E元=e. 故对任意的α>0，都有 A(元+ad)=A1元+a(Ad)≥A1元=b1, E(元+axd=E元+a(Ed)=E元=e. 又由A2元>b2,故必存在一个ā>0，使得对于任意的Q∈(0，都有 A2(元+ad)=A2元+aA2d≥b2. 以上三式表明，存在a,使得对于任意的α∈(0，a,有 A(元+ad)≥b,E(+ad)=e, 即元+ad是可行点，从而d是元处的可行方向. Back Close
5/78 JJ II J I Back Close ø©5. A1d ≥ 0, Ed = 0. œ x¯ ¥å1:, Ö A1x¯ = b1, Ex¯ = e. È?ø α > 0, —k A1(x¯ + αd) = A1x¯ + α(A1d) ≥ A1x¯ = b1, E(x¯ + αd) = Ex¯ + α(Ed) = Ex¯ = e. qd A2x > b ¯ 2, 73òá α >¯ 0, ¶Èu?ø α ∈ (0, α¯], —k A2(x¯ + αd) = A2x¯ + αA2d ≥ b2. ±˛n™L², 3 α¯, ¶Èu?ø α ∈ (0, α¯], k A(x¯ + αd) ≥ b, E(¯x + αd) = e, = x¯ + αd ¥å1:, l d ¥ x¯ ?å1êï