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

DOI10.2307/2001396zbMath0671.90045MaRDI QIDQ3824098

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 field; affine scaling algorithm; Karmarkar's projective scaling algorithm; P-trajectories; A-trajectories

Mathematics Subject Classification ID

90C05: Linear programming

34A34: Nonlinear ordinary differential equations and systems

52A40: Inequalities and extremum problems involving convexity in convex geometry

Related Items

Steepest descent evolution equations: asymptotic behavior of solutions and rate of convergence, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization., The relation between the path of centers and Smale's regularization of the linear programming problem, Interior-point algorithms for global optimization, 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, 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, Examples of ill-behaved central paths in convex optimization, 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 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, An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming