Article Contents
Article Contents

# Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term

• Kernel functions play an important role in the complexity analysis of the interior point methods (IPMs) for linear optimization (LO). In this paper, an interior-point algorithm for LO based on a new parametric kernel function is proposed. By means of some simple analysis tools, we prove that the primal-dual interior-point algorithm for solving LO problems meets $O\left(\sqrt{n} \log(n) \log(\frac{n}{\varepsilon}) \right)$, iteration complexity bound for large-update methods with the special choice of its parameters.

Mathematics Subject Classification: Primary: 90C05, 90C51; Secondary: 90C31.

 Citation:

• Figure 1.  Generic algorithm

Table 4.  Comparison for $p = 3, n = 6$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 15079 116 [12] 0.98 929 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 36917 116 [7] 0.98 2432 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 11550 116 [17] 0.98 476 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 9053 116 [19] 0.98 553 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 3475 116 0.98 64 5

Table 5.  Comparison for $p = 5, n = 10$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 21696 121 [12] 0.98 1423 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 37948 121 [7] 0.98 2137 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 16713 121 [17] 0.98 606 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 12242 121 [19] 0.98 651 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 5754 121 0.98 104 5

Table 6.  Comparison for $p = 10, n = 20$

 Kernel functions Large update Small update $\theta$ Inner It. Outer It. Reference $\frac{1}{2}(t^{2}-1)-\log(t)$ ${\bf{O}}\left(n \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 38278 128 [12] 0.98 2613 5 $\frac{t^{2}-1-\log(t)}{2}+\frac{t^{1-q}-1}{2(q-1)}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 51198 128 [7] 0.98 2307 5 $\frac{1}{2}(t-\frac{1}{t})^{2}$ ${\bf{O}}\left(n^{\frac{2}{3}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 25553 128 [17] 0.98 857 5 $\frac{1}{2}(t^{2}-1)+\frac{t^{1-q}-1}{q-1}$ ${\bf{O}}\left(qn^{\frac{q+1}{2q}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(q^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 21549 128 [19] 0.98 897 5 $\psi_{m}(t)$ ${\bf{O}}\left(mn^{\frac{2m+1}{4m}} \log\left( \frac{n}{\epsilon} \right)\right)$ ${\bf{O}}\left(m^{2}\sqrt{n}\log\left( \frac{n}{\epsilon} \right) \right)$ 0.10 13054 128 0.98 269 5
•  [1] 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. [2] Y. Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, Proceedings of the 9th Australian Optimization Day, 2002. [3] Y. Q. Bai, G. Lesaja, C. Roos, G. Q. Wang and M. Ghami, A class of large- and small-update primal-dual interior-point algorithm for linear optimization, Journal of Optimization Theory and Application, 138 (2008), 341-359.  doi: 10.1007/s10957-008-9389-z. [4] Y. Q. Bai, G. Q. Wang and C. Roos, Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions, Nonlinear Analysis: Theory, Methods and Applications, 70 (2009), 3584-3602.  doi: 10.1016/j.na.2008.07.016. [5] 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, Communications in Mathematics, 28 (2020), 27-41.  doi: 10.2478/cm-2020-0003. [6] A. Benhadid, K. Saoudi and F. Merahi, An interior point approach for linear complementarity problem using new parametrized kernel function, Optimization, 2021. doi: 10.1080/02331934.2021.1945051. [7] M. Bouaafia, D. Benterki and Y. Adnan, An efficient parameterized logarithmic kernel function for linear optimization, Optim. Lett., 12 (2018), 1079-1097.  doi: 10.1007/s11590-017-1170-5. [8] M. Bouaafia, D. Benterki and Y. Adnan, 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. [9] 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, Abstract and Applied Analysis, 11 (2014), Artical ID 710158. doi: 10.1155/2014/710158. [10] 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, Pacific Journal of Optimization, 13 (2017), 547-570. [11] 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. [12] 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. [13] M. El Ghami, G. Q. Wang and T. Steihaug, Primal-dual algorithms for semidefinite optimization problems based on kernel-function with trigonometric barrier term, International Journal of Applied Mathematics, 32 (2019), 333-356. [14] N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 4 (1984), 373-395.  doi: 10.1007/BF02579150. [15] L. Li, J. Y. Tao, M. El Ghami, X. Z. Cai and G. Q. Wang, A new parametric kernel function with a trigonometric barrier term for $P_{*}(\kappa)$-linear complementarity problems, Pacific Journal of Optimization, 13 (2017), 255-278. [16] N. Megiddo, Pathways to the optimal set in linear programming, Progress in Mathematical Programming: Interior Point and Related Methods, Springer, New York, (1989), 131–158. [17] J. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, European Journal of Operational Research, 143 (2002), 234-256.  doi: 10.1016/S0377-2217(02)00275-8. [18] J. Peng,  C. Roos and  T. Terlaky,  Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Princeton University Press, Princeton, 2002. [19] J. Peng, C. Roos and T. Terlaky, A new and efficient large-update interior point method for linear optimization, J. Comput. Technol., 6 (2001), 61-80. [20] J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Mathematical Programming, 93 (2002), 129-171.  doi: 10.1007/s101070200296. [21] 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. [22] 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. [23] C. Roos, T. Terlaky and J. P. Vial, Theory and Algorithms for Linear Optimization, An Interior Point Approach, Wiley, Chichester, 1997. [24] F. H. Sajad, F. J. Alireza, R. P. Mohammad and C. Shengyuan, Complexity of interior point methods for a class of linear complementarity problems using a kernel function with trigonometric growth term, J. Optim. Theory Appl., 178 (2018), 935-949.  doi: 10.1007/s10957-018-1344-z. [25] G. Sonnevend, An "analytic center" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, In System Modelling and Optimization (eds. A. Prekopa, J. Szelezsan and B. Strazicky), Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985. Lecture Notes in Control and Information Science, 84, Springer, Berlin 1986. doi: 10.1007/BFb0043914. [26] M. V. C. Vieira, Jordan algebraic approach to symmetric optimization, Ph.D thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, The Netherlands, 2007. [27] G. Q. Wang, Y. Q. Bai and C. Roos, Primal-dual interior-point algorithms for semidefinite optimization based on a simple kernel function, J. Math. Model. Algorithms, 4 (2005), 409-433.  doi: 10.1007/s10852-005-3561-3. [28] 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., 12 (2008), 189-196.  doi: 10.1007/s11741-008-0301-3. [29] Y. Ye, Interior Point Algorithms, Theory and Analysis, Wiley, Chichester, 1997. doi: 10.1002/9781118032701.

Figures(1)

Tables(3)