ImageVerifierCode 换一换
格式:PPT , 页数:38 ,大小:1.75MB ,
文档编号:3319550      下载积分:25 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-3319550.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(三亚风情)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(最优化理论与方法lec10penalty课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

最优化理论与方法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.

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|