An inexact infeasible arc-search interior-point method for linear optimization problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918274363555840 |
|---|---|
| author | Iida, Einosuke Yamashita, Makoto |
| author_facet | Iida, Einosuke Yamashita, Makoto |
| contents | We propose an inexact infeasible arc-search interior-point method for solving linear optimization problems. The method combines an arc-search strategy with inexact solutions to Newton systems and admits a polynomial iteration complexity bound. In existing inexact infeasible interior-point methods, both the linearization error of the central path and the inexactness of the Newton system accumulate along the search direction, which forces the algorithm to take very small steps. The proposed method mitigates this effect by using an arc-search strategy: the curved search path provides a more accurate approximation of the central path, so the step size can remain larger even when the Newton system is solved inexactly. As a result, the proposed method achieves a provably tighter worst-case iteration bound than existing inexact infeasible line-search methods. Numerical experiments on NETLIB benchmark problems demonstrate that the proposed method reduces both the number of iterations and the computation time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An inexact infeasible arc-search interior-point method for linear optimization problems Iida, Einosuke Yamashita, Makoto Optimization and Control Numerical Analysis 90C51, 65K05, 90C05 F.2.1; G.1.6 We propose an inexact infeasible arc-search interior-point method for solving linear optimization problems. The method combines an arc-search strategy with inexact solutions to Newton systems and admits a polynomial iteration complexity bound. In existing inexact infeasible interior-point methods, both the linearization error of the central path and the inexactness of the Newton system accumulate along the search direction, which forces the algorithm to take very small steps. The proposed method mitigates this effect by using an arc-search strategy: the curved search path provides a more accurate approximation of the central path, so the step size can remain larger even when the Newton system is solved inexactly. As a result, the proposed method achieves a provably tighter worst-case iteration bound than existing inexact infeasible line-search methods. Numerical experiments on NETLIB benchmark problems demonstrate that the proposed method reduces both the number of iterations and the computation time. |
| title | An inexact infeasible arc-search interior-point method for linear optimization problems |
| topic | Optimization and Control Numerical Analysis 90C51, 65K05, 90C05 F.2.1; G.1.6 |
| url | https://arxiv.org/abs/2403.18155 |