General Constrained Matrix Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916436960608256 |
|---|---|
| author | Garner, Casey Lerman, Gilad Zhang, Shuzhong |
| author_facet | Garner, Casey Lerman, Gilad Zhang, Shuzhong |
| contents | This paper presents and analyzes the first matrix optimization model which allows general coordinate and spectral constraints. The breadth of problems our model covers is exemplified by a lengthy list of examples from the literature, including semidefinite programming, matrix completion, and quadratically constrained quadratic programs (QCQPs), and we demonstrate our model enables completely novel formulations of numerous problems. Our solution methodology leverages matrix factorization and constrained manifold optimization to develop an equivalent reformulation of our general matrix optimization model for which we design a feasible, first-order algorithm. We prove our algorithm converges to $(ε,ε)$-approximate first-order KKT points of our reformulation in $\mathcal{O}(1/ε^2)$ iterations. The method we developed applies to a special class of constrained manifold optimization problems and is one of the first which generates a sequence of feasible points which converges to a KKT point. We validate our model and method through numerical experimentation. Our first experiment presents a generalized version of semidefinite programming which allows novel eigenvalue constraints, and our second numerical experiment compares our method to the classical semidefinite relaxation approach for solving QCQPs. For the QCQP numerical experiments, we demonstrate our method is able to dominate the classical state-of-the-art approach, solving more than ten times as many problems compared to the standard solution procedure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09682 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | General Constrained Matrix Optimization Garner, Casey Lerman, Gilad Zhang, Shuzhong Optimization and Control 90C26, 90C52, 65K10, 68W40 This paper presents and analyzes the first matrix optimization model which allows general coordinate and spectral constraints. The breadth of problems our model covers is exemplified by a lengthy list of examples from the literature, including semidefinite programming, matrix completion, and quadratically constrained quadratic programs (QCQPs), and we demonstrate our model enables completely novel formulations of numerous problems. Our solution methodology leverages matrix factorization and constrained manifold optimization to develop an equivalent reformulation of our general matrix optimization model for which we design a feasible, first-order algorithm. We prove our algorithm converges to $(ε,ε)$-approximate first-order KKT points of our reformulation in $\mathcal{O}(1/ε^2)$ iterations. The method we developed applies to a special class of constrained manifold optimization problems and is one of the first which generates a sequence of feasible points which converges to a KKT point. We validate our model and method through numerical experimentation. Our first experiment presents a generalized version of semidefinite programming which allows novel eigenvalue constraints, and our second numerical experiment compares our method to the classical semidefinite relaxation approach for solving QCQPs. For the QCQP numerical experiments, we demonstrate our method is able to dominate the classical state-of-the-art approach, solving more than ten times as many problems compared to the standard solution procedure. |
| title | General Constrained Matrix Optimization |
| topic | Optimization and Control 90C26, 90C52, 65K10, 68W40 |
| url | https://arxiv.org/abs/2410.09682 |