A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension

DOI10.1287/MOOR.15.2.191zbMath0714.90060OpenAlexW2165452678MaRDI QIDQ3200877

Ilan Adler, Renato D. C. Monteiro, Mauricio G. C. Resende

Publication date: 1990

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/b7b7e98a7d183f80c499be62456d90cc6793fe71

zbMATH Keywords

convergence propertiespower series approximationlogarithmic barrier function approachprimal-dual path following algorithm

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (69)

Analysis of some interior point continuous trajectories for convex programming ⋮ New variants of the criss-cross method for linearly constrained convex quadratic programming ⋮ A globally convergent primal-dual interior point algorithm for convex programming ⋮ Theoretical convergence of large-step primal-dual interior point algorithms for linear programming ⋮ An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity ⋮ Constant potential primal-dual algorithms: A framework ⋮ A wide neighborhood infeasible-interior-point method with arc-search for linear programming ⋮ A wide neighborhood interior-point algorithm with arc-search for \(P_{\ast}(\kappa)\) linear complementarity problem ⋮ A wide neighborhood arc-search interior-point algorithm for convex quadratic programming ⋮ A wide neighborhood arc-search interior-point algorithm for convex quadratic programming with box constraints and linear constraints ⋮ Limiting behavior of the affine scaling continuous trajectories for linear programming problems ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ Primal-dual target-following algorithms for linear programming ⋮ The primal power affine scaling method ⋮ An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming ⋮ An affine scaling method using a class of differential barrier functions: primal approach ⋮ Warm start by Hopfield neural networks for interior point methods ⋮ A quadratically convergent scaling newton’s method for nonlinear complementarity problems ⋮ New infeasible interior-point algorithm based on monomial method ⋮ A polynomial arc-search interior-point algorithm for linear programming ⋮ An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints ⋮ Optimized choice of parameters in interior-point methods for linear programming ⋮ A polynomial arc-search interior-point algorithm for convex quadratic programming ⋮ Hopfield neural networks in large-scale linear optimization problems ⋮ A constraint-reduced variant of Mehrotra's predictor-corrector algorithm ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ A Primal-dual affine scaling algorithm with necessary centering as a safeguard ⋮ Comparative analysis of affine scaling algorithms based on simplifying assumptions ⋮ A survey of search directions in interior point methods for linear programming ⋮ A note on a potential reduction algorithm for LP with simultaneous primal-dual updating ⋮ Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path ⋮ Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming ⋮ On the convergence of the affine-scaling algorithm ⋮ Long steps in an \(O(n^ 3L)\) algorithm for linear programming ⋮ A polynomial algorithm for an integer quadratic non-separable transportation problem ⋮ An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming ⋮ A polynomial primal-dual affine scaling algorithm for symmetric conic optimization ⋮ A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions ⋮ A long-step barrier method for convex quadratic programming ⋮ Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema ⋮ An unconstrained convex programming approach to solving convex quadratic programming problems ⋮ An algorithm for portfolio optimization with variable transaction costs. II: Computational analysis ⋮ A new class of preconditioners for large-scale linear systems from interior point methods for linear programming ⋮ On self-regular IPMs (with comments and rejoinder) ⋮ A dynamic large-update primal‐dual interior-point method for linear optimization ⋮ Implementation of interior point methods for mixed semidefinite and second order cone optimization problems ⋮ A quadratically convergent scaling newton’s method for nonlinear programming problems ⋮ A new potential reduction algorithm for smooth convex programming ⋮ A polynomial interior-point algorithm with improved iteration bounds for linear optimization ⋮ Near boundary behavior of primal-dual potential reduction algorithms for linear programming ⋮ Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming ⋮ A polynomial-iteration infeasible interior-point algorithm with arc-search for semidefinite optimization ⋮ An interior-point algorithm for linear programming with optimal selection of centering parameter and step size ⋮ Feasible direction interior-point technique for nonlinear optimization ⋮ A primal-dual interior-point algorithm with arc-search for semidefinite programming ⋮ Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions ⋮ Polynomial primal-dual cone affine scaling for semidefinite programming ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization ⋮ Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ On the symmetric affiine scaling algorithm for line programming^* ⋮ On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ Primal-dual interior point approach for computing \(l_ 1\)-solutions and \(l_ \infty\)-solutions of overdetermined linear systems ⋮ A primal-dual affine-scaling potential-reduction algorithm for linear programming ⋮ Interior-point methods for linear programming: a review ⋮ A class of path-following interior-point methods for \(P_*(\kappa)\)-horizontal linear complementarity problems

This page was built for publication: A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension