Optimization over convex polyhedra via Hadamard parametrizations

• 成果类型: Article; Early Access
• 署名作者: Tang, Tianyun; Toh, Kim-Chuan
• 署名单位: National University of Singapore; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02172-2
• 发表日期: 2024
• 关键词: algorithm

摘要

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.