Primal-dual interior-point methods for second-order conic optimization based on self-regular proximities

Recently the authors introduced the notions of self-regular functions and self-regular proximity functions and used them in the design and analysis of interior-point methods (IPMs) for linear and semidefinite optimization (LO and SDO). In this paper, we consider an extension of these concepts to second-order conic optimization (SOCO). This nontrivial extension requires the development of various new tools. Versatile properties of general analytical functions associated with the second-order cone are exploited. Based on the so-called self-regular proximity functions, new primal-dual Newton methods for solving SOCO problems are proposed. It will be shown that these new large-update IPMs for SOCO enjoy polynomial O(max{p, q}N(q+1)/2q logN/epsilon) iteration bounds analogous to those of their LO and SDO cousins, where N is the number of constraining cones and p, q are constants, the so-called growth degree and barrier degree of the corresponding proximity. Our analysis allows us to choose not only a constant q but also a q as large as log N. In this case, our new algorithm has the best known O(N-1/2 log N logN/epsilon) iteration bound for large-update IPMs.