Status determination by interior-point methods for convex optimization problems in domain-driven form

• 成果类型: Article
• 署名作者: Karimi, Mehdi; Tuncel, Levent
• 署名单位: University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01663-w
• 发表日期: 2022
• 页码: 937-974
• 关键词: algorithms

摘要

We study the geometry of convex optimization problems given in a Domain-Driven form and categorize possible statuses of these problems using duality theory. Our duality theory for the Domain-Driven form, which accepts both conic and non-conic constraints, lets us determine and certify statuses of a problem as rigorously as the best approaches for conic formulations (which have been demonstrably very efficient in this context). We analyze the performance of a class of infeasible-start primal-dual algorithms for the Domain-Driven form in returning the certificates for the defined statuses. Our iteration complexity bounds for this more practical Domain-Driven form match the best ones available for conic formulations. At the end, we propose some stopping criteria for practical algorithms based on insights gained from our analyses.