Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations

Liqun Qi, Houyuan Jiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

76 Citations (Scopus)

Abstract

There are several forms of systems of nonsmooth equations which are equivalent to the Karush-Kuhn-Tucker (KKT) system of a nonlinearly constrained optimization problem (NLP). If the NLP is twice continuously differentiable and the Hessian functions of its objective and constraint functions are locally Lipschitzian, then these KKT equations are strongly semismooth. If furthermore the linear independence condition and the strong second-order sufficiency condition are satisfied at a KKT point, then the generalized Jacobians of these KKT equations are nonsingular at that point and the sequence generated by the generalized Newton method converges to this point Q-quadratically. However, direct application of quasi-Newton methods cannot guarantee Q-superlinear convergence. We present a mixed quasi-Newton method which converges Q-superlinearly with common symmetrical updating rules under the above conditions for the generalized Newton method. Superlinear convergence of the primal variables and global convergence are also discussed.
Original languageEnglish
Pages (from-to)301-325
Number of pages25
JournalMathematics of Operations Research
Volume22
Issue number2
DOIs
Publication statusPublished - 1 Jan 1997
Externally publishedYes

Keywords

  • Convergence
  • KKT equations
  • Nonsmoothness

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Cite this