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

RAIRO - Operations Research (2008)

- Volume: 42, Issue: 2, page 199-213
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topEL Ghami, M., and Roos, C.. "Generic Primal-dual Interior Point Methods Based on a New Kernel Function." RAIRO - Operations Research 42.2 (2008): 199-213. <http://eudml.org/doc/250421>.

@article{ELGhami2008,

abstract = {
In this paper we present a generic primal-dual
interior 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.
},

author = {EL Ghami, M., Roos, C.},

journal = {RAIRO - Operations Research},

keywords = {Linear optimization; primal-dual interior-point algorithm; large and small-update method.; linear optimization; large and small-update method},

language = {eng},

month = {5},

number = {2},

pages = {199-213},

publisher = {EDP Sciences},

title = {Generic Primal-dual Interior Point Methods Based on a New Kernel Function},

url = {http://eudml.org/doc/250421},

volume = {42},

year = {2008},

}

TY - JOUR

AU - EL Ghami, M.

AU - Roos, C.

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

JO - RAIRO - Operations Research

DA - 2008/5//

PB - EDP Sciences

VL - 42

IS - 2

SP - 199

EP - 213

AB -
In this paper we present a generic primal-dual
interior 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.

LA - eng

KW - Linear optimization; primal-dual interior-point algorithm; large and small-update method.; linear optimization; large and small-update method

UR - http://eudml.org/doc/250421

ER -

## References

top- 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. Zbl0874.90127
- Y.Q. Bai, M. El Ghami, and C. Roos, A comparative study of new barrier functions for primal- dual interior-point algorithms in linear optimization. SIAM J. Optim.15 (2004) 101–128. Zbl1077.90038
- 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. Zbl1036.90051
- Y.Q. Bai, C. Roos, and M. El Ghami, A primal-dual interior-point method for linear optimization based on a new proximity function. Optim. Methods Softw.17 (2002) 985–1008. Zbl1032.90068
- C.C. Gonzaga, Path following methods for linear programming. SIAM Rev.34 (1992) 167–227. Zbl0763.90063
- D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Mathematics and its Applications277. 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.
- R.D.C. Monteiro and I. Adler, Interior-path following primal-dual algorithms: Part I: Linear programming. Math. Program.44 (1989) 27–41. Zbl0676.90038
- 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. Zbl1058.90037
- J. Peng, C. Roos, and T. Terlaky, A new and efficient large-update interior-point method for linear optimization. J. Comput. Tech.6 (2001) 61–80. Zbl0987.90089
- 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. Zbl1007.90037
- J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002. Zbl1136.90045
- C. Roos, T. Terlaky, and J.-P. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, Chichester, UK, 1997. Zbl0954.65041
- 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. Zbl0943.90070

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.