Status Determination by Interior-Point Methods for Convex Optimization Problems in Domain-Driven Form

Mehdi Karimi(m7karimiuwaterloo.ca)
Levent Tuncel(ltuncelmath.uwaterloo.ca)

Abstract: 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 an infeasible-start primal-dual algorithm 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.

Keywords: convex optimization, interior-point methods, primal-dual algorithms, duality theory, status determination

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Department of Combinatorics and Optimization, University of Waterloo,

Download: [PDF]

Entry Submitted: 02/28/2019
Entry Accepted: 02/28/2019
Entry Last Modified: 02/28/2019

Modify/Update this entry