Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
Linear optimization; Kernel function; Interior point methods; Complexity bound
Linear optimization; Kernel function; Interior point methods; Complexity bound
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.
References:
[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,
[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, DOI 10.1137/S1052623403423114 | MR 2112978
[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, DOI 10.1051/ro/2015056 | MR 3570540
[4] Bouaafia, M., Benterki, D., Adnan, Y.: An efficient parameterized logarithmic kernel function for linear optimization. Optim. Lett., 12, 2018, 1079-1097, DOI 10.1007/s11590-017-1170-5 | MR 3819677
[5] Ghami, M. El: New Primal-Dual Interior-Point Methods Based on Kernel Functions. 2005, TU Delft, The Netherlands, PhD Thesis.
[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
[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
[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
[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
[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, DOI 10.1016/S0377-2217(02)00275-8 | MR 1934033
[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
[12] Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization, An Interior Point Approach. 1997, Wiley, Chichester, MR 1450094
[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
[14] Ye, Y.: Interior Point Algorithms, Theory and Analysis. 1997, Wiley, Chichester, MR 1481160
Search
Partner of
