An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
Abstract We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blend...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151712 |
| _version_ | 1826188435612762112 |
|---|---|
| author | Yang, Heng Liang, Ling Carlone, Luca Toh, Kim-Chuan |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Yang, Heng Liang, Ling Carlone, Luca Toh, Kim-Chuan |
| author_sort | Yang, Heng |
| collection | MIT |
| description | Abstract
We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss–Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate SDPs to high accuracy, even in the presence of millions of equality constraints. |
| first_indexed | 2024-09-23T07:59:37Z |
| format | Article |
| id | mit-1721.1/151712 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T07:59:37Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1517122023-12-19T06:26:29Z An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization Yang, Heng Liang, Ling Carlone, Luca Toh, Kim-Chuan Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Abstract We consider solving high-order and tight semidefinite programming (SDP) relaxations of nonconvex polynomial optimization problems (POPs) that often admit degenerate rank-one optimal solutions. Instead of solving the SDP alone, we propose a new algorithmic framework that blends local search using the nonconvex POP into global descent using the convex SDP. In particular, we first design a globally convergent inexact projected gradient method (iPGM) for solving the SDP that serves as the backbone of our framework. We then accelerate iPGM by taking long, but safeguarded, rank-one steps generated by fast nonlinear programming algorithms. We prove that the new framework is still globally convergent for solving the SDP. To solve the iPGM subproblem of projecting a given point onto the feasible set of the SDP, we design a two-phase algorithm with phase one using a symmetric Gauss–Seidel based accelerated proximal gradient method (sGS-APG) to generate a good initial point, and phase two using a modified limited-memory BFGS (L-BFGS) method to obtain an accurate solution. We analyze the convergence for both phases and establish a novel global convergence result for the modified L-BFGS that does not require the objective function to be twice continuously differentiable. We conduct numerical experiments for solving second-order SDP relaxations arising from a diverse set of POPs. Our framework demonstrates state-of-the-art efficiency, scalability, and robustness in solving degenerate SDPs to high accuracy, even in the presence of millions of equality constraints. 2023-08-01T16:19:26Z 2023-08-01T16:19:26Z 2022-11-29 2023-07-26T03:18:22Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/151712 Yang, Heng, Liang, Ling, Carlone, Luca and Toh, Kim-Chuan. 2022. "An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization." en https://doi.org/10.1007/s10107-022-01912-6 Creative Commons Attribution-Noncommercial-Share Alike https://creativecommons.org/licenses/by-nc-sa/4.0/ Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Yang, Heng Liang, Ling Carlone, Luca Toh, Kim-Chuan An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title | An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title_full | An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title_fullStr | An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title_full_unstemmed | An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title_short | An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization |
| title_sort | inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank one semidefinite relaxation of polynomial optimization |
| url | https://hdl.handle.net/1721.1/151712 |
| work_keys_str_mv | AT yangheng aninexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT liangling aninexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT carloneluca aninexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT tohkimchuan aninexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT yangheng inexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT liangling inexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT carloneluca inexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization AT tohkimchuan inexactprojectedgradientmethodwithroundingandliftingbynonlinearprogrammingforsolvingrankonesemidefiniterelaxationofpolynomialoptimization |