The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories

DOI10.2307/2001396zbMath0671.90045OpenAlexW4249966188MaRDI QIDQ3824098

David Bayer, Jeffrey C. Lagarias

Publication date: 1989

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2001396

zbMATH Keywords

vector fieldaffine scaling algorithmKarmarkar's projective scaling algorithmP-trajectoriesA-trajectories

Mathematics Subject Classification ID

Linear programming (90C05) Nonlinear ordinary differential equations and systems (34A34) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Related Items (76)

An application of the continuous time replicator dynamic to economics ⋮ Riemannian game dynamics ⋮ Stable barrier-projection and barrier-Newton methods in linear programming ⋮ Steepest descent evolution equations: asymptotic behavior of solutions and rate of convergence ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming ⋮ Nonlinear coordinate representations of smooth optimization problems ⋮ Feasible region contraction interior point algorithm ⋮ Matrix representation and gradient flows for NP-hard problems ⋮ Linear programming and the Newton barrier flow ⋮ Inertial Game Dynamics and Applications to Constrained Optimization ⋮ Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ Unnamed Item ⋮ Primal-dual target-following algorithms for linear programming ⋮ Identifying an optimal basis in linear programming ⋮ Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm ⋮ Interior path following primal-dual algorithms. I: Linear programming ⋮ Trust region affine scaling algorithms for linearly constrained convex and concave programs ⋮ Matching centroids by a projective transformation ⋮ Deep Linear Networks for Matrix Completion—an Infinite Depth Limit ⋮ On the complexity of analyticity in semi-definite optimization ⋮ Doubly autoparallel structure and curvature integrals. Applications to iteration complexity for solving convex programs ⋮ A polynomial arc-search interior-point algorithm for convex quadratic programming ⋮ Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems ⋮ A class of primal affine scaling algorithms ⋮ The degree of the central curve in semidefinite, linear, and quadratic programming ⋮ Image labeling by assignment ⋮ An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations ⋮ Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory ⋮ Karmarkar's linear programming algorithm and Newton's method ⋮ A study of the dual affine scaling continuous trajectories for linear programming ⋮ Hamiltonian structure of dynamical systems which solve linear programming problems ⋮ Global convergence of the affine scaling methods for degenerate linear programming problems ⋮ Improving the rate of convergence of interior point methods for linear programming ⋮ Computational results of an interior point algorithm for large scale linear programming ⋮ Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights ⋮ Unified complexity analysis for Newton LP methods ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ Legendre transform and applications to finite and infinite optimization ⋮ On the convergence time of a natural dynamics for linear programming ⋮ Solving combinatorial optimization problems using Karmarkar's algorithm ⋮ A new vector field method for eigen-decomposition of symmetric matrices ⋮ Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals ⋮ The central curve in linear programming ⋮ Asymptotic behavior of the central path for a special class of degenerate SDP problems ⋮ Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization. ⋮ Examples of ill-behaved central paths in convex optimization ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem ⋮ On the convergence of the method of analytic centers when applied to convex quadratic programs ⋮ Unnamed Item ⋮ Extending the applicability of Newton's method on Lie groups ⋮ An optimization framework of biological dynamical systems ⋮ On the Convergence Time of a Natural Dynamics for Linear Programming ⋮ On the choice of parameters for power-series interior point algorithms in linear programming ⋮ Subgradient algorithm on Riemannian manifolds ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ An interior point potential reduction method for constrained equations ⋮ A class of polynomial variable metric algorithms for linear optimization ⋮ On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems ⋮ An implementation of Karmarkar's algorithm for linear programming ⋮ Learning in Games via Reinforcement and Regularization ⋮ Monotone variable-metric algorithm for linearly constrained nonlinear programming ⋮ An ADMM-based interior-point method for large-scale linear programming ⋮ Analytic centers and repelling inequalities ⋮ The dynamics and internal geometry of the three-city noxious location problem ⋮ A simplified global convergence proof of the affine scaling algorithm ⋮ On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate ⋮ The relation between the path of centers and Smale's regularization of the linear programming problem ⋮ Interior-point algorithms for global optimization ⋮ On the expected optimal value of random assignment problems: Experimental results and open questions ⋮ K-K-T multiplier estimates and objective function lower bounds from projective SUMT ⋮ A quadratically convergent method for linear programming ⋮ Optimizing over three-dimensional subspaces in an interior-point method for linear programming ⋮ Lax pair and fixed point analysis of Karmarkar's projective scaling trajectory for linear programming

This page was built for publication: The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories