An assumption‐free convergence analysis for a perturbation of the scaling algorithm for linear programs, with application to the L1 estimation problem

Hanif D. Sherali, Bradley O. Skarpness and Buyong Kim

Naval Research Logistics (NRL), 1988, vol. 35, issue 5, 473-492

Abstract: This article is concerned with the scaling variant of Karmarkar's algorithm for linear programming problems. Several researchers have presented convergence analyses for this algorithm under various nondegeneracy types of assumptions, or under assumptions regarding the nature of the sequence of iterates generated by the algorithm. By employing a slight perturbation of the algorithm, which is computationally imperceptible, we are able to prove without using any special assumptions that the algorithm converges finitely to an ε‐optimal solution for any chosen ε > 0, from which it can be (polynomically) rounded to an optimum, for ε > 0 small enough. The logarithmic barrier function is used as a construct for this analysis. A rounding scheme which produces an optimal extreme point solution is also suggested. Besides the non‐negatively constrained case, we also present a convergence analysis for the case of bounded variables. An application in statistics to the L1 estimation problem and related computational results are presented.

Date: 1988
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(198810)35:53.0.CO;2-#

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:35:y:1988:i:5:p:473-492

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().