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

DOI10.2307/2001397MaRDI QIDQ3824099zbMATH OpenOpenAlexFDO

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

A-trajectoriesaffine scaling algorithmcentral trajectoriesfeasible solution polytopeKarmarkar's projective scaling algorithmsLegendre transform coordinatesP-trajectoryPower-series expansionsvector field

Mathematics Subject Classification ID

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

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

(59)

• On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems
• Linear programming and the Newton barrier flow
• New trajectory-following polynomial-time algorithm for linear programming problems
• 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
• Improving the rate of convergence of interior point methods for linear programming
• Solving combinatorial optimization problems using Karmarkar's algorithm
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming
• Algorithms for computing centroids
• Subgradient algorithm on Riemannian manifolds
• The dynamics and internal geometry of the three-city noxious location problem
• Degeneracy in interior point methods for linear programming: A survey
• K-K-T multiplier estimates and objective function lower bounds from projective SUMT
• Lax pair and fixed point analysis of Karmarkar's projective scaling trajectory for linear programming
• Gradient systems associated with probability distributions
• 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
• Long-step strategies in interior-point primal-dual methods
• Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
• Long-step path-following algorithm for convex quadratic programming problems in a Hilbert space
• Image labeling by assignment
• 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
• 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
• Differential-algebraic approach to linear programming
• A generalized homogeneous and self-dual algorithm for linear programming
• Nonlinear coordinate representations of smooth optimization problems
• Identifying an optimal basis in linear programming
• Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights
• Computing complex and real tropical curves using monodromy
• A new vector field method for eigen-decomposition of symmetric matrices
• Improved complexity results on solving real-number linear feasibility problems
• Continuous dynamical systems that realize discrete optimization on the hypercube
• The constrained Newton method on a Lie group and the symmetric eigenvalue problem
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• 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
• A class of primal affine scaling algorithms
• Computer geometry and encoding the information on a manifold
• A study of the dual affine scaling continuous trajectories for linear programming
• The degree of the central curve in semidefinite, linear, and quadratic programming
• A convex analysis view of the barrier problem
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• 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
• Hessian barrier algorithms for non-convex conic optimization
• Completely integrable gradient systems on the manifolds of Gaussian and multinomial distributions
• The central curve in linear programming
• Three different views on barrier functions in conic optimization
• Optimizing over three-dimensional subspaces in an interior-point method for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory

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)