Optimization & Algorithms / Algorithms & Optimization MSc in Electrical and Computer Engineering & MSc in Information Systems and Computer Engineering Constrained Optimization João Silva Sequeira1 1InstitutoSuperiorTécnico [email protected] Fall 2010 Bibliography I FrederickHillierandGeraldLieberman IntroductiontoOperationsResearch 8thed,McGraw-Hill,2005 JorgeNocedalandStephenWright NumericalOptimization SpringerSeriesinOperationsResearch,2nded,2006 Constrained Optimization DavidLuenberger IntroductiontoLinearandNonlinearProgramming Addison-Wesley,1973 DimitriBertsekas NonlinearProgramming AthenaScientific,1999 Local and Global Solutions (cid:73) Constraintscanmakethefindingofsolutionsmoredifficultwhen comparedwithunconstrainedproblems Constrained Optimization Thenumberofvariablestobecomputedincreases(1additional variableperconstraint-inasensethisvariablecanbeusedto switchon/offtheconstraint) The Nonlinear Programming Problem Formulation - Equality Constraints maxf(x), istheobjectivefunction x Constrained Optimization subjectto g(x)=0, isthesetofequalityconstraints x ∈Rn Geometric Intuition For a Solution Strategy I (cid:73) Usingseriesapproximationaroundapointverifyingtheconstraint g(x)=0, 0=g(x+s)≈g(x)+∇g(x)Ts=∇g(x)Ts Also,ifsistoproduceadecreaseintheobjectivefunction Constrained Optimization f(x+s)−f(x)≈∇f(x)Ts<0 (cid:73) Thevectorssformtheplanetangenttog(x)atx Iftherearesdirectionsforwhichthetwoaboveconditionshold thenx isnotastationaritypoint Instead,atastationarypointx(cid:63)onemusthave ∇f(x(cid:63))s=0 Geometric Intuition For a Solution Strategy II meaningthatf()cannotdecreaseanymore,independentlyofthe motionsdisturbingx(cid:63) The2conditionsimplythat ∇f(x(cid:63))=λ∇g(x(cid:63)) Constrained Optimization withλaconstant,suchthatλ∇g(x(cid:63))Ts=0 (cid:73) NotethatthiscorrespondstosolvingthefollowingLP max ∇f(x(cid:63))Ts s subjectto ∇g(x(cid:63))Ts=0 1st Example I (cid:16) (cid:17)2 min f(x)= x +x2 2 1 x subjectto x2+x2 =1 1 2 (x ,x )∈R2 1 2 Constrained (cid:73) Anaiveapproachmayyield Optimization x2 =1−x2 1 2 f(x)=(x +1−x2)2 2 2 thesolutioncannowbeobtainedusingbasiccalculus d (cid:16) (cid:17) f(x )=2 x +(1−x2) (1−2x )=0 dx 2 2 2 2 2 whichhassolutionsx ={0.5,1.618,−0.618} 2 1st Example II x =0.5 → x =±0.866 2 1 x =1.618 → x =±1.272 2 1 x =−0.618 → x =±0.7862 2 1 (cid:73) Usingtheintuitioninthepreviousslides Constrained ∇f =(cid:0)4x (x +x2), 2(x +x2)(cid:1)=2(x +x2)(2x , 1) Optimization 1 2 1 2 1 2 1 1 ∇g =(2x , 2x ) 1 2 4x (x +x2)=λ2x 1 2 1 1 2(x +x2)=λ2x 2 1 2 Straightforwardalgebraicmanipulationyieldsx =1/2,ifλ(cid:54)=0, 2 x (cid:54)=0,andx +x2 (cid:54)=0 1 2 1 Sincetheconstraintmusthold,x =±0.866andλ=2.5 1 1st Example III (cid:73) Notethatpointsverifyingx +x2 =0immediatelyset∇f =(0, 0), 2 1 meaningthattheunconstrainedobjectivefunctionisata stationaritypoint Constrained Optimization Iftheobjectivefunctionreachesaminimumpreciselyoverthe constraintthenλ=0,meaningthattheproblemhaslocalsolutions thatcanbefoundwithoutaccountingfortheconstraints(astheyare automaticallyaccountedfor)! First Order Karush-Kuhn-Tucker (KKT) Conditions I (cid:73) DefineaLagrangianfunction L(x,λ)=f(x)−λ g (x)−...−λ g(x) 1 1 n withλ constants i Constrained Optimization (cid:73) NotethattheLagrangiancanalsobedefinedas L(x,λ)=f(x)+λ g (x)+...+λ g(x) 1 1 n (cid:73) Atpointsverifyingtheconstraintsg(x)=0theLagrangianfunction i hasthesamevalueoff(x)andhence minL(x,λ)=min{f(x), subjecttotheconstraints } x,λ x