Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions

Safa Guerdouh; Wided Chikouche; Imene Touil; Adnan Yassine

Kybernetika (2023)

  • Volume: 59, Issue: 6, page 827-860
  • ISSN: 0023-5954

Abstract

top
In this paper, we first present a polynomial-time primal-dual interior-point method (IPM) for solving linear programming (LP) problems, based on a new kernel function (KF) with a hyperbolic-logarithmic barrier term. To improve the iteration bound, we propose a parameterized version of this function. We show that the complexity result meets the currently best iteration bound for large-update methods by choosing a special value of the parameter. Numerical experiments reveal that the new KFs have better results comparing with the existing KFs including log t in their barrier term. To the best of our knowledge, this is the first IPM based on a parameterized hyperbolic-logarithmic KF. Moreover, it contains the first hyperbolic-logarithmic KF (Touil and Chikouche in Filomat 34:3957-3969, 2020) as a special case up to a multiplicative constant, and improves significantly both its theoretical and practical results.

How to cite

top

Guerdouh, Safa, et al. "Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions." Kybernetika 59.6 (2023): 827-860. <http://eudml.org/doc/299208>.

@article{Guerdouh2023,
abstract = {In this paper, we first present a polynomial-time primal-dual interior-point method (IPM) for solving linear programming (LP) problems, based on a new kernel function (KF) with a hyperbolic-logarithmic barrier term. To improve the iteration bound, we propose a parameterized version of this function. We show that the complexity result meets the currently best iteration bound for large-update methods by choosing a special value of the parameter. Numerical experiments reveal that the new KFs have better results comparing with the existing KFs including $\log t$ in their barrier term. To the best of our knowledge, this is the first IPM based on a parameterized hyperbolic-logarithmic KF. Moreover, it contains the first hyperbolic-logarithmic KF (Touil and Chikouche in Filomat 34:3957-3969, 2020) as a special case up to a multiplicative constant, and improves significantly both its theoretical and practical results.},
author = {Guerdouh, Safa, Chikouche, Wided, Touil, Imene, Yassine, Adnan},
journal = {Kybernetika},
keywords = {linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods},
language = {eng},
number = {6},
pages = {827-860},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions},
url = {http://eudml.org/doc/299208},
volume = {59},
year = {2023},
}

TY - JOUR
AU - Guerdouh, Safa
AU - Chikouche, Wided
AU - Touil, Imene
AU - Yassine, Adnan
TI - Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions
JO - Kybernetika
PY - 2023
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 6
SP - 827
EP - 860
AB - In this paper, we first present a polynomial-time primal-dual interior-point method (IPM) for solving linear programming (LP) problems, based on a new kernel function (KF) with a hyperbolic-logarithmic barrier term. To improve the iteration bound, we propose a parameterized version of this function. We show that the complexity result meets the currently best iteration bound for large-update methods by choosing a special value of the parameter. Numerical experiments reveal that the new KFs have better results comparing with the existing KFs including $\log t$ in their barrier term. To the best of our knowledge, this is the first IPM based on a parameterized hyperbolic-logarithmic KF. Moreover, it contains the first hyperbolic-logarithmic KF (Touil and Chikouche in Filomat 34:3957-3969, 2020) as a special case up to a multiplicative constant, and improves significantly both its theoretical and practical results.
LA - eng
KW - linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods
UR - http://eudml.org/doc/299208
ER -

References

top
  1. Anane, N., Méthodes de points intérieurs pour la programmation linéaire basées sur les fonctions noyaux., (Magister Thesis), Ferhat Abbas University, Setif 2012. 
  2. Amini, K., Haseli, K. A., , ANZIAM J. 49 (2007), 259-270. MR2408519DOI
  3. Amini, K., Peyghami, M. R., An interior-point algorithm for linear optimization based on a new kernel function., Southeast Asian Bull. Math. 29 (2005), 651-667. MR2188017
  4. Amini, K., Peyghami, M. R., , Bull. Austral. Math. Soc. 71 (2005), 139-153. MR2127673DOI
  5. Amini, K., Peyghami, M. R., , Appl. Math. Comput. 207(2) (2009), 501-513. MR2489104DOI
  6. Bai, Y.Q., Ghami, M. El, Roos, C., , SIAM J. Optim. 15 (2004), 101-128. MR2112978DOI
  7. Bai, Y. Q., Ghami, M. El, Roos, C., , SIAM J. Optim. 13 (2002), 766-782. MR1972215DOI
  8. Bai, Y. Q., Wang, G. Q., , J. Comput. Appl. Math. 233 (2009), 248-263. MR2568523DOI
  9. Bai, Y. Q., Wang, G. Q., Roos, C., , Nonlinear Anal. 70 (2009), 10, 3584-3602. MR2502767DOI
  10. Benhadid, A., Saoudi, K., , Commun. Math. 28 (2020), 27-41. MR4124288DOI
  11. Bouafia, M., Benterki, D., Yassine, A., , Optim. Lett. 12 (2018), 1079-1097. MR3819677DOI
  12. Bouafia, M., Benterki, D., Yassine, A., , J. Optim. Theory Appl. 170 (2016), 528-545. MR3527709DOI
  13. Cai, X. Z., Li, L., Ghami, M. El, Steihaug, T., Wang, G. Q., A new parametric kernel function yielding the best known iteration bounds of interior-point methods for the Cartesian P * ( κ ) - LCP over symmetric cones., Pac. J. Optim. 13 (2017), 4, 547-570. MR3743080
  14. Cai, X. Z., Wang, G. Q., Ghami, M. El, Yue, Y. J., , Abstr. Appl. Anal. (2014) Article ID 710158. MR3226224DOI
  15. Cai, X. Z., Wang, G. Q., Zhang, Z. H., , Numer. Algorithms 62 (2013), 289-306. MR3011391DOI
  16. Cai, X. Z., Wu, L., Yue, Y. J., L, M. M., Wang, G. Q., Kernel-function based primal dual interior- point methods for convex quadratic optimization over symmetric cone., J. Inequal. Appl. (2014), 308, 22 pp. MR3359089
  17. Choi, B. K., Lee, G. M., , Nonlinear Anal. 71 (2009), 2628-2640. MR2672034DOI
  18. Choi, B. K, Lee, G. M., On complexity analysis of the primal-dual interior-point method for second-order cone optimization problem., J. Korean Soc. Ind. Appl. Math. 14 (2010), 2, 93-111. MR2719195
  19. Derbal, L., Kebbiche, Z., , J. Sib. Fed. Univ. Math. Phys. 12 (2019), 2, 160-172. MR3941774DOI
  20. Ghami, M. El, Bai, Y. Q., Roos, C., , RAIRO Oper. Res. 43 (2009), 189-199. MR2527862DOI
  21. Ghami, M. El, Guennoun, Z. A., Bouali, S., Steihaug, T., , J. Comput. Appl. Math. 236 (2012), 3613-3623. MR2923494DOI
  22. 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. MR2408056
  23. Ghami, M.El., Ivanov, I. D., Melissen, J.B.M., Roos, C., Steihaug, T., , J. Comput. Appl. Math. 224 (2009), 2, 500-513. MR2492883DOI
  24. Ghami, M. El, Ivanov, I. D., Steihaug, T., , In: Proc. International multiconference on computer science and information technology, Mragowo 2009, pp. 743-749. DOI
  25. Ghami, M. El, Roos, C., , RAIRO Oper. Res. 42 (2008), 199-213. MR2431399DOI
  26. Ghami, M. El., Roos, C., Steihaug, T., , Optim. Methods Softw. 25 (2010), 387-403. MR2738833DOI
  27. Guerdouh, S., Chikouche, W., Kheirfam, B., , J. Appl. Math. Comput. 69 (2023), 2935-2953. MR4617120DOI
  28. Guerdouh, S., Chikouche, W., Touil, I., , Stat. Optim. Inf. Comput. 11 (2023), 773-784. MR4601347DOI
  29. Guerdouh, S., Chikouche, W., Touil, I., An efficient primal-dual interior-point algorithm for linear optimization problems based on a novel parameterized kernel function with a hyperbolic barrier term., 2021. halshs-03228790 MR4601347
  30. Hafshejani, S. F., Fatemi, M., Peyghami, M. R., , J. Appl. Math. Comput. 48 (2015), 111-128. MR3340598DOI
  31. Hafshejani, S. F., Jahromi, A. F., , J. Appl. Math. Comput. 62 (2020), 281-300. MR4056901DOI
  32. Karmarkar, N. K., A new polynomial-time algorithm for linear programming 
  33. Keraghel, A., Étude adaptative et comparative des principales variantes dans l'algorithme de karmarkar., Ph.D. Thesis, Grenoble Institute of Technology, 1989. 
  34. Kheirfam, B., , Numer. Algorithms 61 (2012), 659-680. MR2995226DOI
  35. Kheirfam, B., Haghighi, M., , Optimization 65 (2016), 4, 841-857. MR3459385DOI
  36. Kheirfam, B., Moslemi, M., , Yugosl. J. Oper. Res. 25 (2015), 2, 233-250. MR3366826DOI
  37. Lesaja, G., Roos, C., , SIAM J. Optim. 20 (2010), 6, 3014-3039. MR2735942DOI
  38. Li, X., Zhang, M. W., , Oper. Res. Lett. 43 (2015), 471-475. MR3394180DOI
  39. Peng, J., Roos, C., Terlaky, T., , European J. Oper. Res. 143 (2002), 234-256. MR1934033DOI
  40. Peng, J., Roos, C., Terlaky, T., , SIAM J. Optim. 13 (2002), 1, 179-203. MR1922760DOI
  41. Peng, J., Roos, C., Terlaky, T., Self-Regularity: A New Paradigm for Primal-Dual interior-point Algorithms., Princeton University Press, Princeton, New Jersey 2002. MR1938497
  42. Peyghami, M. R., , Asia-Pac. J. Oper. Res. 26 (2009), 3, 365-382. MR2552872DOI
  43. Peyghami, M. R., Amini, K., , Acta Math. Appl. Sin. Engl. Ser. 26 (2010), 1761-1778. MR2672816DOI
  44. Peyghami, M. R., Hafshejani, S. F., , Numer. Algorithms. 67 (2014), 33-48. MR3252835DOI
  45. Peyghami, M. R., Hafshejani, S. F., Chen, S., , Oper. Res. Lett. 44 (2016), 3, 319-323. MR3503107DOI
  46. Peyghami, M. R., Hafshejani, S. F., Shirvani, L., , J. Comput. Appl. Math. 255 (2014), 74-85. MR3093405DOI
  47. Roos, C., , SIAM J. Optim. 16 (2006), 4, 1110-1136. MR2219135DOI
  48. Roos, C., Terlaky, T., Vial, J. Ph., Theory and Algorithms for Linear Optimization., In: An Interior-point Approach, John Wiley and Sons, Chichester 1997. MR1450094
  49. Touil, I., Benterki, D., Yassine, A., , J. Comput. Appl. Math. 312 (2017), 216-230. MR3557876DOI
  50. Touil, I., Chikouche, W., , Acta Math. Appl. Sin. Engl. Ser. 38 (2022), 44-67. MR4375772DOI
  51. Touil, I., Chikouche, W., , Filomat. 34 (2020), 12, 3957-3969. MR4290825DOI
  52. Vieira, M. V. C., , Optim. Methods Softw. 27 (2012), 3, 513-537. MR2916858DOI
  53. Wang, G. Q., Bai, Y. Q., Liu, Y., Zhang, M., , J. Shanghai Univ. (English Edition), 12 (2008), 3, 189-196. MR2422971DOI
  54. Wang, G. Q., Li, M. M., Yue, Y. J., Cai, X. Z., New complexity analysis of interior-point methods for the Cartesian P * ( κ ) - SCLCP., J. Inequal. Appl. (2013) Article number 285. MR3081699
  55. Wang, G. Q., Zhu, D. T., , Numer. Algorithms 57 (2011), 4, 537-558. MR2819461DOI
  56. Wright, S. J., , SIAM, 1997. MR1422257DOI
  57. Ye, Y. Y., Interior-point algorithms. Theory and Analysis., Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, New York 1997. MR1481160

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.