infeasible-interior-point methods

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

  • Mohammad Reza Peyghami
  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    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

  • Bharath Kumar Rangarajan
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    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