• Previous Article
    A new methodology for solving bi-criterion fractional stochastic programming
  • NACO Home
  • This Issue
  • Next Article
    Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable
December  2021, 11(4): 513-531. doi: 10.3934/naco.2020053

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

Laboratoire de Mathématiques Fondamentales et Numériques, Université Ferhat Abbas Sétif1. Sétif. Algérie

Received  June 2020 Revised  October 2020 Published  December 2021 Early access  November 2020

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.

Citation: Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
References:
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] R. W. CottleJ. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

S. J. Wright, Primal-Dual Interior Point Methods, SIAM, 1997. doi: 10.1137/1.9781611971453.  Google Scholar

show all references

References:
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] R. W. CottleJ. S. Pang and R. E. Stone, The Linear Complementarity Problem, Academic Press, San Diego, 1992.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28]

S. J. Wright, Primal-Dual Interior Point Methods, SIAM, 1997. doi: 10.1137/1.9781611971453.  Google Scholar

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}}}.$
${\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}}}.$
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 $
$ \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 $
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 $
$ \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 $
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 $
$ 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 $
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 $
$ 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 $
[1]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[2]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[3]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082

[4]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601

[5]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[6]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[7]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011

[8]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103

[9]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[10]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[11]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[12]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[13]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259

[14]

Li-Xia Liu, Sanyang Liu, Chun-Feng Wang. Smoothing Newton methods for symmetric cone linear complementarity problem with the Cartesian $P$/$P_0$-property. Journal of Industrial & Management Optimization, 2011, 7 (1) : 53-66. doi: 10.3934/jimo.2011.7.53

[15]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[16]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[17]

Kyoungsun Kim, Gen Nakamura, Mourad Sini. The Green function of the interior transmission problem and its applications. Inverse Problems & Imaging, 2012, 6 (3) : 487-521. doi: 10.3934/ipi.2012.6.487

[18]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569

[19]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107

[20]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011

 Impact Factor: 

Metrics

  • PDF downloads (145)
  • HTML views (400)
  • Cited by (0)

Other articles
by authors

[Back to Top]