必要性.设元是可行点，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êï, KU: xk+1 è xk+1 = xk + αkdk. (10.6)