# Bounded Homotopy Path Approach to Find the Solution of Linear
Complementarity Problems

A. Duttaa,1, R. Janab,2, A. K. Dasb,3
_a Department of Mathematics, Jadavpur University, Kolkata, 700 032, India_
_b SQC & OR Unit, Indian Statistical Institute, Kolkata, 700 108, India_
_1 Email<EMAIL_ADDRESS>
_2 Email<EMAIL_ADDRESS>
_3 Email<EMAIL_ADDRESS>

###### Abstract

In this article, we introduce a new homotopy function to trace the trajectory
by applying modified homotopy continuation method for finding the solution of
the Linear Complementarity Problem. Earlier several authors attempted to
propose homotopy functions based on original problems. We propose the homotopy
function based on the Karush-Kuhn-Tucker condition of the corresponding
quadratic programming problem of the original problem. The proposed approach
extends the processability of the larger class of linear complementarity
problems and overcomes the limitations of other existing homotopy approaches.
We show that the homotopy path approaching the solution is smooth and bounded.
We find the positive tangent direction of the homotopy path. The difficulty of
finding a strictly feasible initial point for the interior point algorithm can
be replaced appropriately by combining the interior point with the homotopy
method. Various classes of numerical examples are illustrated to show the
effectiveness of the proposed algorithm.

Keywords: Linear complementarity problem, homotopy method, interior point
method, strictly feasible point.

AMS subject classifications: 90C33, 15A39, 15B99, 14F35.

11footnotetext: Corresponding author22footnotetext: The author R.Jana
presently working in an integrated steel plant of India

##  1 Introduction

Eaves and Saigal [5] formed an important class of globally convergent methods
for solving systems of non-linear equations, which is known as homotopy
method. Such methods have been used to constructively prove the existence of
solutions to many economic and engineering problems. Let $X,Y$ be two
topologocal spaces. Let $f,g:X\to Y$ be continuous maps. A homotopy from $f$
to $g$ is a continuous function $H:X\times[0,1]$$\to Y$ satisfying
$H(x,0)=f(x),$ $H(x,1)=g(x)\ \forall x\in X.$ If such a homotopy exists, then
$f$ is homotopic to $g$ and it is denoted by $f\simeq g.$ Let $f,g:R\to R$ any
two continuous, real functions, then $f\simeq g.$ Now we define a function
$H:R\times[0,1]\to R$ by $H(x,t)=(1-t)f(x)+tg(x).$ Clearly $H$ is continuous
and $H(x,0)=f(x),$ $H(x,1)=g(x).$ Thus $H$ is a homotopy between $f$ and $g.$
Let $X,Y$ be two topological spaces and let Map$(X,Y)$ be the set of all
continuous maps from $X$ to $Y.$ Homotopy is an equivalence relation on
Map$(X,Y).$ Probability one homotopy methods are a class of algorithms for
solving nonlinear systems of equations that are accurate, robust and almost
surely converge from an arbitrary starting point. The fundamental idea of the
homotopy continuation method is to solve a problem by tracing a certain
continuous path that leads to a solution to the problem. Thus, defining a
homotopy mapping that yields a finite continuation path plays an essential
role in a homotopy continuation method. The homotopy method [16] is itself an
important class of globally convergent methods. Many homotopy methods are
proposed for constructive proof of the existence of solutions to systems of
nonlinear equations, nonlinear optimization problems, Brouwer fixed point
problems, nonlinear programming, game problem and complementarity problems
[17]. Chen et al. [1] proposed a homotopy algorithm for computing complex
eigenpairs of a tensor in a tensor complementarity problem. Han [8] proposed a
homotopy method for finding the unique positive solution to a multilinear
system with a nonsingular $M$-tensor and a positive right side vector. We are
interested in solving the complementarity problem, mainly the linear
complementarity problem. The linear complementarity problem is identified as
an important mathematical programming problem and provides a unifying
framework for several optimization problems like linear programming, linear
fractional programming, convex quadratic programming and the bimatrix game
problem. Several applications of linear complementarity problems are reported
in operations research [14], multiple objective programming problems [11],
mathematical economics and engineering. For details see [7], [9] and [10]. The
concept of complementarity is synonymous with the notion of system
equilibrium. The linear complementarity problem [13] is defined as follows:

Given square matrix $A\in R^{n\times n}$ and a vector $\,q\,\in\,R^{n},\,$ the
linear complementarity problem is to find $w\in R^{n}$ and $x\in R^{n}$ such
that

$w-Ax=q,w\geq 0,\,x\geq 0,$ (1.1) $x^{t}w=0.$ (1.2)

This problem is denoted as LCP$(q,A).$

Among the many facets of research in linear complementarity problems, the area
that has received thorough attention in recent years is the development of
robust and efficient algorithms for solving various kinds of linear
complementarity problems. Kojima et al. showed that the interior point method
for linear programming problem was a kind of path-following method. This
polynomial time-bound method is widely used to solve LCP$(q,A)$, but some
matrices are not processable by this method as well as by Lemke’s algorithm.
The homotopy method is a very interesting and useful method to solve
LCP$(q,A)$ for larger matrix classes that are not processable by the interior
point method and Lemke’s algorithm also. In the literature it was proved that
the homotopy method converges globally to the solution of LCP$(q,A),$ where
$A$ is a positive semidefinite matrix [21], a $P$-matrix [20], an $N$\- matrix
[22] or a $P_{*}$-matrix [15] with respect to different type of homotopy
functions. For further details see [3]. In this paper, we attempt to introduce
another homotopy function and condition for global convergence of the homotopy
method to solve LCP$(q,A),$ where $A$ belongs to various matrix classes. We
give some numerical examples of various types of matrix classes like PSD, $N$,
almost $C_{0},$ singular $Q_{0}$, $Q$ etc, which give the solution by our
introduced homotopy function. Most of them are not solvable by Lemke’s
algorithm and also by already existing homotopy functions. The paper is
organized as follows. Section 2 presents some basic notations and results. In
section 3, we propose a new homotopy function to find the solution of
LCP$(q,A)$. We construct a smooth and bounded homotopy path under some
conditions to find the solution of the linear complementarity problem as the
homotopy parameter $\lambda\to 0$. We prove an if and only if condition to get
the solution of LCP$(q,A)$ from the solution of the homotopy equation. We also
find the sign of the positive tangent direction of the homotopy path. We use a
modified interior-point bounded homotopy path algorithm for solving the linear
complementarity problem in section 4. Finally, in section 4, we show various
classes of numerical examples to present the effectiveness of the introduced
homotopy function as well as the algorithm.

##  2 Preliminaries

We denote the $n$ dimensional real space by $R^{n}$ where $R^{n}_{+}$ and
$R^{n}_{++}$ denote the nonnegative and positive orthant of $R^{n}.$ We
consider vectors and matrices with real entries. Any vector $x\in R^{n}$ is a
column vector and $x^{t}$ denotes the row transpose of $x.$ $e$ denotes the
vector of all $1.$ If $A$ is a matrix of order $n,$
$\alpha\subseteq\\{1,2,\cdots,n\\}$ and
$\bar{\alpha}\subseteq\\{1,2,\cdots,n\\}\setminus\alpha$ then
$A_{\alpha\bar{\alpha}}$ denotes the submatrix of $A$ consisting of only the
rows and columns of $A$ whose indices are in $\alpha$ and $\bar{\alpha}$
respectively. $A_{\alpha\alpha}$ is called a principal submatrix of A and
det$(A_{\alpha\alpha})$ is called a principal minor of $A.$ We define
$\mathcal{F}=\\{x\in R^{n}:x>0,Ax+q>0\\},\ \mathcal{\bar{F}}=\\{x\in
R^{n}:x\geq 0,Ax+q\geq 0\\},\mathcal{F}_{1}=\mathcal{F}\times R_{++}^{n}\times
R_{++}^{n}$ and $\mathcal{\bar{F}}_{1}=\mathcal{\bar{F}}\times R_{+}^{n}\times
R_{+}^{n}.$ $\partial{\mathcal{F}_{1}}$ denotes the boundary of
$\bar{\mathcal{F}_{1}}.$

A matrix $A\in R^{n\times n}$ is said to be a/an
$-$ positive semidefinite (PSD) matrix if $x^{t}Ax\geq 0,\;\forall\;x\in
R^{n}.$
$-$ $P$-matrix if all its principal minors are positive.
$-$ $N$-matrix if all its principal minors are negative.
$-$ $P_{*}$-matrix if $\exists$ a constant $\tau>0$ such that for any $x\in
R^{n},$

$(1+\tau)\sum_{i\in I_{+}(x)}x_{i}(Mx)_{i}+\sum_{i\in
I_{-}(x)}x_{i}(Mx)_{i}\geq 0$

where $I_{+}(x)=\\{i\in N:x_{i}(Mx)_{i}>0\\}$ and $I_{-}(x)=\\{i\in
N:x_{i}(Mx)_{i}\leq 0\\}.$
$-$ copositive $(C_{0})$ matrix if $x^{t}Ax\geq 0,\;\forall\;x\geq 0.$
$-$ almost $C_{0}$-matrix if it is copositive of up to order $n-1$ but not of
order $n.$
$-$ $N_{0}$-matrix of exact order $k\,(1\leq k\leq n)$ if every principal
submatrix of order $(n-k)$ is an $N_{0}$-matrix and every principal minor of
order $r,$ $(n-k)<r\leq n$ is positive.
$-$ $Q$-matrix if for every $q\in R^{n},$ LCP$(q,A)$ has a solution. The basic
idea of homotopy methods can be explained as to construct a homotopy from the
auxiliary mapping $g$ to the object mapping $p.$ The original problem can be
solved by following the homotopy path from the zero set of the auxiliary
mapping $g$ to the zero set of the object mapping $p.$ The difficulty of
finding a strictly feasible initial point for the interior point algorithm can
be avoided by combining the interior point with the homotopy method.
Furthermore, the global convergence of the homotopy methods can guarantee the
global convergence for the combined homotopy interior point methods. Suppose
the given problem is to find a root of the non-linear equation $p(x)=0$ and
suppose $g(x)=0$ is auxiliary function with an unique solution $x_{0}.$ Then
the homotopy equation can be written as $H(x,\lambda)=\lambda
g(x)+(1-\lambda)p(x),\,0\leq\lambda\leq 1.$ Then we consider $H(x,\lambda)=0.$
The value of $\lambda$ will start from $1$ and goes to $0.$ In this way one
can find the solution of the given equation $p(x)=0$ from the solution of
$g(x)=0.$ The key idea to solve LCP$(q,A)$ by the homotopy method is to solve
a system of equations of the form $H(x,\lambda)=0,$ where
$H:R^{n}\times[0,1]\to R^{n},x\in R^{n},\lambda\in[0,1]$ is called homotopy
parameter. The homotopy method aims to trace out entire path of equilibria in
$H^{-1}=\\{(x,\lambda):H(x,\lambda)=0\\}$ by varrying both $x$ and $\lambda.$
Now we define a parametric path as a set of functions $(x(s),\lambda(s))\in
H^{-1}.$ When we move along the homotopy path, the auxiliary variable $s$
either decreases or increases monotonically. Differentiating
$H(x(s),\lambda(s))=0$ with respect to $s$ we get $\frac{\partial H}{\partial
x}x^{\prime}(s)+\frac{\partial H}{\partial\lambda}\lambda^{\prime}(s)=0,$
where $\frac{\partial H}{\partial x}$ and $\frac{\partial H}{\partial\lambda}$
are $n\times n$ jacobian matrix of $H$ and $n\times 1$ column vector
respectively. So this is a system of $n$ differential equations in $n+1$
unknowns ${x_{i}}^{\prime}(s)\ \forall\ i$ and $\lambda^{\prime}(s).$ this
system of differential equations has many solutions, which differ by monotone
transformation of the auxiliary variable $s.$ Now we state some results which
will be required in the next section.

######  Lemma 2.1:

[2] Let $U\subset R^{n}$ be an open set and $f:R^{n}\to R^{p}$ be smooth. We
say $y\in R^{p}$ is a regular value for $f$ if $\text{Range}\,Df(x)=R^{p}$
$\forall x\in f^{-1}(y),$ where $Df(x)$ denotes the $n\times p$ matrix of
partial derivatives of $f(x).$

######  Lemma 2.2:

[15] Let $V\subset R^{n},U\subset R^{m}$ be open sets, and let $\phi:V\times
U\to R^{k}$ be a $C^{\alpha}$ mapping, where $\alpha>\text{max}\\{0,m-k\\}.$
If $0\in R^{k}$ is a regular value of $\phi,$ then for almost all $a\in V,0$
is a regular value of $\phi_{a}=\phi(a,.).$

######  Lemma 2.3:

[15] Let $\phi:U\subset R^{n}\to R^{p}$ be $C^{\alpha}$ mapping, where
$\alpha>\text{max}\\{0,n-p\\}.$ Then $\phi^{-1}(0)$ consists of some $(n-p)$
dimensional $C^{\alpha}$ manifolds.

######  Lemma 2.4:

[22] One-dimensional smooth manifold is diffeomorphic to a unit circle or a
unit interval.

##  3 Main results

Watson [18] illustrated an outline of homotopy approach for complementarity
problem. Chow et al.[2] developed sufficiently powerful theoretical tools for
homotopy methods. In 2006, Yu et al. [21] proposed the following homotopy
function to solve the LCP$(q,A)$ where $A$ is a positive semidefinite matrix,

$H(w,w^{(0)},\lambda)=\left[\begin{array}[]{c}(1-\lambda)[Ax+q-y]+\lambda(x-x^{(0)})\\\
XYe-\lambda e\\\ \end{array}\right]=0.$ (3.1)

Zhao et al. [22] proposed the following homotopy function in 2010 to solve
LCP$(q,A)$ where $A$ is an $N$-matrix,

$H(w,w^{(0)},\lambda)=\left[\begin{array}[]{c}(1-\lambda)[y-Ax-q]+\lambda(x-x^{(0)})\\\
Xy-\lambda X^{(0)}y^{(0)}\\\ \end{array}\right]=0.$ (3.2)

Later Xu et al. [20] developed another homotopy function for finding the
solution of LCP$(q,A)$ where $A$ is a $P$-matrix,

$H(w,w^{(0)},\lambda)=\left[\begin{array}[]{c}(1-\lambda)[y-Ax-q]-\lambda(x-x^{(0)})\\\
Xy-\lambda X^{(0)}y^{(0)}\\\ \end{array}\right]=0.$ (3.3)

Wang et al. [19] showed that linear complementarity problem with
$P_{*}$-matrix can be solved using the homotopy function

$H(w,w^{(0)},\lambda)=\left[\begin{array}[]{c}(1-\lambda)[Ax+q]-y+\lambda
y^{(0)}\\\ Xy-\lambda X^{(0)}y^{(0)}\\\ \end{array}\right]=0.$ (3.4)

We propose a new homotopy function to solve LCP$(q,A)$ based on the KKT
condition.

$H(y,y^{(0)},\lambda)=\left[\begin{array}[]{c}(1-\lambda)[(A+A^{t})x+q-z_{1}-A^{t}z_{2}]+\lambda(x-x^{(0)})\\\
Z_{1}x-\lambda Z_{1}^{(0)}x^{(0)}\\\ Z_{2}(Ax+q)-\lambda
Z_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right]=0$ (3.5)

where $Z_{1}=\text{diag}(z_{1}),$ $Z_{2}=\text{diag}(z_{2}),$
$Z_{1}^{(0)}=\text{diag}(z_{1}^{(0)}),$
$Z_{2}^{(0)}=\text{diag}(z_{2}^{(0)}),$ $y=(x,z_{1},z_{2})\in R_{+}^{n}\times
R_{+}^{n}\times R_{+}^{n},$
$y^{(0)}=(x^{(0)},{z_{1}}^{(0)},{z_{2}}^{(0)})\in\mathcal{F}_{1},$ and
$\lambda\in(0,1].$ We denote $\Gamma_{y}^{(0)}=\\{(y,\lambda)\in
R^{3n}\times(0,1]:H(y,y^{(0)},\lambda)=0\\}\subset\mathcal{F}_{1}\times(0,1]\\}.$

Here $\lambda$ varies from $1$ to $0,$ and starting from $\lambda=1$ to
$\lambda\to 0$ if we get a smooth bounded curve, then we will get a finite
solution of the homotopy equation 3.5 at $\lambda\to 0.$ At $\lambda\to 1,$
the homotopy equation 3.5 gives the solution $(y^{(0)},1),$ and at $\lambda\to
0,$ the homotopy equation 3.5 gives the solution of the system of following
equations:

$(A+A^{t})x+q-z_{1}-A^{t}z_{2}=0$

$Z_{1}x=0$

$Z_{2}(Ax+q)=0$

where $Z_{1}=\text{diag}(z_{1})$ and $Z_{2}=\text{diag}(z_{2}).$

Let $z_{1{I_{1}}}=0$ and $x_{I_{2}}=0,$ where $I_{1}\cup I_{2}=\\{n\\}.$ Let
$z_{2J_{1}}=0$ and $(Ax+q)_{J_{2}}=0,$ where $J_{1}\cup J_{2}=\\{n\\}.$ If the
solution of the homotopy function 3.5, $y=(x,z_{1},z_{2})$ gives the solution
of LCP$(q,A)$ which is $x,$ then $x_{{I_{2}}^{c}}\neq 0$ $\implies$
${(Ax+q)_{{I_{2}}^{c}}}=0.$ This implies that ${{I_{2}}^{c}}\subseteq J_{2}$
and ${(Ax+q)_{{J_{2}}^{c}}}\neq 0\implies x_{{J_{2}}^{c}}=0,$ which implies
that ${{J_{2}}^{c}}\subseteq I_{2}.$ ${{I_{2}}^{c}}=J_{2},$
${{J_{2}}^{c}}=I_{2}$ give the nondegenerate solution of LCP$(q,A)$ and
${{I_{2}}^{c}}\subset J_{2},$ ${{J_{2}}^{c}}\subset I_{2}$ give the degenerate
solution of LCP$(q,A).$ When $I_{1}\cap I_{2}=\emptyset$ and $J_{1}\cap
J_{2}=\emptyset,$ it implies $I_{1}={{I_{2}}^{c}}=J_{2}$ and
$J_{1}={{J_{2}}^{c}}=I_{2},$ then $x=z_{2}$ and $Ax+q=z_{1}$ will give the
solution of LCP$(q,A),$ otherwise we get nontrivial solution of LCP$(q,A)$
which is not same as $z_{1}.$ Therefore the homotopy solution $y$ can not give
the LCP solution $x$ when ${{I_{2}}^{c}}\nsubseteq J_{2}$ and
${{J_{2}}^{c}}\nsubseteq I_{2},$ that is ${{I_{2}}^{c}}\subseteq J_{1}$ and
${{J_{2}}^{c}}\subseteq I_{1}.$

First we show that the smooth curve exists for our proposed homotopy function.

######  Theorem 3.1:

For almost all initial points $y^{(0)}\in\mathcal{F}_{1},$ $0$ is a regular
value of the homotopy function $H:R^{3n}\times(0,1]\to R^{3n}$ and the zero
point set
$H_{y^{(0)}}^{-1}(0)=\\{(y,\lambda)\in\mathcal{F}_{1}:H_{y^{(0)}}(y,\lambda)=0\\}$
contains a smooth curve $\Gamma_{y}^{(0)}$ starting from $(y^{(0)},1).$

###### Proof.

The Jacobian matrix of the above homotopy function $H(y,y^{(0)},\lambda)$ is
denoted by $DH(y,y^{(0)},\lambda)$ and we have
$DH(y,y^{(0)},\lambda)=$$\left[\begin{array}[]{ccc}\frac{\partial{H(y,y^{(0)},\lambda)}}{\partial{y}}&\frac{\partial{H(y,y^{(0)},\lambda)}}{\partial{y^{(0)}}}&\frac{\partial{H(y,y^{(0)},\lambda)}}{\partial{\lambda}}\\\
\end{array}\right].$ For all $y^{(0)}\in\mathcal{F}_{1}$ and
$\lambda\in(0,1],$ we have
$\frac{\partial{H(y,y^{(0)},\lambda)}}{\partial{y^{(0)}}}=$$\left[\begin{array}[]{ccc}-\lambda
I&0&0\\\ -\lambda Z_{1}^{(0)}&-\lambda X^{(0)}&0\\\ -\lambda
Z_{2}^{(0)}A&0&-\lambda Y^{(0)}\\\ \end{array}\right],$ where
$Y^{(0)}=\text{diag}(Ax^{(0)}+q),X^{(0)}=\text{diag}(x^{(0)})$ and
$\det(\frac{\partial{H}}{\partial{y^{(0)}}})$$=(-1)^{3n}\lambda^{3n}\prod_{i=1}^{n}x_{i}^{(0)}y_{i}^{(0)}$
$\neq 0$ for $\lambda\in(0,1].$ Thus $DH(y,y^{(0)},\lambda)$ is of full row
rank. Therefore, $0$ is a regular value of $H(y,y^{(0)},\lambda)$ by the Lemma
2.1. By Lemmata 2.2 and 2.3, for almost all $y^{(0)}\in\mathcal{F}_{1},$ $0$
is a regular value of $H_{y^{(0)}}(y,\lambda)$ and $H_{y^{(0)}}^{-1}(0)$
consists of some smooth curves and $H_{y^{(0)}}(y^{(0)},1)=0.$ Hence there
must be a smooth curve $\Gamma_{y}^{(0)}$ starting from $(y^{(0)},1).$ ∎

Now we show that the smooth curve $\Gamma_{y}^{(0)}$ for the proposed homotopy
function 3.5 is bounded and converges and establish conditions for global
convergence of the homotopy method with our newly introduced homotopy function
3.5.

######  Theorem 3.2:

Let $\mathcal{F}$ be a non-empty set and $A\in R^{n\times n}$ a matrix and
assume that there exists a sequence of points
$\\{u^{k}\\}\subset\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1],$ where
$u^{k}=(x^{k},z_{1}^{k},z_{2}^{k},\lambda^{k})$ such that $\|x^{k}\|<\infty\
\text{as}\ k\to\infty$ and $\|z_{2}^{k}\|<\infty\ \text{as}\ k\to\infty$ and
for a given $y^{(0)}\in\mathcal{F}_{1},$ $0$ is a regular value of
$H(y,y^{(0)},\lambda),$ then $\Gamma_{y}^{(0)}$ is a bounded curve in
$\mathcal{F}_{1}\times(0,1].$

###### Proof.

Note that $0$ is a regular value of $H(y,y^{(0)},\lambda)$ by Theorem 3.1. Now
we assume that $\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1]$ is an
unbounded curve. Then there exists a sequence of points $\\{u^{k}\\},$ where
$u^{k}=(y^{k},\lambda^{k})\subset\Gamma_{y}^{(0)}$ such that
$\|(y^{k},\lambda^{k})\|\to\infty.$ As $(0,1]$ is a bounded set and $x$
component and $z_{2}$ component of $\Gamma_{y}^{(0)}$ is bounded, there exists
a subsequence of points
$\\{u^{k}\\}=\\{(y^{k},\lambda^{k})\\}=\\{x^{k},z_{1}^{k},z_{2}^{k},\lambda^{k}\\}$
such that $x^{k}\to\bar{x},\ {z_{2}}^{k}\to\bar{z_{2}},\
\lambda^{k}\to\bar{\lambda}\in[0,1]\ \text{and}\ \|z^{k}\|\to\infty\
\text{as}\ k\to\infty,\ \text{where}\
z^{k}=\left[\begin{array}[]{c}z_{1}^{k}\\\ z_{2}^{k}\\\ \end{array}\right].$
Since $\Gamma_{y}^{(0)}\subset H_{y^{(0)}}^{-1}(0),$ we have

$(1-\lambda^{k})[(A+A^{t})x^{k}+q-z_{1}^{k}-A^{t}z_{2}^{k}]+\lambda^{k}(x^{k}-x^{(0)})=0$
(3.6) $Z_{1}^{k}x^{k}-\lambda^{k}Z_{1}^{(0)}x^{(0)}=0$ (3.7)
$Z_{2}^{k}(Ax^{k}+q)-\lambda^{k}Z_{2}^{(0)}(Ax^{(0)}+q)=0$ (3.8)

where $Z_{1}^{k}=\text{diag}(z_{1}^{k})$ and
$Z_{2}^{k}=\text{diag}(z_{2}^{k}).$ Let
$\bar{\lambda}\in[0,1],\|z_{1}^{k}\|=\infty$ and $\|z_{2}^{k}\|<\infty$ as
$k\to\infty.$ Then $\exists\ i\in\\{1,2,\cdots,n\\}$ such that
$z_{1i}^{k}\to\infty$ as $k\to\infty.$ Let $I_{1z}=\\{i\in\\{1,2,\cdots
n\\}:\lim\limits_{k\to\infty}z_{1i}^{k}=\infty\\}.$ When
$\bar{\lambda}\in[0,1),$ for $i\in I_{1z}$ we can get from Equation 3.6,
$(1-\lambda^{k})[((A+A^{t})x^{k})_{i}+q_{i}-z_{1i}^{k}-(A^{t}z_{2}^{k})_{i}]+\lambda^{k}(x_{i}^{k}-x_{i}^{(0)})=0$
$\implies(1-\lambda^{k})z_{1i}^{k}=(1-\lambda^{k})[((A+A^{t})x^{k})_{i}+q_{i}-(A^{t}z_{2}^{k})_{i}]+\lambda^{k}(x_{i}^{k}-x_{i}^{(0)})\implies
z_{1i}^{k}=[((A+A^{t})x^{k})_{i}+q_{i}-(A^{t}z_{2}^{k})_{i}]+\frac{\lambda^{k}}{(1-\lambda^{k})}(x_{i}^{k}-x_{i}^{(0)}).$
As $k\to\infty$ right hand side is bounded, but left hand side is unbounded.
It contradicts that $\|z_{1}^{k}\|=\infty.$ When $\bar{\lambda}=1,$ then from
Equation 3.7, we get,
$x_{i}^{k}=\frac{\lambda^{k}z_{1i}^{(0)}x_{i}^{(0)}}{z_{1i}^{k}}$ for $i\in
I_{1z}.$ As $k\to\infty,x_{i}^{k}\to 0.$ Again from Equation 3.6, we obtain
$x_{i}^{(0)}=\frac{(1-\lambda_{k})}{\lambda_{k}}[((A+A^{t})x^{k})_{i}+q_{i}-z_{1i}^{k}-(A^{t}z_{2}^{k})_{i}]+x_{i}^{k}$
for $i\in I_{1z}.$ As $k\to\infty,$ we have
$x_{i}^{(0)}=-\lim\limits_{k\to\infty}\frac{(1-\lambda_{k})}{\lambda_{k}}z_{1i}^{k}\leq
0.$ It contradicts that $\|z_{1}^{k}\|=\infty.$
So $\Gamma_{y}^{(0)}$ is a bounded curve in $\mathcal{F}_{1}\times(0,1].$ ∎

######  Theorem 3.3:

Let $\mathcal{F}$ be a non-empty set and $A\in R^{n\times n}$ a nonsingular
matrix and assume that there exists a sequence of points
$\\{u^{k}\\}\subset\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1],$ where
$u^{k}=(x^{k},z_{1}^{k},z_{2}^{k},\lambda^{k})$ such that $\|x^{k}\|<\infty\
\text{as}\ k\to\infty.$ Further suppose for $\lambda^{k}\to 1,$
$\|z_{2}^{k}\|<\infty\ \text{as}\ k\to\infty.$ Suppose that for a given
$y^{(0)}\in\mathcal{F}_{1},$ $0$ is a regular value of $H(y,y^{(0)},\lambda).$
Then $\Gamma_{y}^{(0)}$ is a bounded curve in $\mathcal{F}_{1}\times(0,1].$

###### Proof.

By theorem 3.1, $0$ is a regular value of $H(y,y^{(0)},\lambda)$. Now we
assume that $\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1]$ is an
unbounded curve. Then there exists a sequence of points $\\{u^{k}\\},$ where
$u^{k}=(y^{k},\lambda^{k})\subset\Gamma_{y}^{(0)}$ such that
$\|(y^{k},\lambda^{k})\|\to\infty.$ $(0,1]$ is a bounded set and $x$ component
of $\Gamma_{y}^{(0)}$ is bounded. There exists a subsequence of points
$\\{u^{k}\\}=\\{(y^{k},\lambda^{k})\\}=\\{x^{k},z_{1}^{k},z_{2}^{k},\lambda^{k}\\}$
such that $x^{k}\to\bar{x},\ $ and suppose for $\lambda^{k}\to 1,$
$\|z_{2}^{k}\|<\infty\ \text{as}\ k\to\infty.$ Then two cases will arise. Case
1: $\bar{\lambda}\in[0,1],\|z_{1}^{k}\|<\infty,$ $\|z_{2}^{k}\|=\infty.$
Let $\|z_{2}^{k}\|=\infty.$ Then $\exists\ j\in\\{1,2,\cdots n\\}$ such that
$z_{2j}^{k}\to\infty$ as $k\to\infty.$ Let $I_{2z}=\\{j\in\\{1,2,\cdots
n\\}:\lim\limits_{k\to\infty}z_{2j}^{k}=\infty\\}.$ When
$\bar{\lambda}\in[0,1),$ for $j\in I_{2z}$ we can get from Equation 3.6,
$z_{2j}^{k}=(A^{-t}(A+A^{t})x^{k})_{j}+(A^{-t}q)_{j}-(A^{-t}z_{1}^{k})_{j}+\frac{\lambda^{k}}{1-\lambda^{k}}(x_{j}^{k}-x_{j}^{(0)}).$
As $k\to\infty,$ right hand side is bounded, but left hand side is not. This
also contradicts that $\|z_{2}^{k}\|=\infty.$ So with our assumption for
$\lambda^{k}\to 1,$ $\|z_{2}^{k}\|<\infty\ \text{as}\ k\to\infty,$
$\bar{\lambda}\in[0,1],$ the homotopy curve is bounded. Case 2:
$\bar{\lambda}\in[0,1],\|z_{1}^{k}\|=\infty,$ $\|z_{2}^{k}\|=\infty.$
Let $\|z_{1}^{k}\|=\infty,\|z_{2}^{k}\|=\infty.$ Then either $\exists\
i\in\\{1,2,\cdots n\\}$ such that $z_{1i}^{k}\to\infty$, $z_{2i}^{k}\to\infty$
as $k\to\infty$ or $\exists\ i,j\in\\{1,2,\cdots n\\},i\neq j$ such that
$z_{1i}^{k}\to\infty$ and $z_{2j}^{k}\to\infty$ as $k\to\infty.$ When
$z_{1i}^{k}\to\infty$, $z_{2i}^{k}\to\infty$ as $k\to\infty$ and
$\bar{\lambda}\in[0,1),$ we have,
$z_{1i}^{k}+(A^{t}z_{2}^{k})_{i}=((A+A^{t})x^{k})_{i}+q_{i}+\frac{\lambda^{k}}{(1-\lambda^{k})}(x_{i}^{k}-x_{i}^{(0)}).$
Now as $k\to\infty,$ right hand side is bounded, but left hand side is not,
which is impossible. When $\bar{\lambda}=1,$ then our assumption
$\|z_{2}^{k}\|<\infty\ \text{as}\ k\to\infty$ and the argument of the previous
theorem 3.2 contradicts that $z_{1i}^{k}\to\infty,$ $z_{2i}^{k}\to\infty$ as
$k\to\infty.$ As $k\to\infty,$ when $z_{1i}^{k}\to\infty,$
$z_{2j}^{k}\to\infty$ for $i\neq j$ as $k\to\infty$ then considering the $i$th
and $j$th component and using same argument similar to the previous theorem
3.2 and case 1, we will get a contradiction.

Thus $\Gamma_{y}^{(0)}$ is a bounded curve in $\mathcal{F}_{1}\times(0,1].$ ∎

######  Theorem 3.4:

For $y^{(0)}=(x^{(0)},z_{1}^{(0)},z_{2}^{(0)})\in\mathcal{F}_{1},$ the
homotopy equation finds a bounded smooth curve
$\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1]$ which starts from
$(y^{(0)},1)$ and approaches the hyperplane at $\lambda=0.$ As $\lambda\to 0,$
the limit set $L\times\\{0\\}\subset\bar{\mathcal{F}}_{1}\times\\{0\\}$ of
$\Gamma_{y}^{(0)}$ is nonempty and every point in $L$ is a solution of the
following system:

$\begin{split}(A+A^{t})x+q-z_{1}-A^{t}z_{2}=0\\\ Z_{1}x=0\\\ Z_{2}(Ax+q)=0.\\\
\end{split}$ (3.9)

###### Proof.

Note that $\Gamma_{y}^{(0)}$ is diffeomorphic to a unit circle or a unit
interval $(0,1]$ in view of Lemma 2.4. As
$\frac{\partial{H(y,y^{(0)},1)}}{\partial{y^{(0)}}}$ is nonsingular,
$\Gamma_{y}^{(0)}$ is diffeomorphic to a unit interval $(0,1].$ Again
$\Gamma_{y}^{(0)}$ is a bounded smooth curve by the Theorem 3.2. Let
$(\bar{y},\bar{\lambda})$ be a limit point of $\Gamma_{y}^{(0)}.$ We consider
four cases:

Case 1:

$(\bar{y},\bar{\lambda})\in\mathcal{F}_{1}\times\\{1\\}.$

Case 2:

$(\bar{y},\bar{\lambda})\in\partial{\mathcal{F}_{1}}\times\\{1\\}.$

Case 3:

$(\bar{y},\bar{\lambda})\in\partial{\mathcal{F}_{1}}\times(0,1).$

Case 4:

$(\bar{y},\bar{\lambda})\in\bar{\mathcal{F}}_{1}\times\\{0\\}.$

As the equation $H_{y^{(0)}}(y,1)=0$ has only one solution
$y^{(0)}\in\mathcal{F}_{1},$ the case $1$ is impossible. In case $2$ and $3,$
there exists a subsequence of $(y^{k},\lambda^{k})\in\Gamma_{y}^{(0)}$ such
that $x_{i}^{k}\to 0$ or $(Ax^{k}+q)_{i}\to 0$ for $i\subseteq\\{1,2,\cdots
n\\}.$ From the last two equalities of the homotopy function 3.5, we have
$z_{1}^{k}\to\infty$ or $z_{2}^{k}\to\infty.$ Hence it contradicts the
boundedness of the homotopy path by the Theorem 3.2. Therefore case $4$ is the
only possible option. Hence $\bar{y}=(\bar{x},\bar{z_{1}},\bar{z_{2}})$ is a
solution of the system $(A+A^{t})x+q-z_{1}-A^{t}z_{2}=0,\ Z_{1}x=0,\
Z_{2}(Ax+q)=0.$ ∎

######  Remark 3.1:

From the homotopy function 3.5, we obtain $\bar{z}_{1i}\bar{x}_{i}=0$ and
$\bar{z}_{2i}(A\bar{x}+q)_{i}=0\ \forall i\in\\{1,2,\cdots n\\}.$ Now
$\bar{z}_{1}$ and $\bar{z}_{2}$ can be decomposed as
$\bar{z}_{1}=\bar{w}-\Delta\bar{w}\geq 0$ and
$\bar{z}_{2}=\bar{x}-\Delta\bar{x}\geq 0,$ where $\bar{w}=A\bar{x}+q.$ It is
clear that
$\bar{w}_{i}\bar{x}_{i}=\Delta\bar{w}_{i}\bar{x}_{i}=\Delta\bar{x}_{i}\bar{w}_{i}\
\forall i\in\\{1,2,\cdots n\\}.$

We demonstrate the condition under which the homotopy functions will give the
solution of LCP$(q,A).$

######  Theorem 3.5:

The component $\bar{x}$ of $(\bar{x},\bar{z}_{1},\bar{z}_{2},0)\in
L\times\\{0\\}$ gives the solution of LCP$(q,A)$ if and only if
$\Delta\bar{x}_{i}\Delta\bar{w}_{i}=0$ or $\bar{z}_{1i}+\bar{z}_{2i}>0\
\forall i.$

###### Proof.

Suppose $\bar{x}\geq 0$ and $\bar{w}=A\bar{x}+q\geq 0$ are the solution of
LCP$(q,A).$ Then $\bar{x}_{i}\bar{w}_{i}=0$ $\forall i.$ This implies that
$\bar{x}_{i}=0$ or $\bar{w}_{i}=0$ $\forall i.$ We consider the following
three cases: Case 1: For at least one $i\in\\{1,2,\cdots n\\},$ let
$\bar{w}_{i}>0,\bar{x}_{i}=0.$ In view of Remark 3.1, this implies that
$\Delta\bar{x}_{i}=0\implies\Delta\bar{x}_{i}\Delta\bar{w}_{i}=0.$ Case 2: For
at least one $i\in\\{1,2,\cdots n\\},$ let $\bar{x}_{i}>0,\bar{w}_{i}=0.$ In
view of 3.1, this implies that
$\Delta\bar{w}_{i}=0\implies\Delta\bar{x}_{i}\Delta\bar{w}_{i}=0.$ Case 3: For
at least one $i\in\\{1,2,\cdots n\\},$ let $\bar{w}_{i}=0,\bar{x}_{i}=0.$ This
implies that either $\Delta\bar{w}_{i}\Delta\bar{x}_{i}=0$ or
$\bar{z}_{1i}+\bar{z}_{2i}>0.$ For the converse part, consider
$\Delta\bar{x}_{i}\Delta\bar{w}_{i}=0$ or $\bar{z}_{1i}+\bar{z}_{2i}>0\
\forall i\in\\{1,2,\cdots n\\}.$ Let $\forall i\in\\{1,2,\cdots n\\},\
\Delta\bar{x}_{i}\Delta\bar{w}_{i}=0$ implies either $\Delta\bar{x}_{i}=0$ or
$\Delta\bar{w}_{i}=0.$ This implies that $\bar{w}_{i}\bar{x}_{i}=0\ \forall
i\in\\{1,2,\cdots n\\}.$ Therefore $\bar{w}$ and $\bar{x}$ are the solution of
the LCP$(q,A).$ Consider $\bar{z}_{1i}+\bar{z}_{2i}>0\ \forall
i\in\\{1,2,\cdots n\\}.$ Then following three cases will arise. Case 1: Let
$\bar{z}_{1i}>0,\bar{z}_{2i}=0$ for at least one $i\in\\{1,2,\cdots n\\}.$
This implies that $\bar{x}_{i}=0$ and $\bar{w}_{i}\geq 0.$ Case 2: Let
$\bar{z}_{1i}=0,\bar{z}_{2i}>0$ for at least one $i\in\\{1,2,\cdots n\\}.$
This implies that $\bar{x}_{i}\geq 0$ and $\bar{w}_{i}=0.$ Case 3: Let
$\bar{z}_{1i}>0,\bar{z}_{2i}>0$ for at least one $i\in\\{1,2,\cdots n\\}.$
This implies that $\bar{x}_{i}=0$ and $\bar{w}_{i}=0.$ Considering the above
three cases $\bar{x},\bar{w}$ solve the LCP$(q,A).$ ∎

######  Theorem 3.6:

Suppose the matrix $(\bar{W}+\bar{X}A^{t})$ is nonsingular, where
$\bar{W}=\text{diag}(\bar{w}),$ $\bar{X}=\text{diag}(\bar{x}).$ Then $\bar{x}$
solves the LCP$(q,A).$

###### Proof.

Let the matrix $(\bar{W}+\bar{X}A^{t})$ be nonsingular. By Equation 3.9,
$\Delta\bar{w}+A^{t}\Delta\bar{x}=0$ and
$\bar{X}\Delta\bar{w}=\bar{W}\Delta\bar{x},$ where
$\bar{W}=$diag$(\bar{w})=$diag$(A\bar{x}+q).$ Now
$\bar{X}\Delta\bar{w}+\bar{X}A^{t}\Delta\bar{x}=0$ implies that
$\bar{W}\Delta\bar{x}+\bar{X}A^{t}\Delta\bar{x}=0.$ It implies that
$\Delta\bar{x}=0.$ Then $\bar{x}$ solves the LCP$(q,A).$ ∎

######  Remark 3.2:

We trace the homotopy path $\Gamma_{y}^{(0)}\subset\mathcal{F}_{1}\times(0,1]$
from the initial point $(y^{(0)},1)$ as $\lambda\to 0.$ To find the solution
of the given LCP$(q,A)$ we consider homotopy path along with other
assumptions. Let $s$ denote the arc length of $\Gamma_{y}^{(0)}.$ We
parameterize the homotopy path $\Gamma_{y}^{(0)}$ with respect to $s$ in the
following form

$H_{y^{(0)}}(y(s),\lambda(s))=0,\ y(0)=y^{(0)},\ \lambda(0)=1.$ (3.10)

Differentiating 3.10 with respect to $s,$ we obtain the following system of
ordinary differential equations with given initial values

$H^{\prime}_{y^{(0)}}(y(s),\lambda(s))\left[\begin{array}[]{c}\frac{dy}{ds}\\\
\frac{d\lambda}{ds}\\\ \end{array}\right]=0,\
\|(\frac{dy}{ds},\frac{d\lambda}{ds})\|=1,\ y(0)=y^{(0)},\ \lambda(0)=1,\
\frac{d\lambda}{ds}(0)<0,$ (3.11)

and the $y$-component of $(y(\bar{s}),\lambda(\bar{s}))$ gives the solution of
LCP$(q,A)$ for $\lambda(\bar{s})=0.$ For details, see [6].

Note that the parameter $\lambda$ is updated from the Moore-Penrose inverse of
the Jacobian matrix for tracing the homotopy path. However, this approach does
not ensure that the updated value of the parameter $\lambda$ is in $(0,1].$
Value of $\lambda$ beyond $(0,1]$ leads to a non-homotopy path. To eliminate
deviation, we propose a modification by introducing a method called ensuring
feasibility by changing step length. In this method it is necessary to check
whether $0<(\tilde{\lambda}_{i}-\hat{\lambda}_{i})<1$ and
$(\tilde{y}^{i}-\hat{y}^{i})\in\bar{\cal{F}}_{1}$ holds or not. If any of the
above-mentioned criteria fails, then the step length will be changed
appropriately using geometric series to trace the homotopy path
$\Gamma_{y}^{(0)}.$ This guarantees a homotopy continuation trajectory.

###  3.1 Algorithm

Step 0: Initialize $(y^{(0)},\lambda_{0}).$ Set $l_{0}\in(0,1).$ Choose
$\epsilon_{2}>>\epsilon_{3}>>\epsilon_{1}>0$ which are very small positive
quantity. Step 1:
$\tau^{(0)}=\xi^{(0)}=(\frac{1}{n})\left[\begin{array}[]{c}s\\\ -1\\\
\end{array}\right]$ for $i=0,$ where $n=\|\left[\begin{array}[]{c}s\\\ -1\\\
\end{array}\right]\|$ and $s=(\frac{\partial H}{\partial
y}(y^{(0)},\lambda_{0}))^{-1}(\frac{\partial
H}{\partial\lambda}(y^{(0)},\lambda_{0})).$ If $\det(\frac{\partial
H}{\partial y}(y^{(i)},\lambda_{i}))>0,$ $\tau^{(i)}=\xi^{(i)}$ else
$\tau^{(i)}=-\xi^{(i)},$ $i\geq 1.$ Set $l=0.$ Step 2: (Predictor point
calculation)
$(\tilde{y}^{(i)},\tilde{\lambda}_{i})=(y^{(i)},\lambda_{i})+a\tau^{(i)},$
where $a={l_{0}}^{l}.$ Compute
$(\hat{y}^{(i)},\hat{\lambda}_{i})=H^{\prime}_{y^{(0)}}(\tilde{y}^{(i)},\tilde{\lambda}_{i})^{+}H(\tilde{y}^{(i)},\tilde{\lambda}_{i}).$
If $0<(\tilde{\lambda}_{i}-\hat{\lambda}_{i})<1,$ go to step 3. Otherwise if
$m=\min(a,\|(\tilde{y}^{(i)},\tilde{\lambda}_{i})-(\hat{y}^{(i)},\hat{\lambda}_{i})-(y^{(i)},\lambda_{i})\|)>a_{0},$
update $l$ by $l+1,$ and recompute $(\tilde{\lambda}_{i},\hat{\lambda}_{i})$
else go to step 4. Step 3: (Corrector point calculation)
$(y^{(i+1)},\lambda_{i+1})=(\tilde{y}^{(i)},\tilde{\lambda}_{i})-(\hat{y}^{(i)},\hat{\lambda}_{i}).$
Determine the norm $r=\|H(y^{(i+1)},\lambda_{i+1})\|.$ If $r\leq 1$ and
$y^{(i+1)}>0$ go to step 5, otherwise if $a>\epsilon_{3},$ update $l$ by $l+1$
and go to step 2 else go to step 4. Step 4: If
$|\lambda_{i+1}-\lambda_{i}|<\epsilon_{2},$ then if
$|\lambda_{i+1}|<\epsilon_{2},$ then stop with the solution
$(y^{(i+1)},\lambda_{i+1}),$ else terminate (unable to find solution) else
$i=i+1$ and go to step 1. Step 5: If $|\lambda_{i+1}|\leq\epsilon_{1},$ then
stop with solution $(y^{(i+1)},\lambda_{i+1}),$ else $i=i+1$ and go to step 1.
Note that in step 2,
$H^{\prime}_{y^{(0)}}(y,\lambda)^{+}=H^{\prime}_{y^{(0)}}(y,{\lambda})^{t}(H^{\prime}_{y^{(0)}}(y,{\lambda})H^{\prime}_{y^{(0)}}(y,\lambda)^{t})^{-1}$
is the Moore-Penrose inverse of $H^{\prime}_{y^{(0)}}(y,\lambda).$ We prove
the following result to obtain the positive direction of the proposed
algorithm.

######  Theorem 3.7:

If the homotopy curve $\Gamma_{y}^{(0)}$ is smooth, then the positive
predictor direction $\tau^{(0)}$ at the initial point $y^{(0)}$ satisfies
$\det\left[\begin{array}[]{c}\frac{\partial H}{\partial
y\partial\lambda}(y^{(0)},1)\\\ \tau^{(0)^{t}}\\\ \end{array}\right]$$<0.$

###### Proof.

From the Equation 3.5, we consider the following homotopy function
$H(y,y^{(0)},\lambda)=$
$\left[\begin{array}[]{c}(1-\lambda)[(A+A^{t})x+q-z_{1}-A^{t}z_{2}]+\lambda(x-x^{(0)})\\\
Z_{1}x-\lambda Z_{1}^{(0)}x^{(0)}\\\ Z_{2}(Ax+q)-\lambda
Z_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right]=0.$ Now,
$\frac{\partial H}{\partial
y\partial\lambda}(y,\lambda)=\left[\begin{array}[]{cccc}(1-\lambda)(A+A^{t})+\lambda
I&-(1-\lambda)I&-(1-\lambda)A^{t}&P\\\ Z_{1}&X&0&-Z_{1}^{(0)}x^{(0)}\\\
Z_{2}A&0&Y&-Z_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right],$ where
$P=(x-x^{(0)})-[(A+A^{t})x+q-z_{1}-A^{t}z_{2}]$ and $Y=\text{diag}(Ax+q).$ At
the initial point $(y^{(0)},1)$
$\frac{\partial H}{\partial
y\partial\lambda}(y^{(0)},1)=\left[\begin{array}[]{cccc}I&0&0&-[(A+A^{t})x^{(0)}+q-z^{(0)}_{1}-A^{t}z^{(0)}_{2}]\\\
Z^{(0)}_{1}&X^{(0)}&0&-Z^{(0)}_{1}x^{(0)}\\\
Z^{(0)}_{2}A&0&Y^{(0)}&-Z^{(0)}_{2}(Ax^{(0)}+q)\\\ \end{array}\right].$
Let positive predictor direction be
$\tau^{(0)}=\left[\begin{array}[]{c}\kappa\\\
-1\end{array}\right]=\left[\begin{array}[]{c}(R^{(0)}_{1})^{(-1)}R_{2}^{(0)}\\\
-1\end{array}\right],$ where $R^{(0)}_{1}=\left[\begin{array}[]{ccc}I&0&0\\\
Z^{(0)}_{1}&X^{(0)}&0\\\ Z^{(0)}_{2}A&0&Y^{(0)}\\\ \end{array}\right],$
$R^{(0)}_{2}=\left[\begin{array}[]{c}-[(A+A^{t})x^{(0)}+q-z^{(0)}_{1}-A^{t}z^{(0)}_{2}]\\\
-Z^{(0)}_{1}x^{(0)}\\\ -Z^{(0)}_{2}(Ax^{(0)}+q)\\\ \end{array}\right]$ and
$\kappa$ is a $n\times 1$ column vector.
Hence, $\det\left[\begin{array}[]{c}\frac{\partial H}{\partial
y\partial\lambda}(y^{(0)},1)\\\ \tau^{(0)^{t}}\\\ \end{array}\right]$
$=\det\left[\begin{array}[]{cc}R^{(0)}_{1}&R^{(0)}_{2}\\\
(R^{(0)}_{2})^{t}(R^{(0)}_{1})^{(-t)}&-1\\\ \end{array}\right]$
$=\det\left[\begin{array}[]{cc}R^{(0)}_{1}&R^{(0)}_{2}\\\
0&-1-(R^{(0)}_{2})^{t}(R^{(0)}_{1})^{(-t)}(R^{(0)}_{1})^{(-1)}R_{2}^{(0)}\\\
\end{array}\right]\\\ $
$=\det(R^{(0)}_{1})\det(-1-(R^{(0)}_{2})^{t}(R^{(0)}_{1})^{(-t)}(R^{(0)}_{1})^{(-1)}R_{2}^{(0)})$
$=-\det(R^{(0)}_{1})\det(1+(R^{(0)}_{2})^{t}(R^{(0)}_{1})^{(-t)}(R^{(0)}_{1})^{(-1)}R_{2}^{(0)})$
$=-\prod_{i=1}^{n}x^{(0)}_{i}y^{(0)}_{i}\det(1+(R^{(0)}_{2})^{t}(R^{(0)}_{1})^{(-t)}(R^{(0)}_{1})^{(-1)}R_{2}^{(0)})<0.$
So the positive predictor direction $\tau^{(0)}$ at the initial point
$y^{(0)}$ satisfies $\det\left[\begin{array}[]{c}\frac{\partial H}{\partial
y\partial\lambda}(y^{(0)},1)\\\ \tau^{(0)^{t}}\\\ \end{array}\right]<0.$ ∎

######  Remark 3.3:

We conclude from the Theorem 3.7 that the positive tangent direction $\tau$ of
the homotopy path $\Gamma_{y}^{(0)}$ at any point $(y,\lambda)$ be negative
and it depends on det$(R_{1}),$ where
$R_{1}=\left[\begin{array}[]{ccc}(1-\lambda)(A+A^{t})+\lambda
I&-(1-\lambda)I&-(1-\lambda)A^{t}\\\ Z_{1}&X&0\\\ Z_{2}A&0&Y\\\
\end{array}\right].$

##  4 Numerical Examples

In this section we consider some examples of LCP$(q,A)$ to demonstrate the
effectiveness of our proposed algorithm. Note that Example 4.3 \- 4.7 are not
processable by the algorithms given in Yu et al. [21], Xu et al. [20], Zhao et
al. [22]. Even these examples are not processable by Lemke’s algorithm [4] as
well. We show that the proposed algorithm can process these examples to find
the solution.

######  Example 4.1:

Consider $A=\left[\begin{array}[]{cc}-1&2\\\ 3&-1\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}1\\\ -0.5\\\ \end{array}\right].$ Note that $A$ is
an $N$-matrix. It is solvable by the homotopy method with the homotopy
function 3.2, proposed by Zhao et al. [22]. Now we show that our proposed
homotopy function 3.5 also solves the linear complementarity problem with
$N$-matrix. Now choose the initial point
$x^{(0)}=\left[\begin{array}[]{c}0.4\\\ 0.1\\\ \end{array}\right],\
{z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right]$ and
${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right].$ Using
the proposed algorithm we get the optimal solution of the homotopy function
3.5 after 20 iterations and the solution is given by
$(\bar{y},\bar{\lambda})=(1,0,0,2.5,1,0,0).$ Therefore
$\bar{x}=\left[\begin{array}[]{c}1\\\ 0\\\ \end{array}\right]$ solves
LCP$(q,A).$ The homotopy path shown in Figure 1(a) illustrates the convergence
with respect to the solution vector $x$ and $\lambda$.

######  Example 4.2:

Let $A=\left[\begin{array}[]{cc}1&-1\\\ -1&1\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}-0.5\\\ 2\\\ \end{array}\right].$ It is easy to
show that $A$ is a $PSD$-matrix. It is solvable by the homotopy method with
the homotopy function 3.1, proposed by Yu et al.[21] . Now we show that our
proposed homotopy function 3.5 also solves the linear complementarity problem
with $PSD$-matrix. Now choose the initial point
$x^{(0)}=\left[\begin{array}[]{c}2\\\ 1\\\ \end{array}\right],$
${z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right]$ and
${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right].$ Using
the proposed algorithm we obtain
$(\bar{y},\bar{\lambda})=(0.5,0,0,1.499,0.499,0,0,0)$ after 22 iterations.
Note that $\bar{x}=\left[\begin{array}[]{c}0.5\\\ 0\\\ \end{array}\right]$ is
the solution of LCP$(q,A).$ The homotopy path shown in Figure 1(b) illustrates
the convergence with respect to the solution vector $x$ and $\lambda$.

Now we show that our proposed homotopy function 3.5 can solve LCP$(q,A)$ with
singular matrix $A$ satisfying some conditions.

######  Example 4.3:

Consider $A=\left[\begin{array}[]{cc}1&1\\\ 0&0\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}-1\\\ 1\\\ \end{array}\right].$ Note that $A$ is a
singular $Q_{0}$-matrix. Now choose the initial point
$x^{(0)}=\left[\begin{array}[]{c}1\\\ 0.2\\\ \end{array}\right],\
{z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right]$ and
${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ \end{array}\right].$ Using
the proposed algorithm we get the optimal solution of the homotopy function
3.5 after 15 iterations and the solution is given by
$(\bar{y},\bar{\lambda})=(1,0,0,1,1,0,0).$ Therefore
$\bar{x}=\left[\begin{array}[]{c}1\\\ 0\\\ \end{array}\right]$ solves
LCP$(q,A).$ The homotopy path shown in Figure 1(c) illustrates the convergence
with respect to the solution vector $x$ and $\lambda$.

######  Example 4.4:

Let $A=\left[\begin{array}[]{ccc}-1&2&1\\\ 1&-0.50&-0.25\\\ -0.50&-1&-1\\\
\end{array}\right]$ and $q=\left[\begin{array}[]{c}-0.25\\\ -0.10\\\ 3\\\
\end{array}\right].$ It is easy to show that $A$ is not an $N$-matrix. Now
choose the initial point $x^{(0)}=\left[\begin{array}[]{c}2.3\\\ 1\\\ 0.7\\\
\end{array}\right],$ ${z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\
\end{array}\right]$ and ${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\
\end{array}\right].$ Using the proposed algorithm we obtain
$(\bar{y},\bar{\lambda})=(1.8333,0,2.0833,0,1,2125,0,1.8333,0,2.0833,0)$ after
17 iterations. Note that $\bar{x}=\left[\begin{array}[]{c}1.8333\\\ 0\\\
2.0833\\\ \end{array}\right]$ is the solution of LCP$(q,A).$ The convergence
of the homotopy function is shown in the Figure 1(d). The first, second and
third component of $x$ is represented by data1, data2 and data3 respectively.

######  Example 4.5:

Let $A=\left[\begin{array}[]{ccc}1&-2&0\\\ 0&1&-2\\\ -2&0&1\\\
\end{array}\right]$ and $q=\left[\begin{array}[]{c}-1\\\ 1\\\ 7\\\
\end{array}\right].$ It is easy to show that $A$ is an almost $C_{0}$ matrix.
Now choose the initial point $x^{(0)}=\left[\begin{array}[]{c}3\\\ 0.5\\\
0.5\\\ \end{array}\right],\ {z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\
1\\\ \end{array}\right]$ and ${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\
1\\\ \end{array}\right].$ Using the proposed algorithm we obtain is
$(\bar{y},\bar{\lambda})=(1,0,0,0,1,5,1,0,0,0)$ after $24$ iterations. Note
that $\bar{x}=\left[\begin{array}[]{c}1\\\ 0\\\ 0\\\ \end{array}\right]$
solves LCP$(q,A),$ which is a degenerate solution. The convergence of the
homotopy function is shown in the Figure 1(e). The first, second and third
component of $x$ is represented by data1, data2 and data3 respectively.

######  Example 4.6:

Let $A=\left[\begin{array}[]{cccc}-1&1&1&1\\\ 1&0&0&0\\\ 1&0&0&-1\\\
1&0&-1&0\\\ \end{array}\right]$ and $q=\left[\begin{array}[]{c}-1\\\ 1\\\
-1\\\ 1\\\ \end{array}\right].$ $A$ is a $Q$-matrix by [12]. Now choose the
initial point $x^{(0)}=\left[\begin{array}[]{c}4\\\ 4\\\ 1\\\ 1\\\
\end{array}\right],\ {z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\ 1\\\
\end{array}\right]$ and ${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\
1\\\ \end{array}\right].$ We apply our proposed algorithm to this LCP$(q,A)$
and after 17 iterations we get the approximate optimal solution of the
homotopy function 3.5, which is
$(\bar{y},\bar{\lambda})=(1,0,2,0,0,2,0,0,1,0,2,0,0).$ Note that
$\bar{x}=\left[\begin{array}[]{c}1\\\ 0\\\ 2\\\ 0\\\ \end{array}\right]$
solves LCP$(q,A),$ which gives a degenerate solution. The convergence of the
homotopy function is shown in the Figure 1(f). Data1, data2, data3 and data4
represent the first, second, third and fourth component of $x$ respectively.

######  Example 4.7:

Consider $A=\left[\begin{array}[]{ccccc}0&0&0&1&2\\\ 0&0&-1&-1&2\\\
0&-1&0&-1&1\\\ 1&-1&-1&0&0\\\ 2&1&0&0&0\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}-2\\\ -1\\\ 7\\\ 2\\\ -1\\\ \end{array}\right].$
$A$ is an $N_{0}$-matrix of exact order $2.$ Now choose the initial point
$x^{(0)}=\left[\begin{array}[]{c}3\\\ 1\\\ 1\\\ 1\\\ 3\\\ \end{array}\right],$
${z_{1}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\ 1\\\ 1\\\
\end{array}\right]$ and ${z_{2}}^{(0)}=\left[\begin{array}[]{c}1\\\ 1\\\ 1\\\
1\\\ 1\\\ \end{array}\right].$ Using the proposed algorithm, we obtain the
approximate optimal solution of the homotopy function 3.5,
$(\bar{y},\bar{\lambda})=(0.5,0,0,0,1,0,1,8,2.5,0,0.5,0,0,0,1,0)$ after 27
iterations. Note that $\bar{x}=\left[\begin{array}[]{c}0.5\\\ 0\\\ 0\\\ 0\\\
1\\\ \end{array}\right]$ solves LCP$(q,A).$ The convergence of the homotopy
function is shown in the Figure 1(g). Data1, data2, data3, data4 and data5
represent the first, second, third, fourth and fifth component of $x$
respectively.

(a) Example 4.1

(b) Example 4.2

(c) Example 4.3

(d) Example 4.4

(e) Example 4.5

(f) Example 4.6

(g) Example 4.7

Figure 1: Homotopy path for the LCP$(q,A)$ to show the convergence

##  5 Conclusion

In this study, we consider an interior point homotopy path to solve linear
complementarity problem. We propose a new homotopy function to solve
LCP$(q,A)$ with various type of matrices $A$ which are not processable by
Lemke’s algorithm and existing homotopy functions. We prove that the smooth
curve for the proposed homotopy function is bounded and also converges. We
show that there is an if and only if condition to find the solution of
LCP$(q,A)$ from the solution of our introduced new homotopy function. To
ensure a homotopy continuation trajectory we introduce a new scheme of
choosing step length. Mathematically we find the positive tangent direction of
the homotopy path. Several numerical examples are provided to demonstrate the
processability of larger classes of LCP$(q,A).$

##  6 Acknowledgment

The author A. Dutta is thankful to the Department of Science and Technology,
Govt. of India, INSPIRE Fellowship Scheme for financial support. We
acknowledge Mr. Abhirup Ganguly(M.Tech 2017-2019, ISI Kolkata) for his
contribution.

## References

  * [1] Liping Chen, Lixing Han, and Liangmin Zhou.  Computing tensor eigenvalues via homotopy methods.  SIAM Journal on Matrix Analysis and Applications, 37(1):290–319, 2016.
  * [2] Shui Nee Chow, John Mallet-Paret, and James A Yorke.  Finding zeroes of maps: homotopy methods that are constructive with probability one.  Mathematics of Computation, 32(143):887–899, 1978.
  * [3] AK Das.  Properties of some matrix classes based on principal pivot transform.  Annals of Operations Research, 243(1):375–382, 2016.
  * [4] AK Das, R Jana, and Deepmala.  Finiteness of criss-cross method in complementarity problem.  In International Conference on Mathematics and Computing, pages 170–180. Springer, 2017.
  * [5] B Curtis Eaves and Romesh Saigal.  Homotopies for computation of fixed points on unbounded regions.  Mathematical Programming, 3(1):225–237, 1972.
  * [6] Xiaona Fan, Tingting Xu, Furong Gao, et al.  Solving nonlinear complementarity problem by a smoothing homotopy method.  Taiwanese Journal of Mathematics, 19(1):51–63, 2015.
  * [7] Michael C Ferris and Jong-Shi Pang.  Engineering and economic applications of complementarity problems.  Siam Review, 39(4):669–713, 1997.
  * [8] Lixing Han.  A homotopy method for solving multilinear systems with ${M}$-tensors.  Applied Mathematics Letters, 69:49–54, 2017.
  * [9] R Jana, AK Das, and A Dutta.  On hidden ${Z}$-matrix and interior point algorithm.  Opsearch, pages 1–9, 2019.
  * [10] R Jana, A Dutta, and AK Das.  More on hidden ${Z}$-matrices and linear complementarity problem.  Linear and Multilinear Algebra, pages 1–10, 2019.
  * [11] Michael M Kostreva and Malgorzata M Wiecek.  Linear complementarity problems and multiple objective programming.  Mathematical Programming, 60(1-3):349–359, 1993.
  * [12] SK Neogy and AK Das.  On almost type classes of matrices with ${Q}$-property.  Linear and Multilinear Algebra, 53(4):243–257, 2005.
  * [13] SK Neogy and AK Das.  Principal pivot transforms of some classes of matrices.  Linear algebra and its applications, 400:243–252, 2005.
  * [14] Jong-Shi Pang.  Complementarity problems.  In Handbook of global optimization, pages 271–338. Springer, 1995\.
  * [15] Xiuyu Wang and Xingwu Jiang.  A homotopy method for solving the horizontal linear complementarity problem.  Computational and Applied Mathematics, 33, 04 2013.
  * [16] Layne T Watson.  Globally convergent homotopy methods: a tutorial.  Applied Mathematics and Computation, 31:369–396, 1989.
  * [17] Layne T Watson and Raphael T Haftka.  Modern homotopy methods in optimization.  Computer Methods in Applied Mechanics and Engineering, 74(3):289–305, 1989.
  * [18] Layne Terry Watson.  A variational approach to the linear complementarity problem.  PhD thesis, University of Michigan, 1974.
  * [19] Xiuyu Wang, Xingwu Jiang, and Qinghuai Liu.  Interior point method for solving linear complementarity problems with ${P_{*}}$-matrix.  In 2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering, volume 1, pages 39–42, Aug 2010.
  * [20] Junyan Xu, Q. Liu, and Zhuang Miao.  A infeasible interior point homotopy method for solving linear complementarity problem.  In 2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE), volume 1, pages V1–417–V1–420, Aug 2010.
  * [21] Qian Yu, Chongchao Huang, and Xianjia Wang.  A combined homotopy interior point method for the linear complementarity problem.  Applied Mathematics and Computation, 179(2):696–701, 2006.
  * [22] X Zhao, S Zhang, and Q Liu.  A combined homotopy interior point method for the linear complementarity problem.  Journal of Information and Computational Science, 7:1589–1594, 07 2010.