TY - JOUR
T1 - Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems
AU - Sim, Chee Khian
N1 - 12 month embargo - T&F - may be Gold OA via agreement
“This is an Accepted Manuscript of an article published by Taylor & Francis in [JOURNAL TITLE] on [date of publication], available at: https://doi.org/[Article DOI].”
PY - 2024/8/30
Y1 - 2024/8/30
N2 - In the literature, besides the assumption of strict complementarity, superlinear convergenceof 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.
AB - In the literature, besides the assumption of strict complementarity, superlinear convergenceof 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.
KW - linear semi-definite feasibility problem
KW - strict feasibility
KW - homogeneous feasibility model
KW - interior point method
KW - superlinear convergence
M3 - Article
SN - 1055-6788
JO - Optimization Methods and Software
JF - Optimization Methods and Software
ER -