《现代优化方法现代优化方法 (6).pdf》由会员分享，可在线阅读，更多相关《现代优化方法现代优化方法 (6).pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Chapter 9 Penalty and AugmentedLagrangian MethodsQingna Li(BIT)9.1 Quadratic Penalty Method1/13OutlineQuadratic Penalty MethodExact Penalty FunctionAugmented Lagrangian MethodPropertiesQingna Li(BIT)9.1 Quadratic Penalty Method2/139.1 Quadratic Penalty MethodQingna Li(BIT)9.1 Quadratic Penalty Metho
2、d3/13MotivationConsider the equality constrained problemminxf(x)s.t.ci(x)=0,i ,(1.1)The quadratic penalty function Q(x;)for thisformulation isQ(x;)def=f(x)+2ic2i(x),(1.2)where 0 is the penalty parameter.Qingna Li(BIT)9.1 Quadratic Penalty Method4/13Remark.By deriving to+,we penalize the constraintvi
3、olates with increasing severity.This motivates to consider a sequence of values kwith k as k +and to seek the approximateminimizer xkof Q(x;k)for each k.For each k,we can use techniques from unconstrainedoptimization to search for xk.xk1,xk2can be used as initial guess to solvemin Q(,k).Just a few s
4、teps of unconstrained minimization may beneeded for unconstrained problem.Qingna Li(BIT)9.1 Quadratic Penalty Method5/13Example 9.1minx1+x2s.t.x21+x22 2=0(1.3)The quadratic penalty function is(0)Q(x;)=x1+x2+2(x21+x22 2)2(1.4)Qingna Li(BIT)9.1 Quadratic Penalty Method6/13Figure:Countours of Q(x,)for
5、=1,contour spacing 0.5.=1:minimizer near x=(1.1,1.1)T.Local minimizer:near x=(0.3,0.3)T.Qingna Li(BIT)9.1 Quadratic Penalty Method7/13Figure:Countours of Q(x,)for =0.1,contour spacing 2.Qingna Li(BIT)9.1 Quadratic Penalty Method8/13For inequality constraints,define the quadratic penaltyfunction asQ(
6、x;)=f(x)+2iEc2i(x)+2iI(max(0,ci(x)2.Qingna Li(BIT)9.1 Quadratic Penalty Method9/13Algorithms FrameworkAlgorithm 9.1(Quadratic Penalty Method)Given 0 0,k 0 with k 0,xs0;fork=0,1,2.Find an approximate minimizer xkofQ(;k),starting at xsk,and terminating when xQ(x;k)k;if final convergence test satisfied
7、stop with approximate solution xk;end(if)Choose new penalty parameter k+1 k;Choose new starting point xsk+1;end(for)Qingna Li(BIT)9.1 Quadratic Penalty Method10/13Convergence of The Quadratic PenaltyMethodTheoremSuppose that each xkis the exact global minimizer ofQ(x;k)defined by(1.2)in Algorithm 9.
8、1 above,and thatk.Then every limit point xof the sequence xk isa global solution of the problem(1.1).Qingna Li(BIT)9.1 Quadratic Penalty Method11/13TheoremSuppose that the tolerances and penalty parameters inAlgorithm 9.1 satisfy k 0 and .Then if alimit point xof the sequence xk is infeasible,it is
9、astationary point of the function c(x)2.On the other hand,if a limit point xis feasible andthe constraint gradients ci(x)are linearlyindependent,then xis a KKT point for the problem(1.1).For such points,we have for any infinitesubsequence K such that limkK=xthatlimkK kci(xk)=i,for all i ,(1.5)where is the multiplier vector that satisfies the KKTconditions for the equality-constrained problem(1.1).Qingna Li(BIT)9.1 Quadratic Penalty Method12/13SummaryQuadratic penalty methodAlgorithmConvergenceQingna Li(BIT)9.1 Quadratic Penalty Method13/13