interior point methods

Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

  • Leonid Faybusovich
  • Takashi Tsuchiya
    • Categories Control Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more

    Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
  • Jerome W. O'Neal
    • Categories Linear Programming, Network Optimization Tags , , , , , , ,

    Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more

    A primal-dual second order cone approximations algorithm for symmetric cone programming

  • Chek Beng Chua
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    This paper presents the new concept of second-order cone approximations for convex conic programming. Given any open convex cone $K$, a logarithmically homogeneous self-concordant barrier for $K$ and any positive real number $r \le 1$, we associate, with each direction $x \in K$, a second-order cone $\hat K_r(x)$ containing $K$. We show that $K$ is … Read more

    An annotated bibliography of network interior point methods

  • Mauricio G.C. Resende
  • Geraldo Veiga
    • Categories Linear Programming, Network Optimization Tags , ,

    This paper presents an annotated bibliography on interior point methods for solving network flow problems. We consider single and multi-commodity network flow problems, as well as preconditioners used in implementations of conjugate gradient methods for solving the normal systems of equations that arise in interior network flow algorithms. Applications in electrical engineering and miscellaneous papers … Read more

    Detecting Infeasibility in Infeasible-Interior-Point Methods for Optimization

  • Michael J. Todd
    • Categories Linear Programming, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    We study interior-point methods for optimization problems in the case of infeasibility or unboundedness. While many such methods are designed to search for optimal solutions even when they do not exist, we show that they can be viewed as implicitly searching for well-defined optimal solutions to related problems whose optimal solutions give certificates of infeasibility … Read more

    Smoothed Analysis of Interior-Point Algorithms: Termination

  • Daniel Spielman
  • Shang-Hua Teng
    • Categories Linear Programming Tags , , ,

    We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar’s interior-point algorithm by Dunagan, Spielman and Teng, we show that the smoothed complexity of an interior-point algorithm for linear programming is $O (m^{3} \log (m/\sigma ))$. In contrast, the best known bound … Read more

    Solving large scale semidefinite programsvia an iterative solver onthe augmented systems

  • Kim-Chuan Toh
    • Categories Semi-definite Programming Tags , , , , , ,

    The search directions in an interior-point method for large scale semidefinite programming (SDP) can be computed by applying a Krylov iterative method to either the Schur complement equation (SCE) or the augmented equation. Both methods suffer from slow convergence as interior-point iterates approach optimality. Numerical experiments have shown that diagonally preconditioned conjugate residual method on … Read more

    First- and Second-Order Methods for Semidefinite Programming

  • Renato D.C. Monteiro
    • Categories Nonlinear Optimization, Semi-definite Programming Tags , , , , , , ,

    In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have … Read more

    Interior-Point Method for Nonlinear Nonconvex Optimization

  • Ladislav Lukšan
  • Jan Vlček
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags ,

    In this paper, we propose an algorithm for solving nonlinear nonconvex programming problems, which is based on the interior-point approach. Main theoretical results concern direction determination and step-length selection. We split inequality constraints into active and inactive to overcome problems with stability. Inactive constraints are eliminated directly while active constraints are used to define symmetric … Read more

    A new iteration-complexity bound for the MTY predictor-corrector algorithm

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program $\min\{c^Tx : Ax=b, \, x \ge 0\}$ with decision … Read more