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

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.