不等式约束9(x)≥0为元的非有效约束.称集合 I(⑦)={i:9()=0} (8.6) 为元处的有效约束指标集，简称x处的有效集（或积极集） 下面的两个引理是研究不等式约束问题最优性条件的基础. 引理8.1（Farkas引理)设a,b,∈Rm(i=1,.,r).则线性 不等式组 bd≥0，i=1,.,d∈R” 与不等式 aTd≥0 相容的充要条件是存在非负实数1，·，ar,使得a=∑ab. Back Close
11/37 JJ II J I Back Close ÿ ™Â gi(x) ≥ 0 è x¯ ökÂ. °8‹ I(¯x) = {i : gi(¯x) = 0} (8.6) è x¯ ?kÂçI8, {° x ?k8 (½»48). e°¸á⁄n¥Ôƒÿ ™ÂØKÅ`5^áƒ:. ⁄n 8.1 ( Farkas ⁄n ) a, bi ∈ R n (i = 1, · · · , r). KÇ5 ÿ ™| b T i d ≥ 0, i = 1, · · · , r, d ∈ R n Üÿ ™ a T d ≥ 0 ÉNøá^á¥3öK¢Í α1, · · · , αr, ¶ a = P r i=1 αibi
证充分性.即存在非负实数a1,.,0,使得a=ab.设 d∈Rm满足bd≥0(i=1,·,r.那么有 ad-∑ad≥0 i-1 必要性.设所有满足bd≥0(i=1,·,r）的向量d同时也满足 aTd>0.用反证法.设结论不成立，即 a生C={e∈Rr=∑a,b,a≥0，i=l,.,r} =1 设a0∈C是向量a在凸锥C上的投影，即 llao all2 min lla all2, 则有a6(a0-a)=0. Back Close
12/37 JJ II J I Back Close y ø©5. =3öK¢Í α1, · · · , αr, ¶ a = P r i=1 αibi . d ∈ R n ˜v b T i d ≥ 0 (i = 1, · · · , r). @ok a T d = X r i=1 αib T i d ≥ 0. 7á5. §k˜v b T i d ≥ 0 (i = 1, · · · , r) ï˛ d ”ûè˜v a T d ≥ 0. ^áy{. (ÿÿ§·, = a 6∈ C = x ∈ R n x = X r i=1 αibi , αi ≥ 0, i = 1, · · · , r . a0 ∈ C ¥ï˛ a 3‡I C ˛›K, = ka0 − ak2 = min x∈C kx − ak2, Kk a T 0 (a0 − a) = 0
(1)先证明对于任意的u∈C必有T(a-a)≥0.事实上，若不然， 则存在-个u∈C,使a-a)<0令双=M 则(a0-a)=-T, T>0.注意到C是凸锥且ao,u∈C,故a0+Tu∈C.此时有 llao ru-all2 llao all2 =-72<0, 这与a0是投影的假设矛盾，故必有ur(a0-a)≥0，Hu∈C. (2)现取d=a0-a.由于b,∈C,那么由(1)的结论可得bd≥0. 故由必要性的假设应有ad≥0.但另一方面，有 aTd aT(ao-a)a"(ao-a)-a(ao-a) =-(a0-a)T(ao-a)=-la0-al2<0, 这与假设矛盾，必要性得证 下面的Gordan引理可以认为是Farkas引理的一个推论， Back Close
13/37 JJ II J I Back Close (1) ky²Èu?ø u ∈ C 7k u T (a0−a) ≥ 0. Ø¢˛, eÿ, K3òá u ∈ C, ¶ u T (a0−a) < 0. - u¯ = u kuk , K u¯ T (a0−a) = −τ , τ > 0. 5ø C ¥‡IÖ a0, u¯ ∈ C, a0 + τu¯ ∈ C. dûk ka0 + τu¯ − ak 2 − ka0 − ak 2 = −τ 2 < 0, ˘Ü a0 ¥›KbgÒ, 7k u T (a0 − a) ≥ 0, ∀ u ∈ C. (2) y d = a0−a. du bi ∈ C, @od (1) (ÿå b T i d ≥ 0. d7á5bAk a T d ≥ 0. ,òê°, k a T d = a T (a0 − a) = a T (a0 − a) − a T 0 (a0 − a) = −(a0 − a) T (a0 − a) = −ka0 − ak 2 < 0, ˘ÜbgÒ, 7á5y. e° Gordan ⁄nå±@è¥ Farkas ⁄nòáÌÿ.