PROBABILISTIC BOUNDS ON ONE-STEP OBJECTIVE POTENTIAL FUNCTION IMPROVEMENT IN KARMARKAR ALGORITHM

A detailed probabilistic analysis of the current step of Karmarkar's a lgorithm is presented. It does not rely on asymptotic probabilistic re sults 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 funct ion value and the decrease of the potential function value at one sing le step of the algorithm. 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 Karm arkar's algorithm. Finally it is shown that, contrasting with our anal ysis, results derived from asymptotic analysis only feature poor accur acy in the range of practical interest (n between 1000 and 10(7)).