Khalid El Yassini - Analysis of two interior-exterior penalty algorithms for linear programming

We describe two interior-exterior algorithms for linear programming problem. The algorithms are based on path following idea and use a two parameter mixed penalty function. Each iteration updates the penalty parameters. An approximate solution, of Karush-Kuhn-Tucker system of equations which characterizes a solution of the mixed penalty function, is computed by using only one Newton direction in the first algorithm and by predictor-corrector method in the second algorithm. The approximate solution obtained gives a dual and a pseudo-feasible primal points. Since the primal solution is non feasible, a new pseudo-gap definition is introduced to characterize primal and dual solutions. Finally, Some numerical results will be presented.