Kybernetika 59 no. 6, 827-860, 2023

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

Safa Guerdouh, Wided Chikouche, Imene Touil and Adnan YassineDOI: 10.14736/kyb-2023-6-0827

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.

Keywords:

linear programming, complexity analysis, primal-dual interior-point methods, kernel function, large and small-update methods

Classification:

90C05, 90C51

paper.pdf

References:

  1. N. Anane: Méthodes de points intérieurs pour la programmation linéaire basées sur les fonctions noyaux. (Magister Thesis), Ferhat Abbas University, Setif 2012.   CrossRef
  2. K. Amini and K. A. Haseli: A new proximity function generating the best known iteration bounds for both large-update methods and small-update. ANZIAM J. 49 (2007), 259-270.   DOI:10.1017/S1446181100012827
  3. K. Amini and M. R. Peyghami: An interior-point algorithm for linear optimization based on a new kernel function. Southeast Asian Bull. Math. 29 (2005), 651-667.   CrossRef
  4. K. Amini and M. R. Peyghami: An interior-point method for linear programming based on a class of kernel functions. Bull. Austral. Math. Soc. 71 (2005), 139-153.   DOI:10.1017/S0004972700038090
  5. K. Amini and M. R. Peyghami: Exploring complexity of large update interior-point methods for $P_*(\kappa)-$ linear complementarity problem based on kernel function. Appl. Math. Comput. 207(2) (2009), 501-513.   DOI:10.1016/j.amc.2008.11.002
  6. Y.Q. Bai, M. El Ghami and C. Roos: 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
  7. Y. Q. Bai, M. El Ghami and C. Roos: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13 (2002), 766-782.   DOI:10.1137/S1052623401398132
  8. Y. Q. Bai and G. Q. Wang: Polynomial interior-point algorithms for $P_*(\kappa)$ horizontal linear complementarity problem. J. Comput. Appl. Math. 233 (2009), 248-263.   DOI:10.1016/j.cam.2009.07.014
  9. Y. Q. Bai, G. Q. Wang and C. Roos: Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Anal. 70 (2009), 10, 3584-3602.   DOI:10.1016/j.na.2008.07.016
  10. A. Benhadid and K. Saoudi: A new parameterized logarithmic kernel function for linear optimization with a double barrier term yielding the best known iteration bound. Commun. Math. 28 (2020), 27-41.   DOI:10.2478/cm-2020-0003
  11. M. Bouafia, D. Benterki and A. Yassine: An efficient parameterized logarithmic kernel function for linear optimization. Optim. Lett. 12 (2018), 1079-1097.   DOI:10.1007/s11590-017-1170-5
  12. M. Bouafia, D. Benterki and A. Yassine: An efficient primal-dual interior-point method for linear programming problems based on a new kernel function with a trigonometric barrier term. J. Optim. Theory Appl. 170 (2016), 528-545.   DOI:10.1007/s10957-016-0895-0
  13. X. Z. Cai, L. Li, M. El Ghami, T. Steihaug and G. Q. Wang: A new parametric kernel function yielding the best known iteration bounds of interior-point methods for the Cartesian $P_*(\kappa)-$LCP over symmetric cones. Pac. J. Optim. 13 (2017), 4, 547-570.   CrossRef
  14. X. Z. Cai, G. Q. Wang, M. El Ghami and Y. J. Yue: 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. (2014) Article ID 710158.   DOI:10.1155/2014/710158
  15. X. Z. Cai, G. Q. Wang and Z. H. Zhang: Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier. Numer. Algorithms 62 (2013), 289-306.   DOI:10.1007/s11075-012-9581-y
  16. X. Z. Cai, L. Wu, Y. J. Yue, M. M. L and G. Q. Wang: Kernel-function based primal dual interior- point methods for convex quadratic optimization over symmetric cone. J. Inequal. Appl. (2014), 308, 22 pp.} \enlargethispage{5mm   CrossRef
  17. B. K. Choi and G. M. Lee: On complexity analysis of the primal-dual interior-point method for semidefinite optimization problem based on a new proximity function. Nonlinear Anal. 71 (2009), 2628-2640.   DOI:10.1016/j.na.2009.05.078
  18. B. K Choi and G. M. Lee: 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.   CrossRef
  19. L. Derbal and Z. Kebbiche: Theoretical and numerical result for linear optimization problem based on a new kernel function. J. Sib. Fed. Univ. Math. Phys. 12 (2019), 2, 160-172.   DOI:10.17516/1997-1397-2019-12-2-160-172
  20. M. El Ghami, Y. Q. Bai and C. Roos: Kernel-function based algorithms for semidefinite optimization. RAIRO Oper. Res. 43 (2009), 189-199.   DOI:10.1051/ro/2009011
  21. M. El Ghami, Z. A. Guennoun, S. Bouali and T. Steihaug: Interior-point methods for linear optimization based on a kernel function with a trigonometric barrier term. J. Comput. Appl. Math. 236 (2012), 3613-3623.   DOI:10.1016/j.cam.2011.05.036
  22. M. El Ghami, I. D. Ivanov, C. Roos and T. Steihaug: A polynomial-time algorithm for LO based on generalized logarithmic barrier functions. Int. J. Appl. Math. 21 (2008), 99-115.   CrossRef
  23. M.El. Ghami, I. D. Ivanov, J.B.M. Melissen, C. Roos and T. Steihaug: A polynomial-time algorithm for linear optimization based on a new class of kernel functions. J. Comput. Appl. Math. 224 (2009), 2, 500-513.   DOI:10.1016/j.cam.2008.05.027
  24. M. El Ghami, I. D. Ivanov and T. Steihaug: Primal-dual interior-point methods solver based on kernel functions for linear optimization. In: Proc. International multiconference on computer science and information technology, Mragowo 2009, pp. 743-749.   DOI:10.1109/IMCSIT.2009.5352756
  25. M. El Ghami and C. Roos: Generic primal-dual interior-point methods based on a new kernel function. RAIRO Oper. Res. 42 (2008), 199-213.   DOI:10.1051/ro:2008009
  26. M. El. Ghami, C. Roos and T. Steihaug: A generic primal-dual interior-point method for semidefinite optimization based on a new class of kernel functions. Optim. Methods Softw. 25 (2010), 387-403.   DOI:10.1080/10556780903239048
  27. S. Guerdouh, W. Chikouche and B. Kheirfam: A full-Newton step infeasible interior-point algorithm based on a kernel function with a new barrier term. J. Appl. Math. Comput. 69 (2023), 2935-2953.   DOI:10.1007/s12190-023-01858-8
  28. S. Guerdouh, W. Chikouche and I. Touil: A primal-dual interior-point algorithm based on a kernel function with a new barrier term. Stat. Optim. Inf. Comput. 11 (2023), 773-784.   DOI:10.19139/soic-2310-5070-1381
  29. S. Guerdouh, W. Chikouche and I. Touil: 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   CrossRef
  30. S. F. Hafshejani, M. Fatemi and M. R. Peyghami: An interior-point method for $P_*(\kappa)-$linear complementarity problem based on a trigonometric kernel function. J. Appl. Math. Comput. 48 (2015), 111-128.   DOI:10.1007/s12190-014-0794-1
  31. S. F. Hafshejani and A. F. Jahromi: An interior-point method for $P_*(\kappa)-$horizontal linear complementarity problem based on a new proximity function. J. Appl. Math. Comput. 62 (2020), 281-300.   DOI:10.1007/s12190-019-01284-9
  32. N. K. Karmarkar: A new polynomial-time algorithm for linear programming    CrossRef
  33. A. Keraghel: Étude adaptative et comparative des principales variantes dans l'algorithme de karmarkar. Ph.D. Thesis, Grenoble Institute of Technology, 1989.   CrossRef
  34. B. Kheirfam: Primal-dual interior-point algorithm for semidefinite optimization based on a new kernel function with trigonometric barrier term. Numer. Algorithms 61 (2012), 659-680.   DOI:10.1007/s11075-012-9557-y
  35. B. Kheirfam and M. Haghighi: A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function. Optimization 65 (2016), 4, 841-857.   DOI:10.1080/02331934.2015.1080255
  36. B. Kheirfam and M. Moslemi: A polynomial-time algorithm for linear optimization based on a new kernel function with trigonometric barrier term. Yugosl. J. Oper. Res. 25 (2015), 2, 233-250.   DOI:10.2298/YJOR120904006K
  37. G. Lesaja and C. Roos: Unified analysis of kernel-based interior-point methods for $P_*(\kappa)-$linear complementarity problems. SIAM J. Optim. 20 (2010), 6, 3014-3039.   DOI:10.1137/090766735
  38. X. Li and M. W. Zhang: Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper. Res. Lett. 43 (2015), 471-475.   DOI:10.1016/j.orl.2015.06.013
  39. J. Peng, C. Roos and T. Terlaky: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European J. Oper. Res. 143 (2002), 234-256.   DOI:10.1016/S0377-2217(02)00275-8
  40. J. Peng, C. Roos and T. Terlaky: Primal-dual interior-point methods for second order conic optimization based on self-regular proximities. SIAM J. Optim. 13 (2002), 1, 179-203.   DOI:10.1137/S1052623401383236
  41. J. Peng, C. Roos and T. Terlaky: Self-Regularity: A New Paradigm for Primal-Dual interior-point Algorithms. Princeton University Press, Princeton, New Jersey 2002.   CrossRef
  42. M. R. Peyghami: An interior-point approach for semidefinite optimization using new proximity functions. Asia-Pac. J. Oper. Res. 26 (2009), 3, 365-382.   DOI:10.1142/S0217595909002250
  43. M. R. Peyghami and K. Amini: A kernel function based interior-point methods for solving $P_*(\kappa)-$linear complementarity problem. Acta Math. Appl. Sin. Engl. Ser. 26 (2010), 1761-1778.   DOI:10.1007/s10114-010-7529-5
  44. M. R. Peyghami and S. F. Hafshejani: Complexity analysis of an interior-point algorithm for linear optimization based on a new proximity function. Numer. Algorithms. 67 (2014), 33-48.   DOI:10.1007/s11075-013-9772-1
  45. M. R. Peyghami, S. F. Hafshejani and S. Chen: A primal-dual interior-point method for semidefinite optimization based on a class of trigonometric barrier functions. Oper. Res. Lett. 44 (2016), 3, 319-323.   DOI:10.1016/j.orl.2016.02.013
  46. M. R. Peyghami, S. F. Hafshejani and L. Shirvani: Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function. J. Comput. Appl. Math. 255 (2014), 74-85.   DOI:10.1016/j.cam.2013.04.039
  47. C. Roos: A full-Newton step $\mathcal{O}(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136.   DOI:10.1137/050623917
  48. C. Roos, T. Terlaky and J. Ph. Vial: Theory and Algorithms for Linear Optimization. In: An Interior-point Approach, John Wiley and Sons, Chichester 1997.   CrossRef
  49. I. Touil, D. Benterki and A. Yassine: A feasible primal-dual interior-point method for linear semidefinite programming. J. Comput. Appl. Math. 312 (2017), 216-230.   DOI:10.1016/j.cam.2016.05.008
  50. I. Touil and W. Chikouche: Novel kernel function with a hyperbolic barrier term to primal-dual interior-point algorithm for SDP problems. Acta Math. Appl. Sin. Engl. Ser. 38 (2022), 44-67.   DOI:10.1007/s10255-022-1061-0
  51. I. Touil and W. Chikouche: Primal-dual interior-point methods for semidefinite programming based on a new type of kernel functions. Filomat. 34 (2020), 12, 3957-3969.   DOI:10.2298/FIL2012957T
  52. M. V. C. Vieira: Interior-point methods based on kernel functions for symmetric optimization. Optim. Methods Softw. 27 (2012), 3, 513-537.   DOI:10.1007/s10852-005-3561-310.1007/s10852-005-3561-3
  53. G. Q. Wang, Y. Q. Bai, Y. Liu and M. Zhang: A new primal-dual interior-point algorithm for convex quadratic optimization. J. Shanghai Univ. (English Edition), 12 (2008), 3, 189-196.   DOI:10.1007/s11741-008-0301-3
  54. G. Q. Wang, M. M. Li, Y. J. Yue and X. Z. Cai: New complexity analysis of interior-point methods for the Cartesian $P_*(\kappa)-$SCLCP. J. Inequal. Appl. (2013) Article number 285.   CrossRef
  55. G. Q. Wang and D. T. Zhu: A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO. Numer. Algorithms 57 (2011), 4, 537-558.   DOI:10.1080/10556788.2010.544877
  56. S. J. Wright: Primal-dual interior-point methods. SIAM, 1997.   DOI:10.1137/1.9781611971453
  57. Y. Y. Ye: Interior-point algorithms. Theory and Analysis. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley and Sons, New York 1997.   CrossRef