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

DOI10.2307/2001397MaRDI QIDQ3824099zbMATHOpenAlexFDO

Authors Dave 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/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)

Recommendations

• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• scientific article; zbMATH DE number 4197743
• On the asymptotic behavior of the projective rescaling algorithm for linear programming
• scientific article; zbMATH DE number 4197739

Cited in

(58)

• Deep Linear Networks for Matrix Completion—an Infinite Depth Limit
• Hessian barrier algorithms for non-convex conic optimization
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Doubly autoparallel structure and curvature integrals. Applications to iteration complexity for solving convex programs
• On the complexity of analyticity in semi-definite optimization
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• 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
• Limiting behavior of weighted central paths in linear programming
• Nonlinear coordinate representations of smooth optimization problems
• Gradient systems in view of information geometry
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• Karmarkar's linear programming algorithm and Newton's method
• Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
• Long-step strategies in interior-point primal-dual methods
• A new vector field method for eigen-decomposition of symmetric matrices
• Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
• A generalized homogeneous and self-dual algorithm for linear programming
• Lax pair and fixed point analysis of Karmarkar's projective scaling trajectory for linear programming
• Containing and shrinking ellipsoids in the path-following algorithm
• Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A class of primal affine scaling algorithms
• Improved complexity results on solving real-number linear feasibility problems
• Differential-algebraic approach to linear programming
• Long-step path-following algorithm for convex quadratic programming problems in a Hilbert space
• Computing complex and real tropical curves using monodromy
• A convex analysis view of the barrier problem
• Scaling, shifting and weighting in interior-point methods
• Improving the rate of convergence of interior point methods for linear programming
• K-K-T multiplier estimates and objective function lower bounds from projective SUMT
• A class of polynomial variable metric algorithms for linear optimization
• The constrained Newton method on a Lie group and the symmetric eigenvalue problem
• New trajectory-following polynomial-time algorithm for linear programming problems
• The dynamics and internal geometry of the three-city noxious location problem
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Completely integrable gradient systems on the manifolds of Gaussian and multinomial distributions
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Optimizing over three-dimensional subspaces in an interior-point method for linear programming
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Algorithms for computing centroids
• Gradient systems associated with probability distributions
• An interior point potential reduction method for constrained equations
• Linear programming and the Newton barrier flow
• Affine-scaling for linear programs with free variables
• Continuous dynamical systems that realize discrete optimization on the hypercube
• Solving combinatorial optimization problems using Karmarkar's algorithm
• The central curve in linear programming
• Identifying an optimal basis in linear programming
• A study of the dual affine scaling continuous trajectories for linear programming
• Subgradient algorithm on Riemannian manifolds
• Computer geometry and encoding the information on a manifold
• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• Image labeling by assignment
• Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights
• Degeneracy in interior point methods for linear programming: A survey
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3824099)