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
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
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
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
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
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
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
We propose and analyze a primal-dual interior point method of the “feasible” type, with the additional property that the objective function decreases at each iteration. A distinctive feature of the method is the use of different barrier parameter values for each constraint, with the purpose of better steering the constructed sequence away from non-KKT stationary … Read more
We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the … Read more
The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more