为了使得xk+1∈F,且使f(xk+1)的值尽可能小，可以通过求解下面 的一维搜索问题来解决： min f(k ad), 0≤a≤a (10.7) a=max{alxk+ad∈F}. 在求解(10.7)式时，考虑到线性约束情形时的(10.1)式，先求解 min f(xk+adk), S.t. A(xk+ad)≥b, (10.8) E(xk+adk)=e. 而(10.8)可作进一步的简化：因为d是可行方向，有Ed=0;而c 是可行点，有Exk=e.因此(10.8)中的等式约束条件自然成立，可不 必再考虑它.此外，在x处，将不等式约束分为有效约束和非有效约 Back Close
11/78 JJ II J I Back Close è ¶ xk+1 ∈ F, Ö¶ f(xk+1) ä¶åU, 屜L¶)e° òë|¢ØK5)˚: min 0≤α≤α¯ f(xk + αdk), α¯ = max{α|xk + αdk ∈ F}. (10.7) 3¶) (10.7) ™û, ƒÇ5Âú/û (10.1) ™, k¶) min f(xk + αdk), s.t. A(xk + αdk) ≥ b, E(xk + αdk) = e. (10.8) (10.8) åä?ò⁄{z: œè dk ¥å1êï, k Edk = 0; xk ¥å1:, k Exk = e. œd (10.8) • ™Â^ág,§·, åÿ 72ƒß. d , 3 xk ?, Úÿ ™Â©èkÂ⁄ök
束，设 A1Tk =61,A2Tk>62, (10.9 其中 A2 b2 则(10.8)中的不等式约束条件可分裂成： A1xk+aAdk≥b1, (10.10) A2xk+aA2dk≥b2. (10.11) 又因是可行方向，由引理10.1知A1d≥0.注意到A1xk=b1及 α≥0，因此条件(10.10)也自然成立.于是(10.8)中的约束条件只剩 Back Close
12/78 JJ II J I Back Close Â, A1xk = b1, A2xk > b2, (10.9) Ÿ• A = A1 A2 , b = b1 b2 . K (10.8) •ÿ ™Â^á婧: A1xk + αA1dk ≥ b1, (10.10) A2xk + αA2dk ≥ b2. (10.11) qœ dk ¥å1êï, d⁄n 10.1 A1dk ≥ 0. 5ø A1xk = b1 9 α ≥ 0, œd^á (10.10) èg,§·. u¥ (10.8) •Â^áêê
下(10.11)，故(10.8)可简化为： min f(xk+adk), S.t. A2(Tk adk)>62, (10.12) a≥0. 以下讨论(10.12)中求a上限的公式.将(10.12)中的第一个约束条件 改写成： aA2dk≥b2-A2xk. 若记 万=b2-A2xk,d=A2dk, (10.13) 则有 ad≥b,a≥0. Back Close
13/78 JJ II J I Back Close e (10.11), (10.8) å{zè: min f(xk + αdk), s.t. A2(xk + αdk) > b2, α ≥ 0. (10.12) ±e?ÿ (10.12) •¶ α ˛Å˙™. Ú (10.12) •1òáÂ^á U§: αA2dk ≥ b2 − A2xk. eP ¯b = b2 − A2xk, ¯d = A2dk, (10.13) Kk α ¯d ≥ ¯b, α ≥ 0
注意到(10.9)式，我们有b<0.由此可得a的上界计算公式： b min la; 如d0小a0 (10.14) +00, d≥0， 其中，d分别是向量，d的第i个分量.因此，求解(1012)等价于 求解 min f(xk +adk), (10.15) s.t.0≤a≤a, 其中a由(10.14)式计算 至此，我们可以写出求解问题(10.1)的可行方向法的详细计算步 骤 算法10.1（线性约束的可行方向法） 步0给定初始可行点x0,终止误差0<1<1,0<2←1.令 Back Close
14/78 JJ II J I Back Close 5ø (10.9) ™, ·Çk ¯b < 0. ddå α ˛.Oé˙™: α¯ = min n¯bi ¯di = (b2 − A2xk)i (A2dk)i ¯di < 0 o , ¯d 6≥ 0, +∞, ¯d ≥ 0, (10.14) Ÿ• ¯bi , ¯di ©O¥ï˛ ¯b, ¯d 1 i ᩲ. œd, ¶) (10.12) du ¶) min f(xk + αdk), s.t. 0 ≤ α ≤ α, ¯ (10.15) Ÿ• α¯ d (10.14) ™Oé. ñd, ·Çå±—¶)ØK (10.1) å1êï{ç[Oé⁄ ½: é{ 10.1 (Ç5Âå1êï{) ⁄ 0 â½–©å1: x0, ™éÿ 0 < ε1 1, 0 < ε2 1. -
k=0. 步1在xk处，将不等式约束分为有效约束和非有效约束： A1Tk=61,A2Tk>62, 其中 A A b1 b= 步2若xk是可行域的一个内点（此时问题(10.1）中没有等式约 束，即E=0且A1=0),且Vf(x)川<1，停算，得到近似极小点 xk;否则，若xk是可行域的一个内点但‖Vf(xk)川≥E1,则取搜索方向 d=一Vf(x),转步5（即用目标函数的负梯度方向作为搜索方向再 求步长，此时类似于无约束优化问题).若x不是可行域的一个内点， 则转步3. Back Close
15/78 JJ II J I Back Close k := 0. ⁄ 1 3 xk ?, Úÿ ™Â©èkÂ⁄ökÂ: A1xk = b1, A2xk > b2, Ÿ• A = A1 A2 , b = b1 b2 . ⁄ 2 e xk ¥å1çòáS: (dûØK (10.1) •vk ™ Â, = E = 0 Ö A1 = 0), Ö k∇f(x k )k < ε1, é, Cq4: xk; ƒK, e xk ¥å1çòáS: k∇f(x k )k ≥ ε1,K|¢êï dk = −∇f(xk), =⁄ 5 (=^8IºÍKF›êïäè|¢êï2 ¶⁄, dûaquÃÂ`zØK). e xk ÿ¥å1çòáS:, K=⁄ 3.