Complexity analysis of interior point methods for convex quadratic programming based on a parameterized Kernel function
DOI:
https://doi.org/10.5269/bspm.47772Abstract
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.
References
1. 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
2. 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).
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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
10. Peng, J., Roos, C., Terlaky, T.,A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton. (2002).
11. 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
12. 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
13. C. Roos and T. Terlaky and J.Ph Vial.,Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester. (1997).
14. S. J. Wright.,Primal-dual interior point methods, Copyright by SIAM. (1997). https://doi.org/10.1137/1.9781611971453
15. M. El Ghami.,New Primal-Dual Interior-Point methods Based on Kernel Functions. thesis, Delft University. (2005).
2. 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).
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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
10. Peng, J., Roos, C., Terlaky, T.,A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton. (2002).
11. 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
12. 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
13. C. Roos and T. Terlaky and J.Ph Vial.,Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester. (1997).
14. S. J. Wright.,Primal-dual interior point methods, Copyright by SIAM. (1997). https://doi.org/10.1137/1.9781611971453
15. M. El Ghami.,New Primal-Dual Interior-Point methods Based on Kernel Functions. thesis, Delft University. (2005).
Downloads
Published
2022-02-02
Issue
Section
Research Articles
License
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).
