| Title:
|
Complexity of primal-dual interior-point algorithm for linear programming based on a new class of kernel functions (English) |
| Author:
|
Guerdouh, Safa |
| Author:
|
Chikouche, Wided |
| Author:
|
Touil, Imene |
| Author:
|
Yassine, Adnan |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
59 |
| Issue:
|
6 |
| Year:
|
2023 |
| Pages:
|
827-860 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
linear programming |
| Keyword:
|
primal-dual interior-point methods |
| Keyword:
|
kernel function |
| Keyword:
|
complexity analysis |
| Keyword:
|
large and small-update methods |
| MSC:
|
90C05 |
| MSC:
|
90C51 |
| DOI:
|
10.14736/kyb-2023-6-0827 |
| . |
| Date available:
|
2024-02-26T11:09:50Z |
| Last updated:
|
2024-02-26 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/152260 |
| . |
| Reference:
|
[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. |
| Reference:
|
[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. MR 2408519, |
| Reference:
|
[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 2188017 |
| Reference:
|
[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. MR 2127673, |
| Reference:
|
[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. MR 2489104, |
| Reference:
|
[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. MR 2112978, |
| Reference:
|
[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. MR 1972215, |
| Reference:
|
[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. MR 2568523, |
| Reference:
|
[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. MR 2502767, |
| Reference:
|
[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. MR 4124288, |
| Reference:
|
[11] Bouafia, M., Benterki, D., Yassine, A.: An efficient parameterized logarithmic kernel function for linear optimization..Optim. Lett. 12 (2018), 1079-1097. MR 3819677, |
| Reference:
|
[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. MR 3527709, |
| Reference:
|
[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 3743080 |
| Reference:
|
[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. MR 3226224, |
| Reference:
|
[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. MR 3011391, |
| Reference:
|
[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 3359089 |
| Reference:
|
[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. MR 2672034, |
| Reference:
|
[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 2719195 |
| Reference:
|
[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. MR 3941774, |
| Reference:
|
[20] Ghami, M. El, Bai, Y. Q., Roos, C.: Kernel-function based algorithms for semidefinite optimization..RAIRO Oper. Res. 43 (2009), 189-199. MR 2527862, |
| Reference:
|
[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. MR 2923494, |
| Reference:
|
[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 2408056 |
| Reference:
|
[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. MR 2492883, |
| Reference:
|
[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. |
| Reference:
|
[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. MR 2431399, |
| Reference:
|
[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. MR 2738833, |
| Reference:
|
[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. MR 4617120, |
| Reference:
|
[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. MR 4601347, |
| Reference:
|
[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 4601347 |
| Reference:
|
[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. MR 3340598, |
| Reference:
|
[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. MR 4056901, |
| Reference:
|
[32] Karmarkar, N. K.: A new polynomial-time algorithm for linear programming. |
| Reference:
|
[33] Keraghel, A.: Étude adaptative et comparative des principales variantes dans l'algorithme de karmarkar..Ph.D. Thesis, Grenoble Institute of Technology, 1989. |
| Reference:
|
[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. MR 2995226, |
| Reference:
|
[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. MR 3459385, |
| Reference:
|
[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. MR 3366826, |
| Reference:
|
[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. MR 2735942, |
| Reference:
|
[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. MR 3394180, |
| Reference:
|
[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. MR 1934033, |
| Reference:
|
[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. MR 1922760, |
| Reference:
|
[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 1938497 |
| Reference:
|
[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. MR 2552872, |
| Reference:
|
[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. MR 2672816, |
| Reference:
|
[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. MR 3252835, |
| Reference:
|
[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. MR 3503107, |
| Reference:
|
[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. MR 3093405, |
| Reference:
|
[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. MR 2219135, |
| Reference:
|
[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 1450094 |
| Reference:
|
[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. MR 3557876, |
| Reference:
|
[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. MR 4375772, |
| Reference:
|
[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. MR 4290825, |
| Reference:
|
[52] Vieira, M. V. C.: Interior-point methods based on kernel functions for symmetric optimization..Optim. Methods Softw. 27 (2012), 3, 513-537. MR 2916858, |
| Reference:
|
[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. MR 2422971, |
| Reference:
|
[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 3081699 |
| Reference:
|
[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. MR 2819461, |
| Reference:
|
[56] Wright, S. J.: Primal-dual interior-point methods..SIAM, 1997. MR 1422257, |
| Reference:
|
[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 1481160 |
| . |
