An infeasible interior-point arc-search method with Nesterov's restarting strategy for linear programming problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916132401709056 |
|---|---|
| author | Iida, Einosuke Yamashita, Makoto |
| author_facet | Iida, Einosuke Yamashita, Makoto |
| contents | An arc-search interior-point method is a type of interior-point methods that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov's restarting strategy that is well-known method to accelerate the gradient method with a momentum term. The first one generates a sequence of iterations in the neighborhood, and we prove that the convergence of the generated sequence to an optimal solution and the computation complexity is polynomial time. The second one incorporates the concept of the Mehrotra-type interior-point method to improve numerical performance. The numerical experiments demonstrate that the second one reduced the number of iterations and computational time. In particular, the average number of iterations was reduced compared to existing interior-point methods due to the momentum term. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_01666 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An infeasible interior-point arc-search method with Nesterov's restarting strategy for linear programming problems Iida, Einosuke Yamashita, Makoto Optimization and Control Numerical Analysis 90C51(Primary) 65K05, 90C05(Secondary) F.2.1; G.1.6 An arc-search interior-point method is a type of interior-point methods that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov's restarting strategy that is well-known method to accelerate the gradient method with a momentum term. The first one generates a sequence of iterations in the neighborhood, and we prove that the convergence of the generated sequence to an optimal solution and the computation complexity is polynomial time. The second one incorporates the concept of the Mehrotra-type interior-point method to improve numerical performance. The numerical experiments demonstrate that the second one reduced the number of iterations and computational time. In particular, the average number of iterations was reduced compared to existing interior-point methods due to the momentum term. |
| title | An infeasible interior-point arc-search method with Nesterov's restarting strategy for linear programming problems |
| topic | Optimization and Control Numerical Analysis 90C51(Primary) 65K05, 90C05(Secondary) F.2.1; G.1.6 |
| url | https://arxiv.org/abs/2303.01666 |