Analysis of interior-point-paths for sufficient linear complementarity problems(Continuous and Discrete Mathematical Optimization)

Analysis

of

$\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{o}\mathrm{r}-\mathrm{p}\mathrm{o}\mathrm{i}\mathrm{n}\mathrm{t}_{- \mathrm{p}}\mathrm{a}\mathrm{t}\mathrm{h}\mathrm{s}$

for

sufficient

linear

complementarity

problems

J.

Stoer

Institut

f\"ur

_{Angewandte Mathematik}

_und

_Statistik

Universit\"at

_{W\"urzburg, W\"urzburg,}

_Germany

Abstract: In this lecture we describe the behavior of infeasible-interior-point-paths for

solving horizontal linear complementarity problems

$(LCP)$ _$Px+Qy=q$, $(x, y)\geq 0$, $x^{T}y=0$,

that are sufficient in the sense of Cottle, Pang and Venkateswaran (1989). These paths are

defined as the solution $(x, y)(r, \eta),$ _$r>0,$ $\eta>0$, of

$Px+Qy$ $=$ $q+r\overline{q}$, $(x, y)\geq 0$,

$x_{i}y_{i}$ $=$ $r\eta_{i}$, $\dot{i}=1,$

$\ldots,$$n$,

and they converge to

a

central point of the set of solutions of $(LCP)$ as $r\downarrow \mathrm{O}$. It is

shown that these paths are analytic functions of $r$ even at $r=0$, if $(LCP)$ has a strictly

complementary solution, and are analytic in $\rho:=\sqrt{r}$ at _$\rho=0$, if _$(LCP)$ is solvable but

has no strictly complementary solutions.

数理解析研究所講究録