最优化理论与方法lec7constrained课件

1、Trust-Region MethodsIntroduction Line search generate a search direction Trust-region define a region around the current iterate Trust-region and line search stepsIntroductionsome symmetric matrix Taylor-series: Introductionthe approximation error is To obtain each step, we seek a solution of the su

2、bproblem (1)Introduction 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.Outline of the algorithmactual reduction predicted reduction always 0Outline of the algorithman ove

3、rall bound Outline of the algorithmshinkexpandreach the boundarydo not alterThe Cauchy pointcan be quantified in terms of the Cauchy pointCauchy Point CalculationThe Cauchy pointThe Cauchy pointIn summary, we havewhereImproving on the Cauchy pointthe exact Hessian or a quasi-Newton approximation can

4、 be expected to yield superlinear convergence The dogleg methodFeasibleThe dogleg method The first line segment: it runs from the origin to the unconstrained minimizer along the steepest descent directionExact trajectory and dogleg approx.OThe dogleg method The second line segment: it runs from to .

5、 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. LemmaFor (i), defineLemma (contd)Lemma (contd)Global convergenceReduction obtained by the CP:by the dogleg metho

6、d:(2)Global convergenceGeneral Assumptions: uniformly bounded in norm Chapter 4 Fundamentals of Constrained OptimizationIntroductionA general formulation ise.g., twice continuously differentiable, etc. equality constraints inequality constraints feasible set: The compact form:Review Our aim in this

7、part is to derive similar conditions to characterize the solutions of constrained optimization problems.Local and global solutionsExample1:infinitely many local minima Example2:SmoothnessSingle constraint: A set of smooth constraints:Example 1Definition:A SINGLE EQUALITY CONSTRAINT(1)Example 1 (cont

8、d)Here,Example 1 (contd)So to first order, if there exists a direction d that satisfies both, then? Example 1 (contd)In which case?Example 1 (contd)Lagrange multiplier Is this sufficient to be necessary condition?Example 2A SINGLE INEQUALITY CONSTRAINT(2)the sign is different!Example 2 (contd)Exampl

9、e 2 (contd) In particular, The only situation in which such a direction fails to exist is when Example 2 (contd)The discussed conditions therefore becomeThe two regions fail to intersect only when same direction Example 2 (contd)The optimality conditions for both cases I and II can be summarized nea

10、tly with reference to the Lagrangian function. where we also require thatcomplementarity condition Case ICase IIExample 3TWO INEQUALITY CONSTRAINTS(3)It is easy to see that the solution lies at a point at which both two constraints are active.Example 3 (contd)Example 3 (contd)Example 3 (contd)again both constraints are active, but One first-order feasible descent direction from this point is simplythere are many others. Example 3 (contd)To show that optimality conditions fail, we note thatexist?First-order necessary conditions the relation the nonnegativity