1、Trust-Region MethodsIntroduction Line search generate a search direction Trust-region define a region around the current iterate Trust-region and line search stepsIntroduction 12TTkkkkmpffpp B psome symmetric matrix 212TTkkkkfxpffppfxtp pTaylor-series:2OpIntroduction2If kkBf x the approximation erro
2、r is 3OpTo obtain each step,we seek a solution of the subproblem 1min s.t.2nTTkkkkkpmpffpp B pp 2 ball(1)Introduction1BkkkpBf Full Step In other cases,the solution of the subproblem is not so obvious.In any case,we need only an approximate solution to obtain convergence and good practical behavior.O
3、utline of the algorithm 0kkkkkkkfxfxpmmp actual reduction predicted reduction always 0Outline of the algorithman overall bound Outline of the algorithmshinkexpandreach the boundarydo not alterThe Cauchy pointcan be quantified in terms of the Cauchy pointCauchy Point Calculationargmin s.t.nsTkkkkp Rp
4、ffpp 0argmin s.t.sskkkkkmpp Cskkkpp The Cauchy pointskkkkpff 0Tkkkf Bf the largest value 1k 0Tkkkf Bf31Tkkkkkff Bf The Cauchy pointIn summary,we haveCkkkkkpff where31if 0;min,1otherwise.TkkkkTkkkkkf Bfff Bf Improving on the Cauchy pointthe exact Hessian or a quasi-Newton approximation can be expecte
5、d to yield superlinear convergence The dogleg method 1min s.t.2ndefTTpm pfg pp Bpp *,when BBppp Feasible*,when is small.gpg The dogleg method The first line segment:it runs from the origin to the unconstrained minimizer along the steepest descent directionTUTg gpgg Bg Exact trajectory and dogleg app
6、rox.OThe dogleg methodUpBp The second line segment:it runs from to .,01,1,12.UUBUppppp In fact,it is not even necessary to carry out a search because the dogleg path intersects the trust-region boundary at most once and the intersection point can be computed analytically.Lemma 222221121211.22TUBUUUB
7、UBUhpppppppppp For(i),defineLemma(contd)2121110,TTUUBUBUUBTTTTTTTTTTThppppppppg gg gggB gg Bgg Bgg gg B gg gg Bgg Bgg B g Lemma(contd)0TTBUUBUBUTBUUBUTBUBhppgBpppB ppppgBpB ppppgBp 221UBUppp Global convergence 10min,2kCkkkkkkfmmpfBReduction obtained by the CP:by the dogleg method:10min,kkkkkkkfmmpcf
8、B(2)Usually,Ckkkkmpmp10,1c Global convergenceGeneral Assumptions:uniformly bounded in norm,for some constant 1kkp 0liminf0kkf140,lim0kkfIntroductionA general formulation is 0,min subject to 0,nixicxiEfxcxiIe.g.,twice continuously differentiable,etc.equality constraints inequality constraints|0,;0,ii
9、x cxiE cxiI feasible set:minxf xThe compact form:Review Our aim in this part is to derive similar conditions to characterize the solutions of constrained optimization problems.Local and global solutions2222min,subject to 1nxxxExample1:infinitely many local minima Example2:222121min1000.01,subject to
10、 cos0 xxxx12,1,for 1,3,5,x xkk Smoothness1211xxxSingle constraint:121212121,1,1,1.xxxxxxxxA set of smooth constraints:Example 1Definition:A SINGLE EQUALITY CONSTRAINT221212min s.t.20 xxxx 1222112,12f xxxIEcxxx(1)Example 1(contd)*11fxcx Here,*112 Example 1(contd)11110TTcxdcxcxdcxd 0Tf xdf xf xd So to
11、 first order,100TTcxdfxdif there exists a direction d that satisfies both,then?Example 1(contd)In which case?Example 1(contd)11 1,L xf xcx 111,xL xf xcx*1,0 xL x*11fxcx Lagrange multiplier Is this sufficient to be necessary condition?Example 2A SINGLE INEQUALITY CONSTRAINT221212min s.t.20 xxxx(2)*11
12、fxcx the sign is different!Example 2(contd)0Tfxd 1110TcxdcxcxdExample 2(contd)11f xdcxcxf x In particular,The only situation in which such a direction fails to exist is when 0f xExample 2(contd)The discussed conditions therefore become 100TTfxdcxdThe two regions fail to intersect only when 111 for s
13、ome 0f xcx same direction Example 2(contd)The optimality conditions for both cases I and II can be summarized neatly with reference to the Lagrangian function.*11,0,for some 0 xL x where we also require that*1 10cxcomplementarity condition Case ICase IIExample 3TWO INEQUALITY CONSTRAINTS2212122min s
14、.t.20,0 xxxxx(3)It is easy to see that the solution lies at 2,0Ta point at which both two constraints are active.Example 3(contd)0,1,2,0TTicxdiIfxd 1 12 2,L xf xcxcx Example 3(contd)*,0,for some 0 xL x*1 1220,0cxcx*12102 2,110fxcxcx *1 2 21 Example 3(contd)2,0Tx again both constraints are active,but
15、 f x1,0Td One first-order feasible descent direction from this point is simplythere are many others.Example 3(contd)1,0Tx 1210,0,0TTTcxdcxdfxd 210,11f xcx 1 1,2 4d To show that optimality conditions fail,we note that 110 0cx 220f xcx exist?First-order necessary conditions the relation the nonnegativity of for all inequality constraints the complementarity condition that is required for all the inequality constraints.,0 xL x i icx 0iicxGeneralize the observationState in a rigorous fashion
