SOME ALGORITHMS FOR SOLVING PRIMAL-DUAL LINEAR PROGRAMMING USING BARRIER METHODS

Abstract

There are many literatures in the field of interior point methods for exploring the properties of linear programming and its dual linear programming. Most of them use advanced mathematical arguments to introduce the field of linear programming. The purpose of this paper is to show that the interior point methods by barrier function approach can be used to introduce the field of linear programming. By using only elementary analytically results, we have proved that for every value of the barrier parameters, the primal logarithmic barrier function for the primal problem has a unique minimizer, and then the sequence of the minimizers converges to a minimizer of the primal problem. From this, we present an algorithm for solving primal problem using barrier function methods.

Similarly, we have also proved that for every value of the barrier parameters, the dual logarithmic barrier function for the dual problem has a unique maximizer, and then the sequence of the maximizers converges to a maximizer of the dual problem. From this, we also present an algorithm for solving dual problem using barrier function methods. Finally, by introducing a system called centering conditions, we also present a characterization of existence of optimal solution for primal-dual problem using barrier function methods.

Keywords: Barrier Function, Boundedness, Centering Conditions, Linear Programming, and Interior Points