On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm

DOI10.1007/BF01580602zbMath0804.90087OpenAlexW1991534386MaRDI QIDQ688920

Jean-Philippe Vial, Jean-Louis Goffin

Publication date: 1 November 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580602

zbMATH Keywords

convergence analysisweighted analytic centerdual ellipsoidsprimal projective algorithmweighted Karmarkar potential function

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming, Primal-dual target-following algorithms for linear programming, An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix, A cutting plane method from analytic centers for stochastic programming, A \(J\)-symmetric quasi-Newton method for minimax problems, Learning lyapunov functions for hybrid systems, An interior point cutting plane heuristic for mixed integer programming, A path-following cutting plane method for some monotone variational inequalities^∗, A cutting-plane method to nonsmooth multiobjective optimization problems, Using central prices in the decomposition of linear programs, Linearization of McCormick relaxations and hybridization with the auxiliary variable method, A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs, Long-step interior-point algorithms for a class of variational inequalities with monotone operators, On improved Choi-Goldfarb solution-containing ellipsoids in linear programming

Uses Software

• ACCPM

Cites Work

• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A polynomial Newton method for linear programming
• Karmarkar's algorithm and the ellipsoid method
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On the convexity of the multiplicative version of Karmarkar's potential function
• New trajectory-following polynomial-time algorithm for linear programming problems
• Cutting planes and column generation techniques with the projective algorithm
• Containing and shrinking ellipsoids in the path-following algorithm
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• A Centered Projective Algorithm for Linear Programming
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• A Polynomial Method of Weighted Centers for Convex Quadratic Programming
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm