The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories

DOI10.2307/2001397zbMath0671.90046OpenAlexW4244652052MaRDI QIDQ3824099

Jeffrey C. Lagarias, David Bayer

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/2001397

zbMATH Keywords

vector fieldaffine scaling algorithmA-trajectoriescentral trajectoriesfeasible solution polytopeKarmarkar's projective scaling algorithmsLegendre transform coordinatesP-trajectoryPower-series expansions

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 (55)

Limiting behavior of weighted central paths in linear programming ⋮ Scaling, shifting and weighting in interior-point methods ⋮ Gradient systems in view of information geometry ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ Limiting behavior of the affine scaling continuous trajectories for linear programming problems ⋮ Long-step strategies in interior-point primal-dual methods ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ A generalized homogeneous and self-dual algorithm for linear programming ⋮ Nonlinear coordinate representations of smooth optimization problems ⋮ Linear programming and the Newton barrier flow ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ Identifying an optimal basis in linear programming ⋮ Long-step path-following algorithm for convex quadratic programming problems in a Hilbert space ⋮ 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 ⋮ 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 ⋮ Computer geometry and encoding the information on a manifold ⋮ 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 ⋮ Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function ⋮ A study of the dual affine scaling continuous trajectories for linear programming ⋮ Improving the rate of convergence of interior point methods for linear programming ⋮ Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights ⋮ Solving combinatorial optimization problems using Karmarkar's algorithm ⋮ Long steps in an \(O(n^ 3L)\) algorithm for linear programming ⋮ A new vector field method for eigen-decomposition of symmetric matrices ⋮ Completely integrable gradient systems on the manifolds of Gaussian and multinomial distributions ⋮ Algorithms for computing centroids ⋮ The central curve in linear programming ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ Continuous dynamical systems that realize discrete optimization on the hypercube ⋮ Unnamed Item ⋮ On the choice of parameters for power-series interior point algorithms in linear programming ⋮ On the convergence of primal-dual interior-point methods with wide neighborhoods ⋮ Subgradient algorithm on Riemannian manifolds ⋮ Affine-scaling for linear programs with free variables ⋮ Containing and shrinking ellipsoids in the path-following algorithm ⋮ 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 ⋮ Computing complex and real tropical curves using monodromy ⋮ The constrained Newton method on a Lie group and the symmetric eigenvalue problem ⋮ The dynamics and internal geometry of the three-city noxious location problem ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate ⋮ Differential-algebraic approach to linear programming ⋮ K-K-T multiplier estimates and objective function lower bounds from projective SUMT ⋮ Optimizing over three-dimensional subspaces in an interior-point method for linear programming ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ Lax pair and fixed point analysis of Karmarkar's projective scaling trajectory for linear programming ⋮ Gradient systems associated with probability distributions

This page was built for publication: The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories