Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-24T13:39:33.800Z Has data issue: false hasContentIssue false
  • English
  • Français

Generic Primal-dual Interior Point Methods Based on a New Kernel Function

Published online by Cambridge University Press:  17 May 2008

M. EL Ghami  and
C. Roos
M. EL Ghami
Affiliation:
Department of Informatics, University of Bergen, Thormøblensgate 55, 5008 Bergen, Norway; [email protected]
C. Roos
Affiliation:
Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, PO Box 5031, 2600 GA Delft, The Netherlands; [email protected]
Get access

Abstract

In this paper we present a generic primal-dualinterior point methods (IPMs) for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. The proposed kernel function does not satisfy all the conditions proposed in [2].We show that the corresponding large-update algorithm improves the iteration complexity with a factor $n^{\frac16}$ when compared with the method based on the use of the classical logarithmic barrier function. For small-update interior point methods the iteration bound is $O(\sqrt{n}\log\frac{n}{\epsilon}),$ which is currently the best-known bound for primal-dual IPMs.

Keywords

Linear optimizationprimal-dual interior-point algorithmlarge and small-update method.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 2: CIRO 05 , April 2008 , pp. 199 - 213
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

E.D. Andersen, J. Gondzio, Cs. Mészáros, 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 Publishers, The Netherlands (1996) 189–252.
Bai, Y.Q., El Ghami, M., and Roos, C., A comparative study of new barrier functions for primal- dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004) 101–128. CrossRef
Bai, Y.Q., El Ghami, M., and Roos, C., A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13 (2003) 766-782. CrossRef
Bai, Y.Q., Roos, C., and El Ghami, M., A primal-dual interior-point method for linear optimization based on a new proximity function. Optim. Methods Softw. 17 (2002) 985–1008. CrossRef
Gonzaga, C.C., Path following methods for linear programming. SIAM Rev. 34 (1992) 167–227. CrossRef
D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Mathematics and its Applications 277. Kluwer Academic Publishers, Dordrecht, 1994.
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. Identical version in: Proceedings of the 6th Mathematical Programming Symposium of Japan, Nagoya, Japan, (1986) 1–35.
Monteiro, R.D.C. and Adler, I., Interior-path following primal-dual algorithms: Part I: Linear programming. Math. Program. 44 (1989) 27–41. CrossRef
J. Peng, C. Roos, and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization. To appear in Eur. J. Oper. Res.
Peng, J., Roos, C., and Terlaky, T., A new and efficient large-update interior-point method for linear optimization. J. Comput. Tech. 6 (2001) 61–80.
Peng, J., Roos, C., and Terlaky, T., Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002) 129–171. CrossRef
J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002.
C. Roos, T. Terlaky, and J.-P. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, Chichester, UK, 1997.
G. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In System Modelling and Optimization : Proceedings of the 12th IFIP- Conference held in Budapest, Hungary, September 1985, edited by A. Prékopa, J. Szelezsán, and B. Strazicky, Lecture Notes in Control and Information Sciences, Springer Verlag, Berlin, West–Germany, 84 (1986) 866–876.
M.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 Press, Dordrecht (1989) 109–157.
Y. Ye, Interior Point Algorithms, Theory and Analysis, John Wiley and Sons, Chichester, UK, 1997.