Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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.

share|improve this answer

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.

share|improve this answer
    
Sounds interesting. Yes, please send it to me (dundjoh'at'googlemail'dot'com) –  Johannes Jun 1 '11 at 8:44

Maybe this is what you are looking for: http://www.springerlink.com/content/q500vk752161j33p/abstract/

share|improve this answer
    
Thanks for looking that up, but it only deals with Minkowsky (en.wikipedia.org/wiki/M-matrix) matrices! –  Johannes Jun 1 '11 at 8:42

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.