Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916625779785728 |
|---|---|
| author | Papp, Dávid Varga, Anita |
| author_facet | Papp, Dávid Varga, Anita |
| contents | We design and analyze primal-dual, feasible interior-point algorithms (IPAs) employing full Newton steps to solve convex optimization problems in standard conic form. Unlike most nonsymmetric cone programming methods, the algorithms presented in this paper require only a logarithmically homogeneous self-concordant barrier (LHSCB) of the primal cone, but compute feasible and $\varepsilon$-optimal solutions to both the primal and dual problems in $O(\sqrtν\log(1/\varepsilon))$ iterations, where $ν$ is the barrier parameter of the LHSCB; this matches the best known theoretical iteration complexity of IPAs for both symmetric and nonsymmetric cone programming. The definition of the neighborhood of the central path and feasible starts ensure that the computed solutions are compatible with the dual certificates framework of (Davis and Papp, 2022). Several initialization strategies are discussed, including two-phase methods that can be applied if a strictly feasible primal solution is available, and one based on a homogeneous self-dual embedding that allows the rigorous detection of large feasible or optimal solutions. In a detailed study of a classic, notoriously difficult, polynomial optimization problem, we demonstrate that the methods are efficient and numerically reliable. Although the standard approach using semidefinite programming fails for this problem with the solvers we tried, the new IPAs compute highly accurate near-optimal solutions that can be certified to be near-optimal in exact arithmetic. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16020 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization Papp, Dávid Varga, Anita Optimization and Control 90C51, 90C25, 90C23 We design and analyze primal-dual, feasible interior-point algorithms (IPAs) employing full Newton steps to solve convex optimization problems in standard conic form. Unlike most nonsymmetric cone programming methods, the algorithms presented in this paper require only a logarithmically homogeneous self-concordant barrier (LHSCB) of the primal cone, but compute feasible and $\varepsilon$-optimal solutions to both the primal and dual problems in $O(\sqrtν\log(1/\varepsilon))$ iterations, where $ν$ is the barrier parameter of the LHSCB; this matches the best known theoretical iteration complexity of IPAs for both symmetric and nonsymmetric cone programming. The definition of the neighborhood of the central path and feasible starts ensure that the computed solutions are compatible with the dual certificates framework of (Davis and Papp, 2022). Several initialization strategies are discussed, including two-phase methods that can be applied if a strictly feasible primal solution is available, and one based on a homogeneous self-dual embedding that allows the rigorous detection of large feasible or optimal solutions. In a detailed study of a classic, notoriously difficult, polynomial optimization problem, we demonstrate that the methods are efficient and numerically reliable. Although the standard approach using semidefinite programming fails for this problem with the solvers we tried, the new IPAs compute highly accurate near-optimal solutions that can be certified to be near-optimal in exact arithmetic. |
| title | Interior-point algorithms with full Newton steps for nonsymmetric convex conic optimization |
| topic | Optimization and Control 90C51, 90C25, 90C23 |
| url | https://arxiv.org/abs/2502.16020 |