Linear complementarity problem – tridiagonal and convex case

Question

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

Answer 1

You can solve a P-LCP with a tridiagonal matrix (not using the definiteness) by solving O($n^2$) many systems of equations where $n$ is the dimension of $M$. You have to use the Unique Sink Orientation (USO) framework. Call a USO generated by a tridiagonal matrix a tridiagonal USO. Note that the Subcube of a tridiagonal USO is again a tridiagonal USO. Furthermore if you consider the subcube with $z_i=0$ you can write it as a "ProductUSO" of two USOs of dimension $i-1$ and $n-i$. Then you can recursively determine the sinks of the subcubes corresponding to $\{v \in \{0,1\}^n|v_k=1 \forall k>i\}$ for $i=1,...,n$. Im currently writing a master thesis about this topic. I can send you the current version if you want. The idea of the algorithm had my supervisor. He will probably write a paper this summer.

Answer 2

One "quick" idea for solving the associated QP is to try CVXOPT, which is a nice package for doing convex optimization. Since the Hessian of your QP is tridiagonal, implementing a customized solver that takes advantage of this tridiagonal structure (essentially in the part where you have to solve the associated Newton equations), should not be too hard.

The CVXOPT software has several useful examples (takes a bit of effort to read the Python code, but eventually patience should pay off) that you could use as building blocks for your particular problem.

Answer 3

I came across this: https://github.com/otherlab/tridiagonal, but haven't tried it. Obviously it could be used for monotone LCPs as well, through the convex QP formulation.