A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
From MaRDI portal
Publication:3200877
DOI10.1287/moor.15.2.191zbMath0714.90060MaRDI QIDQ3200877
Mauricio G. C. Resende, Renato D. C. Monteiro, Ilan Adler
Publication date: 1990
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/b7b7e98a7d183f80c499be62456d90cc6793fe71
convergence properties; power series approximation; logarithmic barrier function approach; primal-dual path following algorithm
90C25: Convex programming
90C60: Abstract computational complexity for mathematical programming problems
90C20: Quadratic programming
90C05: Linear programming
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
A Primal-dual affine scaling algorithm with necessary centering as a safeguard, 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, Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants, On the symmetric affiine scaling algorithm for line programming*, A quadratically convergent scaling newton’s method for nonlinear complementarity problems, A quadratically convergent scaling newton’s method for nonlinear programming problems, A new potential reduction algorithm for smooth convex programming, An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming, A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions, A long-step barrier method for convex quadratic programming, An \(O(n^ 3L)\) potential reduction algorithm for linear programming, Warm start by Hopfield neural networks for interior point methods, 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, 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, Feasible direction interior-point technique for nonlinear optimization, Primal-dual potential reduction methods for semidefinite programming using affine-scaling directions, Polynomial primal-dual cone affine scaling for semidefinite programming, Degeneracy in interior point methods for linear programming: A survey, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP, 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, A globally convergent primal-dual interior point algorithm for convex programming, Constant potential primal-dual algorithms: A framework, Improved complexity using higher-order correctors for primal-dual Dikin affine scaling, Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems, 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), Near boundary behavior of primal-dual potential reduction algorithms for linear programming, A new class of polynomial primal-dual methods for linear and semidefinite optimization, New variants of the criss-cross method for linearly constrained convex quadratic programming, 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, New infeasible interior-point algorithm based on monomial method, Theoretical convergence of large-step primal-dual interior point algorithms for linear programming, Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path, An algorithm for portfolio optimization with variable transaction costs. II: Computational analysis, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Interior-point methods for linear programming: a review, An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity, Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema, An unconstrained convex programming approach to solving convex quadratic programming problems
