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. 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 the present analysis, results derived from asymptotic analysis only feature poor accuracy in the range of practical interest (n between 1000 and 107).
