On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
Two versions of the `primal projective algorithm for linear programs' are given that use a weighted Karmarkar potential function. This potential is defined with respect to a strict lower bound to the optimal objective function value. The first solves the linear programming problem in the standard form of Karmarkar and the second computes a `weighted analytic center' of a certain dual polytope. For both algorithms a convergence analysis is given. A certain part of the article is devoted to the construction of a class of inner and outer ellipsoids for the dual polytope. It is shown that such a pair of homothetic dual ellipsoids can be constructed as soon as an interior feasible point sufficiently `deep' in the polytope is obtained. This approach extends results of Sonnevend.
- A Centered Projective Algorithm for Linear Programming
- Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
- A scaling technique for finding the weighted analytic center of a polytope
- Short Steps with Karmarkar’s Projective Algorithm for Linear Programming
- An extension of Karmarkar's algorithm for linear programming using dual variables
- A Centered Projective Algorithm for Linear Programming
- A new polynomial-time algorithm for linear programming
- A Polynomial Method of Weighted Centers for Convex Quadratic Programming
- A polynomial Newton method for linear programming
- A polynomial-time algorithm, based on Newton's method, 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
- Containing and shrinking ellipsoids in the path-following algorithm
- Cutting planes and column generation techniques with the projective algorithm
- Decomposition and Nondifferentiable Optimization with the Projective Algorithm
- scientific article; zbMATH DE number 3253619 (Why is no real title available?)
- Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
- Karmarkar's algorithm and the ellipsoid method
- Limiting behavior of the affine scaling continuous trajectories for linear programming problems
- New trajectory-following polynomial-time algorithm for linear programming problems
- On the convexity of the multiplicative version of Karmarkar's potential function
- Long-step interior-point algorithms for a class of variational inequalities with monotone operators
- Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming
- On improved Choi-Goldfarb solution-containing ellipsoids in linear programming
- A cutting-plane method to nonsmooth multiobjective optimization problems
- Primal-dual target-following algorithms for linear programming
- A cutting plane method from analytic centers for stochastic programming
- 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
- Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
- A path-following cutting plane method for some monotone variational inequalities∗
- scientific article; zbMATH DE number 4202018 (Why is no real title available?)
- An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
- Interior-point algorithms for a generalization of linear programming and weighted centring
- A weighted projection centering method
- 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
- Using central prices in the decomposition of linear programs
- A scaling technique for finding the weighted analytic center of a polytope
This page was built for publication: On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688920)
