《数值最优化方法》课程教学课件（讲稿，打印版）可行方向法

最优化方法及其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()'db2表明约束条件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 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êï

必要性.设元是可行点，d是元处的一个可行方向.由可行方向的 定义，存在，使得对于任意的α∈(0，有 A(元+axd)≥b,E(元+ad）=e, 或 A1(元+axd≥b1,A2(元+ad)≥b2,E(c+axd)=e. 于是由 A1(元+ad)=A1元+a(A1d）≥b1,A1元=b1,a>0 可推出A1d≥0.又由 E(元+ad)=E元+a(Ed）=e,E元=e,a>0 可推出Ed=0.证毕 Back Close

6/78 JJ II J I Back Close 7á5.  x¯ ¥å1:, d ¥ x¯ ?òáå1êï. då1êï ½¬, 3 α¯, ¶Èu?ø α ∈ (0, α¯], k A(x¯ + αd) ≥ b, E(¯x + αd) = e, ½ A1(x¯ + αd) ≥ b1, A2(x¯ + αd) ≥ b2, E(x¯ + αd) = e. u¥d A1(¯x + αd) = A1x¯ + α(A1d) ≥ b1, A1x¯ = b1, α > 0 åÌ— A1d ≥ 0. qd E(x¯ + αd) = Ex¯ + α(Ed) = e, Ex¯ = e, α > 0 åÌ— Ed = 0. y.

上面的引理启发我们，要寻找问题(10.1)的可行点元处的一个下 降可行方向d,可以通过求解下述线性规划问题得到： min vf()Td, s.t.A1d≥0， (10.2) Ed=0, -1≤d≤1，i=1,·,n, 其中d=(d1,.,dn)T.增加约束条件-1≤d≤1，i=1,·,n是 为了防止d→o. 注意到，d=0显然是子问题(10.2)的一个可行解，故目标函 数7f()Td的最优值必然小于或等于0.若目标函数的最优值乏= 7f()Td<0,则由引理10.1可知，d即为元处的下降可行方向.否则， 若标函数的最优值乏=Vf()Td=0,则可以证明元是问题(10.1)的 KT点. Back Close

7/78 JJ II J I Back Close ˛°⁄nÈu·Ç, áœÈØK (10.1) å1: x¯ ?òáe ¸å1êï d, 屜L¶)e„Ç55yØK:    min ∇f(x¯) T d, s.t. A1d ≥ 0, Ed = 0, −1 ≤ di ≤ 1, i = 1, · · · , n, (10.2) Ÿ• d = (d1, · · · , dn) T . O\Â^á −1 ≤ di ≤ 1, i = 1, · · · , n ¥ è ìé kdk → ∞. 5ø, d = 0 w,¥fØK (10.2) òáå1), 8Iº Í ∇f(x¯) T d Å`ä7,u½u 0. e8IºÍÅ`ä z¯ = ∇f(¯x) T ¯d < 0, Kd⁄n 10.1 å, ¯d =è x¯ ?e¸å1êï. ƒK, eIºÍÅ`ä z¯ = ∇f(¯x) T ¯d = 0, Kå±y² x¯ ¥ØK (10.1)  KT :.

定理10.1设元是问题(10.1)的一个可行点，且在元处有A1元= b1,A2元>b2,其中 则元是问题(10.1)的KT点的充要条件是子问题(10.2)的最优值为 0. 由于上述定理的证明需要用到Farkas引理（引理8.1），为了使用 方便，我们给出Farkas引理的一个等价描述方式. 引理10.2(Farkas引理)设A为m×n矩阵，c为n维向量. 则Ay=C,y≥0有解的充分必要条件是Ax≤0，cTx>0无解，其 中x,y分别是为n,m维向量. Back Close

8/78 JJ II J I Back Close ½n 10.1  x¯ ¥ØK (10.1) òáå1:, Ö3 x¯ ?k A1x¯ = b1, A2x > b ¯ 2, Ÿ• A =   A1 A2   , b =   b1 b2   . K x¯ ¥ØK (10.1)  KT :øá^á¥fØK (10.2) Å`äè 0. du˛„½ny²Iá^ Farkas ⁄n (⁄n 8.1), è ¶^ êB, ·Çâ— Farkas ⁄nòád£„ê™. ⁄n 10.2 (Farkas ⁄n)  A è m ×n › , c è n ëï˛. K AT y = c, y ≥ 0 k)ø©7á^ᥠAx ≤ 0, c T x > 0 Ã), Ÿ • x, y ©O¥è n, m ëï˛

定理10.1的证明：注意到，元是KT点充要条件是，存在入≥0 和4，使得 7f()-A入-E4u=0. (10.3) 令4=1-2(y1,2≥0)，把(10.3)写成 入 入 (-AT:-ET,ET) =-Vf(), ≥0. (10.4) 根据Farkas引理，(10.4)有解的充要条件是 -A -E d≤0，-Vf)Td>0 (10.5) E 无解，即 A1d≥0，Ed=0,Vf()'d<0 Back Close

9/78 JJ II J I Back Close ½n 10.1 y²: 5ø, x¯ ¥ KT :øá^á¥, 3 λ ≥ 0 ⁄ µ, ¶ ∇f(¯x) − A T 1 λ − E Tµ = 0. (10.3) - µ = ν1 − ν2 (ν1, ν2 ≥ 0), r (10.3) § ￾ − A T 1 , −E T , ET
  λ ν1 ν2   = −∇f(¯x),   λ ν1 ν2   ≥ 0. (10.4) ä‚ Farkas ⁄n, (10.4) k)øá^ᥠ  −A1 −E E   d ≤ 0, −∇f(¯x) T d > 0 (10.5) Ã), = A1d ≥ 0, Ed = 0, ∇f(x¯) T d < 0

无解.故元是问题(10.1)的KT点的充要条件是子问题(10.2)的最优 值为0. 口 由上述定理可知，求解子问题(10.2)的结果，或者得到下降可行 方向，或者得到原问题的一个KT点， 2.计算步骤 下面讨论可行方向法的具体计算步骤.首先分析如何确定搜索步 长α.设问题的可行域为下.第k次迭代的出发点xk∈下是可行点， d是其下降可行方向，则后继点xk+1为 Tk+1=Tk okdk. (10.6) 7 Back Close

10/78 JJ II J I Back Close Ã).  x¯ ¥ØK (10.1)  KT :øá^á¥fØK (10.2) Å` äè 0. d˛„½nå, ¶)fØK (10.2) (J, ½ˆe¸å1 êï, ½ˆØKòá KT :. 2. Oé⁄½ e°?ÿå1êï{‰NOé⁄½. ƒk©¤X¤(½|¢⁄  αk. ØKå1çè F. 1 k gSì—u: xk ∈ F ¥å1:, dk ¥Ÿe¸å1êï, K￾U: xk+1 è xk+1 = xk + αkdk. (10.6)