Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2604.27427 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911635404226560 |
|---|---|
| author | Han, Shaoning Li, Liangju Li, Yongchun |
| author_facet | Han, Shaoning Li, Liangju Li, Yongchun |
| contents | Convex maximization encompasses a broad class of optimization problems and is generally NP-hard, even for low-rank objectives. This paper investigates structural conditions under which convex maximization becomes polynomially solvable. From a geometric perspective, we introduce comonotonicity, a structural property of the feasible region crucial for problem tractability, and establish mathematical characterizations of this property. Under comonotonicity and mild additional assumptions, we develop a unified enumerative framework showing that fixed-rank convex maximization is polynomially solvable. This viewpoint recovers several known tractability results that previously required separate analyses, such as fixed-rank convex matroid maximization and sparse principal component analysis (SPCA). Furthermore, for the more structured class of standard comonotone feasible regions, we refine the analysis via a lifting technique to achieve a square-root improvement in the complexity bound. Finally, applications to SPCA and its variants illustrate the broad applicability and effectiveness of the proposed framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_27427 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Geometric Perspective on Polynomially Solvable Convex Maximization Han, Shaoning Li, Liangju Li, Yongchun Optimization and Control Convex maximization encompasses a broad class of optimization problems and is generally NP-hard, even for low-rank objectives. This paper investigates structural conditions under which convex maximization becomes polynomially solvable. From a geometric perspective, we introduce comonotonicity, a structural property of the feasible region crucial for problem tractability, and establish mathematical characterizations of this property. Under comonotonicity and mild additional assumptions, we develop a unified enumerative framework showing that fixed-rank convex maximization is polynomially solvable. This viewpoint recovers several known tractability results that previously required separate analyses, such as fixed-rank convex matroid maximization and sparse principal component analysis (SPCA). Furthermore, for the more structured class of standard comonotone feasible regions, we refine the analysis via a lifting technique to achieve a square-root improvement in the complexity bound. Finally, applications to SPCA and its variants illustrate the broad applicability and effectiveness of the proposed framework. |
| title | A Geometric Perspective on Polynomially Solvable Convex Maximization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.27427 |