6. Inequality constrained optimization and the Kuhn-Tucker formulation

《6. Inequality constrained optimization and the Kuhn-Tucker formulation 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、InequalityconstrainedoptimizationandtheKuhn-TuckerformulationInstructor:MinWang1.Nonnegativityconstraints.ConsidertheoptimizationproblemmaxF(x)w:r:t:xs:t:x10;x20;:::;xn0whereF:Rn!Risdi¤erentiable.Supposexisalocalsolution,thenthereexists">0suchthatF(x)F(x+h
x)forall
x2Rn,k
xk=1,andforallhsuc

2、hthatx+h
x2B(x)Rn:+"RecalltheTaylorexpansion@F1@2FF(x+h
x)=F(x)+h(x)
x+h2
x0(x+h
x)
x;@x2@x2forsome2(0;1).Then@F1@2Fh(x)
x+h2
x0(x+h
x)
x0@x2@x2forall
x2Rn,k
xk=1,andforallhsuchthatx+h
x2B(x)Rn:+"Take
x=(00:::10:::)wheretheithitemequalstozero.Assumex>0thenx+h
x2iB(x)Rnforsu¢c

3、ientlysmallhofeithersign.+"–Takeh>0,dividethefundamentalinequalitybyhandtakethelimitash!0+,wehave@F(x)0:@xiTakeh<0,dividethefundamentalinequalitybyhandtakethelimitash!0,wehave@F(x)0:@xiHenceifx>0,@F(x)=0andifx=0,@F(x)0.i@xii@xiSummarizingtheaboveresults,wehavethefollowing…rst-ordernecess

4、aryconditions:x0iand@F(x)0@xifori=1;2;:::;n.–Ifforsomej,x>0,then@F(x)=0.j@xj–Ifforsomej,@F(x)<0,thenx=0.@xjjComplementaryslacknesscondition@F@Fxi0;(x)0;xi(x)=0@xi@xifori=1;2;:::;n.12.InequalityconstraintsonlyConsidertheproblemmaxF(x1;x2)w:r:t:x1;x2s:t:g(x1;x2)bwhereF:R2!Randg:R2!Ra

5、redi¤erentiable.Suppose(x;x)isalocalsolutionandtheconstraintquali…cationholds,i.e.ifg(x)=b,@g(x)6=12@x0.Thenthelocalsolutionhastwocases.Case1:g(x)=b.–Tangencybetweenfx:g(x)=bgandfx:F(x)=F(x)g:–@g(x)isperpendiculartofx:g(x)=bgandpointsinthedirectionoffx:g(x)>bg,and@x@F(x)isperpendiculartof

6、x:F(x)=F(x)gandpointsinthedirectionoffx:F(x)F(x)g.@x–@g(x)and@F(x)arecolinear.Hencethereexistssuchthat@x@x@F@g(x)(x)=0:(1)@x@x–LagrangianfunctionL(x1;x2;)=F(x)+[bg(x1;x2)]:Noticethat(1)isthesameasthereexistssuchthat@L@L(x;)=(x;)=0:@x1@x2and@L(x;)=0;>0:@Case2:g(x)

7、isalocalsolutiontotheunconstrainedmaxproblem,i.e.,@F(x)=0;whichisthesameas@x@L@L(x;)=(x;)=0;if=0@x1@x2and@L(x;)>0:@Theseresultsleadtothefollowing…rstordernecessaryconditions@L(x;)=0;@x1@L