Complexity analysis of interior point methods for convex quadratic programming based on a parameterized Kernel function
Résumé
The kernel functions play an important role in the amelioration of the computational complexity of algorithms. In this paper, we present a primal-dual interior-point algorithm for solving convex quadratic programming based on a new parametric kernel function. The proposed kernel function is not logarithmic and not self-regular. We analysis a large and small-update versions which are based on a new kernel function. We obtain the best known iteration bound for large-update methods, which improves signicantly the so far obtained complexity results. This
result is the rst to reach this goal.
Téléchargements
Références
Bai, Y. Q., El Ghami, M., Roos, C.,A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization, SIAM. J. Optim. 15(1), 101-128 (2005). https://doi.org/10.1137/S1052623403423114
Bai, Roos, C.,A primal-dual interior point method based on a new kernel function with linear growth rate, In: Proceedings of the 9th Australian Optimization Day, Perth, Australia. 1 (2002).
Bouafia, M., Benterki, D., Yassine, A.,Complexity analysis of interior point methods for linear programming based on a parameterized kernel function, RAIRO-Oper. Res. 50, 935-949 (2016). https://doi.org/10.1051/ro/2015056
Bouafia, M., Benterki, D., Yassine, A.,An efficient primal-dual interior point method for linear programming problems based on a new kernel function with a trigonometric barrier term, Journal of Optimization Theory and Applications. 170(2), 528-545 (2016). https://doi.org/10.1007/s10957-016-0895-0
Cai, X. Z., Wang, G. Q., El Ghami, M., Yue, Y. J.,Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term, Abstr. Appl. Anal., Art. ID 710158, 11 (2014). https://doi.org/10.1155/2014/710158
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, J. Comput. Appl. Math. 236, 3613-3623 (2012). https://doi.org/10.1016/j.cam.2011.05.036
Kheirfam, B., Moslem, M.,A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term, YUJOR 25(2), 233-250 (2015). https://doi.org/10.2298/YJOR120904006K
Li, X., Zhang, M.,Interior-point algorithm for linear optimization based on a new trigonometric kernel function, Oper. Res. Lett 43(5), 471-475 (2015). https://doi.org/10.1016/j.orl.2015.06.013
Peng, J., Roos, C., Terlaky, T., A new and efficient large-update interior point method for linear optimization, J. Comput. Technol. 6, 61-80 (2001). https://doi.org/10.1080/1055678021000039175
Peng, J., Roos, C., Terlaky, T.,A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton. (2002).
Peyghami, M. R., Hafshejani, S. F.,Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function, Numer. Algorithms. 67, 33-48 (2014). https://doi.org/10.1007/s11075-013-9772-1
Peyghami, M. R., Hafshejani, S. F., Shirvani, L.,Complexity of interior point methods for linear optimization based on a new trigonometric kernel function, J. Comput. Appl. Math. 255, 74-85 (2014). https://doi.org/10.1016/j.cam.2013.04.039
C. Roos and T. Terlaky and J.Ph Vial.,Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester. (1997).
S. J. Wright.,Primal-dual interior point methods, Copyright by SIAM. (1997). https://doi.org/10.1137/1.9781611971453
M. El Ghami.,New Primal-Dual Interior-Point methods Based on Kernel Functions. thesis, Delft University. (2005).
Copyright (c) 2022 Boletim da Sociedade Paranaense de Matemática
Ce travail est disponible sous la licence Creative Commons Attribution 4.0 International .
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
