\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions

Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by
  • In an attempt to improve theoretical complexity of large-update methods, in this paper, we propose a primal-dual interior-point method for $ P_{\ast}\left( \kappa \right) $-horizontal linear complementarity problem. The method is based on a class of parametric kernel functions. We show that the corresponding algorithm has $ O\left( \left( 1+2\kappa \right) p^{2}n^{\frac{2+p}{2\left( 1+p\right) }}\log \frac{n}{\epsilon }\right) $ iteration complexity for large-update methods and we match the best known iteration bounds with special choice of the parameter $ p $ for $ P_{\ast }\left(\kappa \right) $-horizontal linear complementarity problem that is $ O\left(\left( 1+2\kappa \right) \sqrt{n}\log n\log \frac{n}{\epsilon }\right) $. We illustrate the performance of the proposed kernel function by some comparative numerical results that are derived by applying our algorithm on five kernel functions.

    Mathematics Subject Classification: Primary: 90C33; Secondary: 90C51.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Some kernel functions

    ${\psi _1}(t) = p\left( {\frac{{{t^2} - 1}}{2}} \right) + \frac{4}{\pi }\left( {{{\tan }^p}\left( {\frac{\pi }{{2t + 2}}} \right) - 1} \right),t > 0,p \ge \sqrt 2 ,$
    $\alpha_{1}=\frac{1}{(1+2 \kappa)\left(9 p+4 \pi p^{2}\right)\left(\frac{8}{p}+2\right)^{\frac{p+2}{p+1}}}.$
    $\psi_{2}(t)=\frac{t^{2}-1}{2}-\log t+\frac{1}{8} \tan ^{2}\left(\frac{\pi(1-t)}{2+4 t}\right), t>0,[25]$
    $\alpha_{2}=\frac{1}{(1+2 \kappa) 5020 \delta^{\frac{4}{3}}}.$
    $\psi_{3}(t)=t-1+\frac{t^{1-q}-1}{q-1}, t>0, q \geq 2,[8]$
    $\alpha_{3}=\frac{1}{(1+2 \kappa) q(2 \delta+1)^{\frac{1}{q}}(4 \delta+1)}.$
    $\psi_{4}(t)=\frac{t^{2}-1}{2}+\frac{q^{\frac{1}{t}-1}}{q \log q}-\frac{q-1}{q}(t-1), q>1,[2]$
    $\alpha_{4}=\frac{1}{(1+2 \kappa)(\log q+2)(1+4 \delta)\left(2+\frac{\log (1+4 \delta)}{\log q}\right)}.$
    $\psi_{5}(t)=\frac{t^{2}-1}{2}+\frac{4}{p \pi}\left(\tan ^{p}\left(\frac{\pi}{2 t+2}\right)-1\right), t>0, p \geq 2,[9]$
    $\alpha_{5}=\frac{1}{(1+2 \kappa)(9+4 p \pi)(8 \delta+2)^{\frac{p+2}{p+1}}}.$
     | Show Table
    DownLoad: CSV

    Table 2.   

    $ \psi _{1}\left( t\right) $ $ \psi _{2}\left( t\right) $ $ \psi _{3}\left( t\right) $ $ \psi _{4}\left( t\right) $ $ \psi _{5}\left( t\right) $
    Inn $ 5 $ $ 282 $ $ 10 $ $ 16 $ $ 5 $
    Time $ 0.07 $ $ 0.18 $ $ 0.062 $ $ 0.06 $ $ 0.06 $
     | Show Table
    DownLoad: CSV

    Table 3.   

    $ \psi _{1}\left( t\right) $ $ \psi _{2}\left( t\right) $ $ \psi _{3}\left( t\right) $ $ \psi _{4}\left( t\right) $ $ \psi _{5}\left( t\right) $
    Inn $ 7 $ $ 167 $ $ 12 $ $ 19 $ $ 10 $
    Time $ 0.06 $ $ 0.10 $ $ 0.06 $ $ 0.063 $ $ 0.07 $
     | Show Table
    DownLoad: CSV

    Table 4.   

    $ n=3 $ $ n=100 $ $ n=150 $
    Inn Time Inn Time Inn Time
    $ \psi _{1}\left( t\right) $ $ 4 $ $ 0.06 $ $ 12 $ $ 0.45 $ $ 18 $ $ 3.06 $
    $ \psi _{2}\left( t\right) $ $ 179 $ $ 0.11 $ $ 70 $ $ 9.07 $ $ 1447 $ $ 11.6 $
    $ \psi _{3}\left( t\right) $ $ 15 $ $ 0.06 $ $ 52 $ $ 0.19 $ $ 77 $ $ 0.91 $
    $ \psi _{4}\left( t\right) $ $ 14 $ $ 0.063 $ $ - $ $ - $ $ - $ $ - $
    $ \psi _{5}\left( t\right) $ $ 8 $ $ 0.068 $ $ 23 $ $ 0.63 $ $ 28 $ $ 2.30 $
     | Show Table
    DownLoad: CSV

    Table 5.   

    $ n=3 $ $ n=50 $ $ n=150 $
    Inn Time Inn Time Inn Time
    $ \psi _{1}\left( t\right) $ $ 3 $ $ 0.07 $ $ 10 $ $ 0.12 $ $ 19 $ $ 1.73 $
    $ \psi _{2}\left( t\right) $ $ 259 $ $ 0.15 $ $ 615 $ $ 0.67 $ $ 1301 $ $ 13.96 $
    $ \psi _{3}\left( t\right) $ $ 16 $ $ 0.05 $ $ 215 $ $ 0.45 $ $ 71 $ $ 0.64 $
    $ \psi _{4}\left( t\right) $ $ 18 $ $ 0.05 $ $ - $ $ - $ $ - $ $ - $
    $ \psi _{5}\left( t\right) $ $ 12 $ $ 0.07 $ $ 18 $ $ 0.15 $ $ 39 $ $ 2.47 $
     | Show Table
    DownLoad: CSV
  • [1] M. Achache, Complexity analysis of a weighted-full-Newton step interior-point algorithm for $P_{\ast }\left(\kappa \right)$-LCP, RAIRO-Oper. Res., 50 (2016), 131-143.  doi: 10.1051/ro/2015020.
    [2] M. Achache and N. Tabchouche, Complexity analysis and numerical implementation of large-update interior-point methods for SDLCP based on a new parametric barrier kernel function, Optimization, 67 (2018), 1211-1230.  doi: 10.1080/02331934.2018.1462356.
    [3] S. Asadi and H. Mansouri, Polynomial interior-point algorithm for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, Numer. Algorithms, 63 (2013), 385-398.  doi: 10.1007/s11075-012-9628-0.
    [4] S. AsadiH. Mansouri and M. Zangiabadi, A class of path-following interior-point methods for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems, J. Oper Res Soc China, 3 (2015), 17-30.  doi: 10.1007/s40305-015-0070-6.
    [5] S. AsadiM. Zangiabadi and H. Mansouri, An infeasible interior-point algorithm with full-Newton steps for $P_{\ast }\left(\kappa \right)$-horizontal linear complementarity problems based on a kernel function, J. Appl. Math. Comput., 50 (2016), 15-37.  doi: 10.1007/s12190-014-0856-4.
    [6] Y. Q. BaiM. El Ghami and C. Roos, A new efficient large-update primal-dual interior-point method based on a finite barrier, SIAM J. Optim., 13 (2003), 766-782.  doi: 10.1137/S1052623401398132.
    [7] Y. Q. BaiM. 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.
    [8] 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.
    [9] M. BouafiaD. 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.
    [10] Ch. Chennouf, Extension d'une Méthode de Point Intérieur au Problème Complémentaire Linéaire avec $P_{\ast }\left(\kappa \right)-$matrice, Mémoire de Master $2, $ Université Ferhat Abbas Sétif1, Algérie, 2018.
    [11] G. M. Cho and M. K. Kim, A new large-update interior point algorithm for $P_{\ast}\left(\kappa \right)$ LCPs based on kernel functions, Appl. Math. Comput., 182 (2006), 1169-1183.  doi: 10.1016/j.amc.2006.04.060.
    [12] G. M. Cho, A new large–update interior point algorithm for $P_{\ast}\left(\kappa \right)$ linear complementarity problems, J. Comput. Appl. Math., 216 (2008), 256-278.  doi: 10.1016/j.cam.2007.05.007.
    [13] G. M. Cho, Large–update interior point algorithm for $P_{\ast }$-linear complementarity problem, J. Inequalities Appl., 363 (2014), 1-12.  doi: 10.1186/1029-242X-2014-363.
    [14] R. W. CottleJ. S. Pang and  R. E. StoneThe Linear Complementarity Problem, Academic Press, San Diego, 1992. 
    [15] M. El Ghami and T. Steihaug, Kernel–function based primal-dual algorithms for $P_{\ast }\left(\kappa \right) $ linear comlementarity problem, RAIRO-Oper. Res., 44 (2010), 185-205.  doi: 10.1051/ro/2010014.
    [16] M. El Ghami and G. Q. Wang, Interior–point methods for $P_{\ast}\left(\kappa \right) $ linear comlementarity problem based on generalized trigonometric barrier function, International Journal of Applied Mathematics, (2017), 11–33. doi: 10.12732/ijam.v30i1.2.
    [17] S. Fathi-Hafshejani and A. Fakharzadeh Jahromi, An interior point method for $P_{\ast}\left(\kappa \right) $-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.
    [18] S. Fathi-HafshejaniH. Mansouri and M. Peyghamic, An interior-point algorithm for $P_{\ast }\left(\kappa \right) $-linear complementarity problem based on a new trigonometric kernel functions, Journal of Mathematical Modeling, 5 (2017), 171-197. 
    [19] P. JiM. Zhang and X. Li, A Primal-dual large-update interior-point algorithm for $P_{\ast}(\kappa)$-LCP based on a new class of kernel functions, Acta Mathematicae Applicatae Sinica, English Series, 34 (2018), 119-134.  doi: 10.1007/s10255-018-0729-y.
    [20] M. KojimaN. MegiddoT. Noma and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems: A summary, Operations Research Letters, 10 (1991), 247-254.  doi: 10.1016/0167-6377(91)90010-M.
    [21] Y. Lee, Y. Cho and G. Cho, Kernel function based interior-point methods for horizontal linear complementarity problems, Journal of Inequalities and Applications, (2013), Article number: 215. doi: 10.1186/1029-242X-2013-215.
    [22] G. Lesaja and C. Roos, Unified analysis of kernel–based interior–point methods for $P_{\ast } (\kappa) $-LCP, SIAM Journal on Optimization, 20 (2010), 3014-3039.  doi: 10.1137/090766735.
    [23] J. PengC. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, Math. Program., Ser., 93 (2002), 129-171.  doi: 10.1007/s101070200296.
    [24] Z. G. Qian and Y. Q. Bai, Primal-dual interior point algorithm with dynamic step-size based on kernel function for linear programming, Journal of Shanghai University (English Edition), 9 (2005), 391-396.  doi: 10.1007/s11741-005-0021-2.
    [25] M. Reza PeyghamiS. Fathi Hafshejani and L. Shirvani, Complexity of interior-point methods for linear optimization based on a new trigonometric kernel function, Journal of Computational and Applied Mathematics, 2 (2014), 74-85.  doi: 10.1016/j.cam.2013.04.039.
    [26] C. Roos, T. Terlaky and J. Ph. Vial, Theory and Algorithms for Linear optimization. An Interior Point Approach, John Wiley and Sons, Chichester, 1997.
    [27] G. Q. Wang and Y. Q. Bai, Polynomial interior-point algorithm for $P_{\ast}\left(\kappa \right)$ horizontal linear complementarity problem, J. Comput. Appl. Math., 233 (2009), 248-263.  doi: 10.1016/j.cam.2009.07.014.
    [28] S. J. Wright, Primal-Dual Interior Point Methods, SIAM, 1997. doi: 10.1137/1.9781611971453.
  • 加载中

Tables(5)

SHARE

Article Metrics

HTML views(2063) PDF downloads(281) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return