Karmarkar's algorithm with improved steps

DOI10.1007/BF01585728MaRDI QIDQ910334zbMATH OpenFDO

Authors Bahman Kalantari

Publication date 1990

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

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

zbMATH Keywords

improved stepsKarmarkar's algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

The paper studies Karmarkar's canonical linear program: \(v=Min\{c^ tx:\) \(x\in \Omega \}\) where \(\Omega =\{x\in R^ n|\) \(Ax=0\), \(e^ tx=1\), \(x>0\}\) and \(\Omega^ 0=\{x\in \Omega |\) \(x>0\}\neq \emptyset\). It is assumed that \(c^ tx>0\) for all \(x\in \Omega^ 0\). The author defines a function \(\beta\) on \(\Omega^ 0\) such that \(\sup_{d\in \Omega^ 0}\beta (d)\leq 1\) if and only if \(v=0\). It is shown that for a given \(d\in \Omega^ 0\), there exists \(x_ d\in \Omega\) such that \(f(x_ d)\leq f(d)r_ d\) where the constant \(\gamma_ d\) increases monotonically and improves \textit{M. Padberg}'s constant [Oper. Res. Lett. 4, 253-257 (1986; Zbl 0617.90059)] if \(\beta (d)<1\). This compares also with \textit{N. Karmarkar}'s result [Combinatorica 4, No.4, 373-395 (1984; Zbl 0557.90065)] which states that for \(d\in \Omega^ 0\) there exists \(x_ d\in \Omega^ 0\) satisfying the inequality \(f(x_ d)\leq f(d)\gamma\) where \(0<\gamma <1\) depends on n.

Recommendations

• On the improvement per iteration in Karmarkar's algorithm for linear programming
• The Worst-Case Step in Karmarkar's Algorithm
• scientific article; zbMATH DE number 4079165
• Short Steps with Karmarkar’s Projective Algorithm for Linear Programming
• A Self-Correcting Version of Karmarkar’s Algorithm

Cites work

• A different convergence proof of the projective method for linear programming
• A new polynomial-time algorithm for linear programming
• A relaxed version of Karmarkar's method
• An extension of Karmarkar's algorithm for linear programming using dual variables
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)

Cited in

(7)

• A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm
• Generalization of Karmarkar's algorithm to convex homogeneous functions
• Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
• A theorem of the alternative for multihomogeneous functions and its relationship to diagonal scaling of matrices
• The Worst-Case Step in Karmarkar's Algorithm
• scientific article; zbMATH DE number 975789 (Why is no real title available?)
• A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm

This page was built for publication: Karmarkar's algorithm with improved steps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q910334)