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

DOI10.2307/2001396MaRDI QIDQ3824098zbMATH 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/2001396

zbMATH Keywords

A-trajectoriesaffine scaling algorithmKarmarkar's projective scaling algorithmP-trajectoriesvector 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. II Legendre Transform Coordinates and Central Trajectories
• scientific article; zbMATH DE number 4043632
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• scientific article; zbMATH DE number 4197742
• Affine-Scaling Trajectories Associated with a Semi-Infinite Linear Program
• Affine geometric method for linear programs
• scientific article; zbMATH DE number 4197743
• Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
• A study of the dual affine scaling continuous trajectories for linear programming

Cited in

(91)

• 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
• Interior path following primal-dual algorithms. I: Linear programming
• Karmarkar's linear programming algorithm and Newton's method
• 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
• Unified complexity analysis for Newton LP methods
• Solving combinatorial optimization problems using Karmarkar's algorithm
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• Subgradient algorithm on Riemannian manifolds
• The dynamics and internal geometry of the three-city noxious location problem
• A simplified global convergence proof of the affine scaling algorithm
• 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
• Lax pair and fixed point analysis of Karmarkar's projective scaling trajectory for linear programming
• Stable barrier-projection and barrier-Newton methods in linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• Trust region affine scaling algorithms for linearly constrained convex and concave programs
• Monotone variable-metric algorithm for linearly constrained nonlinear programming
• An application of the continuous time replicator dynamic to economics
• Riemannian game dynamics
• Image labeling by assignment
• Examples of ill-behaved central paths in convex optimization
• An optimization framework of biological dynamical systems
• On the choice of parameters for power-series interior point algorithms in linear programming
• An interior point potential reduction method for constrained equations
• A class of polynomial variable metric algorithms for linear optimization
• An implementation of Karmarkar's algorithm for linear programming
• Analytic centers and repelling inequalities
• Nonlinear coordinate representations of smooth optimization problems
• Matrix representation and gradient flows for NP-hard problems
• 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
• Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights
• On the convergence time of a natural dynamics for linear programming
• Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
• On the convergence of the method of analytic centers when applied to convex quadratic programs
• A new vector field method for eigen-decomposition of symmetric matrices
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• Extending the applicability of Newton's method on Lie groups
• An O(n^ 3L) primal interior point algorithm for convex quadratic programming
• Learning in games via reinforcement and regularization
• Inertial game dynamics and applications to constrained optimization
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• On the central paths and Cauchy trajectories in semidefinite programming
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• scientific article; zbMATH DE number 17712 (Why is no real title available?)
• The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods
• Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
• A polynomial arc-search interior-point algorithm for convex quadratic programming
• Steepest descent evolution equations: asymptotic behavior of solutions and rate of convergence
• A class of primal affine scaling algorithms
• Log-Barrier Interior Point Methods Are Not Strongly Polynomial
• scientific article; zbMATH DE number 753751 (Why is no real title available?)
• Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
• On the symmetric affiine scaling algorithm for line programming^*
• A study of the dual affine scaling continuous trajectories for linear programming
• An ADMM-based interior-point method for large-scale linear programming
• The degree of the central curve in semidefinite, linear, and quadratic programming
• Legendre transform and applications to finite and infinite optimization
• A convex analysis view of the barrier problem
• On the convergence time of a natural dynamics for linear programming
• What Tropical Geometry Tells Us about the Complexity of Linear Programming
• scientific article; zbMATH DE number 4197739 (Why is no real title available?)
• scientific article; zbMATH DE number 4197742 (Why is no real title available?)
• scientific article; zbMATH DE number 4197743 (Why is no real title available?)
• On the central path of semidefinite optimization: degree and worst-case convergence rate
• 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
• Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
• Hessian barrier algorithms for non-convex conic optimization
• The central curve in linear programming
• Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization.
• Non-negative sparse signal recovery with a feasible based sequential quadratic programming
• A gradient descent akin method for constrained optimization: algorithms and applications
• On the asymptotic behavior of the projective rescaling algorithm for linear programming
• The relation between the path of centers and Smale's regularization of the linear programming problem
• Interior-point algorithms for global optimization
• The affine-scaling direction for linear programming is a limit of projective-scaling directions
• A quadratically convergent method for linear programming
• Optimizing over three-dimensional subspaces in an interior-point method for linear programming
• Feasible region contraction interior point algorithm
• 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
• Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

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

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