A modification of Karmarkar's linear programming algorithm
From MaRDI portal
The authors present a modification of Karmarkar's algorithm, which uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal value of the objective function. The proof of the convergence is given assuming primal and dual nondegeneracy. Computational comparisons between this algorithm and the revised simplex method are reported. The authors undertook a regression on the algorithm of the time (number of iterations) as a linear function of the logarithms of m and n.
Recommendations
Cites work
- A new polynomial-time algorithm for linear programming
- Efficient Implementation of a Class of Preconditioned Conjugate Gradient Methods
- scientific article; zbMATH DE number 3854804 (Why is no real title available?)
- scientific article; zbMATH DE number 3808817 (Why is no real title available?)
- scientific article; zbMATH DE number 3356467 (Why is no real title available?)
Cited in
(only showing first 100 items - show all)- Intelligent gradient search in linear programming
- Introduction: New approaches to linear programming
- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- Exploiting special structure in Karmarkar's linear programming algorithm
- A relaxed version of Karmarkar's method
- Linear programming and the Newton barrier flow
- New trajectory-following polynomial-time algorithm for linear programming problems
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- An interior point algorithm for semi-infinite linear programming
- An optimal-basis identification technique for interior-point linear programming algorithms
- Karmarkar's linear programming algorithm and Newton's method
- A primal projective interior point method for linear programming
- A hybrid method for the nonlinear least squares problem with simple bounds
- A unified approach to interior point algorithms for linear complementarity problems: A summary
- Global convergence of the affine scaling methods for degenerate linear programming problems
- Comparative analysis of affine scaling algorithms based on simplifying assumptions
- A survey of search directions in interior point methods for linear programming
- Solving combinatorial optimization problems using Karmarkar's algorithm
- On affine scaling algorithms for nonconvex quadratic programming
- On the convergence of the affine-scaling algorithm
- Long steps in an \(O(n^ 3L)\) algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- Prior reduced fill-in in solving equations in interior point algorithms
- Projection algorithms for linear programming
- A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems
- An interior point method for quadratic programs based on conjugate projected gradients
- A weighted least squares study of robustness in interior point linear programming
- Using aspiration levels in an interactive interior multiobjective linear programming algorithm
- Using approximate gradients in developing an interactive interior primal-dual multiobjective linear programming algorithm
- Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems
- Affine scaling algorithm fails for semidefinite programming
- Polynomial primal-dual cone affine scaling for semidefinite programming
- The role of the augmented system in interior point methods
- The empirical performance of a polynomial algorithm for constrained nonlinear optimization
- Degeneracy in interior point methods for linear programming: A survey
- A simplified global convergence proof of the affine scaling algorithm
- Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems
- On the big \({\mathcal M}\) in the affine scaling algorithm
- A primal-dual affine-scaling potential-reduction algorithm for linear programming
- Interior-point algorithms for semi-infinite programming
- Convergence property of the Iri-Imai algorithm for some smooth convex programming problems
- On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds
- Stable barrier-projection and barrier-Newton methods in linear programming
- Scaling, shifting and weighting in interior-point methods
- Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
- Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case
- An interior multiobjective primal-dual linear programming algorithm based on approximated gradients and efficient anchoring points
- Trust region affine scaling algorithms for linearly constrained convex and concave programs
- Solving stochastic programming problems via Kalman filter and affine scaling
- Monotone variable-metric algorithm for linearly constrained nonlinear programming
- The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors
- Shape-preserving, multiscale interpolation by univariate curvature-based cubic \(L_{1}\) splines in Cartesian and polar coordinates
- Robust and efficient estimation with weighted composite quantile regression
- A partial first-order affine-scaling method
- Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization
- Symmetric indefinite systems for interior point methods
- Efficient solution of two-stage stochastic linear programs using interior point methods
- Affine-scaling for linear programs with free variables
- An implementation of Karmarkar's algorithm for linear programming
- On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables
- Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems
- Some variants of the Todd low-complexity algorithm
- A primal-dual interior-point method for linear programming based on a weighted barrier function
- An interior point algorithm for nonlinear quantile regression
- A relaxed primal-dual path-following algorithm for linear programming
- A simple proof of a primal affine scaling method
- An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption
- A convergence analysis for a convex version of Dikin's algorithm
- The primal power affine scaling method
- Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm
- A trust region affine scaling method for bound constrained optimization
- Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis
- Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
- A strategy of global convergence for the affine scaling algorithm for convex semidefinite programming
- Interior point method: history and prospects
- Generalized affine scaling algorithms for linear programming problems
- Lagrangian transformation and interior ellipsoid methods in convex optimization
- Superlinear convergence of the affine scaling algorithm
- Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
- Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
- Shape-preserving approximation of multiscale univariate data by cubic \(L_1\) spline fits
- Shape-preserving, first-derivative-based parametric and nonparametric cubic \(L_{1}\) spline curves
- Shape-preserving interpolation of irregular data by bivariate curvature-based cubic \(L_1\) splines in spherical coordinates
- A modification to the LINPACK downdating algorithm
- Search directions for interior linear-programming methods
- Limiting behavior of the affine scaling continuous trajectories for linear programming problems
- Affine scaling with degenerate linear programming problems
- Modification of the recursive solution procedure for a linear programming problem
- Loss and retention of accuracy in affine scaling methods
- An affine-scaling pivot algorithm for linear programming
- A trust region method based on a new affine scaling technique for simple bounded optimization
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- A variation on Karmarkar’s algorithm for solving linear programming problems
- Interior-point methods for linear programming: a review
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- scientific article; zbMATH DE number 4112381 (Why is no real title available?)
- Generating interior search directions for multiobjective linear programming using approximate gradients and efficient anchoring points
- Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema
- A new variant of the primal affine scaling algorithm for linear programs
This page was built for publication: A modification of Karmarkar's linear programming algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581231)
