Interior path following primal-dual algorithms. I: Linear programming

DOI10.1007/BF01587075zbMath0676.90038OpenAlexW2074316151MaRDI QIDQ1123121

Ilan Adler, Renato D. C. Monteiro

Publication date: 1989

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01587075

zbMATH Keywords

logarithmic barrier functionpath followingprimal-dual interior point algorithmpolynomial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (only showing first 100 items - show all)

Analysis of some interior point continuous trajectories for convex programming ⋮ Theoretical convergence of large-step primal-dual interior point algorithms for linear programming ⋮ Determination of optimal vertices from feasible solutions in unimodular linear programming ⋮ Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem ⋮ An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity ⋮ Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem ⋮ Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints ⋮ A full-step interior-point algorithm for second-order cone optimization based on a simple locally kernel function ⋮ THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS ⋮ Unnamed Item ⋮ An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ Interior Point Algorithms in Linear Optimization ⋮ A New Wide Neighborhood Primal-Dual Predictor-Corrector Interior-Point Method for Linear Programming ⋮ ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ A path following algorithm for a class of convex programming problems ⋮ An interior point algorithm for solving linear optimization problems using a new trigonometric kernel function ⋮ An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints ⋮ A full-Newton step infeasible interior-point algorithm based on a kernel function with a new barrier term ⋮ Primal-Dual Algorithms for P ∗(κ) Linear Complementarity Problems Based on Kernel-Function with Trigonometric Barrier Term ⋮ A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ Unnamed Item ⋮ An interior-point algorithm for linearly constrained convex optimization based on kernel function and application in non-negative matrix factorization ⋮ Properties Of Primal Interior Point Methods For QP^∗ ⋮ Generic Primal-dual Interior Point Methods Based on a New Kernel Function ⋮ Calmness of partially perturbed linear systems with an application to the central path ⋮ Solving scalarized multi-objective network flow problems using an interior point method ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ An interior point algorithm for convex quadratic programming with strict equilibrium constraints ⋮ A path to the Arrow-Debreu competitive market equilibrium ⋮ On some properties and an application of the logarithmic barrier method ⋮ A resolução do problema de despacho ótimo de reativos pelo método da função lagrangiana-barreira relaxada ⋮ Primal–dual interior-point method for linear optimization based on a kernel function with trigonometric growth term ⋮ A generic kernel function for interior point methods ⋮ An adversarial optimization approach to efficient outlier removal ⋮ The asymptotic Browder Hartman Stampacchia condition and interior bands of \(\varepsilon\)-solutions for nonlinear complementarity problems ⋮ Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ A primal‐dual interior-point method for linear optimization based on a new proximity function ⋮ Optimization of algorithmic parameters using a meta-control approach ⋮ The aggregate constraint homotopy method for nonconvex nonlinear programming ⋮ General central path and the largest step general central path following algorithm for linear programming ⋮ Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem ⋮ A new potential reduction algorithm for smooth convex programming ⋮ Kernel-function Based Primal-Dual Algorithms forP_*(κ) Linear Complementarity Problems ⋮ The complexity of self-regular proximity based infeasible IPMs ⋮ An Introduction to Formally Real Jordan Algebras and Their Applications in Optimization ⋮ Unnamed Item ⋮ An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a finite exponential-trigonometric barrier term ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ Calmness of linear constraint systems under structured perturbations with an application to the path-following scheme ⋮ A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in aWide Neighborhood ⋮ Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning ⋮ Introduction to duality in optimization theory ⋮ An exterior-point method for linear programming problems ⋮ An exterior point polynomial-time algorithm for convex quadratic programming ⋮ An alternative derivation of the projective interior point method for linear programming through the least squares approach ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming ⋮ A globally convergent primal-dual interior point algorithm for convex programming ⋮ Global convergence in infeasible-interior-point algorithms ⋮ Interior-point algorithms for semi-infinite programming ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ Primal-dual algorithms for linear programming based on the logarithmic barrier method ⋮ Limiting behavior of weighted central paths in linear programming ⋮ Polynomiality of infeasible-interior-point algorithms for linear programming ⋮ An efficient fifth-order method for linear optimization ⋮ Asymptotic convergence in a generalized predictor-corrector method ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ A combined homotopy interior point method for general nonlinear programming problems ⋮ Fast convergence of the simplified largest step path following algorithm ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ A QMR-based interior-point algorithm for solving linear programs ⋮ A generalized homogeneous and self-dual algorithm for linear programming ⋮ The largest step path following algorithm for monotone linear complementarity problems ⋮ On the complexity of a combined homotopy interior method for convex programming ⋮ A primal-dual interior-point method for linear programming based on a weighted barrier function ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ A combined homotopy interior point method for convex nonlinear programming ⋮ Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs ⋮ An infeasible-interior-point algorithm using projections onto a convex set ⋮ A relaxed primal-dual path-following algorithm for linear programming ⋮ Primal-dual target-following algorithms for linear programming ⋮ A lower bound on the number of iterations of long-step primal-dual linear programming algorithms ⋮ A path-following version of the Todd-Burrell procedure for linear programming ⋮ An extension of predictor-corrector algorithm to a class of convex separable program ⋮ Interior-point methods for nonlinear complementarity problems ⋮ An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming ⋮ New infeasible interior-point algorithm based on monomial method ⋮ Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ Primal-dual methods for linear programming ⋮ A numerical study of an infeasible primal-dual path-following algorithm for linear programming ⋮ Curvature integrals and iteration complexities in SDP and symmetric cone programs ⋮ A polynomial arc-search interior-point algorithm for convex quadratic programming ⋮ Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term ⋮ The \(Q\) method for symmetric cone programming ⋮ On the extension of an arc-search interior-point algorithm for semidefinite optimization ⋮ A noninterior path following algorithm for solving a class of multiobjective programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Introduction: New approaches to linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories

This page was built for publication: Interior path following primal-dual algorithms. I: Linear programming