Primal-Dual Interior-Point Methods for Domain-Driven Formulations

• 成果类型: Article
• 署名作者: Karimi, Mehdi; Tuncel, Levent
• 署名单位: University of Waterloo
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2019.1003
• 发表日期: 2020
• 页码: 591-621
• 关键词: convex-optimization problems; algorithms; CONVERGENCE; entropy

摘要

We study infeasible-start, primal-dual interior-point methods for convex optimization problems given in a typically natural form we denote as domain-driven formulations. Our algorithms extend many advantages of primal-dual interior-point techniques available for conic formulations, such as the current best complexity bounds, and more robust certificates of approximate optimality, unboundedness, and infeasibility, to domain-driven formulations. The complexity results are new for the infeasible-start setup used even in the case of linear programming. In addition to complexity results, our algorithms aim for expanding the applications of and software for interior-point methods to wider classes of problems beyond optimization over symmetric cones.