Linear systems arising in interior methods for convex optimization: a symmetric formulation with bounded condition number. (4th July 2022)

• Record Type: Journal Article
• Authors: Ghannad, Alexandre; Orban, Dominique; Saunders, Michael A.
• Is Part Of: Optimization methods and software. Volume 37:Number 4(2022)
• Page Start: 1344
• Page End: 1369
• Publication Date: 2022-07-04
• Subjects: Convex optimization -- primal-dual interior methods -- indefinite linear systems -- eigenvalues -- condition number -- inertia -- eigenvalue bounds -- regularization; 15A06 -- 15A12 -- 15A18 -- 15B57 -- 65F22 -- 65F50 -- 90C06 -- 90C20 -- 90C51; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1965599
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : We provide eigenvalues bounds for a new formulation of the step equations in interior methods for convex quadratic optimization. The matrix of our formulation, named K 2.5, has bounded condition number, converges to a well-defined limit under strict complementarity, and has the same size as the traditional, ill-conditioned, saddle-point formulation. We evaluate the performance in the context of a Matlab object-oriented implementation of PDCO, an interior-point solver for minimizing a smooth convex function subject to linear constraints. The main benefit of our implementation, named PDCOO, is to separate the logic of the interior-point method from the formulation of the system used to compute a step at each iteration and the method used to solve the system. Thus, PDCOO allows easy addition of a new system formulation and/or solution method for experimentation. Our numerical experiments indicate that the K 2.5 formulation has the same storage requirements as the traditional ill-conditioned saddle-point formulation, and its condition is often more favourable than the unsymmetric block 3 × 3 formulation.