步3求解线性规划问题 min之=Vf(xk)Td, s.t.A1d≥0， (10.16) Ed=0, -1≤d≤1，i=1,.,n, 其中d=(d,·,dn)T.设求得最优解和最优值分别为d和. 步4若2<2，停算，输出xk作为近似极小点.否则，以d, 作为搜索方向，转步5. 步5首先由(10.13)和(10.14)计算ā，然后作一维线搜索： min f(g+adk), s.t.0≤a≤a, 求得最优解Q Back Close
16/78 JJ II J I Back Close ⁄ 3 ¶)Ç55yØK min z = ∇f(xk) T d, s.t. A1d ≥ 0, Ed = 0, −1 ≤ di ≤ 1, i = 1, · · · , n, (10.16) Ÿ• d = (d1, · · · , dn) T . ¶Å`)⁄Å`ä©Oè dk ⁄ zk. ⁄ 4 e |zk| < ε2, é, —— xk äèCq4:. ƒK, ± dk äè|¢êï, =⁄ 5. ⁄ 5 ƒkd (10.13) ⁄ (10.14) Oé α¯, ,äòëÇ|¢: min f(xk + αdk), s.t. 0 ≤ α ≤ α, ¯ ¶Å`) αk.
步6置E+1=ck十Q4dk,k=k+1,转步1. §10.1.2非线性约束下的可行方向法 1.基本原理 考虑下面带有非线性不等式约束的优化问题： min f(x), (10.17) s.t.9(x)≥0，i=1,·,m, 其中x∈R”,f(x),g(x)(i=1,·,m)都是连续可微的函数. 下面的引理指出了问题(10.17)的一个下降可行方向d所应满 足的条件 引理10.3设元是问题(10.17)的一个可行点，指标集I() Back {i|g()=0},f(x),9(x)(i∈I()在元处可微，g9(c)(i主I()在 Close
17/78 JJ II J I Back Close ⁄ 6 ò xk+1 := xk + αkdk, k := k + 1, =⁄ 1. §10.1.2 öÇ5Âeå1êï{ 1. ƒ n ƒe°ëköÇ5ÿ ™Â`zØK: min f(x), s.t. gi(x) ≥ 0, i = 1, · · · , m, (10.17) Ÿ• x ∈ R n , f(x), gi(x) (i = 1, · · · , m) —¥ÎYåáºÍ. e°⁄nç— ØK (10.17) òáe¸å1êï d §A˜ v^á. ⁄n 10.3 x¯ ¥ØK (10.17) òáå1:, çI8 I(¯x) = {i| gi(x¯) = 0}, f(x), gi(x) (i ∈ I(x¯)) 3 x¯ ?åá, gi(x) (i 6∈ I(x¯)) 3
元处连续.若 Vf()d<0,Vgi()d>0(iI()), 那么d是问题(10.17)在元处的下降可行方向. 证由引理8.3中的下降可行方向的代数条件(8.10)可知，d必是 问题(10.17）在元处的一个下降可行方向.证毕 由上述引理可知，问题(10.17)在可行点元处的下降可行方向d 应满足： Vf(x)d<0, (10.18) Vg()Td>0,i∈I() Back Close
18/78 JJ II J I Back Close x¯ ?ÎY. e ∇f(x¯) T d < 0, ∇gi(x¯) T d > 0 (i ∈ I(x¯)), @o d ¥ØK (10.17) 3 x¯ ?e¸å1êï. y d⁄n 8.3 •e¸å1êïìÍ^á (8.10) å, d 7¥ ØK (10.17) 3 x¯ ?òáe¸å1êï. y. d˛„⁄nå, ØK (10.17) 3å1: x¯ ?e¸å1êï d A˜v: ∇f(¯x) T d < 0, ∇gi(¯x) T d > 0, i ∈ I(¯x). (10.18)
而在(10.18)中引进辅助变量之后，等价于下面的线性不等式组求d 和： Vf()Td≤z, -Vg()Td≤之，i∈I(⑦)， (10.19) z≤0. 注意到，满足(1019)的下降可行方向d及数z一般有很多个，我们自 然希望求出能使目标函数下降最多的方向d.故而可将(10.19)转化 为以之为目标函数的线性规划问题 min 2, s.t.Vf()Td≤z, (10.20) -Vg(Yd≤之，i∈I(), -1≤d≤1，i=1,·,n, 其中d=(d,.,dn)T. Back Close
19/78 JJ II J I Back Close 3 (10.18) •⁄?9œC˛ z , due°Ç5ÿ ™|¶ d ⁄ z: ∇f(¯x) T d ≤ z, −∇gi(x¯) T d ≤ z, i ∈ I(x¯), z ≤ 0. (10.19) 5ø, ˜v (10.19) e¸å1êï d 9Í z òÑkÈıá, ·Çg ,F"¶—U¶8IºÍe¸Åıêï d. åÚ (10.19) =z è± z è8IºÍÇ55yØK min z, s.t. ∇f(x¯) T d ≤ z, −∇gi(x¯) T d ≤ z, i ∈ I(x¯), −1 ≤ di ≤ 1, i = 1, · · · , n, (10.20) Ÿ• d = (d1, · · · , dn) T
设(10.20)的最优解为d,最优值为乏.那么，若乏<0，则d是问题 (10.17）在元处的下降可行方向；否则，若元=0，则下面的定理将证明： 相应的元必为问题(10.17)的ritz John点 定理10.2设元是问题(10.17)的可行点，I()={ig:()=0}. 则元是问题(10.17)的Fritz John点的充要条件是子问题(10.20)的 最优值为0. 证对于子问题(10.20)，其最优值为0的充要条件是不等式组 Vf(x)d<0, Vg(⑦)Td>0,i∈I(), 即 Vf(x)Td<0, (10.21 -Vg()Td<0,i∈I(), Back Close
20/78 JJ II J I Back Close (10.20) Å`)è ¯d, Å`äè z¯. @o, e z <¯ 0, K ¯d ¥ØK (10.17) 3 x¯ ?e¸å1êï; ƒK, e z¯ = 0, Ke°½nÚy²: ÉA x¯ 7èØK (10.17) Fritz John :. ½n 10.2 x¯ ¥ØK (10.17) å1:, I(x¯) = {i| gi(x¯) = 0}. K x¯ ¥ØK (10.17) Fritz John :øá^á¥fØK (10.20) Å`äè 0. y ÈufØK (10.20), ŸÅ`äè 0 øá^á¥ÿ ™| ∇f(x¯) T d < 0, ∇gi(¯x) T d > 0, i ∈ I(¯x), = ∇f(x¯) T d < 0, −∇gi(¯x) T d < 0, i ∈ I(¯x), (10.21)