An affine scaling method using a class of differential barrier functions: primal approach

Abstract

In this paper we propose a family of affine scaling interior point algorithms, called galpv4, using a primal approach, based on a large class of differential barrier functions. We show that these algorithms are in fact an extension and generalization of the classical affine scaling algorithm based on the well-known log barrier function. After carrying out a complete convergence analysis, we select some of these algorithms for comparison with the classical affine scaling algorithm, performed with the help of the familiar Netlib test set.

Keywords:

• concave gauge
• differential barrier
• interior point methods
• linear programs
• primal algorithm

2010 Mathematics Subject Classifications:

• 90C05
• 90C51
• 49M30
• 49N15

Acknowledgments

The anonymous referees are kindly acknowledged. Their comments greatly helped to improve the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Self-concordant functions were introduced by Yu. E. Nesterov and A. S. Nemirowskii in [18]. These functions are particularly useful in the analysis of Newton's method.

2 We recall that the idea to approximate a linear program by a nonlinear optimization problem is due originally to Courant [19] in 1941 with a penalty function of exterior type and later to Frisch [20], in 1955, when he introduced the logarithmic barrier function which is an interior penalty one. We recall also that the notion of interior penalty operators were introduced by Auslender [21] in 1976 to generalize the concept of barrier functions.

3 An affine scaling algorithm was originally proposed by Dikin in 1967 [22]. It was rediscovered by several researchers such as Barnes [5] and Vanderbei et al. [6] after Karmarkar [23] proposed his famous projective scaling algorithm.

4 A good description can be found in for example the book of Roos, Terlaky and Vial [24].

5 Note that the primal-dual affine scaling approach, proposed for the first time by Monteiro, Adler and Resende [25], has also been the subject of many works such as Jansen, Roos and Terlaky [26] and Potra [27].