Optimization over convex polyhedra via Hadamard parametrizations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913568982564864 |
|---|---|
| author | Tang, Tianyun Toh, Kim-Chuan |
| author_facet | Tang, Tianyun Toh, Kim-Chuan |
| contents | In this paper, we study linearly constrained optimization problems (LCP). After applying Hadamard parametrization, the feasible set of the parametrized problem (LCPH) becomes an algebraic variety, with conducive geometric properties which we explore in depth. We derive explicit formulas for the tangent cones and second-order tangent sets associated with the parametrized polyhedra. Based on these formulas, we develop a procedure to recover the Lagrangian multipliers associated with the constraints to verify the optimality conditions of the given primal variable without requiring additional constraint qualifications. Moreover, we develop a systematic way to stratify the variety into a disjoint union of finitely many Riemannian manifolds. This leads us to develop a hybrid algorithm combining Riemannian optimization and projected gradient to solve (LCP) with convergence guarantees. Numerical experiments are conducted to verify the effectiveness of our method compared with various state-of-the-art algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23874 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimization over convex polyhedra via Hadamard parametrizations Tang, Tianyun Toh, Kim-Chuan Optimization and Control 90C26, 90C30, 90C46 In this paper, we study linearly constrained optimization problems (LCP). After applying Hadamard parametrization, the feasible set of the parametrized problem (LCPH) becomes an algebraic variety, with conducive geometric properties which we explore in depth. We derive explicit formulas for the tangent cones and second-order tangent sets associated with the parametrized polyhedra. Based on these formulas, we develop a procedure to recover the Lagrangian multipliers associated with the constraints to verify the optimality conditions of the given primal variable without requiring additional constraint qualifications. Moreover, we develop a systematic way to stratify the variety into a disjoint union of finitely many Riemannian manifolds. This leads us to develop a hybrid algorithm combining Riemannian optimization and projected gradient to solve (LCP) with convergence guarantees. Numerical experiments are conducted to verify the effectiveness of our method compared with various state-of-the-art algorithms. |
| title | Optimization over convex polyhedra via Hadamard parametrizations |
| topic | Optimization and Control 90C26, 90C30, 90C46 |
| url | https://arxiv.org/abs/2410.23874 |