Trust Region Methods For Constrained Optimization And Semidefinite Complementarity Problems

Trust region method is a class of important numerical method for nonlinear optimization problems. Because of its remarkable numerical reliability in conjunction with a sound and complete convergence theory, researchers in nonlinear optimization area have paid great attention to it since 80's, especially during 90's. At present, trust region method and line search method are two mainly types numerical algorithms for nonlinear programming. For variational inequality problems and complementarity problems, one can also design the corresponding trust region algorithms. Moreover, it also play an important role in a recently developed filter method.The aim of this thesis is to study the trust region method in nonlinear optimization, which including the forming and the solving of the trust region subproblem and applications for constrained optimization and semidefmite complementarity problems. This thesis includes six chapters.Chapter 1: Introduction.Chapter 2: A trust region subproblem model with memory is proposed. The model includes memory of the past iteration, which makes the algorithm more farsighted in the sense that its behavior is not completely dominated by the local nature of the objective function, but rather by a more global view. We apply this model to convex constrained and equality constrained optimization problems and establish the global convergence with the help of nonmonotone techniques.Chapter 3: Using spectral projected gradient method and a new nonmonotone line search technique, we propose a algorithm for solving the trust region subproblem. Under weak conditions, the global convergence is established.Chapter 4: We analyze an active set trust region-CG method for the solution of nonlinear system with equalities and inequalities. By reformulating the system into a nonlinear minimization problem with non-negative constraint, we proposed an active set trust region algorithm with which the subproblem is solved bythe truncated conjugate gradient method. The global convergence is established without requiring the existence of an accumulation point.Chapter 5: We apply the combining trust region and line search algorithm to solve equality constrained optimization. By using L1 exact penalty function as the merit function and solving a trust region subproblem, we prove that the trust region trial step provide a descent direction for the merit function. To allow the negative curvature direction and avoid the Maratos effect, we add second correction step to trust region trial step and employ nonmonotone technique in line search. The global convergence and local superlinear rate are obtained under certain conditions. Some numerical tests are also presented.Chapter 6: In this chapter, we present a new merit function for the semi-definite complementarity problem (SDCP) by extending the bounded smooth reformulation for variational inequality problems. We prove that the merit function has a bounded level set and any stationary point of it is a global minimizer without the assumption of monotonicity. Moreover, we present a trust region algorithm for solving the minimization problem with semidefinite constraints. The trust region subproblem is solved by the truncated conjugate gradient method and the global convergence is established even without requiring the existence of an accumulation point of the generated sequence.