Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems with Application to Linear Matrix Inequalities
Preprint
Abstract
In the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [10], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs) and requiring the initial iterate to the algorithm to satisfy certain conditions [26, 27]. Otherwise, these algorithms are not easy to implement even though they are shown to have polynomial iteration complexities and superlinear convergence [14]. The conditions in [26, 27] that the initial iterate to the algorithm is required to satisfy to have superlinear convergence when solving LSDFPs however are not practical. In this paper, we propose a practical initial iterate to an implementable infeasible interior point algorithm that guarantees superlinear convergence when the algorithm is used to solve the homogeneous feasibility model of an LSDFP.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- An Interior Point-Proximal Method of Multipliers for Linear Positive Semi-Definite ProgrammingJournal of Optimization Theory and Applications, 2021
- Interior point method on semi-definite linear complementarity problems using the Nesterov–Todd (NT) search direction: polynomial complexity and local convergenceComputational Optimization and Applications, 2019
- Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functionsComputational Optimization and Applications, 2018
- A primal-dual interior-point method based on various selections of displacement step for symmetric optimizationComputational Optimization and Applications, 2018
- Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrierComputational Optimization and Applications, 2018
- Asymptotic Behavior of Helmberg-Kojima-Monteiro (HKM) Paths in Interior-Point Methods for Monotone Semidefinite Linear Complementarity Problems: General TheoryJournal of Optimization Theory and Applications, 2007
- On implementing a primal-dual interior-point method for conic quadratic optimizationMathematical Programming, 2003
- Q-superlinear convergence of the iterates in primal-dual interior-point methodsMathematical Programming, 2001
- Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPsMathematical Programming, 1998
- Local convergence of interior-point algorithms for degenerate monotone LCPComputational Optimization and Applications, 1994