PGS LCP solver Conclusion

Introduction

The form of the LCP problem is as following:

$$ \begin{align} Find\ w\ a\\ w = Aa + b \\ a^Tw = 0\\ a \geq 0\\ w \geq 0 \end{align} $$

To introduce the PGS solver, first, we should take a look at the GS solver to the linear equations:

Guass-Seidel Iteration Solver

Assume we have to find the answer $x$ of the $Ax = b$:

$A$ could be written in the following way:

$$ A = D - L - U $$

$D$ is the diagonal matrix, $L$ is the lower triangular matrix, and $U$ is the upper triangular matrix.

so the original equations are:

$$ \begin{align} (D -L -U)x &= b \\ (D - L)x &= Ux + b\\ x &= (D - L)^{-1}Ux + (D - L)^{-1}b \end{align} $$

Using the thought of iteration, the request relationship is:

$$ \begin{align} x^{k + 1} = (D - L)^{-1}Ux^k + (D - L)^{-1}b \end{align} $$

The necessary and sufficient condition of the convergence of this method is $p(A) < 1$.

Now let’s take a look at the PGS method.

Projected Gauss-Seidel Solver

If we return the LCP problem to the original form from the iteration equation of the GS method, we have:

$$ \begin{align} (D - L)x^{k+1} + b - Ux^k &\geq 0 \\ x^{k + 1} &\geq 0 \\ (x^{k + 1})^T((D - L)x^{k+1} + b - Ux^k) &= 0 \end{align} $$

Let $z^k = b - Ux^k$, we have:

$$ \begin{align} (D - L)x^{k+1} + z^k &\geq 0 \\ x^{k + 1} &\geq 0 \\ (x^{k + 1})^T((D - L)x^{k+1} + z^k) &= 0 \end{align} $$

which means:

$$ \begin{align} \min \{x^{k+1}_i, ((D - L)x^{k+1} + z^k)_i\} = 0, i = 0,1, \cdots, n \end{align} $$

The equivalence of this form is:

$$ \max \{0, x^{k+1}_i -((D - L)x^{k+1} + z^k)_i\} = x^{k + 1}_i, i = 0, 1, \cdots, n $$

Let $m^k_i = x^{k+1}_i -((D - L)x^{k+1} + z^k)_i$, we have:

$$ \begin{align} x^{k + 1}_i = \max \{0, m^k_i\} \end{align} $$

There is two situations of the value of the $m^k_i$, the first is $m_i^k < 0$, which implies that $x_i^{k+1} = 0$. The other situation is $m_i^{k+1} \geq 0$, we could go deep into this situation.

Now we know that $x_i^{k+1} = m_i^{k} = x^{k+1}_i -((D - L)x^{k+1} + z^k)_i$, then $((D - L)x^{k+1} + z^k)_i$ should be $0$.

$$ \begin{align} ((D - L)x^{k+1} + z^k)_i &= 0\\ ((D - L)x^{k+1} + b - Ux^k)_i &= 0\\ x^{k + 1} &= (D - L)^{-1}(Ux^k - b) \\ x^{k + 1} &= (D - L)^{-1}Ux^k - (D - L)^{-1}b \\ \end{align} $$

Let $c_i^k = ((D - L)^{-1}Ux^k - (D - L)^{-1}b)_i$, the conclusion is:

$$ \begin{align} x_i^{k+1} = \max \{0, m_i^k\} = \max \{0, c_i^k\} \end{align} $$

So:

$$ \begin{align} x_i^{k+1} = \max \{0, (D - L)^{-1}Ux_i^k - (D - L)^{-1}b_i\}, i = 0, 1, \cdots, n \end{align} $$

Using the PGS method to solve the MLCP problem

Basically speaking, the Mixed LCP problem is:

$$ \begin{align} Find\ w\ x\\ lo \leq x\ \leq hi\\ w = Ax + b \\ \end{align} $$

There are $3$ situations of the $a_i$:

$$ \begin{align} &x_i = lo_i\ \ w_i \geq 0 \\ &x_i = hi_i\ \ w_i \leq 0 \\ lo_i < &x_i < hi_i\ \ w = 0 \end{align} $$

Using the thought of iteration, we have:

$$ \begin{align} w^{k+1} &= (D - L)x^{k+1} + z^k \\ x_i^{k+1} &= lo_i\ \ w_i^{k+1} \geq 0 \\ x_i^{k+1} &= hi_i\ \ w_i^{k+1} \leq 0 \\ lo_i < x_i^{k+1} &< hi_i\ \ w_i^{k+1} = 0 \end{align} $$

$z^k = b - Ux^k$.

In the first situation, we have:

$$ \begin{align} (x_i^{k+1} - lo_i)w_i^{k+1} = 0 \end{align} $$

which means:

$$ \min \{(x_i^{k+1} - lo_i), w_i^{k+1}\} = 0 $$

Using the same method as the above section. we have:

$$ x_i^{k+1} = \max \{lo_i, (D - L)^{-1}Ux^k - (D - L)^{-1}b\} $$

Considering the upper bound of the $x$, we must add a constraint:

$$ x_i^{k+1} = \min \{\max \{lo_i, (D - L)^{-1}Ux^k - (D - L)^{-1}b\}, hi_i\} $$

If we start from the second situation, we will get:

$$ x_i^{k+1} = \max \{\min \{hi_i, (D - L)^{-1}Ux^k - (D - L)^{-1}b\}, lo_i\} $$

It is the same thing.

By the way, the sufficient condition of the convergence of this method is $A$ is positive definite based on this paper An Algorithm for the Fast Solution of Linear Complementarity Problems.