Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0857.90084
Minoux, M.
Probabilistic bounds on one step objective/potential function improvement in Karmarkar's algorithm. (English)
[J] RAIRO, Rech. Opér. 28, No.4, 329-355 (1994). ISSN 0399-0559

Summary: A detailed probabilistic analysis of the current step of Karmarkar's algorithm is presented. It does not rely on asymptotic probabilistic results and hence its validity is not restricted to ``sufficiently large'' values of $n$ (the dimension of the space). The main results obtained are probabilistic bounds for both the decrease of the objective function value and the decrease of the potential function value at one single step of the algorithm.\par When compared with those classically derived from worst case analysis, these bounds show that much larger figures of the decrease are obtained with high probability; this may be viewed as a partial explanation of the very good practical behaviour of Karmarkar's algorithm. Finally, it is shown that, contrasting with our analysis, results derived from asymptotic analysis only feature poor accuracy in the range of practical interest ($n$ between 1000 and $10^7$).

MSC 2000:: *90C05 Linear programming

Keywords: interior point methods; probabilistic analysis; Karmarkar's algorithm; worst case analysis

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]