Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems with application to linear matrix inequalities

In the literature, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual and the NT direction, to solve semi-definite programs (SDPs) can be shown by (i) assuming that the given SDP is nondegenerate and modifying these algorithms [10], or (ii) considering special classes of SDPs, such as the class of linear semi-definite feasibility problems (LSDFPs), when a suitable initial iterate is required as well [26,27].  Otherwise, these algorithms are not easy to implement even though they can be shown to have polynomial iteration complexities and superlinear convergence [14].  These are besides the assumption of strict complementarity imposed on the given SDP.  The initial iterate to the algorithm using these search directions proposed in [26,27] to guarantee superlinear convergence when solving LSDFPs however is not meaningful.  In this paper, we propose a practical initial iterate that is shown to guarantee superlinear convergence of the algorithm on the homogeneous feasibility model of an LSDFP, hence solving the LSDFP.  We also discuss how we can get this initial iterate.

Citation

Submitted. NOTE: This preprint is fundamentally different from an earlier preprint submitted to the repository. Interested readers can correspond with the author to know the differences.

Article

Download

View Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems with application to linear matrix inequalities