QP-FREE And Newton-Type Algorithms For Nonlinear Constrained Optimization And Variational Inequality Problems

QP-free algorithms for constrained optimization problems are aimed at settling two inherent problems in traditional sequential quadratic programming (SQP) algorithms ?the potential inconsistence of their quadratic programming (QP) sub-problems and the high cost on computation effect triggered by the QP subproblems. A number of QP-free algorithms were proposed and their convergence behavior was widely studied in the past fifteen years. However, two main shortcomings triggering convergence property failure still exist in these QP-free algorithms. First in order to ensure local fast convergence and avoid the Maratos-like effect, as a regular assumption the strict complementarity condition is indispensable. Second, a strong assumption which requires the linear independence of gradients of all equality and active inequality constraints, must be assumed to keep these algorithms for solving generally constrained optimization problems well defined.The first aim of this work is to circumvent the two drawbacks just mentioned. Three QP-free algorithms based on Facchinei-Fischer-Kanzow KKT identification technique are proposed in the first chapter. As the main contribution, these algorithms converge locally superlinearly implying the absence of the Maratos-like effect even if the strict complementarity condition does not hold. This achievement benefits from a judging system of equalities incorporated in them. Moreover, the algorithms enjoy many other desirable features. For example, at each iteration at most four reduced linear systems of equations with the same iterative coefficient matrix need to be solved to get iterative directions and the iterative matrix involves only constraints in the working set, the number of which are much less than that of the original problem. And the global convergence to KKT points can be established without assuming the isolatedness of every accumulation point, the boundedness of the multiplier approximation sequence or that the strict complementarity condition holds at all accumulation points. In particular, as another important contribution, in the third algorithm the strong linear independence condition is slacked to a muchmilder assumption, by which the Wachter-Biegler phenomenon can be significantly avoided, and however all desirable convergence properties remain uneffected.Newton's methods play an important role for solving variational inequality problems (VIP) due to their fast convergence rate. However, in existing global Newton's methods a linearized variational inequality subproblem has to be solved at each iteration, whose computational cost is equivalent with a QP problem, and the local fast convergence is usually established theoretically incompletely. The second aim of this work is to construct a simpler formulation of Newton's methods. Two Newton type methods based on Taji-Fukushima merit function are proposed for strongly monotone VIP with inequality constraints in the second chapter. For both methods, at most two reduced linear systems of equations with the same coefficient matrix need to be solved in order to get iterative directions at each iteration and the iterative matrix involves only constraints in the working set, whose cardinality are much less than the number of original constraints. Under suitable assumptions, the methods converge globally to the unique solution of the original problem. Moreover, faster convergence rate-quadratic convergence-is got in both methods without assuming that unit step size is eventually accepted or that the feasible set is polyhedral convex. In particular, for the second algorithm, its local fast convergence result is proved even without assuming the strict complementarity condition.