现代优化方法现代优化方法 (8).pdf

9.3 Augmented Lagrangian MethodQingna Li(BIT)9.3 Augmented Lagrangian Method1/12MotivationConsider the equality constrained case.minxf(x)s.t.ci(x)=0,i E,(1.1)The quadratic penalty method solvesminxf(x)+k2iEc2i(x).(1.2)Quadratic Penalty returns infeasible solutionxk:ci(xk)=0.will lead to ill-conditioned problem.Qingna Li(BIT)9.3 Augmented Lagrangian Method2/12Augmented Lagrangian FunctionGiven k,k,define the augmented Lagrange functionLA(x;k;k)=f(x)iEici(x)+k2iEc2i(x).xk arg minxLA(x;k;k)gives0 xLA(xk,k;k)=f(xk)ik kci(xk)ci(xk).Comparing with the optimality condition for(1.1)0=xL(xk,)=f(xk)ici(xk),we can geti ki kci(xk),i E.So we update k+1ibyk+1i=ki kci(xk),i E.(1.3)Qingna Li(BIT)9.3 Augmented Lagrangian Method3/12Algorithm 9.3(Augmented Lagrangian Method-EqualityConstranits)Given 0 0,tolerance 0 0,starting points xs0and 0;fork=0,1,2.Find an approximate minimizer xkof LA(,k;k),starting atxsk,and terminating when xLA(xk,k;k)k;if a convergence test for(1.1)is satisfiedstop with approximate solution xk;end(if)Update Lagrangian multipliers using(1.3)to obtain k+1;Choose k+1 k;Let xsk+1=xk;Select tolerance k+1;end(for)Qingna Li(BIT)9.3 Augmented Lagrangian Method4/12Exampleminx1+x2s.t.x21+x22 2=0The optimal solution is(1,1)T,the Lagrangemultiplier is=0.5.The augmented Lagrangian function isLA(x;,)=x1+x2(x21+x22 2)+2(x21+x22 2)2.At k-th iteration,suppose k=0.4,k=1.See theFigure below for LA(x;0.4,1).Qingna Li(BIT)9.3 Augmented Lagrangian Method5/12Figure:Countours of L(x,)for =0.4 and =1.Optimal solution of LA(x;0.4,1)is near(1.02,1.02)the quadratic penalty minimizer of Q(x;1)is(1.1,1.1)T.Qingna Li(BIT)9.3 Augmented Lagrangian Method6/12Properties of the Augmented LagranaianTheoremLet xbe a local solution of(1.1)at which the LICQ issatisfied,and the second-order sufficient conditions aresatisfied for =.Then there is a threshold valuesuch that for all ,xis a strict local minimizer ofLA(x,;).Qingna Li(BIT)9.3 Augmented Lagrangian Method7/12General Nonlinear Constrained ProblemGiven the general nonlinear program,minxf(x)s.t.ci(x)=0,i ,ci(x)0,i I.(1.4)It can be converted tominxf(x)s.t.ci(x)=0,i ,ci(x)si=0,si 0,i I.(1.5)Qingna Li(BIT)9.3 Augmented Lagrangian Method8/12We can then write the nonlinear program as follows:minxRnf(x)s.t.ci(x)=0,i=1,2,.,m,l x .(1.6)Remark.Bound constraints need not be transformed.Let P(x)be the projection of x onto the set x|l x u.That isP(x)=maxl,minx,u(1.7)Qingna Li(BIT)9.3 Augmented Lagrangian Method9/12Algorithm 9.4(Bound-Constrained Lagrangian Method).Choose an initial point x0and initial multipliers 0;Choose convergence tolerances and;Set 0=10,0=10,and 0=10.10;fork=0,1,2.Find an approximate solution xkof the subproblem such thatxk P(xk xLA(xk,k;k),l,)k;if c(xk)k(*test for convergence*)if c(xk)andxk P(xk xLA(xk,k;k),l,)stop with approximate solution xk;end(if)Qingna Li(BIT)9.3 Augmented Lagrangian Method10/12(*update multipliers,tighten tolerances*)k+1=k ukc(xk);k+1=k;k+1=k0.9k+1;k+1=kk+1;else(*incrase penalty parameter,tighten tolerances*)k+1=kk+1=100k;k+1=10.1k+1;k+1=1k+1;end(if)end(for)Qingna Li(BIT)9.3 Augmented Lagrangian Method11/12SummaryAugmented Lagrangian methodAlgorithmPropertyInequality Constrained CaseQingna Li(BIT)9.3 Augmented Lagrangian Method12/12