New Complexity Analysis of IIPMs for Linear Optimization Based on a Specific Self-Regular Function

Primal-dual Interior-Point Methods (IPMs) have shown their ability in solving large classes of optimization problems efficiently. Feasible IPMs require a strictly feasible starting point to generate the iterates that converge to an optimal solution. The self-dual embedding model provides an elegant solution to this problem with the cost of slightly increasing the size of the … Read more

Polynomial Convergence of Infeasible-Interior-Point Methods over Symmetric Cones

We establish polynomial-time convergence of infeasible-interior-point methods for conic programs over symmetric cones using a wide neighborhood of the central path. The convergence is shown for a commutative family of search directions used in Schmieta and Alizadeh. These conic programs include linear and semidefinite programs. This extends the work of Rangarajan and Todd, which established … Read more