| Title:
|
A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound (English) |
| Author:
|
Ayache, Benhadid |
| Author:
|
Khaled, Saoudi |
| Language:
|
English |
| Journal:
|
Communications in Mathematics |
| ISSN:
|
1804-1388 (print) |
| ISSN:
|
2336-1298 (online) |
| Volume:
|
28 |
| Issue:
|
1 |
| Year:
|
2020 |
| Pages:
|
27-41 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this paper, we propose a large-update primal-dual interior point algorithm for linear optimization. The method is based on a new class of kernel functions which differs from the existing kernel functions in which it has a double barrier term. The investigation according to it yields the best known iteration bound $O(\sqrt {n} \log (n) \log (\frac {n}{\varepsilon }) )$ for large-update algorithm with the special choice of its parameter $m$ and thus improves the iteration bound obtained in Bai et al.~\cite {El Ghami2004} for large-update algorithm. (English) |
| Keyword:
|
Linear optimization |
| Keyword:
|
Kernel function |
| Keyword:
|
Interior point methods |
| Keyword:
|
Complexity bound |
| MSC:
|
90C05 |
| MSC:
|
90C31 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1465.90041 |
| idMR:
|
MR4124288 |
| . |
| Date available:
|
2020-07-22T11:49:23Z |
| Last updated:
|
2021-11-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148259 |
| . |
| Reference:
|
[1] Bai, Y.Q., Roos, C.: A primal-dual interior point method based on a new kernel function with linear growth rate.Proceedings of the 9th Australian Optimization Day, Perth, Australia, 2002, 14p, |
| Reference:
|
[2] Bai, Y.Q., Ghami, M. El, Roos, C.: A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization.SIAM J. Optim., 15, 2004, 101-128, MR 2112978, 10.1137/S1052623403423114 |
| Reference:
|
[3] Bouaafia, M., Benterki, D., Adnan, Y.: Complexity analysis of interior point methods for linear programming based on a parameterized kernel.RAIRO-Oper. Res., 50, 2016, 935-949, MR 3570540, 10.1051/ro/2015056 |
| Reference:
|
[4] Bouaafia, M., Benterki, D., Adnan, Y.: An efficient parameterized logarithmic kernel function for linear optimization.Optim. Lett., 12, 2018, 1079-1097, MR 3819677, 10.1007/s11590-017-1170-5 |
| Reference:
|
[5] Ghami, M. El: New Primal-Dual Interior-Point Methods Based on Kernel Functions.2005, TU Delft, The Netherlands, PhD Thesis. |
| Reference:
|
[6] Ghami, M. El, Ivanov, I.D., Roos, C., Steihaug, T.: A polynomial-time algorithm for LO based on generalized logarithmic barrier functions.Int. J. Appl. Math., 21, 2008, 99-115, MR 2408056 |
| Reference:
|
[7] Karmarkar, N.K.: A new polynomial-time algorithm for linear programming.Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4, 1984, 373-395, MR 0779900 |
| Reference:
|
[8] Megiddo, N.: Pathways to the optimal set in linear programming.Progress in Mathematical Programming: Interior Point and Related Methods, 1989, 131-158, Springer, New York, MR 0982720 |
| Reference:
|
[9] Peng, J., Roos, C., Terlaky, T.: A new and efficient large-update interior point method for linear optimization.J. Comput. Technol., 6, 2001, 61-80, MR 1860114 |
| Reference:
|
[10] Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization.European Journal of Operational Research, 143, 2002, 234-256, MR 1934033, 10.1016/S0377-2217(02)00275-8 |
| Reference:
|
[11] Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms.2002, Princeton University Press, Princeton, MR 1938497 |
| Reference:
|
[12] Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization, An Interior Point Approach.1997, Wiley, Chichester, MR 1450094 |
| Reference:
|
[13] Sonnevend, G.: An ``analytic center'' for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming.System Modelling and Optimization: Proceedings of the 12th IFIP-Conference, Budapest, Hungary, Lecture Notes in Control and Information Science, 84, 1986, 866-876, Springer, Berlin, MR 0903521 |
| Reference:
|
[14] Ye, Y.: Interior Point Algorithms, Theory and Analysis.1997, Wiley, Chichester, MR 1481160 |
| . |
