Generic primal-dual interior point methods based on a new kernel function

Ghami, M. El; Roos, C.

doi:10.1051/ro:2008009

Ghami, M. El ; Roos, C.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 199-213.

Résumé

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^{\frac{1}{6}}$ 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}{ϵ}),$ which is currently the best-known bound for primal-dual IPMs.

MR | 2 citations dans Numdam

DOI : 10.1051/ro:2008009

Classification : 90C05, 90C31
Mots-clés : linear optimization, primal-dual interior-point algorithm, large and small-update method

@article{RO_2008__42_2_199_0,
     author = {Ghami, M. El and Roos, C.},
     title = {Generic primal-dual interior point methods based on a new kernel function},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {199--213},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ro:2008009},
     mrnumber = {2431399},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro:2008009/}
}

TY  - JOUR
AU  - Ghami, M. El
AU  - Roos, C.
TI  - Generic primal-dual interior point methods based on a new kernel function
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 199
EP  - 213
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro:2008009/
DO  - 10.1051/ro:2008009
LA  - en
ID  - RO_2008__42_2_199_0
ER  -

%0 Journal Article
%A Ghami, M. El
%A Roos, C.
%T Generic primal-dual interior point methods based on a new kernel function
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 199-213
%V 42
%N 2
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro:2008009/
%R 10.1051/ro:2008009
%G en
%F RO_2008__42_2_199_0

Ghami, M. El; Roos, C. Generic primal-dual interior point methods based on a new kernel function. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 199-213. doi : 10.1051/ro:2008009. https://www.numdam.org/articles/10.1051/ro:2008009/

Bibliographie
Cité par

[1] 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. | MR | Zbl

[2] 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. | MR | Zbl

[3] 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. | MR | Zbl

[4] 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. | MR | Zbl

[5] C.C. Gonzaga, Path following methods for linear programming. SIAM Rev. 34 (1992) 167-227. | MR | Zbl

[6] D. Den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Mathematics and its Applications 277. Kluwer Academic Publishers, Dordrecht, 1994. | MR | Zbl

[7] 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. | MR | Zbl

[8] R.D.C. Monteiro and I. Adler, Interior-path following primal-dual algorithms: Part I: Linear programming. Math. Program. 44 (1989) 27-41. | MR | Zbl

[9] 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. | MR | Zbl

[10] 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. | MR | Zbl

[11] 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. | MR | Zbl

[12] J. Peng, C. Roos, and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, 2002. | MR | Zbl

[13] C. Roos, T. Terlaky, and J.-P. Vial, Theory and Algorithms for Linear Optimization. An Interior-Point Approach. John Wiley & Sons, Chichester, UK, 1997. | MR | Zbl

[14] 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. | MR | Zbl

[15] 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. | MR | Zbl

[16] Y. Ye, Interior Point Algorithms, Theory and Analysis, John Wiley and Sons, Chichester, UK, 1997. | MR | Zbl

Touil, Imene; Chikouche, Wided; Benterki, Djamel; Zerari, Amina An Efficient Hyperbolic Kernel Function Yielding the Best Known Iteration Bounds for Linear Programming, Acta Mathematicae Applicatae Sinica, English Series, Volume 41 (2025) no. 1, p. 133 | DOI:10.1007/s10255-024-1146-z
Hafshejani, S. Fathi; Fatemi, M.; Peyghami, M. Reza An interior-point method for $P_{*} (κ)$ P ∗ ( κ ) -linear complementarity problem based on a trigonometric kernel function, Journal of Applied Mathematics and Computing, Volume 48 (2015) no. 1-2, p. 111 | DOI:10.1007/s12190-014-0794-1
Bouafia, Mousaab; Benterki, Djamel; Yassine, Adnan A Numerical Implementation of an Interior Point Methods for Linear Programming Based on a New Kernel Function, Modelling, Computation and Optimization in Information Systems and Management Sciences, Volume 359 (2015), p. 357 | DOI:10.1007/978-3-319-18161-5_30
Peyghami, M. Reza; Hafshejani, S. Fathi; Shirvani, L. Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, Volume 255 (2014), p. 74 | DOI:10.1016/j.cam.2013.04.039
Cai, Xinzhong; Wu, Lin; Yue, Yujing; Li, Minmin; Wang, Guoqiang Kernel-function-based primal-dual interior-point methods for convex quadratic optimization over symmetric cone, Journal of Inequalities and Applications, Volume 2014 (2014) no. 1 | DOI:10.1186/1029-242x-2014-308
Peyghami, M. Reza; Hafshejani, S. Fathi Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function, Numerical Algorithms, Volume 67 (2014) no. 1, p. 33 | DOI:10.1007/s11075-013-9772-1
El Ghami, M.; Guennoun, Z.A.; Bouali, S.; Steihaug, T. Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term, Journal of Computational and Applied Mathematics, Volume 236 (2012) no. 15, p. 3613 | DOI:10.1016/j.cam.2011.05.036
Vieira, Manuel V. C. The Accuracy of Interior-Point Methods Based on Kernel Functions, Journal of Optimization Theory and Applications, Volume 155 (2012) no. 2, p. 637 | DOI:10.1007/s10957-012-0071-0
Cho, Gyeong-Mi An interior-point algorithm for linear optimization based on a new barrier function, Applied Mathematics and Computation, Volume 218 (2011) no. 2, p. 386 | DOI:10.1016/j.amc.2011.05.075
CHO, G. M.; CHO, Y. Y.; LEE, Y. H. A PRIMAL-DUAL INTERIOR-POINT ALGORITHM BASED ON A NEW KERNEL FUNCTION, The ANZIAM Journal, Volume 51 (2010) no. 4, p. 476 | DOI:10.1017/s1446181110000908
EL Ghami, M.; Bai, Y. Q.; Roos, C. Kernel-function Based Algorithms for Semidefinite Optimization, RAIRO - Operations Research, Volume 43 (2009) no. 2, p. 189 | DOI:10.1051/ro/2009011

Cité par 11 documents. Sources : Crossref