Full-step interior-point methods for symmetric optimization

Abstract

In [SIAM J. Optim., 16(4):1110--1136 (electronic), 2006] Roos proposed a full-Newton step Infeasible Interior-Point Method (IIPM) for Linear Optimization (LO). It is a primal-dual homotopy method; it differs from the classical IIPMs in that it uses only full steps. This means that no line searches are needed. In this thesis, we first present an improved full-Newton step IIPM for LO. Then, based on the properties of Euclidean Jordan algebras, we generalize the improved full-Newton step IIPM for LO to full Nesterov-Todd step (NT-step) IIPM for Symmetric Optimization (SO). Since the analysis requires a quadratic convergence result for the feasible case, primal-dual feasible IPMs with full steps are presented as well. Although our devised IIPMs admit the best known iteration bound, from a practical perspective they are not efficient. This is because they always perform according to their worst-case theoretical complexity bounds, which means that only tiny reductions of the so-called barrier parameter are admitted. As a remedy, we propose a more aggressive (adaptive) updating strategy. Finally, our full NT-step IIPM for SO is implemented with both standard and adaptive updates of the barrier parameter. The significant improvement in performance of the adaptive updating strategy over the original short updating strategy is illustrated. The algorithm with adaptive updates is also used to solve problems from the well known library SDPLIB [Optim. Methods Softw., 11/12(1-4):683--690, 1999] of test problems. The results are promising, and to some extend competing with SDPT3 [Math. Program., 95(2, Ser. B):189--217, 2003].