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

Guerdouh, Safa ; Chikouche, Wided ; Touil, Imene ; Yassine, Adnan

Kybernetika, Tome 59 (2023) no. 6, pp. 827-860

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2023-6-0827

Classification : 90C05, 90C51
Keywords: linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods

Bibliographie

[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.: 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 | MR

[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. | MR

[4] Amini, K., Peyghami, M. R.: An interior-point method for linear programming based on a class of kernel functions. Bull. Austral. Math. Soc. 71 (2005), 139-153. | DOI | MR

[5] Amini, K., Peyghami, M. R.: 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 | MR

[6] Bai, Y.Q., Ghami, M. El, Roos, C.: A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization. SIAM J. Optim. 15 (2004), 101-128. | DOI | MR

[7] Bai, Y. Q., Ghami, M. El, Roos, C.: A new efficient large-update primal-dual interior-point method based on a finite barrier. SIAM J. Optim. 13 (2002), 766-782. | DOI | MR

[8] Bai, Y. Q., Wang, G. Q.: Polynomial interior-point algorithms for $P_*(\kappa)$ horizontal linear complementarity problem. J. Comput. Appl. Math. 233 (2009), 248-263. | DOI | MR

[9] Bai, Y. Q., Wang, G. Q., Roos, C.: Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Anal. 70 (2009), 10, 3584-3602. | DOI | MR

[10] Benhadid, A., Saoudi, K.: 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 | MR

[11] Bouafia, M., Benterki, D., Yassine, A.: An efficient parameterized logarithmic kernel function for linear optimization. Optim. Lett. 12 (2018), 1079-1097. | DOI | MR

[12] 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. J. Optim. Theory Appl. 170 (2016), 528-545. | DOI | MR

[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_*(\kappa)-$LCP over symmetric cones. Pac. J. Optim. 13 (2017), 4, 547-570. | MR

[14] Cai, X. Z., Wang, G. Q., Ghami, M. El, 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. (2014) Article ID 710158. | DOI | MR

[15] Cai, X. Z., Wang, G. Q., Zhang, Z. H.: 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 | MR

[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. | MR

[17] Choi, B. K., Lee, G. M.: 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 | MR

[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. | MR

[19] Derbal, L., Kebbiche, Z.: 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 | MR

[20] Ghami, M. El, Bai, Y. Q., Roos, C.: Kernel-function based algorithms for semidefinite optimization. RAIRO Oper. Res. 43 (2009), 189-199. | DOI | MR

[21] Ghami, M. El, 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 (2012), 3613-3623. | DOI | MR

[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. | MR

[23] Ghami, M.El., Ivanov, I. D., Melissen, J.B.M., Roos, C., Steihaug, T.: 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 | MR

[24] Ghami, M. El, Ivanov, I. D., Steihaug, T.: 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

[25] Ghami, M. El, Roos, C.: Generic primal-dual interior-point methods based on a new kernel function. RAIRO Oper. Res. 42 (2008), 199-213. | DOI | MR

[26] Ghami, M. El., Roos, C., Steihaug, T.: 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 | MR

[27] Guerdouh, S., Chikouche, W., Kheirfam, B.: 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 | MR

[28] Guerdouh, S., Chikouche, W., Touil, I.: 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 | MR

[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 | MR

[30] Hafshejani, S. F., Fatemi, M., Peyghami, M. R.: 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 | MR

[31] Hafshejani, S. F., Jahromi, A. F.: 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 | MR

[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.: 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 | MR

[35] Kheirfam, B., Haghighi, M.: A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function. Optimization 65 (2016), 4, 841-857. | DOI | MR

[36] Kheirfam, B., Moslemi, M.: 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 | MR

[37] Lesaja, G., Roos, C.: Unified analysis of kernel-based interior-point methods for $P_*(\kappa)-$linear complementarity problems. SIAM J. Optim. 20 (2010), 6, 3014-3039. | DOI | MR

[38] Li, X., Zhang, M. W.: Interior-point algorithm for linear optimization based on a new trigonometric kernel function. Oper. Res. Lett. 43 (2015), 471-475. | DOI | MR

[39] Peng, J., Roos, C., Terlaky, T.: A new class of polynomial primal-dual methods for linear and semidefinite optimization. European J. Oper. Res. 143 (2002), 234-256. | DOI | MR

[40] Peng, J., Roos, C., Terlaky, T.: Primal-dual interior-point methods for second order conic optimization based on self-regular proximities. SIAM J. Optim. 13 (2002), 1, 179-203. | DOI | MR

[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. | MR

[42] Peyghami, M. R.: An interior-point approach for semidefinite optimization using new proximity functions. Asia-Pac. J. Oper. Res. 26 (2009), 3, 365-382. | DOI | MR

[43] Peyghami, M. R., Amini, K.: 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 | MR

[44] 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 (2014), 33-48. | DOI | MR

[45] Peyghami, M. R., Hafshejani, S. F., Chen, S.: 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 | MR

[46] 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 (2014), 74-85. | DOI | MR

[47] Roos, C.: A full-Newton step $\mathcal{O}(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. | DOI | MR

[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. | MR

[49] Touil, I., Benterki, D., Yassine, A.: A feasible primal-dual interior-point method for linear semidefinite programming. J. Comput. Appl. Math. 312 (2017), 216-230. | DOI | MR

[50] Touil, I., Chikouche, W.: 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 | MR

[51] Touil, I., Chikouche, W.: Primal-dual interior-point methods for semidefinite programming based on a new type of kernel functions. Filomat. 34 (2020), 12, 3957-3969. | DOI | MR

[52] Vieira, M. V. C.: Interior-point methods based on kernel functions for symmetric optimization. Optim. Methods Softw. 27 (2012), 3, 513-537. | DOI | MR

[53] Wang, G. Q., Bai, Y. Q., Liu, Y., Zhang, M.: A new primal-dual interior-point algorithm for convex quadratic optimization. J. Shanghai Univ. (English Edition), 12 (2008), 3, 189-196. | DOI | MR

[54] Wang, G. Q., Li, M. M., Yue, Y. J., Cai, X. Z.: New complexity analysis of interior-point methods for the Cartesian $P_*(\kappa)-$SCLCP. J. Inequal. Appl. (2013) Article number 285. | MR

[55] Wang, G. Q., Zhu, D. T.: A unified kernel function approach to primal-dual interior-point algorithms for convex quadratic SDO. Numer. Algorithms 57 (2011), 4, 537-558. | DOI | MR

[56] Wright, S. J.: Primal-dual interior-point methods. SIAM, 1997. | DOI | MR

[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. | MR