Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915964960899072 |
|---|---|
| author | Nishijima, Mitsuhiro Poirion, Pierre-Louis Takeda, Akiko |
| author_facet | Nishijima, Mitsuhiro Poirion, Pierre-Louis Takeda, Akiko |
| contents | In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $ε> 0$ for both the objective function and the constraint arising from the copositivity condition, the proposed algorithm yields an approximate solution after $O(ε^{-2})$ iterations, even when the subproblems are solved inexactly. We also discuss exact and inexact approaches for solving standard quadratic programming problems and compare their performance through numerical experiments. In addition, we apply the proposed algorithm to the problem of testing complete positivity of a matrix and derive a sufficient condition for certifying that a matrix is not completely positive. Experimental results demonstrate that we can detect the lack of complete positivity in various doubly nonnegative matrices that are not completely positive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27160 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems Nishijima, Mitsuhiro Poirion, Pierre-Louis Takeda, Akiko Optimization and Control In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $ε> 0$ for both the objective function and the constraint arising from the copositivity condition, the proposed algorithm yields an approximate solution after $O(ε^{-2})$ iterations, even when the subproblems are solved inexactly. We also discuss exact and inexact approaches for solving standard quadratic programming problems and compare their performance through numerical experiments. In addition, we apply the proposed algorithm to the problem of testing complete positivity of a matrix and derive a sufficient condition for certifying that a matrix is not completely positive. Experimental results demonstrate that we can detect the lack of complete positivity in various doubly nonnegative matrices that are not completely positive. |
| title | Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2510.27160 |