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

Nadia Hazzam; Zakia Kebbiche

doi:10.3934/naco.2020053

Article Contents

2021, Volume 11, Issue 4: 513-531. Doi: 10.3934/naco.2020053

This issue Previous 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 Next Article A new methodology for solving bi-criterion fractional stochastic programming

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

Nadia Hazzam and
Zakia Kebbiche

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

Received: June 2020

Revised: October 2020

Early access: November 2020

Published: December 2021

Abstract Full Text(HTML) Figure(0) / Table(5) Related Papers Cited by

Abstract

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.

Keywords:

Horizontal linear complementarity problem,
P_*(κ)-matrix,
interior-point method,
kernel function,
complexity bound.

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

Citation:

FullText(HTML)

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

Related Papers

Cited by

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.
[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. Asadi, H. 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. Asadi, M. 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. Bai, M. 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. 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.
[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. Bouafia, D. 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. Cottle, J. S. Pang and R. E. Stone, The 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-Hafshejani, H. 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. Ji, M. 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. Kojima, N. Megiddo, T. 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. Peng, C. 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 Peyghami, S. 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.