3
$\begingroup$

I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book (Algorithm 4.2.11 on page 248 of my edition).

The algorithm looks like this:

Given $(q,M)$ with $M$ being square, symmetric and positive semi-definite and of size $n$, try to find $z$ s.t. $Mz+q = w$ and $z\perp w, w \ge 0 \space z \ge 0$, or indicate if no such $z$ exists.

...

Initialize:

$\alpha = \emptyset$, $\beta = \{ 1, ..., n\}$

Step 1: Breaking ties arbitrarily, find: $r \in arg \space min \{ q_i : i \in \beta \}$

If $q_r \ge 0$, stop. A solution of $(q,M)$ is given by $z_\alpha = q_\alpha, z_\beta = 0$

If $M_{rr} = 0$ and $M_{ir} \ge 0$ for all $i \in \alpha$ stop. There is no solution

Step 2: Use the minimum ratio test to find the index $s \in \alpha \cup \{r\}$ of a blocking variable to $r$. Break ties arbitrarily, but prefer $r$ if there's a choice.

Step 3: Using a simple principal pivot on row/column s to update $M$ and $q$

If $s = r$, transfer $r$ from $\beta$ to $\alpha$ and goto Step 1

If $s \ne r$, transfer $s$ from $\alpha$ to $\beta$ and goto Step 2

...

This algorithm works most of the time, but in cases where I perform $n$ pivots, I'm getting to step 1 and $\beta$ is empty, and I'm not sure how to proceed. Some detective work shows that often one more pivot will arrive at the correct answer, but I have a number of different cases and they all require slight differences once they run out of elements in $\beta$ in order to arrive at the correct answer.

One such case is: $M = \begin{bmatrix} 60 & 26 & 37 \\\\ 26 & 36 & 29 \\\\ 37 & 29 & 30 \end{bmatrix}$ and $q = \begin{bmatrix} -1 \\\\ -1 \\\\ -1 \end{bmatrix}$

For which I know the answer is: $z = \begin{bmatrix} 0 \\\\ .004184 \\\\ .029289 \end{bmatrix}$

The matrix M is symmetric PSD as near as I can tell (all the eigen values are positive), so it should be something that Dantzig's algorithm can process. Stepping through the code the above problem gets pivoted 3 times, and I find that a 4th pivot will arrive at a correct answer.

I'm getting tired of hack and check so I'm wondering if there's something I'm just missing about the algorithm's termination condition, or if this case implies a bug in my implementation.

I can provide definitions for "minimum ratio test", "arg min", and "simple principal pivot" if they aren't familiar terms (though they seem to be pretty universal to all pivoting methods for LCPs).

$\endgroup$
4
  • $\begingroup$ This is not a research (or otherwise) mathematics question; you should try stack overflow $\endgroup$
    – Igor Rivin
    Oct 6, 2011 at 19:44
  • 2
    $\begingroup$ From the FAQ: "MathOverflow's primary goal is for users to ask and answer research level math questions, the sorts of questions you come across when you're writing or reading articles or graduate level books." The book sure seems graduate level to me. $\endgroup$
    – Jay Lemmon
    Oct 6, 2011 at 19:47
  • $\begingroup$ You are asking us to find a bug in your implementation. Would you ask your advisor this? If not, what are we, chopped liver? $\endgroup$
    – Igor Rivin
    Oct 6, 2011 at 20:13
  • 3
    $\begingroup$ I'm not asking to find the bug, I'm asking how you're supposed to handle a specific edge case (the case where you perform $n$ "major cycles" and $\beta = \nullset$) of this algorithm. The algorithm as written in the book doesn't handle it. The proof of termination doesn't seem to either, at least not directly. I don't have an instructor; I'm not in university. Non-students do read textbooks, on occasion. $\endgroup$
    – Jay Lemmon
    Oct 6, 2011 at 20:31

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.