Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods
linear programming; primal-dual interior-point methods; kernel function; complexity analysis; large and small-update methods
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.
References:
[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 2408519
[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
[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 2127673
[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 2489104
[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 2112978
[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 1972215
[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 2568523
[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 2502767
[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 4124288
[11] Bouafia, M., Benterki, D., Yassine, A.: An efficient parameterized logarithmic kernel function for linear optimization. Optim. Lett. 12 (2018), 1079-1097. DOI | MR 3819677
[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 3527709
[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
[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 3226224
[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 3011391
[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
[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 2672034
[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
[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 3941774
[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 2527862
[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 2923494
[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
[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 2492883
[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 2431399
[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 2738833
[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 4617120
[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 4601347
[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
[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 3340598
[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 4056901
[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 2995226
[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 3459385
[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 3366826
[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 2735942
[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 3394180
[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 1934033
[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 1922760
[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
[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 2552872
[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 2672816
[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 3252835
[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 3503107
[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 3093405
[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 2219135
[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
[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 3557876
[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 4375772
[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 4290825
[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 2916858
[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 2422971
[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
[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 2819461
[56] Wright, S. J.: Primal-dual interior-point methods. SIAM, 1997. DOI | MR 1422257
[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
Search
Partner of
