Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910571502239744 |
|---|---|
| author | Sim, Chee-Khian |
| author_facet | Sim, Chee-Khian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_08215 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems Sim, Chee-Khian Optimization and Control 90C22, 90C51 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. |
| title | Superlinear Convergence of an Interior Point Algorithm on Linear Semi-definite Feasibility Problems |
| topic | Optimization and Control 90C22, 90C51 |
| url | https://arxiv.org/abs/2211.08215 |