\documentstyle[12pt,german,fullpage]{article}
\sloppy
\pagestyle{empty}
\begin{document}
{\huge
{\bf
\mbox{}\\
\begin{center}
Optimal Inclusion of the Solution Set \\[1ex]
concerning a Linear Complementarity\\[1ex]
Problem with Interval Data\\[3ex]
Dr. Uwe Sch\"afer\\[1ex]
University of Karlsruhe  \\[1ex]
Dagstuhl Seminar January 2003
\end{center}
\section*{I. The Linear Complementarity Problem}
Given: $A \in R^{n \times n}$ and $b \in R^n$.\\[1ex]
$LCP(A,b)$: Find $ x \in R^n$ with
\[
\begin{array}{rcl}
b+Ax & \geq & o, \\[1ex]
x & \geq & o, \\[1ex]
(b+ Ax)^{T}x & = &  0.
\end{array}
\]
\newpage
\vspace{-0.5cm}
\mbox{}\\
$\underline{\mbox{Definition:}}$\\[2ex]
 Let $A = (a_{ij}) \in R^{n \times n}$, then:
\begin{enumerate}
\item $A\in Z^{n \times n}:\Leftrightarrow a_{ij}\leq 0,i \not=j.$
\item $A$ is called M-matrix\\[1ex]
 $:\Leftrightarrow
A\in Z^{n \times n}$, $A^{-1}\geq O$.
\end{enumerate}
\vspace{1cm}
$\underline{\mbox{Lemma (Fan)}}$\\[2ex]
Let $A$ be an M-matrix and\\[1ex]
$A \leq B \in Z^{n \times n}$,\\[1ex]
 then $B$ is an M-matrix, too,\\[1ex] i.e. $B^{-1}\geq O$.
\newpage
\vspace{-0.5cm}
\mbox{}\\
$\underline{\mbox{Definition:}}$\\[2ex]
Let $[A]=[\underline{A},\overline{A}]=([a_{ij}])=([\underline{a}_{ij},
\overline{a}_{ij}])\in IR^{n \times n}$, then:
\begin{enumerate}
\item $[A]$ is an M-matrix\\[1ex]
$:\Leftrightarrow$ each $A \in [A]$ is an M-matrix.
\item $[A]$ is an H-matrix,\\[1ex]
if $\Big< [A] \Big>=(c_{ij})$ is an M-matrix, where
\[
c_{ij} = \left\{
\begin{array}{ll}
\min \{|a|: a \in [a_{ij}] \} & \mbox{ if } i=j, \\[1ex]
-\max \{|a|: a \in [a_{ij}] \} & \mbox{ if } i\not= j.
\end{array}
\right.
\]
\item $[A]$ is called H$^{+}$-matrix,\\[1ex]
if $[A]$ is an H-matrix and\\[1ex] $0
< \underline{a}_{ii}$, $i=1,...,n$.
\end{enumerate}
\newpage
\vspace{-0.5cm}
\mbox{}\\
II. The Solution set $\Sigma = \Sigma([A],[b])$
\[
\begin{array}{rl}
\Sigma := & \Big\{ x  :  x \mbox{ solves } LCP(A,b), \\[1ex]
                    & A \in [A],\, b \in [b] \Big\}
\end{array}
\]
Example:
\[
[A] = \left(
\begin{array}{cc}
 [0.125,1] & [-0.25,-0.2] \\[1ex]
 [-0.25,-0.1] & 1
\end{array}
\right),
\]
\[
[b]=\left(
\begin{array}{c}
 [-3,-1] \\[1ex]
 [1,2]
\end{array}
\right)
\]
  \begin{figure}[h]
\unitlength1.5cm
\begin{picture}(8,4.5)
\thinlines
\put(2,0){\vector(0,1){4}}
\put(1,1){\vector(1,0){7}}
\thicklines
\put(2.5,1){\line(2,1){5}}
\put(4.5,1){\line(5,1){0.625}}
\put(5.125,1.125){\line(1,1){2.375}}
\put(2.125,1){\line(1,0){2.375}}
\put(7.5,3,4){$(44,10)$}
\put(7.5,0.5){$z_{1}$}
\put(1.3,3.9){$z_{2}$}
\thinlines
%\put(2.5,0.9){\line(0,1){0.1}}
%\put(2.4,0.5){$4$}
\put(2.125,0.9){\line(0,1){0.1}}
\put(2.0,0.5){$1$}
\put(1.9,3.5){\line(1,0){0.1}}
\put(1.4,3.1){$10$}
\put(4.5,0.9){\line(0,1){0,1}}
\put(4.3,0.5){$20$}
\end{picture}
\end{figure}
\vspace{0.5cm}
\mbox{}\\
\[
[\inf \Sigma,\sup \Sigma]=
\left(
\begin{array}{c}
[1,44] \\[1ex]
[0,10]
\end{array}
\right)
\]
\newpage
\vspace{-0.5cm}
\mbox{}\\
$\underline{\mbox{Theorem}}$\\[2ex]
Let $[A]=[\underline{A},\overline{A}]$ an  M-matrix\\[1ex]
and $[b]=[\underline{b},\overline{b}]$ arbitrary. Then:
\begin{enumerate}
\item $\inf \Sigma = u$,  \\[1ex]
$u$ unique solution of $ LCP(\overline{A},\overline{b})$
\item $\sup \Sigma = v$,  \\[1ex]
$v$ unique solution of $ LCP(\underline{A},\underline{b})$
\item $[x^*]=[u,v]$,\\[1ex]
for the fixed point $[x^*]$\\[1ex]
of the total step method.
\end{enumerate}
\newpage
\vspace{-0.5cm}
\mbox{}\\
Proof of 1.:\\[1ex]
$u$ is the unique solution of $LCP(\overline{A},\overline{b})$; i.e.:
\[
\begin{array}{rcl}
\overline{b}+\overline{A}u & \geq & o, \\[1ex]
u & \geq & o, \\[1ex]
(\overline{b}+ \overline{A}u)^{T}u & = &  0.
\end{array}
\]
Let $A \in [A]$, $b \in [b]$, let
$x$ be the unique solution of $LCP(A,b)$; i.e.:
\[
\begin{array}{rcl}
b+Ax & \geq & o, \\[1ex]
x & \geq & o, \\[1ex]
(b+ Ax)^{T}x & = &  0.
\end{array}
\]
Aim: $u \leq x$\\[2ex]
Define
\[
\Im = \{ i: u_{i}=0\}
\]
 \newpage
\vspace{-0.5cm}
\mbox{}\\
$\Im:= \{i:u_{i} =0 \}$\\[1ex]
define $\tilde A=(\tilde a_{ij})$ and
$\tilde b=(\tilde b_{i})$ via $\overline{A},\, \overline{b}$ by\\[1ex]
\[
\tilde a_{ij}:=
\left\{
\begin{array}{ll}
\overline{a}_{ij} & \mbox{ if } i \not\in \Im ,\\[1ex]
0 & \mbox{ if } i \in \Im \mbox{ and } j\not=i, \\[1ex]
\overline{a}_{ii} & \mbox{ if } i \in \Im \mbox{ and } j=i,
\end{array}
\right\}  i,j=1,...,n
\]
\mbox{}\\
\[
\tilde b_{i} := \left\{
\begin{array}{ll}
\overline{b}_{i} & \mbox{if } i \not\in \Im,\\[1ex]
0 & \mbox{if } i \in \Im,
\end{array}
\right\} i=1,...,n
\]\\[1ex]
Example, let $n=4$ and $\Im=\{2,4\}$ then
\[
\overline{A} \leq
\tilde A =
\left(
\begin{array}{cccc}
\overline{a}_{11} & \overline{a}_{12} & \overline{a}_{13}
& \overline{a}_{14} \\
0 & \overline{a}_{22}  & 0 & 0 \\
\overline{a}_{31} & \overline{a}_{32} & \overline{a}_{33}
& \overline{a}_{34}  \\
0 & 0 & 0 & \overline{a}_{44}
\end{array}
\right) \in Z^{n \times n}, \quad
\tilde b =
\left(
\begin{array}{c}
\overline{b}_{1} \\
0 \\
\overline{b}_{3} \\
0
\end{array}
\right)
\]\\[1ex]
Show
\[
\tilde b + \tilde A u = o \leq \tilde b + \tilde A x .
\]
Then it follows $u \leq x$.
\newpage
\vspace{-0.5cm}
\mbox{}\\
!!$ \quad \tilde b + \tilde A u = o \leq \tilde b + \tilde A x \quad $!!\\[1ex]
\[
\Im = \{2,4\}, \,
\tilde A =
\left(
\begin{array}{cccc}
\overline{a}_{11} & \overline{a}_{12} & \overline{a}_{13}
& \overline{a}_{14} \\
0 & \overline{a}_{22}  & 0 & 0 \\
\overline{a}_{31} & \overline{a}_{32} & \overline{a}_{33}
& \overline{a}_{34}  \\
0 & 0 & 0 & \overline{a}_{44}
\end{array}
\right) , \quad
\tilde b =
\left(
\begin{array}{c}
\overline{b}_{1} \\
0 \\
\overline{b}_{3} \\
0
\end{array}
\right)
\]\\[1ex]
Case 1: If $i \in \Im$, then $u_{i}=0$ and
\[
\begin{array}{rcl}
(\tilde b +\tilde A u)_{i} & = & 0\\[1ex]
& \leq &  \overline{a}_{ii} x_{i} \\[1ex]
& = & (\tilde b +\tilde A x)_{i}
\end{array}
\]
Case 2: If $i \not\in \Im$, then $u_{i} > 0 \Rightarrow$
\[
(\tilde b + \tilde A u)_{i}  =(\overline{b} + \overline{A} u)_{i}
=0 \quad \mbox{and}
\]
\[
\begin{array}{rcl}
\overline{b}_{i} + \sum
\limits_{j=1}^{n} \overline{a}_{ij}u_{j} & = & 0 \\[1ex]
& \leq & (b + A x)_{i}= b_{i} + \sum
\limits_{j=1}^{n} a_{ij}x_{j} \\[1ex]
 & \leq &
\overline{b}_{i} + \sum
\limits_{j=1}^{n} \overline{a}_{ij}x_{j}\\[1ex]
& = & (\overline{b} + \overline{A} x)_{i} =  (\tilde b + \tilde A x)_{i}
\end{array}
\]
\newpage
\vspace{-0.5cm}
\mbox{}\\
Proof of 3.: $[u,v]=[x^*]$\\[1ex]
\[
[u,v] \stackrel{!}{=} \max \{o, [D]^{-1}([R] [u,v] -[b]) \}=:[c,d]
\]\\[1ex]
with $[D]=diag([a_{11}],...,[a_{nn}])$ and
\[
[R]=-
\left(
\begin{array}{cccc}
\, 0 & [a_{12}] & \cdots & [a_{1n}] \\[1ex]
\, [a_{21}] & 0 & \ddots & \vdots \\[1ex]
\, \vdots & \ddots & \ddots & [a_{n-1n}] \\[1ex]
\, [a_{n1}] & \cdots & [a_{nn-1}] & 0
\end{array}
\right)
\]\\[1ex]
It is $[\underline{r}_{ij},\overline{r}_{ij}]= [-\overline{a}_{ij},
-\underline{a}_{ij}],\,  i\not=j$, $ \underline{R} \geq O$\\[1ex]
\[
 [c_{i},d_{i}]= \max \{0,\frac{[(\underline{R}u-\overline{b})_{i},
 (\overline{R}v-\underline{b})_{i}]}{[a_{ii}]} \}  \quad i=1..n
\]\\[1ex]
1.Case: $(\overline{R}v-\underline{b})_{i} \leq 0$\\[1ex]
Then $d_{i}=0\stackrel{!}{=}v_{i}  $
\newpage
\vspace{-0.5cm}
\mbox{}\\
Assume $v_{i} >0$\\[1ex]
$\Rightarrow$
\[
(\underline{A}v-\underline{b})_{i} = 0
\]
However,
\[
(\overline{R}v-\underline{b})_{i} \leq 0 \Leftrightarrow
-\sum \limits_{j=1,j\not=i}^{n}
\underline{a}_{ij}v_{j} - \underline{b}_{i} \leq 0
\]
i.e.
\[
\begin{array}{rcl}
0 & \leq & \sum \limits_{j=1,j\not=i}^{n} \underline{a}_{ij}v_{j} + \underline{b}_{i} \\[3ex]
& < & \sum \limits_{j=1}^{n} \underline{a}_{ij}v_{j} + \underline{b}_{i} \\[3ex]
& = & (\underline{A}v-\underline{b})_{i}
\end{array}
\] \\[3ex]
2. Case, 3. Case similar...
\newpage
\vspace{-0.5cm}
\mbox{}\\
Remarks: Let $[A]$ H$^{+}$-matrix:\\[3ex]
$v$ the unique solution of $LCP(\Big< [A] \Big>,\underline{b})$,\\[1ex]
then
\[
\Sigma([A],[b]) \subseteq [o,v].
\]\\[1ex]
If $\underline{\tilde b} \leq \underline{b}$\\[1ex]
then
\[
\Sigma \Big( [A],[\underline{b},\overline{b}] \Big) \subseteq
\Sigma \Big( [A],[ \underline{\tilde b},\overline{b}] \Big),
\]
$\tilde v$ the unique solution of $LCP(\Big< [A] \Big>,\underline{\tilde b})$,\\[1ex]
then
\[
\Sigma([A],[b]) \subseteq [o,\tilde v].
\]\\[1ex]
Let $\underline{\tilde b} \leq o$, then
\[
\tilde v = \Big< [A] \Big>^{-1}(- \underline{\tilde b}).
\]
}
\end{document}
