I need an algorithm for the following LCP:

- $\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}$
- $\mathbf{z} \ge \mathbf{0}$
- $\mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0$

Here, $\mathbf{M}$, is a general tridiagonal, positive (semi-)definite Matrix.

I am considering to design a fast algorithm that takes into account the special tridiagonal structure. Especially, because I cannot find any material on the web! (There are algorithms for M-Matrices, but not for more general ones!)

Also for the equivalent Quadratic Program there seems to be no special tridiagonal algorithm.

Do you know of any algorithm or have a general advice for the design of such an algorithm?

Thanks