text:
\begin{document}

\maketitle

\begin{abstract}

In this paper, we present a new smoothing approach to solve general  nonlinear complementarity problems.  Under  the $P_0$ condition on the original problems, we prove some existence and convergence results . We also present an error estimate under a new and general monotonicity condition. The numerical tests conÞrm the efÞciency of our proposed methods.
\end{abstract}

\noindent

\noindent
{\sl Key words }:
Nonlinear complementarity problem; smoothing function; optimal trajectory; asymptotic analysis; error estimate.\\
{\sl Mathematics Subject Classification (2000)}:
 90C33,

\noindent

\section{Introduction}\label{intro}
\setcounter{equation}{0}

Consider the nonlinear complementarity problem (NCP), which is to find
a solution of the system :
\begin{equation}\label{complem}
x\geq 0, F(x)\geq 0\quad {\rm and} \quad  x^{\top} F(x)=0,
\end{equation}
where  $F:\R^n\longrightarrow \R^n$ is a continuous function that satisfies some additional assumptions to be precise later.\\

This problem has a number of important applications in operations research, economic equilibrium
problems and in the engineering sciences \cite{FP} . It has been extensively studied and the number of proposed solution methods  is enormous eg  (\cite{FMP}  and references therein).
There are almost three  different classes of methods: equation-based methods (smoothing) , merit functions and projection-type methods.\\
Our goal in this paper is to present  new and very simple  smoothing and approximation schemes to solve NCPs and to produce   efficient  numerical methods. These  functions are based on penalty functions for convex programs.\\

Almost all the solution methods consider at least the following  important and standard condition on the mapping $F$ ( monotonicity)

: for any $x, y\geq 0$,

\begin{equation}\label{complem}
( x-y)^{\top}(F(x)-F(y))\geq 0.
\end{equation}
We will assume that
$$F {\rm\  is\  a\quad } (P_0){\rm -function }\leqno{(H0)}$$
to prove the convergence of our approach. This assumption is weaker than monotonicity.\\
We recall the following definitions of $(P_0)$-  and $(P)$ -functions.
We say that     $F:\R^n\rightarrow \R^n$ is a $(P_0)$-function if
$$
\max_{i: x_i\neq y_i} (x-y)_i(F_i(x)-F_i(y))\geq 0,\quad x,y\in \R^n,
$$
and $F$ is a $(P)$-function if
$$
\max_{i: x_i\neq y_i} (x-y)_i(F_i(x)-F_i(y))> 0 ,\quad x,y\in \R^n.
$$
We start with an easy result. We define   component-wise  the function
$F_{min}(x):=\min(x,F(x))$ with   $F_{{min},i}(x)=\min(x_i,F_i(x))$ for any $i:1...n$.

This function possesses the same properties as $F$

\begin{lem}
Assume that $F$ is a $(P_0)$ (respectively $(P)$)-function then $F_{min}(x):=\min (x,F(x))$ is also
$(P_0)$ (respectively $(P)$)-function.
\end{lem}

\proof
Assume that  $F$ is a $(P_0)$-function. For  any $x,y\in\R^n$, there exists $i $ such that $x_i\neq y_i$ and $(x_i-y_i)(F_i(x)-F_i(y))\geq 0$.  We can assume $x_i>y_i$. Then
$
F_i(x)\geq F_i(y)
$.
So
$
F_i(x)\geq \min(y_i,F_i(y))
$ and $x_i\geq \min(y_i,F_i(y))$.
Then
$
 \min(x_i,F_i(x))
\geq \min(y_i,F_i(y))
$.  Thus
$(x_i-y_i)(F_{min,i}(x)-F_{min,i}(y))\geq 0
$.
Then $F_{min}$ is a  $(P_0)$-function.
The proof is analogue if $F$ is a $(P)$-function.
\findemo
\\

An other ssumption that will be useful in our approach is that the   solution set is compact
$${\mathcal Z}:=\{x\geq 0, F(x)\geq 0,  x^{\top} F(x)=0\} {\rm\  is\  nonempty\  and\  compact. } \leqno{(H1)}$$

\begin{rem}
Under some sufficient conditions, the assumption (H1) is satisfied.  Note that this set may be empty, for instance if $-F(x)>0$ for any $x\in \R^n$ even when $F$ is continuous and monotone. Such counter-example is easy to show,  for example :$F(x)=\frac{-1}{x+1}$ for $x\geq 0$ and $F(x)=-1$ if $x\leq 0$.
\end{rem}
 We give in the following lemma an  example of sufficient condition on the mapping $F$ to  insure $(H1)$.
 \\

\begin{lem}
Assume that $F$ is continuous and monotone on $\R^n$. Moreover, we assume that:
\begin{enumerate}
\item
There exits $y\in\R^n$ with
$F(y)>0$ .
\item
There exist constants  $c, M>0$ such that
for any $x$, $\vert x\vert_1 \geq M$,
$\vert F(x)\vert \leq c \vert x\vert_1$ with $c<m(F(y))/\vert y\vert $ where
$m(F(y))=\min_i F_i(y)$.
\end{enumerate}

Let $\varepsilon>0$.
Then ${\mathcal Z}_{\varepsilon}:=\{x\geq 0, F(x)\geq 0,  x^{\top} F(x)
\leq \varepsilon
\}$ is compact (may be empty).
\end{lem}

\proof
Since $F$ is continuous,  the set ${\mathcal Z}_{\varepsilon}$ is closed. To show the compactness, it is enough to show the boundedness of ${\mathcal Z}$. The monotonicity property implies for any $x\in {\mathcal Z}_{\varepsilon}$:
$$
 x^{\top} F(y)\leq  x^{\top} F(x)-y^{\top} F(x)+y^{\top} F(y)
\leq
 \vert y\vert \vert F(x)\vert +\vert y\vert \vert F(y)\vert +{\varepsilon}.
$$
Let $x\in  {\mathcal Z}_{\varepsilon}$ and $\vert x\vert_1 \geq M$,
then
$$
m(F(y)) \vert x\vert_1\leq
\sum_{i=1}^n x_i F_i(y)\leq
c  \vert y\vert  \vert x\vert_1
+\vert y\vert \vert F(y)\vert
+{\varepsilon}.
$$
Thus
$$
(m(F(y))- c  \vert y\vert  )
\vert x\vert_1
\leq \vert y\vert \vert F(y)\vert +{\varepsilon}.
$$

Since $\kappa := m(F(y)) -c  \vert y\vert>0$, we get
$$
\vert x\vert_1
\leq (\vert y\vert \vert F(y)\vert +{\varepsilon})\vert/\kappa.
$$
Thus
$$
\vert x\vert_1
\leq
\max( M,(\vert y\vert \vert F(y)\vert +{\varepsilon})/\kappa).
$$

So ${\mathcal Z}_{\varepsilon}$ is bounded, hence compact.
\findemo
\\
\begin{rem} All   continuous monotone bounded function $F$  satisfying  the  condition (1) also satisfies condition (2)  of the lemma.
Indeed there exists $R>0$ such that for any $M>0$ and any $x$ such that $\vert x\vert_1 \geq M$,
$$
\vert F(x)\vert \leq R\leq \frac{R}{M} \vert x\vert_1
$$
Let $c:=\frac{R}{M}$, it enough to choose $M$ large enough such that $c< m(F(y))/\vert y\vert $.
\\

This condition (2) allows us to consider a family of functions  $F$ satisfying some sub-linear growth  at infinity.
\end{rem}

The organization of the paper is as follows. In Section 2, we define the smoothing functions  and the approximation technique. In Section 3, we  give a detailed discussion of the properties of the smoothing function and the approximation scheme. Section 4 is devoted to the proof of convergence and the error estimate. Numerical examples and results will be reported  in the last section.

\section{The smoothing  functions}

We start our discussion by introducing the function $\theta$ with the following properties (See \cite{ACH,Had}).
Let $\theta:\R\rightarrow (-\infty,1)$ be an increasing continuous function such that
$\theta(t)<0$ if $t<0$, $\theta(0)=0$ and $\theta(+\infty)=1$.
For instance $\theta^{(1)}(t)=\frac{t}{t+1}, t\geq 0$ and  $\theta^{(1)}(t)=t$ if  $t<0$,
$\theta^{(2)}(t)=1-e^{-t},\, t\in \R$.

This function "detects" if $t=0$ or $t>0$ i.e. if $t\geq 0$ in a "continuous way".
The ideal function will be the function $\theta^{(0)}(-\infty)=-\infty$, $\theta^{(0)}(t)<0$ if $t<0$, $\theta^{(0)}(0)=0$ and
$\theta^{(0)}(t)=1$ for $t>0$. But doing so, at least a discontinuity at $t=0$ is introduced.  We smooth this ideal function $\theta^{(0)}$ by introducing  $\theta_r(t)=\theta(t/r)$ for $r>0$.
\\
So that,  $ \theta_r(0)=0$,  $\forall r>0$, $\lim_{r\rightarrow 0^+} \theta_r(t)=1$  for
all $t>0$ and $\lim_{r\rightarrow 0^+} \theta_r(t)=\inf  \theta=\theta(-\infty)<0$ if $t<0$. So   $\lim_{r\rightarrow 0^+} \theta_r$ behaves essentially as   $\theta^{(0)}$. Moreover, note that the  function  $\theta_r$corresponding differentiates quantitatively the positive values of t: if $0<t_1<t_2$ then $0<\theta_r(t_1)<\theta_r(t_2)$ and conversely.
\\

Now, let's  consider the following equation on the one-dimensional case. Let $s,t\in \R^+$ be such that

\begin{equation}\label{theta}
\theta_r(s)+\theta_r(t)=1.
\end{equation}

For instance, let's take $\theta^{(1)}$.
The equality (\ref{theta})  is  then equivalent to
$$st=r^2$$
So, when $r$ tends to $0$, we simply get   $st=0$. This limit case applied with $s=x\in\R^+$ and $t=F(x)\in\R^+$ gives  our relation $xF(x)=0$. Our approximation is
$x^{(r)}F(x^{(r)})=r^2$.
So, for  general $\theta$, the aim of this paper is to produce, for each $r\in(0,r_0)$, a solution $x=x^{(r)}\in \R^n$ with $x^{(r)}\geq 0$ such that
$F(x^{(r)})\geq 0$ and

\begin{equation}\label{thetadim}
\theta_r(x)+\theta_r(F(x))=1.
\end{equation}

and to show the compactness of the set $\{x^{(r)}, r\in(0,r_0)\}$. Hence by taking a subsequence of $x^{(r)}$, we expect to converge to a solution of $xF(x)=0$.
The equation just above  has to be interpreted, in the multidimensional case, as
$$
\theta_r(x_i^{(r)})+\theta_r(F_i(x^{(r)}))=1, \qquad i:1...n.
$$

Note that the relation (\ref{thetadim})  is symmetric in $x$ and $F(x)$ and it can be seen as a fixed point problem for the function
$F_{r,\theta}(x)$ defined just
below.
 Indeed,
(\ref{thetadim}) is equivalent to
$$
x= \theta_r^{-1}\left(1-\theta_r(F(x))\right)=r \theta^{-1}\left(1-\theta(F(x)/r)\right)
= :
F_{r,\theta}(x)
$$
and also, by  symmetry of the equation  (\ref{theta}) (if any), we have the relations:
$$
F(x)= \theta_r^{-1}\left(1-\theta_r(x)\right)=r \theta^{-1}\left(1-\theta(x/r)\right).
$$

This fact may be of some interest for numerical methods.
The  speed of convergence to a solution can be compared  for different choices of $\theta$.
\\

Now, we  propose another way to approximate a  solution of the (NC) problem.
\\

Let $\psi_r(t)=1-\theta_r(t)$.
The relation (\ref{thetadim})  is equivalent to
$$
\psi_r(x)+\psi_r\left(F(x)\right)=1=\psi_r(0).
$$
Hence,  the relation can be written as
$$
\psi_r^{-1}[\psi_r(x)+\psi_r(F(x))]=0.
$$
Let $\psi=\psi_1=1-\theta$. thus, we have
$$
r\psi^{-1}\left[\psi\left(\frac{x}{r}\right)+\psi\left(\frac{F(x)}{r}\right)\right]=0.
$$
For the sequel, we set
$$
G_r(x,y):=
r\psi^{-1}\left[\psi\left(\frac{x}{r}\right)+\psi\left(\frac{y}{r}\right)\right].
$$

First, we characterize solutions $(x,y)$  of $G_r(x,y)=0$
when $\theta$ satisfies some conditions independent of $F$.
\\

Let $0<a<1$. We say that $\theta$ satisfies
$(H_a)$ if there exists   $s_a>0$ such that, for all  $s\geq s_a$,
$$
\frac{1}{2}+\frac{1}{2}\theta(as)\leq \theta(s).
$$
This condition is equivalent to
$$
 \psi(s)\leq \frac{1}{2}  \psi(as),\quad s\geq s_a.
$$

{\bf
Two  examples}:

\begin{enumerate}
\item
Let  $\theta^{(1)}(t)=\frac{t}{t+1}, t\geq 0$ and  $\theta^{(1)}(t)=t$ if  $t<0$ (But the case  $t<0$ is not useful in this discussion).  Then
$\psi^{(1)}(t)=\frac{1}{t+1}$ if $t\geq 0$ and $\psi^{(1)}(t)=1-t$ if $t<0$.
The condition $(H_a)$ is only satisfied with $0<a<1/2$ and $s_a\geq \frac{1}{1-2a}$.
\item
Let $\theta^{(2)}(t)=1-e^{-t},\, t\in \R$.
Then $\psi^{(2)}(t)=e^{-t}$  satisfies the condition $(H_a)$ for any $0<a<1$ with
$s_a=\frac{\ln 2}{1-a}$.
\end{enumerate}

Note that these functions $\psi$ do not satisfies the condition $(H_a)$ in the same range for $a$. This has some consequence for the limite of $G_r(s,t)$ as $r$ goes to zero (See Th.\ref{allha} and  Example 1 after the proof of Th.\ref{zero}).
\\

\begin{Th}\label{zero}
Assume that for some $0<a<1$, the condition  $(H_a)$ is satisfied for $\theta$. Let $s,t\in \R$.
 The two following statements are equivalent

\begin{enumerate}
\item
$\lim_{r\rightarrow 0}G_r(s,t)=0$
\item
$\min(s,t)=0$.
\end{enumerate}
\end{Th}

The statement $\min(s,t)=0$ is equivalent to
$s=0\leq t$ or $t=0\leq s$. This is the reason why we expect   a solution of the (NC) problem
with $s=x_i$ and $t=F_i(x)$ by considering the function $G_r$.
\\

\proof
We asserts that
$
G_r(s,t)\leq \min(s,t)
$ for any $r>0$ and $s,t\in\R$.
Indeed,  assume that $s\leq t$ i.e. $s=\min(s,t)$.
 Since $\psi \geq 0$,
$$
\psi(s/r)\leq  \psi(s/r)+\psi(t/r)
$$
So, by the fact that $\psi$ is non-increasing,
$$
s/r\geq  \psi^{-1}\left( \psi(s/r)+\psi(t/r)\right).
$$
Then
$$G_r(s,t)\leq s.$$
The assertion is proved.
We now prove (1) implies (2). Let $s,t\in \R$,
we have assumed that
$\lim_{r\rightarrow 0}G_r(s,t)=0$ thus $ \min(s,t)\geq 0$.
By symmetry, we can suppose  that
$s= \min(s,t)$.  We deduce the result by contradiction.
Assume that $s>0$. Since $\psi$ is non-increasing,
$$
 \psi(s/r)+\psi(t/r)\leq 2 \psi(s/r).
 $$
 For $r$ small enough,
 $2 \psi(s/r)\leq  \psi(as/r)$ because $s/r$ goes to infinity.
 Whence
 $$
 \psi(s/r)+\psi(t/r)\leq  \psi(as/r).
 $$
 Again since $\psi$ is non-increasing,
 $$
as/r\leq  \psi^{-1}\left( \psi(s/r)+\psi(t/r)\right).
$$
or equivalently ($r$ small enough),
$$
s\leq a^{-1}G_r(s,t).
$$
By assumption, $\lim_{r\rightarrow 0}G_r(s,t)=0$ then $s\leq 0$.  Contradiction. So $s=0$
and the implication is proved.
\\

We now prove the converse.
Assume
$ s=\min(s,t)= 0$. Then
$ G_r(s,t)=r\psi^{-1}\left( 1+\psi(t/r)\right)$ due to  $\psi(0)=1$.
If $t=0$, $ \lim_{r\rightarrow 0}G_r(s,t)=\lim_{r\rightarrow 0}r\psi^{-1}(2)=0.$
If $t>0$,
$\lim_{r\rightarrow 0}\psi(t/r)=1-\lim_{r\rightarrow 0}\theta(t/r)=0
$. Thus
$ \lim_{r\rightarrow 0}G_r(s,t)=\lim_{r\rightarrow 0}r\psi^{-1}(1)=0$ by continuity of $\psi^{-1}$.
The proof is completed.
\\

{\bf Two examples}:

\begin{enumerate}
\item
Let  $\theta^{(1)}(t)=\frac{t}{t+1}, t\geq 0$ and  $\theta^{(1)}(t)=t$ if  $t<0$.  Then
$\psi^{(1)}(t)=\frac{1}{t+1}$ if $t\geq 0$ and $\psi^{(1)}(t)=1-t$ if $t<0$. For $s>0$ and $t>0$ such that $\frac{1}{s}+\frac{1}{t}\leq \frac{1}{r}$, then
$$
 G_{1,r}(s,t)=\frac{st-r^2}{s+t+2r}.
 $$
 Note that the denominator is not zero when $s,t$ are positive even in the case $s=t=0$. This is interesting fact for numerical simulation.
\\

In that case
  $\lim_{r\rightarrow 0} G_{1,r}(s,t)=\frac{st}{s+t}$.
  Note that this is not   $\min(s,t)$. We can easily prove that
    $\lim_{r\rightarrow 0} G_{1,r}(s,t)=0$ if $s=0$ and $t>0$ or $t=0$ and $s>0$.
    \\

 If $t,s> 0$, the derivative in $r$ of $ G_{1,r}(s,t)$ is
$$
\frac{-2br-2r^2-2a}{(b+2r)^2}\leq 0
$$
 with $a=st$ and $b=s+t$.
 So $ G_{1,r}(s,t)$ is non-increasing in $r$ for fixed $s,t>0$. Since  $G_{1,r}(s,t)\leq \min(s,t)$
 then   $\lim_{r\rightarrow 0} G_{1,r}(s,t)$ always exists.

\item
Let $\theta^{(2)}(t)=1-e^{-t},\, t\in \R$.
Then $\psi^{(2)}(t)=e^{-t}$ and
$$
 G_{2,r}(s,t)=-r\log (e^{-s/r}+e^{-t/r}).
 $$
for any $s,t\in \R$,
$$
\lim_{r\rightarrow 0} G_{2,r}(s,t)=\min(s,t).
$$
Indeed,  if $s=\min(s,t)$ then  $-r\log 2+s\leq G_{2,r}(s,t)$ because
$ e^{-s/r}+e^{-t/r}\leq 2  e^{-s/r}$.
Thus
$$
-r\log 2+\min(s,t)\leq  G_{2,r}(s,t)\leq \min(s,t).
$$
So, we deduce the expected limit. The assertion of Th.\ref{zero} is clealy satisfied.\\
\end{enumerate}

It is an easy exercice to show that these  two functions $ G_{1,r} $ and  $G_{2,r}$ and there limit function $G_{1,0}, G_{2,0}$  are concave functions on $(\R^2)^+$.

(Pb:  Is  it always true for any $\theta$?)
\\

Now, we focus on the case where  $\theta$ satisfies  $(H_a)$  for all $a\in (0,1)$.

\begin{Th}\label{allha}
Assume that $\theta$ satisfies  $(H_a)$ is for all $a\in (0,1)$.
Then for any $s,t>0$,
$$
\lim_{r\rightarrow 0}G_r(s,t)=\min(s,t).
$$
\end{Th}

\proof
We use essentially the arguments of Th.\ref{zero}.
We have seen in the course of the proof  that
$
G_r(s,t)\leq min(s,t)
$ for any $r>0$, $s,t\in \R$ and any $\psi$.
\\

Now  we fixe $s,t>0$ and assume that $s=\min(s,t)>0$.
For the lower bound, we have for any fixed $0<a<1$,
since $\psi$ is non-increasing,
$$
 \psi(s/r)+\psi(t/r)\leq 2 \psi(s/r)\leq \psi(as/r)
 $$
 for any $r>0$ such that $s/r\geq s_a$.
Again by monotonicity of   $\psi$,
 $$
as/r\leq  \psi^{-1}\left( \psi(s/r)+\psi(t/r)\right).
$$
So, for any   $0<a<1$, there exists $r_a>0$ such that, for any $0<r<r_a$,
$$
as\leq G_r(s,t).
$$
We deduce, for any $0<a<1$,
$$
a\min(s,t)=as\leq \liminf_{r\rightarrow 0}G_r(s,t)
\leq \limsup_{r\rightarrow 0}G_r(s,t)
\leq \min(s,t)
$$
We get the result with $a\rightarrow 1$. This concludes the proof.
\\

Note that $\theta^{(1)}$ doesn't satisfy the condition $(H_a)$ for any $0<a<1$. We have seen above that $\lim_{r\rightarrow0}G_r(s,t)=\frac{st}{s+t},\; (s,t>0)$
which is strictly less than $\min(s,t)$.
\\

We denote by $f(r):=G_r(s,t)$ with fixed $s,t\in\R$.
We want to prove that $G_0(s,t):=\lim_{r\rightarrow 0^+}f(r)$ exists under some natural condition on $\psi$ with $s,t>0$. This existence is insured if $f(r)$ is non-increasing on some interval
$(0,\varepsilon)$ that is $f'(r)\leq 0$. We give a necessary and sufficient  condition on $\psi$ to fulfil this last condition.
Let $\psi$ as above $(\psi=1-\theta$) and let $V:=(-\psi'\,o\, \psi^{-1})\times\psi^{-1}$. We say that $V$ is locally sub-additive at $0^+$ if there exists $\eta>0$ such that, for all $0<\alpha,\,\beta,\,
\alpha+\beta<\eta$,  we have
$$
V(\alpha+\beta)\leq V(\alpha)+V(\beta).
$$

We can express the fact that $f'(r)\leq 0 $ is equivalent to this property on $V$.

\begin{Th}\label{limexist}
Let $\psi=1-\theta$ with $\theta :\R\rightarrow (-\infty,1)$ of class $C^2$ such that $\theta'>0$ and
$\theta''\leq 0$ (i.e. $\psi$ convex). Suppose that $V:=(-\psi'\,o\, \psi^{-1})\times \psi^{-1}$ is locally sub-addditive at $0^+$. Then for any $s,t>0$,
 $G_0(s,t):=\lim_{r\rightarrow 0^+}f(r)$ exists and
 $G_0(s,t)\leq \min(s,t)$.
 Moreover, if
there exists $r_0>0$ such that $f'\leq 0$
and
$rf'(r)\leq f(r)- f(0^+), 0<r\leq r_0$ then, for any $r\in(0,r_0)$,
\begin{equation}\label{speed}
-r\,\frac{\left(f(0^+)-f(r_0)\right)}{r_0}+f(0^+)\leq f(r)\leq f(0^+).
\end{equation}

\end{Th}

{\bf Comment}:
The   bounds of $f(r)$ in (\ref{speed}) give useful information for numerical simulation because of the bounds
$0\leq   f(0^+)-f(r) \leq r\,\frac{\left(f(0^+)-f(r_0)\right)}{r_0}
\leq
r\,\frac{\left(\min(s,t)-f(r_0)\right)}{r_0}
$.
\\

\proof

 Let $f(r):=G_r(s,t)$ with $s,t>0$ and $r>0$.
 Let $H:=-\psi'=\theta'>0$ and $H'=\theta''\leq 0$. So $H$ is positive and non-increasing. A simple computation gives us
 $$
 rf'(r)= f(r)-\frac{sH(s/r)+tH(t/r)}{(H\,o\,\psi^{-1})(\psi(s/r)+\psi(t/r))}.
 $$
 The condition $f'(r)\leq 0$  is equivalent
 to
 $$
  \psi^{-1}(\psi(s/r)+\psi(t/r))
\leq\frac{\frac{s}{r}H(\frac{s}{r})+\frac{t}{r}H(\frac{t}{r})}{(H\,o\,\psi^{-1})(\psi(s/r)+\psi(t/r))}.
 $$
 Let
 $\alpha=\psi(s/r)$ and $\beta=\psi(t/r)$.
 Then $f'(r)\leq 0$ if and only if
 $$
  \psi^{-1}(\alpha+\beta)
\leq
\frac{\psi^{-1}(\alpha)\,(H\,o\, \psi^{-1})(\alpha)+\psi^{-1}(\beta)\, (H\,o\, \psi^{-1})(\beta))}{(H\,o\,\psi^{-1})( \alpha+\beta)}.
 $$
 Because $H>0$,
 this condition is exactly the sub-additivity property

 \begin{equation}\label {vee}
 V(\alpha+\beta)\leq V(\alpha)+V(\beta).
 \end{equation}

 Now assume that $V$  is locally sub-addditive at $0^+$ that is there exists $\eta>0$ such that
 for all $0<\alpha,\beta,\alpha+\beta<\eta$,  we have
$
V(\alpha+\beta)\leq V(\alpha)+V(\beta).
$
 Fix $s,t>0$ and let $\varepsilon>0$ such that
 $0<  \max(\psi(s/\varepsilon),\psi(t/\varepsilon))
 \leq \eta$.
 This is possible because $\psi(+\infty)=0^+$
 and
 $\psi>0$ ($\theta<1$).
  For $r\in (0,\varepsilon)$, we have
 $0<\alpha:=\psi(s/r)<\eta $ and $0<\beta:=\psi(t/r)<\eta$ since $\psi$ is decreasing. Hence,
 $V(\alpha+\beta)\leq V(\alpha)+V(\beta)$ which implies $f'(r)\leq 0$ for any $0<r< \varepsilon$.
 As a consequence $f(0^+):=\lim_{r\rightarrow 0^+} f(r)$ exists because
 $f(r)$ is always bounded by $\min(s,t)$ (see Proof of  Thm. \ref{zero}).
 \\

 Now, we prove (\ref{speed}).
 We have assumed that
 $$
 rf'(r)\leq f(r)-f(0^+),\; 0<r \leq r_0.
 $$
 So,
 $$
 \left(\frac{f(r)}{r}\right)'= \frac{rf'(r)-f(r)}{r^2}\leq \frac{-1}{r^2}f(0^+).
 $$
Let $0<t<r_0$, by integration on $[t,r_0]$ of the inequality just above, we get
 $$
 \frac{f(r_0)}{r_0} -\frac{f(t)}{t}\leq f(0^+)\left( \frac{1}{r_0}-\frac{1}{t}\right).
 $$
 This can be written as
 $$
 -t\left[\frac{f(0^+)-f(r_0)}{r_0}\right]+f(0)\leq f(t),\quad  0<t\leq r_0.
 $$
 This is the desired result and  completes the proof.
\\

{\bf Two examples}:

In both examples below, it is easy to check that $V$ is sub-addditive on $(0,+\infty)$.
\begin{enumerate}
\item
$\psi^{(1)}(x)=\frac{1}{x+1}, x\geq 1$. So,
$V(y)=y-y^2, \, 0<y<1$ or $V(y)=1-y, \,y>1$.

\item
$\psi^{(2)}(x)=e^{-x},x\in \R$. So,  $V(y)=-y\ln y$, $0<y<\infty$. \end{enumerate}

The condition  $rf'(r)\leq f(r)- f(0) $  with $0<r$ small enough is satisfied by these two examples.
Let $K=H\,o\,\psi^{-1}=-\psi'\,o\,\psi^{-1}$. With the notations above, we have for $\alpha,\beta>0$:
$$
rf'(r)=f(r)-\frac{sK(\alpha)+tK(\beta)}{K(\alpha+\beta)}.
$$

\begin{enumerate}
\item
For $\psi^{(1)}$:
$$
\frac{sK(\alpha)+tK(\beta)}{K(\alpha+\beta)}=s\left(\frac{\alpha }{\alpha+\beta}\right)^2
+ t\left(\frac{\beta}{\alpha+\beta}\right)^2
\geq
\inf_{0\leq \lambda\leq 1} \{s\lambda^2+t(1-\lambda)^2\}
=\frac{st}{s+t}=f(0).
$$
In that case, we have equality:
$$
rf'(r)=f(r)-f(0).
$$

\item
For $\psi^{(2)}$:
Since $K=Id$,
$$
\frac{sK(\alpha)+tK(\beta)}{K(\alpha+\beta)}=\frac{s\alpha+t\beta}{\alpha+\beta}
\geq \min(s,t)=f(0).
$$
Thus  $rf'(r)\leq f(r)- f(0) $.

\end{enumerate}

Now, we give a necessary and sufficient condition on $G(s,t)=\psi^{-1}\left(\psi(s)+\psi(t)\right)$ to be concave
in $(s,t)$ with $s,t>0$.
First, note that $G$  is concave iff $G_r(s,t)=r\,G(s/r,t/r)$ is concave.
($G=G_1$ with this notation).

\begin{Th}\label{concave}
Assume that $\psi: \R \rightarrow (0,+\infty)$ satisfies $\psi'<0$, $\psi''>0$ (i.e. convex).
Let
$$
L(\alpha):=-\frac{(\psi'\,o\,\psi^{-1})^2}{\psi'' \,o\,\psi^{-1}}(\alpha),\quad \alpha \in \psi(\R).
$$

The following statements are equivalent:
\begin{enumerate}
\item
$G$ is concave in the argument $(s,t)$.
\item
$L$ is non-increasing and sub-additive i.e.
$$
L(\alpha+\beta)\leq L(\alpha)+L(\beta),\quad \alpha,\beta \in \psi(\R).
$$
\end{enumerate}
\end{Th}

Note that $\psi(\R)$ the image of $\R$ by $\psi$ is a subset of $(0,+\infty)$.
\\

\proof
To simplify the presentation of our results, we denote
by $\alpha=\psi(s)$ and $\beta=\psi(t)$,
$$
W:=W(\alpha+\beta)=(\psi'\,o\,\psi^{-1})(\alpha+\beta)<0, \quad \alpha+\beta \in \psi(\R),
$$
and
$$
U:=U(\alpha+\beta)=(\psi''\,o\,\psi^{-1})(\alpha+\beta)>0, \quad \alpha+\beta \in \psi(\R).
$$

A rather boring computation gives us,
$$
R:={\partial}_{s,s}G(s,t)=
\left[ \psi''(s) W^2-(\psi'(s))^2U\right]/W^3,
$$

$$
T:= {\partial}_{t,t}G(s,t)=
\left[ \psi''(t) W^2-(\psi'(t))^2U\right]/W^3,
$$

$$
S:= {\partial}_{s,t}G(s,t)=
-\psi'(s)\psi'(t)\frac{U}{W^3}.
$$
It is well-known that $G$ is concave iff $R\leq 0, T\leq 0$ and $RT-S^2\geq 0$.
For  the condition $R\leq 0$ (similarily for $T\leq 0$),   we get due to the fact that $W^3< 0$,
 $$
 \psi''(s) W^2\geq
 (\psi'(s))^2U.
$$
This can written as
$$
- \frac{(\psi'(s))^2}{ \psi''(s)}\geq  -\frac{W^2}{U}.
 $$
That is, with $s=\psi^{-1}(\alpha)$ and $t=\psi^{-1}(\beta)$,
$$
L(\alpha)\geq L(\alpha+\beta)
$$
 This expresses  the fact that $L$ is non-increasing.
\\

For  the condition $RT-S^2\geq 0$,   we obtain after simplifications:
$$
W^6(RT-S^2)=
\psi''(s)\,\psi''(t)W^4-
\left[
\psi''(s)(\psi')^2(t)+\psi''(t)(\psi')^2(s)\right]W^2U.
$$
By  similar manipulations as in the case   $R\leq 0$, we can express the condition
$RT-S^2\geq 0$ by
$$
L(\alpha+\beta)\leq L(\alpha)+L(\beta),\quad \alpha,\beta,\alpha+\beta \in \psi(\R).
$$
that is $L$ is sub-additive. The proof is completed.
\\

Note that $T\leq 0$ iff $R\leq 0$. Indeed,  $R\leq 0$ iff $L$ is non-increasing. Thus, by symmetry arguments in $(s,t)$,
 $T\leq 0$ iff $L$ is non-increasing.
 \\

An examination of the two examples above leads to the  following  important remark. We compute the functions $L$ for the examples
  $\psi^{(1)}(x)=\frac{1}{x+1}$ and $\psi^{(2)}(x)=e^{-x}$ and  obtain  $L_1(\alpha)=-\frac{1}{2} \alpha$ and $L_2(\alpha)=-\alpha$. They are additive functions !
  It suggests to find a one parameter family of function $\phi_{\lambda}$
  giving as particular cases the functions
  $\psi^{(1)}$ and $\psi^{(2)}$.
  This can be done by solving the equation $RT-S^2=0$. Indeed, additivity of $L$ exactly correspond to this equation. The equation $RT-S^2=0$ can be written as
  $L(\alpha)=-\frac{1}{\lambda}\alpha,\, \lambda>0$ ($L$ is non-increasing) or equivalently
  $$
  (\psi')^2=\frac{1}{\lambda}\psi\,\psi''.
  $$
First case: $\lambda>1$. We obtain as solution of this equation
$$
\phi_{\lambda}(x)=\frac{1}{(c_1x+1)^{\frac{1}{\lambda -1}}}, \, \quad x>\frac{-1}{c_1},
$$
for some $ c_1 >0$.
\\

Second case $\lambda=1$: this case  has to be solved independently,
we get
$$
\phi_{1}(x)=e^{-Dx},\, x\in \R,
$$
for some $D>0$.
This case can be seen as a limit case as $\lambda \rightarrow 1^+$. The function $\phi_{1}$ is different of nature
of the functions $\phi_{\lambda}, \lambda>1$.
\\

The condition $RT-S^2=0$ introduces a family of new examples of $\psi$ satisfying the conditions
of Theorem  \ref{concave} namely
$\phi_{\lambda}$. This condition is exactly
$\det \,(Hess G)=0$. That is the Hessian has an eigenvalue $\mu_1=0$ and $\mu_2\leq0$ (since the trace
of the Hessian matrix is $R+T\leq 0$).

\section{Convergence and error estimate}

Let $H_r(x):=G_r(x,F(x))=\left( G_r(x_i,F_i(x))\right)_{i=1}^n $ with $G_r$ defined as above.
When $F$ is a $(P_0)$-function, we can easily prove the following result.

\begin{lem}
Assume that $F$ is a $(P_0)$-function then $H_r$ is
$(P)$-function for any $r>0$.
\end{lem}

\proof For any $x,y\in \R^n$, there exits $i:1...n$ such that $x_i\neq y_i$. We can assume that
$x_i> y_i$ and $F_i(x)\geq F_i(y)$. Since $\psi$ is decreasing
:
$\psi(x_i/r)< \psi(y_i/r)$
and
$ \psi(F_i(x)/r)\leq \psi(F_i(y)/r)$.
Consequently,
$\psi(x_i/r)+ \psi(F_i(x)/r)< \psi(y_i/r)+\psi(F_i(y)/r)$.
Again by the monotonicity of $\psi^{-1}$,
$G_r(x_i,F_i(x))> G_r(y_i,F_i(y))$.
 Hence, $H_r$ is
$(P)$-function for any $r>0$.

\noindent So that, when  the assumptions of Theorem \ref{limexist} are satisfied, we obtain the following convergence result.

\begin{Th}
Under the assumptions of Theorem \ref{limexist}, assume that $F$ is a $(P_0)$-function and that  $(H1)$ is  satisfied (The solution set of the NCP is nonempty and compact).\\
(i) There exists an $\hat r>0$ such that for any $0<r<\hat r$,  $H_r(x)=0$ will have a unique solution $x^{(r)}$, the mapping $r\to x^{(r)}$ is continuous on $(0,\hat r)$,  and \\
(ii) $ \displaystyle \lim_{r\to 0} dist (x^{(r)},$ \cal{Z} $) =0$.
\end{Th}
\proof
 This is a dierct application of (\cite{Se-Ta} Theorem 4 (2)).\\
\begin{rem}
Under  the assumptions of Theorem \ref{concave}, we can prove an other convergence result based on the smoothing
thechnique disscussed in {\rm \cite{BT}}.
\end{rem}

\noindent When using $\theta \ge \theta^{(1)}$ on $\R^+$ (this is the case of $\theta^{(2)} $for example), we can prove  an estimate for  the error term $ \vert\vert x^*-x^{(r)}\vert\vert $ between the solution $x^*$ and the approximation $x^{(r)}$ under an assumption of monotonicity of $F$.

\begin{prop}
Assume that  $\theta \ge \theta^{(1)}$ on $\R^+$, that $x^*$ is a solution of $<x^*,F(x^*)>=0$ and
$x^{(r)}$ is a nonnegative solution of $H_r(x)=0$.\\
(i) $x_i^{(r)}F_i(x^{(r)}) \le r^2$  $\forall i=1\dots n$\\
(ii) If $F$ satisfies the  condition:
$$
h(\vert\vert x-y\vert\vert) \leq\; <x-y,F(x)-F(y)>
$$
with  $h:\R^+\longrightarrow \R$ such that
$h(0)=0$
and there exists
  $\varepsilon>0$ such that
$h:[0,\varepsilon)\longrightarrow [0,\eta)$
is  an increasing bijection.

Then there exists $r_0>0$ such that for any $r\in (0,r_0)$,
\begin{equation}\label{error}
 \vert\vert x^*-x^{(r)}\vert\vert
 \leq h^{-1}(n r^2).
\end{equation}
\end{prop}

The inequality  (\ref{error}) gives the maximal behavior of the error
 in terms of the function $h$.
\\

\proof
(i) $x^{(r)}$ satisfies  $H_r(x^{(r)})=0$, so that
$$
\theta(\frac{x_i^{(r)}}{r})+\theta(\frac{F_i(x^{(r)}}{r})=1, \qquad i:1...n.
$$
and since $\theta \ge \theta^{(1)}$, we obtain
$$
\theta^{(1)}(\frac{x_i^{(r)}}{r})+\theta^{(1)}(\frac{F_i(x^{(r)}}{r})\leq 1, \qquad i:1...n.
$$
Then, a simple calculus yields to
$$x_i^{(r)}F_i(x^{(r)}) \le r^2 \qquad i:1...n.$$

(ii) We have
$$
<x^*-x^{(r)},F(x^*)-F(x^{(r)})>=
$$
$$
<x^*,F(x^*)> - <x^*,F(x^{(r)})>-
<(x^{(r)},F(x^*)>+<x^{(r)},F(x^{(r)})>\;
\leq n r^2.
$$
Indeed,  the first term of the R-H-S is zero, the two middle terms are non-positive and the last term is $n r^2$.
So, by monotonicity,
$$
 h(\vert\vert x^*-x^{(r)}\vert\vert)
\leq  n r^2
 $$
  Let $r_0$ such that $r^2_0 <\eta$.
Since
 $h$ is a bijection from $[0,\varepsilon)$ onto $[0,\eta)$
 and $h^{-1}$ is increasing, we obtain
 $$
  \vert\vert x^*-x^{(r)}\vert\vert
 \leq h^{-1}(n r^2).
 $$
 The proof is completed.

\section{Numerical results}

In order to verify the theoretical assertions, we present some numerical experiments for  two smoothing approaches using the $\theta$ functions $\theta^{(1)}$ and $\theta^{(2)}$.  We first consider a simple 2-dimensional problem which is analytically solvable
where
$$F(x,y)=(2-x-x^3,y+y^3-2)^T.$$
The unique optimal solution for this problem is $(0,1)$. \\
The following figure presents the evolution of the second coordinate of the iterates for the two smoothing functions. The optimal solution was reached up to a tolearance of $10^{-10}$ in no more than 3 iterations. We use the updating strategy for the penalization parameter as precised later. The red and green points correspond respectively to the iterates of the smoothing method
$\theta^{(1)}$ and $\theta^{(2)}$.\\
 \begin{figure}[ht!]
\begin{center}
{\label{gout}\includegraphics[width=8cm]{gnl.ps}}
\caption{Evolution of $(y,F_2(x,y),r)$.}\label{figcomp}
\end{center}
\end{figure}

We also consider a set of 10 NCP test problems with different and varying number of variables. \\
For each test problem and each smoothing function, we use 11 different starting points:  a vector of ones and 10 uniformly generated vectors with entries in $(0,20)$.\\
The starting value for the smoothing parameter is fixed with respect to the theoretical properties as
$$r^0=\max ( 1, \sqrt{ \max_{1\le i\le n} \vert x^0_i \bullet F_i(x^0)\vert  } ).$$
This parameter is then updated as follows
$$r^{k+1}=\min (0.1r^k,({r^k})^2, \sqrt{\max_{1\le i\le n}\vert x^k_i \bullet F_i(x^k)\vert } )$$
until the stopping rule
$$\max_{1\le i\le n}\vert x^k_i \bullet F_i(x^k)\vert \le 10^{-8}$$
is satisfied.\\

Precise descriptions of the test problems   P1 and P2 can be found in \cite{HW}.
 P3 is a test problem from  \cite{LZ}  while P4 and P5 can be found in  \cite{DY} , these two problems correspond to a non-degenerate and a degenerate examples  of Kojima-Shindo NCP test problems \cite{KS}.
 The other test problem are described in\cite{Tin,Har}. They correspond respectively to the NASH-COURNOT test problems with $n=5$ and $n=10$ and to the HpHard test problem with $n=20$ , $n=30$ and $n=100$.\\
We used a standard laptop (2.5 Ghz, 2Go M) and a very simple matlab program using the $fsolve$ function. \\

We list  in the following table, the worst obtained results.  $n$ stands for the number of variables. OutIter is the number of outer iterations (number of changes of the smoothing parameter $r$) and InIter corresponds to the total number of jacobian evaluations. Res. and Feas. correspond to the following optimality and feasibility measures
$$\textrm{Res.}=\max_{1\le i\le n}\vert x_i \bullet F_i(x)\vert $$
and
$$\textrm{Feas.}=\Vert\min(x,0)\Vert_1+\Vert\min(F(x),0)\Vert_1.$$
The results show that the second smoothing function is much more efficient and powerful. This was foreseeable since
$$\forall x\ge 0 \qquad 1-\delta_0 (x)\ge \theta^{(2)} (x)\ge \theta^{(1)}(x).$$
\newpage

{
\begin{table}[htb]
\begin{displaymath}
\begin{array}{llclclclclclclcll}
\hline\hline
\textrm{Pb} & \textrm{size}&\textrm{OutIter} & \textrm{InIter} & \textrm{Res.} &  \textrm{Feas.} &\textrm{cpu time (s)}\\
 &&(\theta_1,\theta_2) &(\theta_1,\theta_2) & (\theta_1,\theta_2) & (\theta_1,\theta_2) &(\theta_1,\theta_2) \\ \hline
\hline \textrm{P1}&\textrm{10}&(6 ,4)&(65 ,15)&(5.6e\!\!-\!\!15 ,2.5e\!\!-\!\!18)&(  1.1e\!\!-\!\!11  ,1.3e\!\!-\!\!10)&(0.22,0.09)\\
\hline \textrm{}&\textrm{100}&(6 ,4)&(68 ,19)&(1.6e\!\!-\!\!14 ,7.1e\!\!-\!\!22)&(  5.1e\!\!-\!\!13  ,1.4e\!\!-\!\!14)&(3.73,1.19)\\
\hline \textrm{}&\textrm{500}&(6 ,4)&(83 ,21)&(5.4e\!\!-\!\!12 ,1.6e\!\!-\!\!16)&(  1.9e\!\!-\!\!16  ,1.4e\!\!-\!\!14)&(31.15,89.26,)\\
\hline \textrm{}&\textrm{1000}&(6 ,5)&(77 ,40)&(3.0e\!\!-\!\!14 ,3.1e\!\!-\!\!14)&(  5.1e\!\!-\!\!18  ,1.8e\!\!-\!\!17)&(388.59,201.43)\\ \hline
\hline \textrm{P2}&\textrm{10}&(6,4)&(79,23)&(2.1e\!\!-\!\!15,2.7e\!\!-\!\!15)& (7.6e\!\!-\!\!11, 9.6e\!\!-\!\!19)  &(0.31,0.11)\\
\hline \textrm{}&\textrm{100}&(6,4)&(88,33)&(1.84e\!\!-\!\!12,1.0e\!\!-\!\!23)&   (7.1e\!\!-\!\!10,3.1e\!\!-\!\!14)&(4.83,1.80)\\
\hline \textrm{}&\textrm{500}&(6,4)&(96,41)&(6.5e\!\!-\!\!10,1.9e\!\!-\!\!16)&  (6.6e\!\!-\!\!09,1.2e\!\!-\!\!12)  &(112.14,49.59)\\
\hline \textrm{}&\textrm{1000}&(6,5)&(114,67)&(1.0e\!\!-\!\!17,1.4e\!\!-\!\!23)&( 2.4e\!\!-\!\!08 ,7.5e\!\!-\!\!18)&(530.42,328.15)\\ \hline
\hline \textrm{P3}&\textrm{10}&(5,4)&(63,15  ) & ( 2.2e\!\!-\!\!12,2.7e\!\!-\!\!21)&(4.9e\!\!-\!\!08,1.4e\!\!-\!\!11 )   &(0.22,0.09)\\
\hline \textrm{}&\textrm{100}&(5,4)&(71,18  )  &(7.9e\!\!-\!\!13, 2.6e\!\!-\!\!15)& (9.5e\!\!-\!\!08,4.5e\!\!-\!\!08 ) &(3.10,1.02)\\
\hline \textrm{}&\textrm{500}&(5,4)&(73,21 )   &(1.1e\!\!-\!\!14,2.6e\!\!-\!\!16)& (1.5e\!\!-\!\!07, 5.9e\!\!-\!\!09 ) &(78.11,26.15)\\
\hline \textrm{}&\textrm{1000}&(5,4)&(81,26)&(6.1e\!\!-\!\!13,1.2e\!\!-\!\!15) &( 8.2e\!\!-\!\!10      ,2.4e\!\!-\!\!16)& (335.37,138.23)\\ \hline
\hline \textrm{P4}&\textrm{4}&(6,4)&(63,20)&(5.4e\!\!-\!\!12,3.2e\!\!-\!\!17)&(6.1e\!\!-\!\!09,2.8e\!\!-\!\!12)&(0.15,0.08)\\ \hline
\hline \textrm{P5}&\textrm{4}& (6,4)&(141,23)& (9.8e\!\!-\!\!14,2.1e\!\!-\!\!23)&(3.4e\!\!-\!\!07,3.2e\!\!-\!\!12)&(0.28,0.06)\\  \hline
\hline \textrm{P6}&\textrm{5}&(5,3)&(47,17)& (1.3e\!\!-\!\!14, 4.3e\!\!-\!\!27)&(4.9e\!\!-\!\!12,8.1e\!\!-\!\!17)&(0.16,0.07)\\ \hline
\hline \textrm{P7}&\textrm{10}&(6,4)&(110,33)& (1.2e\!\!-\!\!16, 6.1e\!\!-\!\!19)&(1.1e\!\!-\!\!12,4.5e\!\!-\!\!14)&(0.37,0.14)\\  \hline
\hline \textrm{P8}&\textrm{20}&(6,5)&(145,66)& (2.9e\!\!-\!\!13, 3.7e\!\!-\!\!21)&(0,4.4e\!\!-\!\!12)&(1.33,0.46)\\
\hline \textrm{P9}&\textrm{30}&(6,6)&(106,77)& (3.7e\!\!-\!\!14, 9.6e\!\!-\!\!21)&(4.4e\!\!-\!\!08,6.4e\!\!-\!\!11)&(2.24,0.85)\\
\hline \textrm{P10}&\textrm{100}&(6,6)&(209,113)& (8.5e\!\!-\!\!11, 2.1e\!\!-\!\!23)&(2.1e\!\!-\!\!07,1.8e\!\!-\!\!12)&(42.09,19.12)\\  \hline \hline

\end{array}
\end{displaymath} \caption{Results for  $\theta^{1}$ and  $\theta^{2}$}\label{kk}
\end{table}
}


TITLE: For $x'(t)= f(t, x(t)) + \int_0^t g(x(s))\, ds$ show that if $x_1(0) \leq x_2(0)$ that also $x_1(t) \leq x_2(t)$
QUESTION [3 upvotes]: Note
The Question has changed significantly since it was posed, but it is now as follows:
Question
Suppose we have some integro or delayed differential equation:
$$
x'(t)=f(t,x(t)) + \int_0^t g(x(s))\, ds + \sum_n h(x(t-a_n)),
$$
where we assume that conditions are satisfied such that this equation always has a unique, continuous solution.
let $x_1(t)$ and $x_2(t)$ be two solutions with some boundary conditions $x_1(0)=x_1$ and $x_2(0)=x_2$ such that $x_1 \leq x_2$. I would now like to show that we have for all $t: x_1(t) \leq x_2(t)$. What are some methods for showing this? I know of the following method:

Suppose there is some $t>0$ such that $x_1(t) > x_2(t)$, then there exists a value $s \in [0,t]$ such that $x_1(s)=x_2(s)$ and for all $u\leq s: x_1(u) \leq x_2(u)$. If one can show under these conditions that $x_1'(t) = f(t,x_1(t)) \leq f(t,x_2(t)) = x_2'(t)$ then it follows that $x_1(t)$ stays below $x_2(t)$ for all $t$.
Write $x(t) = \int_0^t f(s,x(s))\, ds$ and show that $\int_0^t f(s,x_1(s))\, ds \leq \int_0^t f(s,x_2(s))\, ds$ for all $t$.

The first method is easy to apply but too restrictive and the second method is not restrictive at all but is hard to apply.
My question is a reference or an explenation of other methods in case the first method is not applicable.
An Example
Suppose for example we have the following Delay Differential Equation:
$$
\begin{cases}
x'(t) &= x(t)-1 \mbox{ if } t \leq 1\\
x'(t) &= x(t-1) (x(t) - x(t-1)) \mbox{ if } t >1
\end{cases}
$$
this delay differential equation satisfies the property that if we have $x_1,x_2 \in (0.8,1)$ with $x_1 \leq x_2$ and $x_1(t), x_2(t)$ are solutions satisfying $x_i(0) = x_i$ then for all $t: x_1(t) \leq x_2(t)$. I can check this numerically but not analytically.

REPLY [1 votes]: This is wrong in general
The differential equation
$$x^\prime = \vert x \vert^{\dfrac{1}{2}}$$
has $x_1(t)=0$ as a solution. Another one is
$$x_2(t)=\begin{cases}
0& \text{for } t\le 1\\
\dfrac{(t-1)^2}{4} & \text{for } t>1
\end{cases}$$
You have $x_2(0) \le x_1(0)$. However $x_2(2)>x_1(2)$.
You need to add additional hypothesis’s. The ones of Picard–Lindelöf theorem are for example sufficient as under this theorem solutions are unique.
If unicity of solutions is assumed, then you can use a simple argument.
Suppose that $x_2(t_0) > x_1(t_0)$ and $x_1(t_1)=x_2(t_1)$ with $t_0<t_1$. Then $x_1, x_2$ are two solutions on $[0, t_1]$. Another one is
$$x_3(t)=\begin{cases}
x_2(t) & \text{for } t\le t_0\\
x_1(t) & \text{for } t \ge t_0
\end{cases}$$
in contradiction with unicity of IVP.

REPLY [0 votes]: This is not true without extra conditions.
Let $f(t,x) = 2 \sqrt{|x|}$.
Then let $x_p(t) = 0$ for $t < p$ and $x_p(t) = (t-p)^2$ for $t \ge p$. It is straightforward to show that if $p \ge 0$ then $x_p$ is a solution to the problem
$\dot{x} = f(t,x)$, $x(0) =0$.
Also, note that $x_z(t) = 0$ is a solution.
Then we see that $x_1(0) \le x_z(0)$ but it is not true that $x_1(t) \le x_z(t)$ for all $t \ge 0$.


TITLE: Proof that a polynomial is irreducible over $\mathbb Q$
QUESTION [3 upvotes]: Let $P(x)=x^3-21x^2+5x+2$. I want to show that $P(x)$ is irreducible over $\mathbb Q$.

Using the Mod $p$ Test, I can reduce $P(x)$ to $\bar P(x)=x^3+2x+2$ in $\mathbb Z_3[x]$, and show that $\bar P(x)$ has no zeroes in $\mathbb Z_3$ by trying $0,1,2$. So $\bar P(x)$ is irreducible over $\mathbb Z_3$, and deg$(\bar P(x))$=deg$(P(x))$, thus by the Mod $p$ Test, $P(x)$ is irreducible over $\mathbb Q$.
Is this proof correct?

REPLY [1 votes]: Well since this is a degree three polynomial all you have to show is that there is no root in $\mathbb{Q}$. By looking at the coefficients you can show that the only possible roots are $\pm 2, \pm1$. Since these are not roots, the polynomial is irreducible.
EDIT: If the polynomial $\sum\limits_{i=0}^n a_ix^i $ has a rational root $\frac{p}{q}$ $(p,q)=1$, then $p|a_0$ and $q|a_n$.


TITLE: Solve system of equations $9^y=3^x$ and $2\log_2{x}-\log_43=\log_2y$.
QUESTION [0 upvotes]: Solve system of equations $9^y=3^x$ and $2\log_2{x}-\log_43=\log_2y$.
I got $2y=x$ and $2\log_2{x} - \frac{1}{2}\log3=\log_2\frac{1}{2}x$. I am stuck at this point. Could you provide a hint ?

REPLY [1 votes]: Remember that by definition, $\log_43$ is the real number, say $z,$ such that $4^z=3.$ Put another way, $(2^2)^z=3.$ Put yet another way, $2^{2\cdot z}=3.$ Translated back into terms of logarithms, $$2z=\log_23,$$ so that $$\log_43=z=\frac12\log_23.$$
This may have been what you've done already, though your post doesn't actually show it (there's an index missing). If that is what you've done, then your second equation should actually show $$2\log_2x-\frac12\log_2 3=\log_2y,$$ or equivalently, $$4\log_2x-\log_23=2\log_2y.$$ This is again equivalent to $$4\log_2x=2\log_2y+\log_23,$$ or $$\log_2x^4=\log_2y^2+\log_23,$$ or $$\log_2x^4=\log_23y^2,$$ or finally $$x^4=3y^2.$$ Since $x=2y,$ and since $x$ and $y$ are both positive (do you see why?) what can we conclude?


TITLE: Finding CDF of $Y$ when $Y=1/X$.
QUESTION [1 upvotes]: $X$ be a uniform random variable on $[1,3]$. $Y=1/X$. What is the CDF of $Y$?
My attempt so far:
CDF of $Y$ by definition:
$= P(Y\le y)\\
= P (1/X \le y)\\
= P (X\ge 1/y)$
I don't know how to proceed.

REPLY [1 votes]: My attempt so far: CDF of Y by definition: $= P(Y\leq y) \\ = P (1/X \leq y) \\ = P (X\geq  1/y)$

Correct. You also know $X\sim\mathcal{U}[1,3]$ and so $P(X\leq x)= \tfrac{x-1}2\cdot\mathbf 1_{1\leqslant x\lt 3}+\mathbf 1_{3\leqslant x}$


TITLE: Non-linear systems in classical mechanics
QUESTION [17 upvotes]: In general, what is meant by non-linear system in classical mechanics? Does it always concern the differential equations one ends up with (any examples would be greatly appreciated)?  If so, is it considered as non-linear because of: Higher powers of system variables? ($x^2,x^3...$), or does also any function of $x$ makes the system non-linear? like $\cos(x)$, $\ln(x)$, $e^x$ etc. I am confused.
Furthermore, why is it that most non-linear systems are considered non-integrable? Is it due to this fact that such systems are usually considered to be unpredictable even classically? (because we can't have exact analytical solutions?).

REPLY [4 votes]: As the first question has received sufficient exposition, I would like to make a point with regard to the second one. First thing to understand is that integrability and non-linearity of a system are two different concepts. It is true though that all linear systems in classical mechanics (i.e those that are described by systems of linear equations, be them algebraic or differential) are integrable, but integrability does not imply linearity. Typically looking at the case of a system of differential equations describing a system, integrability is then a condition requiring analytical solvability when all the required initial and boundary conditions have been specified (the problem is then well-posed). In classical Hamiltonian systems (or the more general case being a finite system of ODEs), integrability is then specified by the  Liouville-Arnold theorem . In all autonomous systems, the hamiltonian automatically becomes a constant of motion and hence in 1 dimension, all hamiltonian systems are integrable. Enlarging the phase space of dynamics, one now requires many more integrals of motion that specify iso-surfaces upon which dynamics occurs and the intersection of all these surfaces will give the required trajectory of the system, once the initial conditions are fixed.
The idea of requiring constants or invariants of an equation is a very broad one and the argument mostly goes through for most other cases too. For infinite dimensional systems (like PDEs, say), we in principle need an infinite set of constants, though it is not sufficient. The existence of such independent constants in involution with each other many times points to a deeper symmetry or degeneracy in the problem. Take for example the Kepler problem, which has three constants of motion
$$
H=\dfrac{\vec{p}^2}{2m}-\dfrac{k}{r}\quad(k>0)
$$
The three constants of motion in this problem are $H,\vec{L}^2$ and $L_z$ and they all poisson commute with each other. The dynamical symmetry group of this problem turns out to be $SO(4)$ (this group contains all the canonical transformations that preserve the symmetry of the hamiltonian). An additional constant of motion is the Laplace-Runge-Lenz vector $\vec{A}$,
$$
\vec{A}=\vec{p}\times\vec{L}-\dfrac{mk\vec{r}}{r}
$$
which also poisson commutes with the other constants $(\{\vec{A},H\}=0,\{\vec{A},\vec{L}\}=0)$. It is these two vectors $(\vec{L}\pm\vec{A})$ modulo constant factors, that generate the group of dynamical symmetries. The fact that $\vec{A}$ is a constant implies that orbits in the Kepler problem do not precess. In the context of the hydrogen atom, this same constancy gives rise to the degeneracy of the energy levels with $\ell$ (the azimuthal quantum number). Degeneracy in $m$ (the magnetic quantum number) is demanded by the spherical symmetry of the potential. From this, we see that the existence of constants of motions that allow a system to be integrable almost always point to a deeper understanding of the problem by exposing hitherto unknown symmetries or degeneracies in the system.
There are a number of non-linear systems like the KdV equation that exhibit soliton and soliton-like solutions and this is a very active area of research in understanding the existence of solutions and integrability of nonlinear systems. One can be pretty sure that if a non-linear equation is found to be integrable, then it is definitely special and has some underlying properties that allow one to solve the equation. There is a nice write up on some of these things given in this document, that I suppose will be helpful in elucidating further details with regard to integrable systems.


text:
Most Internet traffic derives from the transfer of stored documents, corresponding
to texts, music and movies. This traffic is elastic in the sense that the transmission
rate varies depending on current network congestion. Each document transfer is a flow of
packets whose rate is usually regulated by the Transmission Control Protocol (TCP).
The rate is allowed to increase linearly until a packet loss is observed.
The rate is then divided by two. These two mechanisms ensure that network bandwidth
is shared approximately fairly between the varying number of flows in progress
at any time. TCP also ensures that lost packets are retransmitted.

There is, however, no constraint on users to actually implement TCP algorithm
and a more aggressive, greedy congestion control would be individually more profitable.
Indeed, new, more aggressive versions of TCP are emerging to better exploit
increasing link capacity \cite{rfc3649,cheng-04,lisong-04}. Some have suggested
that the packet retransmission function of TCP could be
replaced by forward error correction in the form of source coding \cite{snoeren-05}.
It consists in the use of erasure codes in order to encode files
before sending them into the network. As a consequence, if the file has been
divided in $K$ packets, the destination is able to rebuild the data with
$(1+\varepsilon)K$ packets. A typical class of erasure codes which is adapted
to source coding are the \emph{Digital fountains} \cite{mitzenmacher-04}.
The use of source coding enables the relaxation of control requirements and
facilitates aggressive packet transmission policies.

If the congestion avoidance of TCP is no longer universally used, there is a
danger that the Internet may again experience the congestion collapse observed
in its early days \cite{rfc896}. Packets dropped downstream and therefore
retransmitted needlessly encumber upstream links, amplifying and spreading
congestion. The consequence may be that the rate realized by concurrent flows is
much less than the optimum (in terms of utility maximization) and may even tend
to zero. The capacity of a network can be defined as the demand, flow arrival
rate $\times$ mean flow size, that can be sustained. It depends on the way
bandwidth is shared. It is important to understand
what happens to capacity when the assumption that users compliantly implement TCP
is relaxed. This is our objective in the present paper.

In this paper, we  assume users are greedy and do not implement congestion control. They send
data at the greatest possible rate determined by an external constraint  that we
assimilate to an access rate.  Bandwidth sharing is determined by this behavior.
We consider a flow-level model, as decribed in \cite{massoulie-00}, where the bandwidth
allocation changes instantly as new flows arrive or existing flows terminate.
Tail dropping is interpreted in this model such that, at each link, the output
rate of flows is proportional to their input rate to the link in question.
This is
consistent with the assumption that packets are all equally likely to be dropped.
The drop rate is such that the overall output rate is bounded by the link capacity.
Flows are categorized into classes defined by their route  and their
access rate. We assume flows arrive according to a Poisson process and have an
exponentially distributed size. The stochastic
process describing the number of flows in each class is a Markov process. We say
that the network is stable when this process is recurrent positive and unstable
otherwise.

To illustrate the realized bandwidth sharing without congestion control, consider
the linear network depicted in
Figure \ref{fig:line} with two links 1, 2 of capacity $C_1$ and $C_2$, respectively, $n_0$ class-0 flows
going through links 1 and 2, $n_1$ class-1 flows going through
link 1 and $n_2$ class-2 flows going through link 2. The access rate for class-$k$ flows is denoted by $a_k$.
The aggregate  input
rates of classes 0 and 1 at the first link are respectively $n_0a_0$ and $n_1a_1$ and
the total input rate at link $1$ is $R_1=n_0a_0+n_1a_1$. If $R_1>C_1$,
then the first link is saturated and the aggregate output rates of classes 0 and 1 are
respectively
$$
\theta_0^1 = C_1\frac{n_0a_0}{n_0a_0+n_1a_1}\quad \text{and}\quad
\theta_1^1 = C_1\frac{n_1a_1}{n_0a_0+n_1a_1}.
$$
If $R_1\leq C_1$ then the first link is not saturated and  $\theta_0^1=n_0a_0$
and $\theta_1^1=n_1a_1$. The aggregate input rate of class 0 at link 2 is $\theta_0^1$
and the aggregate input rate of class 2 is $n_2a_2$. As above, we derive
the respective aggregate output rates of class 0 and 2 after link 2:
$$
\theta_0^2=  \theta_0^1\min\left(1, \frac{C_2}{\theta_0^1+n_2a_2} \right)\quad \text{and}\quad
\theta_2^2 = n_2a_2 \min\left(1, \frac{C_2}{\theta_0^1+n_2a_2} \right).
$$

\begin{figure}[h]
  \centering
  \begin{minipage}{0.45\linewidth}
  \centering
  \includegraphics[width=0.5\linewidth]{triangle.eps}
  \caption{A cyclic network}
  \label{fig:cyclic}
  \end{minipage}
  \begin{minipage}{0.45\linewidth}
  \centering
  \newlength{\graphicheight}
  \settoheight\graphicheight{\includegraphics[width=0.5\linewidth]{triangle.eps}}
  \parbox[c][\graphicheight]{\linewidth}{\includegraphics[width=0.8\linewidth]{line.eps}}\\
  ~\vfill
  \caption{A linear network}
  \label{fig:line}
  \label{fig:2-line}
  \end{minipage}
\end{figure}

The question of the capacity of networks without congestion control has already
been addressed in \cite{bonald-09}. It was
shown that congestion collapse does occur in cyclic networks like that depicted in Figure
\ref{fig:cyclic} where the system is unstable for any positive demand.  In acyclic
networks, however, capacity is not reduced to 0 and this performance degradation is
significantly mitigated by the access rates. It was conjectured in \cite{bonald-09}
that capacity in acyclic networks increases as access rates tend to 0 and, in the
limit, is determined only by the optimal per-link stability conditions. In this
paper, we prove that the conjecture is indeed true for two particular acyclic
topologies, linear networks and upstream trees. For linear networks, we derive
bounds on stability conditions for arbitrary access rates.

\paragraph{Averaging phenomenon}
We evaluate stability conditions by applying fluid limit techniques. The end-to-end
class in a linear network plays a particular role. In the fluid limit, all other
flow classes are shown to empty in finite time for any initial conditions. When all these classes are empty,
a phenomenon of \emph{averaging} occurs and allow us to prove that the end-to-end class also empties in finite time.
In that situation, the rate at which this class evolves depends on the stochastic
evolution of the remaining local classes which in turn depends on the current
fluid state of the end-to-end class.  This dependence is decoupled by a time
scale separation argument. The rate at which the fluid component (the end-to-end flow)
evolves is infinitely slower than the rate at which the stochastic components
evolve. It is therefore possible to apply a \emph{quasi-stationary} model through
 which the \emph{average} impact of the local traffic can be evaluated.

This is a non-trivial example of a local equilibrium
of fluid limits. A simpler example of such a phenomenon can be found in
\cite[9.6, p271]{robert-03}. Averaging in fluid limits has also been considered
in the context of wireless networks (see \cite{bonald-04} and subsequent papers
\cite{simatos-10} and \cite{ganesh-10}). The main difference here is that the local equilibrium
depends on the state of the fluid limit. Note that this is somewhat related to the averaging
phenomenon considered for loss networks  \cite{kurtz-94}.

To evaluate the impact of access rates on capacity, we introduce an ad-hoc scaling.
Scaled processes are shown to converge to a simple deterministic process. Generally
speaking, the convergence of processes does not imply the convergence of
stationary distributions. However, in our case, we can prove this is true in two
specific cases exhibiting an interesting example of limit
inversion for stochastic processes. We use the same technique as in \cite{dumas-02}
to prove this inversion.
We use the convergence of stationary distributions combined with the averaging
phenomenon to prove the asymptotic optimality of linear networks. For upstream
trees, we use convergence and monotonicity.

The paper is structured as follows. In Section \ref{section:model}, we give a
complete description of the considered model. In Section
\ref{section:line}, we study the
stability conditions of linear networks with general access rates.
In Section \ref{section:asymptotic}, we study the stability of
linear networks and upstream trees when access rates decrease to $0$
and prove their capacity is asymptotically optimal.

config: arxiv


TITLE: Why a Box moving at Constant Velocity isn't doing Work?
QUESTION [0 upvotes]: This was a question from an A-Level past paper and the question is pretty straightforward.
I was in a hurry so I couldn't think much on this problem and chose $C$ as my answer, checked it on the answer key, and yes, my answer was correct. So I decided to briefly look at the options once again, and wondered why I chose $C$.
By definition $W=F×d$ , and according to Newton's 1st Law, an object at constant velocity means there isn't any unbalanced force acting on it, thus if $F$ is $0$ , it is said that the object isn't doing any work.

So I changed the scenario a bit, imagine that I'm pushing a car at a constant velocity, according to the definition, I'm not doing work on the car, but that doesn't seem very intuitive to me. I'm clearly exerting my energy to push the car which eventually exhausts me.
Coming back to the first case, I assumed the surface, where the box was sliding, to be frictionless and is placed on a massive vacuum chamber. If my hand was initially pushing that box and after a while, I released it, it'll move at a constant velocity, this suddenly becomes sensible, as there is nothing pushing it and thus no work done.
It seems that when letting go a box with no resistive force, I wasn't doing any work, but when I was pushing the car, I did. It is somehow contradictive and confusing. What concept am I missing? Any concise explanation would be great!

REPLY [2 votes]: Your example of pushing a car at a constant velocity is doing work, because you are applying force on the car.
The difference is that in that case, there is a friction force that also does work, in direct opposition to the work provided by pushing.  The work done on the car by you is counteracted by the work done on the car due to friction, and thus net kinetic energy doesn't change, because both you and the ground are doing work on the car.
The key difference in the examples here is the inclusion of a force that opposes the motion.  In the car example, if you stopped pushing, the friction would continue doing work on the car until it stops; which is why it requires a constant force (and thus work) to move the car.


TITLE: Let $f: \mathbb{R} \to \mathbb{R}$, continuous and bounded function
QUESTION [3 upvotes]: $\blacksquare$ Problem: Let $f: \mathbb{R} \to \mathbb{R}$ be a continuous and bounded function such that
$$ x \int_{x}^{x + 1} f(t) \mathrm{d}t = \int_{0}^x f(t) \mathrm{d}t \quad \text{for any } x \in \mathbb{R} $$
Prove that the function $f$ is a constant function.

$\bullet~$ My Approach: The function $f$ $\in$ $\mathscr{C}^{0}$ and $f$ is bounded, i,e., $$ \lvert f(u) \rvert < M \quad \text{for all } u \in [0, \infty) \text{ and for some } M > 0 $$
By Fundamental Theorem of Calculus, there exists a map $F$ $\in$ $\mathscr{C}^1$ such that
$$ F(x) = \int_0^x f(t) \mathrm{d}t \quad \text{for } x \in \mathcal{D} := \text{domain} $$
Now, we observe that,
\begin{align*}
    &\int_0^{x + 1} f(t) \mathrm{d}t = F(x + 1)\\
    \implies & \int_{x}^{x + 1} f(t) \mathrm{d}t + \int_{0}^x f(t) \mathrm{d}t = F(x + 1)\\
    \implies & \int_x^{x + 1} f(t) \mathrm{d}t = F(x + 1) - F(x)
\end{align*}
Now, according to the problem,
\begin{align*}
    &x \int_x^{x + 1} f(t) \mathrm{d}t = \int_0^x f(t) \mathrm{d}t \\
    \implies & \int_x^{x + 1} f(t) \mathrm{d}t = \frac{\int_0^x f(t) \mathrm{d}t}{x}\\
    \implies & \int_x^{x + 1} f(t) \mathrm{d}t = f(c) \quad [\text{By MVT, for some } c \in (0, x)] \\
    \implies & F(x + 1) - F(x) = k %\quad [\text{by Liebnitz Rule}]
    \\
    \implies & F(x + 1) = F(x) + k \quad \text{for all } x \in [0, \infty)
\end{align*}
Now we have a claim.
$\bullet$ Claim: The functional Equation that just cropped up, namely $ F(x + 1) = F(x) + k ~\forall~  x$ $\in$ $\mathbb{R}$, has solution $F(x) = kx$ for any $x$ $\in$ $\mathbb{R}$.
$\bullet$ Proof: From the definition of $F(x)$ we have that $$ F(0) = \int_0^0 f(t) \mathrm{d}t = 0 $$
Then we have that
\begin{align*}
    F(x + 1) =&~ F(x) + k \\
     =&~ F(x - 1) + 2k \\
     =&~ F(x - 2) + 3k\\
     &~\vdots \\
     = &~ F(0) + (x + 1) k\\
     = &~ (x + 1)k \quad [\text{as } F(0) = 0 \text{ and for any }x \in \mathbb{R} ]
\end{align*}
Hence we have that
\begin{align*}
    &F(x) = kx = \int_0^x f(t) \mathrm{d}t\\
    \implies &F'(x) = \frac{\mathrm{d}}{\mathrm{d}x} ( kx ) = f(x) \quad [\text{by Leibnitz Rule}]\\
    \implies & f(x) = k \quad \text{for any }  x \in \mathbb{R}
\end{align*}
Hence we are done!

Is there any glitch in the proof? Any different solution approach (maybe using the boundedness of the map $f$) will be desired too!
Thanks in advance!

REPLY [1 votes]: I have thought about another solution.
Say, from given,
$$ x \int_{x}^{x + 1} f(t) \mathrm{d}t = \int_{0}^x f(t) \mathrm{d}t \quad \text{for any } x \in \mathbb{R} $$
$$ \implies  \int_x^{x + 1} f(t) \mathrm{d}t = \frac{\int_0^x f(t) \mathrm{d}t}{x} \quad \text{for any } x \in \mathbb{R}  $$
$$ \implies  \int_x^{x + 1} f(t) \mathrm{d}t = f(c) \quad [\text{By MVT, for some } c \in (0, x)] \\ $$
$$ \implies \frac{\mathrm{d}}{\mathrm{d}x} \int_{x}^{x + 1} f(t) \mathrm{d}t = 0 \implies f(x + 1) - f(x) = 0 \implies f(x + 1) = f(x) \quad \text{for any } x \in \mathbb{R} $$
$$ \implies f(x + 1) = f(x) = f(x - 1) = \cdots = f(0) \quad \text{for any }  x\in \mathbb{R}  $$
Hence, $f(x) = f(0)~$ for any $~x \in \mathbb{R}$. Hence, $f(x)$ is constant for any $x \in \mathbb{R}$.

Is it right?


TITLE: Solve Unknown Matrix Variables
QUESTION [0 upvotes]: I have a markov chain matrix with probabilities as such, on finding the steady state..
(x,y,z) * [0.9 0.1 0]   = (x,y,z)
          [0 0.9 0.1]
          [.05 .05 .9]

Knowing that x + y + z = 1
How can i know the values of x,y and z ?
I came up with these 3 equations but got lost :
0.9x + 0y + 0.05z = x
0.1x + 0.9y + 0.05z = y
0x + 0.1y + 0.9z = z

Could be simple  substitution and elimination maths but i can't succeed in finding the values.

REPLY [0 votes]: Let $A=\begin{bmatrix} 0.9 & 0.1 & 0 \\
0 & 0.9 & 0.1 \\
0.05 & 0.05 & 0.9 \end{bmatrix}$. You want to find some non zero vector $v$
such that $v^T A = v^T$.
in other words, you are looking for an element of $\ker (A^T-I)$.
$A^T-I = \begin{bmatrix} -0.1 & 0 & 0.05 \\
0.1 & -0.1 & 0.05 \\
0 & 0.1 & -0.1 \end{bmatrix}$. Since the null space of $B$ and $\lambda B$ are the same for $\lambda \neq 0$, we look at $B=20(A^T-I) = \begin{bmatrix} -2 & 0 & 1 \\
2 & -2 & 1 \\
0 & 2 & -2 \end{bmatrix}$ instead. If $Bv = 0$, then the first line gives $v_1$ in terms of $v_3$, and the second line gives $v_2$ in terms of $v_3$, hence we can set $v_3 = 1$ and compute a vector $v\neq 0$ satisfying $A^T v = v$.