A Self-Correcting Version of Karmarkar's Algorithm

D. Goldfarb; S. Mehrotra

doi:10.1137/0726056

A Self-Correcting Version of Karmarkar's Algorithm

D. Goldfarb, S. Mehrotra

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

Abstract

A relaxed version of Karmarkar's algorithm is developed that does not require the direction of movement to be in the null space of the constraint matrix. The algorithm is proved to have the same rate of convergence as Karmarkar's algorithm. Conditions are also given guaranteeing that the approach suggested by Karmarkar for transforming an "inequality form" linear program into the form required by his algorithm is well defined.

Original language	English
Pages (from-to)	1006-1015
Journal	SIAM Journal on Numerical Analysis
Volume	26
DOIs	https://doi.org/10.1137/0726056
State	Published - Aug 1989

Access to Document

10.1137/0726056

http://epubs.siam.or

Cite this

@article{dad9747bf0214b46b0df7699470175b6,

title = "A Self-Correcting Version of Karmarkar's Algorithm",

abstract = "A relaxed version of Karmarkar's algorithm is developed that does not require the direction of movement to be in the null space of the constraint matrix. The algorithm is proved to have the same rate of convergence as Karmarkar's algorithm. Conditions are also given guaranteeing that the approach suggested by Karmarkar for transforming an {"}inequality form{"} linear program into the form required by his algorithm is well defined.",

author = "D. Goldfarb and S. Mehrotra",

year = "1989",

month = aug,

doi = "10.1137/0726056",

language = "English",

volume = "26",

pages = "1006--1015",

journal = "SIAM Journal on Numerical Analysis",

issn = "0036-1429",

publisher = "Society for Industrial and Applied Mathematics Publications",

}

TY - JOUR

T1 - A Self-Correcting Version of Karmarkar's Algorithm

AU - Goldfarb, D.

AU - Mehrotra, S.

PY - 1989/8

Y1 - 1989/8

N2 - A relaxed version of Karmarkar's algorithm is developed that does not require the direction of movement to be in the null space of the constraint matrix. The algorithm is proved to have the same rate of convergence as Karmarkar's algorithm. Conditions are also given guaranteeing that the approach suggested by Karmarkar for transforming an "inequality form" linear program into the form required by his algorithm is well defined.

AB - A relaxed version of Karmarkar's algorithm is developed that does not require the direction of movement to be in the null space of the constraint matrix. The algorithm is proved to have the same rate of convergence as Karmarkar's algorithm. Conditions are also given guaranteeing that the approach suggested by Karmarkar for transforming an "inequality form" linear program into the form required by his algorithm is well defined.

U2 - 10.1137/0726056

DO - 10.1137/0726056

M3 - Article

SN - 0036-1429

VL - 26

SP - 1006

EP - 1015

JO - SIAM Journal on Numerical Analysis

JF - SIAM Journal on Numerical Analysis

ER -

A Self-Correcting Version of Karmarkar's Algorithm

Abstract

Access to Document

Fingerprint

Cite this