Complexity analysis of interior point methods for linear programming based on a parameterized kernel function

Bouafia, Mousaab; Benterki, Djamel; Yassine, Adnan

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 935-949.

Kernel function plays an important role in defining new search directions for primal-dual interior point algorithm for solving linear optimization problems. This problem has attracted the attention of many researchers for some years. The goal of their works is to find kernel functions that improve algorithmic complexity of this problem. In this paper, we introduce a real parameter $p>0$ to generalize the kernel function (5) given by Bai et al. in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.], and give the corresponding primal-dual interior point methods for linear optimization. This parameterized kernel function yields the similar complexity bound given in [Y.Q. Bai, M El Ghami and C. Roos, SIAM J. Optim. 15 (2004) 101–128.] for both large-update and small-update methods.

Classification : 90C05, 90C31, 90C51
Mots clés : Linear optimization, Kernel function, interior point methods, complexity bound

E.D. Andersen, J. Gondzio, Cs. Meszaros and X. Xu, Implementation of interior point methods for large scale linear programming, in: Interior Point Methods of Mathematical Programming, edited by T. Terlaky. Kluwer Academic Publisher, The Netherlands (1996) 189–252. | MR | Zbl

Y.Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, in: Proc. of the 9th Australian Optimization Day. Perth, Australia (2002).

Y.Q. Bai and C. Roos, A polynomial-time algorithm for linear optimization based on a new simple kernel function. Optim. Methods Software 18 (2003) 631–646. | DOI | MR | Zbl

Y.Q. Bai, M. El Ghami and C. Roos, A new efficient large-update primal-dual interior point method based on a finite barrier. SIAM J. Optim. 13 (2003) 766–782. | DOI | MR | Zbl

Y.Q. Bai, M. El Ghami, C. Roos, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101–128. | DOI | MR | Zbl

Y.Q. Bai, G. Lesaja, C. Roos, G.Q. Wang and M. El Ghami, A class of large-update and small-update primal-dual interior point algorithms for linear optimization. J. Optim. Theory Appl. 138 (2008) 341–359. | DOI | MR | Zbl

Y.Q. Bai, J. Guo and C. Roos, A new kernel function yielding the best known iteration bounds for primal-dual interior point algorithms. Acta Mathematica Sinica 49 (2007) 259–270. | MR | Zbl

G.M. Cho, An interior point algorithm for linear optimization based on a new barrier function. Appl. Math. Comput. 218 (2011) 386–395. | DOI | MR | Zbl

M. El Ghami, Z.A. Guennoun, S. Bouali and T. Steihaug, Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math. 236 (2012) 3613–3623. | DOI | MR | Zbl

M. El Ghami, I. Ivanov, J.B.M. Melissen and C. Roos, T. Steihaug, A polynomial-time algorithm for linear optimization based on a new class of kernel functions. J. Comput. Appl. Math. 224 (2009) 500–513. | DOI | MR | Zbl

M. El Ghami and C. Roos, Generic primal-dual interior point methods based on a new kernel function. RAIRO: OR 42 (2008) 199–213. | DOI | Numdam | MR | Zbl

C.C. Gonzaga, Path following methods for linear programming. SIAM Rev. 34 (1992) 167–227. | DOI | MR | Zbl

D. den Hertog, Interior point approach to linear, quadratic and convex programming. Vol. 277 of Mathematical Application. Kluwer Academic Publishers, Dordrecht, The Netherlands (1994). | MR | Zbl

N.K. Karmarkar, A new polynomial-time algorithm for linear programming, in: Proc. of the 16th Annual ACM Symposium on Theory of Computing 4 (1984) 373–395. | MR | Zbl

N. Megiddo, Pathways to the optimal set in linear programming, in: Progress in Mathematical Programming: Interior Point and Related Methods, edited by N. Megiddo. Springer-Verlag, New York (1989) 131–158. | MR | Zbl

J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002) 129–171. | DOI | MR | Zbl

J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual interior point Algorithms. Princeton University Press, Princeton, NJ (2002). | MR | Zbl

C. Roos, T. Terlaky and J.Ph. Vial, Theory and algorithms for linear optimization, in: An interior point Approach. John Wiley & Sons, Chichester, UK (1997). | MR | Zbl

G. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, System Modelling and Optimization: Proc. of the 12th IFIP-Conference, edited by A. Prekopa, J. Szelezsan and B. Strazicky. Budapest, Hungary, 1985. In Vol. 84 of Lecture Notes in Control and Inform. Sci. Springer-Verlag, Berlin (1986) 866–876. | Zbl

N.J. Todd, Recent developments and new directions in linear programming, in: Mathematical Programming: Recent developments and applications, edited by M. Iri and K. Tanabe. Kluwer Academic Publishers, Dordrecht (1989) 109–157. | MR | Zbl

S.J. Wright, Primal-Dual Interior Point Methods. SIAM, Philadelphia, USA (1997). | MR | Zbl

Y. Ye, Interior Point Algorithms. Theory and Analysis. John-Wiley. Sons, Chichester, UK (1997). | MR | Zbl