Complexity analysis of interior point methods for convex quadratic programming based on a parameterized Kernel function

Nawel Boudjellal; Hayet Roumili; Djamel Benterki

doi:10.5269/bspm.47772

Nawel Boudjellal Ferhat Abbas Setif University
Hayet Roumili Ferhat Abbas Setif University
Djamel Benterki Ferhat Abbas Setif University

Resumen

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.

Descargas

La descarga de datos todavía no está disponible.

Citas

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).