最优化理论与方法lec10penalty课件.ppt

1、Introduction The general class of penalization methods includes two groups of methods:(i)One group imposes a penalty for violating a constraint;(ii)The other imposes a penalty for reaching the boundary of an inequality constraint.(ii)Barrier Methods(i)Penalty Methods This part discusses a group of m

2、ethods,referred to as penalization methods,which solve a constrained optimization problem by solving a sequence of unconstrained optimization problems.The hope is that,in the limit,the solutions of the unconstrained problems will converge to the solution of the constrained problem.IntroductionSuppos

3、e that our constrained problem is given in the form minimize subject to f xxS 0,if,if xSxxS DefineHence the constrained problem can be transformed into equivalent unconstrained problem minimize f xx Conceptually,if we could solve this unconstrained minimization problem we would be done.IntroductionU

4、nfortunately this is not a practical idea,since the objective function of the unconstrained minimization is not defined outside the feasible region.Barrier and penalty methods solve a sequence of unconstrained subproblems that are more“manageable”.Barrier MethodsPenalty Methodsbarrier termpenalty te

5、rmIntroduction generate a sequence of strictly feasible iterates that converge to a solution of the problem from the interior of the feasible region also called interior-point methods since the methods require the interior of the feasible region to be nonempty,they are not appropriate for problems w

6、ith equality constraints Barrier methods Penalty methods generate a sequence of points that converges to a solution of the problem from the exterior of the feasible region usually more convenient on problems with equality constraints IntroductionDespite their apparent differences,barrier and penalty

7、 methods have much in common.Their convergence theories are similar,and the underlying structure of their unconstrained problems is similar Much of the theory for barrier methods can be replicated for penalty methods and vice versa It is common to use the generic name“penalty methods”to describe bot

8、h methodsBarrier MethodsPenalty Methodsinterior penalty methods exterior penalty methods Barrier MethodsConsider the nonlinear inequality-constrained problem minimize subject to 0,1,ifxgximThe functions are assumed to be twice continuously differentiable.Barrier FunctionsTwo examples of such a funct

9、ion are the logarithmic functionBarrier FunctionsEffect of Barrier Terma one-dimensional problem with bounded constraintsBarrier Functions ,xf xx 1,logmiixf xgx The best known barrier function is the logarithmic barrier function:but the inverse barrier function is also widely used:11,miixf xgx Barri

10、er Functionsminimize ,kxx Barrier methods solve a sequence of unconstrained minimization problems of the form As the barrier parameter is decreased,the effect of the barrier term is diminished,so that the iterates can gradually approach the boundary of the feasible region.Barrier Methods Example 1 1

11、22122minimize 2subject to 10 0f xxxxxxConsider the nonlinear program:Then the logarithmic barrier function gives the unconstrained problem212122minimize ,2log 1logxxxxxxx 212101xx221222201xxxx Barrier Methods Example 1 222102xx 211 22x 11 2312x If the constraints are strictly satisfied,the denominat

12、ors are positive.The unconstrained objective is strictly convex,hence this solution is the unique local minimizer in the feasible region.101 2 03 01lim02x 2011 2 0lim12x Barrier Methods Some RemarksFrom the Example 1,we see thatIndeed,it is possible to prove convergence for barrier methods under mil

13、d conditions.barrier trajectoryA regular point is a point that satisfies some constraint qualification(LICQ).Barrier Methods Some Remarks 10miiigxf xgx 10miiif xgxgx 10miiif xgx iiigx Setting the gradient of the barrier function to zero we obtain.10,1,0,1,miiiiiif xgxgximim Barrier Methods Some Rema

14、rks The above results show that the points on the barrier trajectory,together with their associated Lagrange multiplier estimates,are the solutions to a perturbation of the first-order optimality conditions 221212minimize subject to 10 10f xxxxx Example 2*1,0Tx*122,0Obviously,the optimum:Barrier Met

15、hods Example 2221212minimize ,log1log1xxxxxx 1122201201xxxxThe first-order necessary conditions for optimality are:Suppose the problem is solved via a logarithmic barrier method.Then the method solves the unconstrained minimization problem 112211 22 11 22xxxx The Lagrange multiplier estimates at thi

16、s point are:1121 2111 21x 2121211121x 0 1020 0 00 *xx Barrier Methods Some Remarks Another desirable property shared by both the logarithmic barrier function and the inverse barrier function is that the barrier function is convex if the constrained problem is a convex program.Barrier methods also ha

17、ve potential difficulties.The property for which barrier methods have drawn the most severe criticism is that the unconstrained problems become increasingly difficult to solve as the barrier parameter decreases.The reason is that(with the exception of some special cases)the condition number of the H

18、essian matrix of the barrier function at its minimum point becomes increasingly large,tending to infinity as the barrier parameter tends to zero.Barrier Methods Example 3Consider the problem of Example 2.Then21222201,021xxxx 2122220420,0202xx 4Condition number:22112O The Hessian matrix is ill condit

19、ioned.Barrier MethodsBarrier methods require that the initial guess of the solution be strictly feasible.In our examples,such an initial guess has been provided,but for general problems a strictly feasible point may not be known.It is sometimes possible to find an initial point by solving an auxilia

20、ry optimization problem.This is analougous to the use of a two-phase method in linear programming.Penalty Methods In contrast to barrier methods,penalty methods solve a sequence of unconstrained optimization problems whose solution is usually infeasible to the original constrained problem.A penalty

21、for violation of the constraints is incurred.As this penalty is increased,the iterates are forced towards the feasible region.An advantage of penalty methods is that they do not require the iterates to be strictly feasible.Thus,unlike barrier methods,they are suitable for problems with equality cons

22、traints.Consider the equality-constrained problem minimize subject to 0f xg x Assume that all functions are twice continuously differentiable.where 0.ig xgxPenalty Methods 0,if is feasible0,otherwisexxxThe best-known such penalty is the quadratic-loss function:211122mTiixgxg xg xAlso possible is a p

23、enalty of the form 11 1miixgx ,xf xx Penalty MethodsThe penalty method consists of solving a sequence of unconstrained minimization problems of the formminimize ,kxxPenalty methods share many of the properties of barrier methods:Under mild conditions,it is possible to guarantee convergence Under app

24、ropriate conditions,the sequence of penalty function minimizers defines a continuous trajectory It is possible to get estimates of the Lagrange multipliers at the solutionPenalty MethodsFor example,consider the quadratic-loss penalty function 211,2miixf xgx 1,0mxiiixf xgxgx 10miiif xgx iigx Penalty

25、Methods Example 3 1212minimize subject to 240f xx xg xxx Suppose that this problem is solved via a penalty method using the quadratic-loss penalty function.Consider the problem212121minimize ,242xxx xxx The necessary conditions for optimality for the unconstrained problem are 2121122402420 xxxxxx 11

26、228 41 441xxxx 1 4 Penalty Methods Example 3 121642444141g xxx 441g x 1221limlim2,limlim11 1 41 1 4xx Define a Lagrange multiplier estimate:As,we have 1limlim11 1 4 Penalty Methods Example 3Penalty functions suffer from the same problems of ill conditioning as do barrier functions.221,214xx 212121,2

27、42xx xxx Penalty MethodsIt is also possible to apply penalty methods to problems with inequality constraints.minimize subject to 0,1,if xgxim The quadratic-loss penalty in this case is 211min,02miixgxThis function has continuous first derivatives 1min,0miiixgxgxPenalty MethodsThe same observation ho

28、lds for other simple forms of the penalty function.Thus,one cannot safely use Newtons method to minimize the function.For this reason,straightforward penalty methods have not been widely used for solving general inequality-constrained problems.Multiplier-Based Methods The ill conditioning of penalty

29、 methods can be ameliorated by including multipliers explicitly in the penalty function.Of course,multipliers appear in the context of the classical penalty method,but in that case they are a by-product of the method.For example,in classical penalty method,the multiplier estimate is g x where g is t

30、he vector of constraint functions.These multiplier estimates are used in termination tests in sensitivity analysis in a more active way to derive an optimization algorithm Multiplier-Based MethodsExamining problems of the form minimize subject to 0f xg x minimize ,=subject to 0TL xf xg xg x 1minimiz

31、e ,=2TTxA xf xg xg xg x augmented Lagrangian methodMultiplier-Based Methods AlgorithmA simple augmented-Lagrangian method has the following form:Multiplier-Based MethodsComments on the final step requires.,0 xkkA x 11110kkkkkkf xg xg xg x 1110kkkkkf xg xg x 11111,0 xkkkkkL xf xg x11kkkkg x 111,0kkkL

32、 xg x The algorithm will terminate whenMultiplier-Based Methods Example123412221212minimize ,subject to ,10 xxf x xeg x xxx 12234222212121,=112xxA xexxxx The augmented-Lagrangian function isMultiplier-Based Methods ExampleAt the initial point 1111,xkkkkkkkkA xf xg xg xg x 2221121111,xxkkkkkTkkkkkkA

33、xf xg xg xg xg xg x 12341230.02234,40.02979xxf x xe 12342129120.067020.08936,12 160.089360.11915xxf x xe221210.02gxx 12221.420 21.402xggx Multiplier-Based Methods ExampleUse Newtons method to solve the unconstrained subproblem.12xxxxxAA 21.097721.26719.689 and 1.090219.68921.319xxxAA0.70.0294500.670

34、550.70.0239790.67606x910 xA10.569930.75991x 10011 100.0977220.022784g x Multiplier-Based MethodsSome basic properties of the augmented-Lagrangian function:*1,=2TTA xf xg xg xg xf x This shows that the objective function and the augmented-Lagrangian function have the same value at the solution.*,0 xA

35、 xf xg xg xg xf xg x Hence the gradient of the augmented-Lagrangian is equal to the gradient of the Lagrangian,and vanishes at the solution.Multiplier-Based MethodsA multiplier-based method can also be derived for problems with inequality constraints minimize subject to 0f xg x 111minimize ,log1mkkk

36、kkikixiS xf xgx 1111kikikikgx11111,0 xkkkkkL xf xg xThen the multipliers are updated usingMultiplier-Based MethodsIn the barrier method,every estimate of the solution has to be strictly feasible so that the logarithmic barrier term can be evaluated.110igx igx The modified barrier function has many of the same properties as the augmented-Lagrangian function.