Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity. (3rd September 2019)

• Record Type: Journal Article
• Authors: Mohammad-Nezhad, Ali; Terlaky, Tamás
• Is Part Of: Optimization methods and software. Volume 34:Number 5(2019)
• Page Start: 960
• Page End: 990
• Publication Date: 2019-09-03
• Subjects: Second-order conic optimization -- optimal partition -- quadratic convergence -- maximally complementary optimal solution -- nondegeneracy conditions; 90C51 -- 90C22 -- 90C25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2018.1528249
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: Under primal and dual nondegeneracy conditions, we establish the quadratic convergence of Newton's method to the unique optimal solution of second-order conic optimization. Only very few approaches have been proposed to remedy the failure of strict complementarity, mostly based on nonsmooth analysis of the optimality conditions. Our local convergence result depends on the optimal partition of the problem, which can be identified from a bounded sequence of interior solutions. We provide a theoretical complexity bound for identifying the quadratic convergence region of Newton's method from the trajectory of central solutions. By way of experimentation, we illustrate quadratic convergence of Newton's method on some SOCO problems which fail strict complementarity condition.