最优化-lec7 Trust-Region Methods 最优化理论与方法课件（英文版－南京大学）.pptVIP

Example 1 (cont’d) Here, Example 1 (cont’d) So to first order, if there exists a direction d that satisfies both, then? Example 1 (cont’d) In which case? Example 1 (cont’d) Lagrange multiplier Is this sufficient to be necessary condition? Example 2 A SINGLE INEQUALITY CONSTRAINT (2) the sign is different! Example 2 (cont’d) ● ● Example 2 (cont’d) In particular, The only situation in which such a direction fails to exist is when Example 2 (cont’d) The discussed conditions therefore become The two regions fail to intersect only when same direction Example 2 (cont’d) The optimality conditions for both cases I and II can be summarized neatly with reference to the Lagrangian function. where we also require that complementarity condition Case I Case II Example 3 TWO INEQUALITY CONSTRAINTS (3) It is easy to see that the solution lies at a point at which both two constraints are active. Example 3 (cont’d) Example 3 (cont’d) Example 3 (cont’d) ● again both constraints are active, but … — One first-order feasible descent direction from this point is simply there are many others. Example 3 (cont’d) ● To show that optimality conditions fail, we note that 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. Generalize the observation State in a rigorous fashion Trust-Region Methods Introduction Line search — generate a search direction Trust-region — define a region around the current iterate Trust-region and line search steps Introduction some symmetric matrix Taylor-series: Introduction the approximation error is To obtain each step, we seek a solution of the subproblem (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