A modification of Karmarkar's linear programming algorithm
From MaRDI portal
Publication:581231
DOI10.1007/BF01840454zbMath0626.90056OpenAlexW2086920040MaRDI QIDQ581231
Marc S. Meketon, Robert J. Vanderbei, Barry A. Freedman
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840454
least squaresprojected gradientmodificationComputational comparisonsKarmarkar's algorithmrevised simplex method
Related Items
A generalized interior-point barrier function approach for smooth convex programming with linear constraints ⋮ A new variant of the primal affine scaling algorithm for linear programs ⋮ Search directions for interior linear-programming methods ⋮ Limiting behavior of the affine scaling continuous trajectories for linear programming problems ⋮ Interior Point Algorithms in Linear Optimization ⋮ Insights into the interior-point methods ⋮ An affine scaling method using a class of differential barrier functions: primal approach ⋮ On the chaotic behavior of the primal–dual affine–scaling algorithm for linear optimization ⋮ An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions ⋮ Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming ⋮ Affine scaling with degenerate linear programming problems ⋮ 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 ⋮ 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 ⋮ Shape-preserving, multiscale interpolation by bi- and multivariate cubic \(L_{1}\) splines ⋮ Loss and retention of accuracy in affine scaling methods ⋮ Matrix partitioning methods for interior point algorithms. ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ An affine-scaling pivot algorithm for linear programming ⋮ Shape-preserving interpolation of irregular data by bivariate curvature-based cubic \(L_1\) splines in spherical coordinates ⋮ A trust region method based on a new affine scaling technique for simple bounded optimization ⋮ On the symmetric affiine scaling algorithm for line programming* ⋮ An alternative derivation of the projective interior point method for linear programming through the least squares approach ⋮ An interior multiobjective primal-dual linear programming algorithm using approximated gradients and sequential generation of anchor points ⋮ Interior-point methods for linear programming: a review ⋮ Robust and efficient estimation with weighted composite quantile regression ⋮ Superlinear convergence of the affine scaling algorithm ⋮ Interior-point algorithms for semi-infinite programming ⋮ Convergence property of the Iri-Imai algorithm for some smooth convex programming problems ⋮ 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 ⋮ Introduction: New approaches to linear programming ⋮ 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 ⋮ Computational experience with a dual affine variant of Karmarkar's method for linear programming ⋮ Shape-preserving approximation of multiscale univariate data by cubic \(L_1\) spline fits ⋮ Exploiting special structure in Karmarkar's linear programming algorithm ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems ⋮ Some variants of the Todd low-complexity algorithm ⋮ A relaxed version of Karmarkar's method ⋮ A primal-dual interior-point method for linear programming based on a weighted barrier function ⋮ Linear programming and the Newton barrier flow ⋮ Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case ⋮ A compressed primal-dual method for generating bivariate cubic \(L_{1}\) splines ⋮ An interior multiobjective primal-dual linear programming algorithm based on approximated gradients and efficient anchoring points ⋮ 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 ⋮ An extension of Karmarkar's projective algorithm for convex quadratic programming ⋮ Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm ⋮ An interior point algorithm for semi-infinite linear programming ⋮ Trust region affine scaling algorithms for linearly constrained convex and concave programs ⋮ Solving stochastic programming problems via Kalman filter and affine scaling ⋮ Shape-preserving univariate cubic and higher-degree \(L_{1}\) splines with function-value-based and multistep minimization principles ⋮ A trust region affine scaling method for bound constrained optimization ⋮ Fast \(L_1^kC^k\) polynomial spline interpolation algorithm with shape-preserving properties ⋮ Cubically convergent method for locating a nearby vertex in linear programming ⋮ Asymptotic behaviour of Karmarkar's method for linear programming ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ Decomposed block Cholesky factorization in the Karmarkar algorithm. Solving a class of super large LP problems ⋮ Dual interior point algorithms ⋮ 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 ⋮ A partial first-order affine-scaling method ⋮ 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 ⋮ Two-thirds is sharp for affine scaling ⋮ The \(\ell_1\) solution of linear inequalities ⋮ A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions ⋮ Convergence behavior of interior-point algorithms ⋮ An interior multiobjective linear programming algorithm ⋮ Shape-preserving, first-derivative-based parametric and nonparametric cubic \(L_{1}\) spline curves ⋮ Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization ⋮ The steepest descent gravitational method for linear programming ⋮ A strategy of global convergence for the affine scaling algorithm for convex semidefinite programming ⋮ \(C^1\) and \(C^2\)-continuous polynomial parametric \(L_p\) splines (\(p\geq 1\)) ⋮ Symmetric indefinite systems for interior point methods ⋮ Efficient solution of two-stage stochastic linear programs using interior point methods ⋮ An interior point method for quadratic programs based on conjugate projected gradients ⋮ A weighted least squares study of robustness in interior point linear programming ⋮ Interior point method: history and prospects ⋮ Computation of the collapse state in limit analysis using the LP primal affine scaling algorithm ⋮ Affine-scaling for linear programs with free variables ⋮ 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 ⋮ An implementation of Karmarkar's algorithm for linear programming ⋮ Affine scaling algorithm fails for semidefinite programming ⋮ Monotone variable-metric algorithm for linearly constrained nonlinear programming ⋮ Polynomial primal-dual cone affine scaling for semidefinite programming ⋮ The role of the augmented system in interior point methods ⋮ Generalized affine scaling algorithms for linear programming problems ⋮ Lagrangian transformation and interior ellipsoid methods in convex optimization ⋮ The empirical performance of a polynomial algorithm for constrained nonlinear optimization ⋮ 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 ⋮ A unified view of interior point methods for linear programming ⋮ Feasibility issues in a primal-dual interior-point method for linear programming ⋮ 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 monotonicity in the scaled potential algorithm for linear programming ⋮ The affine-scaling direction for linear programming is a limit of projective-scaling directions ⋮ Shape-preserving, multiscale interpolation by univariate curvature-based cubic \(L_{1}\) splines in Cartesian and polar coordinates ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ On the big \({\mathcal M}\) in the affine scaling algorithm ⋮ A primal-dual affine-scaling potential-reduction algorithm for linear programming
Cites Work
