• PDF
• Cite
• Share
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

• 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: • • 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,$$\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,$$\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,$$\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,$$\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$

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$

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$

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$
• Tables(5)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint