text:
\begin{document}

\title[Heston Model]{Analytic approach to solve a degenerate parabolic PDE for the Heston model}
\author{A. Canale}
\address{Dipartimento di Matematica, Universit\`a degli Studi di Salerno, Via Giovanni Paolo II, 132, I 84084 FISCIANO (Sa), Italy.}
\email{acanale@unisa.it}
\author{R.M. Mininni}
\address{Dipartimento di Matematica Universit\`a degli Studi di Bari A. Moro, Via E. Orabona 4, 70125 Bari, Italy.}
\email{rosamaria.mininni@uniba.it}
\author{A. Rhandi}
\thanks{The third author has been supported by the M.I.U.R. research project
Prin 2010MXMAJR}

\address{Dipartimento di Ingegneria dell'Informazione, Ingegneria Elettrica e Matematica Applicata, Universit\`a di Salerno, Via Giovanni Paolo II, 132, I 84084 FISCIANO (Sa), Italy.}
\email{arhandi@unisa.it}
\keywords{European option, degenerate parabolic PDE, stochastic volatility process, Heston model, mathematical finance,
variational formulation, weighted Sobolev spaces, semigroup of operators.}
\subjclass[2000]{35K65, 47D06, 49J40, 60J60}

\maketitle

\begin{abstract}
We present an analytic approach to solve a degenerate parabolic problem associated to the Heston model, which is widely used in mathematical finance to derive the price of an European option on an risky asset with stochastic volatility. We give a variational formulation, involving weighted Sobolev spaces, of the second order degenerate elliptic operator of the parabolic PDE. We use this approach to prove, under appropriate assumptions on some involved unknown parameters, the existence and uniqueness of weak solutions to the parabolic problem on unbounded subdomains of the half-plane.
\end{abstract}

\maketitle

\section{Introduction}
Heston in \cite{H} derived the pricing formula of a stock European option when the price process $\{S_t, t\ge 0\}$ of the underlying asset satisfies the following stochastic differential equation (SDE)

\be\label{bseq}
dS_t = \eta\, S_t\, dt + \sqrt{Y_t}\, S_t\, dW_t, \quad t\ge 0,
\ee
where the constant parameter $\eta\in\R$ denotes the instantaneous mean return of the underlying asset, and, contrary to the original Black and Scholes model for European options \cite{BS}, the non-constant volatility $\sqrt{Y_t}$ is supposed to be stochastic. The variance process $Y=\{Y_t, t\ge 0\}$ is assumed to be a diffusion process whose dynamics is described by the following SDE
\be\label{cireq}
dY_t = \kappa(m - Y_t)\, dt + \sigma\, \sqrt{Y_t}\, dZ_t, \quad t\ge 0,
\ee
used in mathematical finance by Cox et al. \cite{CIR} to model ``short-term interest rates" of zero-coupon bonds. The parameters $\kappa, m$ and $\sigma$ are supposed to be positive constants. The process $Y$ is known in literature as \emph{CIR process} or \emph{square-root process}. In particular, $m$ is the long-run mean value of $Y_t$ as $t\to\infty$, $\kappa$ is called the ``rate of mean reversion" that is, $\kappa$ determines the speed of adjustment of the sample paths of $Y$ toward $m$, and $\sigma$ is the constant volatility of variance (often called the  \emph{volatility of volatility}). The state space of the diffusion $Y$ is the interval $[0,\infty)$.

The processes $\{W_t, t\ge 0\}$ and $\{Z_t, t\ge 0\}$ in \eqref{bseq} and \eqref{cireq} are standard one-dimensional Brownian motions. They are supposed to be correlated
$$
dW_t\, dZ_t = \rho\, dt,
$$
where $\rho\in [-1,1]$ denotes the instantaneous correlation coefficient.

Using the two-dimensional Ito's formula (cf., for example, \cite[Chap. IV.32]{RW}), the price $U$ of an European option with a risky underlying asset, fixed maturity date $T>0$ and exercise price $K>0$ satisfies the following degenerate parabolic problem
\smallskip
\be\label{eq1}
\small
\left\{\begin{array}{ll}
\df{\partial U}{\partial t} + \df{1}{2} y S^2\df{\partial^2 U}{\partial S^2} + \df{1}{2}y \sigma^2\df{\partial^2 U}{\partial y^2} + \rho \sigma y S \df{\partial^2 U}{\partial S\partial y} + \kappa(m-y)\df{\partial U}{\partial y}& + r(S\df{\partial U}{\partial S}-U)= 0,\\[2.5\jot]
 & \hbox{in $[0,T)\times [0,\infty)^2$}\\[3.5\jot]
U(T,S,y) = h(S) & \hbox{in $[0,\infty)^2$},
\end{array}\right.
\ee

\medskip
\noindent with the final pay-off of the option as the terminal condition, namely
$$
h(S)=(S - K)_+ \quad\text{or}\quad h(S)=(K - S)_+
$$
corresponding to European call and put options, respectively. The price $U:=U(t,S,y)$ depends on time $t$, on the stock price variable $S$ and on the variance variable $y$.

The degenerate parabolic problem \eqref{eq1} is obtained imposing some assumptions about the financial market, as the no-arbitrage condition i.e., given the evolutions of $S_t$ and of $Y_t$, the European option is priced in such a way that there are no opportunities to make money from nothing.

The PDE in \eqref{eq1} has degenerate coefficients in the $S$ variable and possibly also in the $y$ variable. In order to remove the degeneracy with respect to the variable $S$, we define the stochastic process $\{X_t, t\ge 0\}$ as follows
$$
X_t = \ln{\left(\df{S_t}{S_0}\right)}, \quad t\ge 0.
$$

\noindent
Further, consider the following function
$$
\widetilde{u}(t,S,y):= U(t,S,y)-e^{-r(T-t)}h(Se^{r(T-t)}),
$$
 which indicates the excess to discounted pay-off. The parameter $r\ge 0$ denotes the constant risk-neutral interest rate, As observed by Hilber et al. in \cite{HMS}, according to the boundary conditions on the PDE in \eqref{eq1} suggested in \cite{H}, $\widetilde{u}$ decays to zero as $S\to 0$ and $S\to\infty$. Then, by changing the time $t\to T-t$, setting $x=\ln{S}$ (assume $S_0 = 1$), and using the following transformation
\begin{equation}\label{transf}
u(t,x,y):=e^{-\f{\omega}{2}y^2}\, \widetilde{u}(T-t,S,y),\quad \omega>0,
\end{equation}
we deduce from (\ref{eq1}) that the function $u$ satisfies the following initial value forward parabolic problem
\begin{equation}\label{eq2}
\left\{\begin{array}{ll}
\df{\partial u}{\partial t}(t,x,y) = - (\mathcal{L}^Hu)(t,x,y) + F(t,y), & \hbox{$t\in (0,T],\, (x,y)\in\Omega$} \\[3.5\jot]
u(0,x,y)=0, & \hbox{$(x,y)\in\Omega$},
\end{array}
\right.
\end{equation}
where $\Omega =\mathbb{R}\times [0,\infty)$. The operator $\mathcal{L}^H$ is given by
\begin{align}\label{lhop}
(\mathcal{L}^H\varphi)(x,y) &= -\df{1}{2}y\df{\partial^2 \varphi}{\partial x^2}-\df{1}{2}\sigma^2 y\df{\partial^2 \varphi}{\partial y^2}-\rho \sigma y\df{\partial^2 \varphi}{\partial x\partial y}\nnm\\[1.5\jot]
&- (\omega \rho \sigma y^2-\df{1}{2}y+r)\df{\partial \varphi}{\partial x}
- [\omega \sigma^2 y^2+\kappa(m-y)]\frac{\partial \varphi}{\partial y}\nnm\\[1.5\jot]
&-\left[\frac{1}{2}\omega \sigma^2 y(\omega y^2+1)+\omega y\kappa(m-y)-r\right]\varphi
\end{align}
and
$$
F(t,y)=\df{K}{2}ye^{-rt}e^{-\f{\omega}{2} y^2}\delta_{\ln{K} - rt}.
$$

The motivation to consider the transformation \eqref{transf} is explained in \cite{HMS}, taking into account that the price $U$ remains bounded for all $y$ (cf. \cite{H}).

To our knowledge, the use of a variational approach to prove existence and uniqueness of solutions to these pricing problems is very recent. Achdou et al. \cite{AT}-\cite{AFT} used variational analysis using appropriate weighted Sobolev spaces to solve parabolic problems connected to option pricing when the variance process $Y$ is a function of a mean reverting Ornstein-Uhlenbech (OU) process. Successively, proceedings as in the previous works, Hilber et al. \cite{HMS} used variational formulation to present numerical solutions by a sparse wavelet finite element method to pricing problems in terms of parabolic PDEs when the volatility is modeled by a OU process or a CIR process. Daskalopoulos and Feehan \cite{DF} used variational analysis with the aid of weighted Sobolev spaces to prove the existence, uniqueness and global regularity of solutions to obstacle problems for the Heston model, which in mathematical finance correspond to solve pricing problems for perpetual American options on underlying risky assets.

Observe that by applying a space-time transformation, the diffusion $Y$ follows the dynamics of a squared Bessel process with dimension
$$
\alpha=\df{4\kappa m}{\sigma^2} > 0
$$
(cf. \cite[Section 6.3]{JYC}). It is known (cf. \cite[Chap. V.48]{RW}) that for $\alpha>2$ a general $\alpha$-dimensional squared Bessel process starting from a positive initial point stays strictly positive and tends to infinity almost surely as time approaches infinity while, for $\alpha=2$ the process is strictly positive but gets arbitrarily close to zero and $\infty$, and for $\alpha > 2$ the process hits zero 0 recurrently but will not stay at zero, i.e. the 0-boundary is strongly reflecting.

Ideally, one would like a variance process which is strictly positive, because otherwise it degenerates to a deterministic function for the time it stays at zero. Then to translate this property to the CIR process $Y$, we assume the condition
\be\label{feller-condition}
\kappa m>\f{\sigma^2}{2}.
\ee
Simulation studies to investigate numerically how the effect of varying the correlation $\rho$ (cf. \cite{G}) and the volatility parameter $\sigma$ (cf. \cite{M}) impacts on the shape of the implied volatility curve in the Heston model, clearly show that under the condition \eqref{feller-condition} the volatility $\sqrt{Y_t}$ always remains strictly positive.

Thus, the above arguments let us to assume $y\in [a,\infty)$ with a sufficiently small $a>0$, in order to remove the degeneracy at zero with respect to the variable $y$ and take $\Omega=\mathbb{R}\times [a,\infty)$ in \eqref{eq2}.

By using the variational formulation of the parabolic PDE in \eqref{eq2} performed in \cite{HMS}, the aim of the present paper is to use form methods to prove the existence and uniqueness of a weak solution to the problem \eqref{eq2} and to study the existence of a positive and analytic semigroup generated by $-\mathcal{L}^H$, with an appropriate domain, in a weighted $L^2$-space with suitable weights $\phi$ and $\psi$.

The article is organized as follows. In Section 2 we define the Hilbert and weighted Sobolev spaces
we shall need throughout this article, describe our assumptions on the Heston operator coefficients and prove
the continuity estimate for the sesquilinear form defined by the operator $\mathcal{L}^H$ given in \eqref{lhop}, with Dirichlet boundary conditions. In Section 3 we derive Garding's inequality for the sesquilinear form, and deduce the existence of a unique weak solution to the problem \eqref{eq2}. We obtain also that the realization of $-\mathcal{L}^H$ in $L^2$ with Dirichlet boundary conditions generates an analytic semigroup $(e^{-t\mathcal{L}^H})$. The positivity of $(e^{-t\mathcal{L}^H})$ can be proved applying the first Beurling-Deny criteria.

\section{Heston model: the variational formulation}
Throughout this article, the coefficients of the operator $\mathcal{L}^H$ are required to obey the Feller condition \eqref{feller-condition} and $\Omega=\mathbb{R}\times [a,\infty)$ with some positive constant $a$.

We propose to use form methods to solve the parabolic PDE in (\ref{eq2}). To this purpose we consider the weight functions
\[
\phi(x)=e^{\nu|x|}, \qquad \psi(y)=e^{\frac{\mu}{2}y^2},\quad (x,y)\in\Omega,
\qquad \nu,\,\mu>0,
\]
and define the Hilbert space
$$L^2_{\phi, \psi}(\Omega)=
\{v\,|\,(x,y)\mapsto v(x,y)\phi(x)\psi(y)\in L^2(\Omega)\}$$
equipped with the weighted $L^2$-norm
$$\|v\|_{\phi ,\psi}=\left(\int_\Omega |v(x,y)|^2\phi^2(x)\psi^2(y)\,dx\,dy\right)^{\frac{1}{2}}.$$
Furthermore we define the weighted Sobolev space
\[
V_{\phi,\psi}=
\Big\{v\,\Big|\quad \Big(v,\sqrt y{\frac{\partial v}{\partial x}},
\sqrt {y}{\frac{\partial v}{\partial y}}\Big)
\in (L^2_{\phi, \psi}(\Omega))^3\Big\}.
\]
The space $V_{\phi,\psi}$ is equipped with the norm
\[
\|u\|_{V_{\phi,\psi}}=
\Big(\|u\|^2_{\phi, \psi}+
\Big\|\sqrt y{\f{\partial u}{\partial x}}\Big\|^2_{\phi, \psi}+
\Big\|\sqrt {y}\, {\f{\partial u}{\partial y}}\Big\|^2_{\phi, \psi}\Big)^
{\frac{1}{2}}.
\]
The sesquilinear form associated to $\mathcal {L}^H$ in $L^2_{\phi ,\psi}(\Omega)$ is given by
\begin{equation}\label{eq3}
a^{\phi, \psi}_H(u,v)=
\int_{\Omega}(\mathcal {L}^H u)(x,y) \overline{v}(x,y)\phi^2(x)\psi^2(y) dx\,dy,
\qquad u,v\in C^{\infty}_c(\Omega).
\end{equation}

We note first the following standard result.

\begin{lemma}\label{l0}
The following assertions hold:
\begin{enumerate}
\item[(a)] The space of test functions $C_c^\infty(\Omega)$ is dense in $L^2_{\phi ,\psi}(\Omega)$,
\item[(b)] the space $V_{\phi,\psi}$ equipped with the norm
$\|\cdot \|_{V_{\phi,\psi}}$ is a Hilbert space.
\end{enumerate}
\end{lemma}
\begin{proof}
Let $u\in L^2_{\phi ,\psi}(\Omega)$. Then $u\phi \psi\in L^2(\Omega)$ and so, for any $\varepsilon >0$ there is $\varphi\in C_c^\infty(\Omega)$ such that $\|\varphi -u\phi \psi\|_{L^2}=\|\phi^{-1}\psi^{-1}\varphi -u\|_{\phi ,\psi}<\varepsilon$. Since $\phi^{-1}\psi^{-1}\varphi\in C_c(\Omega)$, we deduce that $C_c(\Omega)$ is dense in $L^2_{\phi ,\psi}(\Omega)$. Thus the assertion (a) follows by standard mollifier argument.

To prove (b) we have only to show that $V_{\phi,\psi}$ equipped with the norm
$\|\cdot \|_{V_{\phi,\psi}}$ is complete. Consider a Cauchy sequence $(u_n)$ in $(V_{\phi,\psi}, \|\cdot \|_{V_{\phi,\psi}})$. Since $y\ge a$, it follows that $V_{\phi,\psi}$ is continuously embedded in the classical weighted Sobolev space
$$H^1_{\phi ,\psi}(\Omega):=
\Big\{v\,\Big|\quad \Big(v,{\frac{\partial v}{\partial x}},
{\frac{\partial v}{\partial y}}\Big)
\in (L^2_{\phi, \psi}(\Omega))^3\Big\}.$$ Hence, $u_n$ converges to some $u\in H^1_{\phi ,\psi}(\Omega)$. On the other hand, by the convergence of $\sqrt{y}{\frac{\partial u_n}{\partial x}}$ and $\sqrt{y}{\frac{\partial u_n}{\partial y}}$ in $L^2_{\phi, \psi}(\Omega)$ (and hence a.e. by taking a subsequence), it follows that $u\in V_{\phi,\psi}$ and $u_n$ converges to $u$ with respect to the norm $\|\cdot \|_{V_{\phi,\psi}}$.
\end{proof}

The following lemma shows that $a_H^{\phi ,\psi}$ can be extended continuously to a sesquilinear form on
$V_{\phi,\psi}^0\times V_{\phi,\psi}^0$, where $V_{\phi,\psi}^0$ denotes the closure of $C^{\infty}_c(\Omega)$ in $V_{\phi,\psi}$
\begin{lemma}\label{l1}
There is a positive constant $M$ such that
$$|a_H^{\phi ,\psi}(u,v)|\le M \|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},\quad \forall u,\,v\in V_{\phi,\psi}^0.$$
\end{lemma}
\begin{proof}
Integrating by parts, it follows from (\ref{eq3}) that
\begin{eqnarray*}
a_H^{\phi ,\psi}(u,v) &=& \frac{1}{2}\int_\Omega y\frac{\partial u}{\partial x}\frac{\partial \overline{v}}{\partial x}\phi^2\psi^2 +\int_\Omega y\frac{\partial u}{\partial x}\overline{v}\left(\frac{\phi '}{\phi}\right)\phi^2\psi^2+\frac{\sigma^2}{2}\int_\Omega y\frac{\partial u}{\partial y}\frac{\partial \overline{v}}{\partial y}\phi^2\psi^2\\
& & +\frac{\sigma^2}{2}\int_\Omega \frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2+\mu \sigma^2\int_\Omega y^2\frac{\partial u}{\partial y}\overline{v}\phi^2 \psi^2+2\rho \sigma \int_\Omega y\frac{\partial u}{\partial y}\overline{v}\left(\frac{\phi '}{\phi}\right)\phi^2\psi^2\\
& & +\rho \sigma \int_\Omega y\frac{\partial u}{\partial y}\frac{\partial \overline{v}}{\partial x}\phi^2\psi^2-\int_\Omega(\omega \rho \sigma y^2-\frac{1}{2}y+r)\frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2\\
& & -\int_\Omega[\omega \sigma^2 y^2+\kappa(m-y)]\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2\\
& & -\int_\Omega \left[\frac{1}{2}\omega \sigma^2 y(\omega y^2+1)+\omega y\kappa(m-y)-r\right]u\overline{v}\phi^2\psi^2
\end{eqnarray*}
holds for $u,\,v\in C_c^\infty(\Omega)$.
By H\"older's inequality, and since $\frac{y}{a}\ge 1$ for $y\in [a,\infty),\,a>0$, we have
$$\left|\int_\Omega y\frac{\partial u}{\partial x}\frac{\partial \overline{v}}{\partial x}\phi^2\psi^2 \right|\le \|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},\,\left|\int_\Omega y\frac{\partial u}{\partial y}\frac{\partial \overline{v}}{\partial y}\phi^2\psi^2 \right|\le \|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},$$
$$\left|\int_\Omega y\frac{\partial u}{\partial y}\frac{\partial \overline{v}}{\partial x}\phi^2\psi^2 \right|\le \|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},\,\,\left|\int_\Omega \frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2\right|\le \frac{1}{\sqrt{a}}\|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},\,\hbox{\ and }$$
$$\left|\int_\Omega \frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2\right|\le \frac{1}{\sqrt{a}}\|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}}.$$

Since $\psi '(y)=\mu y\psi(y)$, it follows that
\begin{eqnarray}
\int_\Omega yu\overline{v}\phi^2\psi^2 &=& -\frac{1}{2\mu}\left(\int_\Omega \frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2+ \int_\Omega u\frac{\partial \overline{v}}{\partial y}\phi^2\psi^2\right),\label{eq5} \\
\int_\Omega y^2u\overline{v}\phi^2\psi^2 &=& -\frac{1}{2\mu}\left(\int_\Omega y\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2+ \int_\Omega y\frac{\partial \overline{v}}{\partial y}u\phi^2\psi^2+\int_\Omega u\overline{v}\phi^2\psi^2\right),\label{eq6} \\
\int_\Omega y^3u\overline{v}\phi^2\psi^2 &=& -\frac{1}{2\mu}\left(2\int_\Omega yu\overline{v}\phi^2\psi^2+\int_\Omega y^2\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2+ \int_\Omega y^2\frac{\partial \overline{v}}{\partial y}u\phi^2\psi^2\right)\label{eq7}.
\end{eqnarray}

Thus it suffices to estimate the integrals
$$\int_\Omega y\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2,\, \int_\Omega y^2\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2,\,
\int_\Omega y\frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2,\,\hbox{\ and }\int_\Omega y^2\frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2.$$
Applying (\ref{eq5}) and H\"older's inequality we have
\begin{eqnarray*}
\left|\int_\Omega y\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2\right| &\le & \|u\|_{V_{\phi ,\psi}}\|\sqrt{y}v\|_{\phi ,\psi}\le \frac{1}{a\mu}\|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}},\\
\left|\int_\Omega y\frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2\right| &\le & \|u\|_{V_{\phi ,\psi}}\|\sqrt{y}v\|_{\phi ,\psi}\le \frac{1}{a\mu}\|u\|_{V_{\phi ,\psi}}\|v\|_{V_{\phi ,\psi}}.
\end{eqnarray*}
On the other hand, applying again H\"older's inequality we get
\begin{eqnarray*}
\left|\int_\Omega y^2\frac{\partial u}{\partial y}\overline{v}\phi^2\psi^2\right| &\le & \|u\|_{V_{\phi ,\psi}}\|y^{\frac{3}{2}}v\|_{\phi ,\psi} \,\hbox{\ and }\\
\left|\int_\Omega y^2\frac{\partial u}{\partial x}\overline{v}\phi^2\psi^2\right| &\le & \|u\|_{V_{\phi ,\psi}}\|y^{\frac{3}{2}}v\|_{\phi ,\psi}.
\end{eqnarray*}
It remains to estimate $\|y^{\frac{3}{2}}v\|_{\phi ,\psi}$. It follows from (\ref{eq7}) that
\begin{eqnarray*}
\|y^{\frac{3}{2}}v\|_{\phi ,\psi}^2 &\le & \frac{1}{\mu}\left|\int_\Omega y^2\frac{\partial v}{\partial y}\overline{v}\phi^2\psi^2\right|\\
&\le & \frac{1}{2}\|y^{\frac{3}{2}}v\|_{\phi ,\psi}^2 +\frac{1}{2\mu^2}\|\sqrt{y}\frac{\partial v}{\partial y}\|_{\phi ,\psi}^2.
\end{eqnarray*}
Hence,
$$\|y^{\frac{3}{2}}v\|_{\phi ,\psi}\le \frac{1}{\mu}\|\sqrt{y}\frac{\partial v}{\partial y}\|_{\phi ,\psi}.$$
This ends the proof of the lemma.
\end{proof}

\section{Existence and uniqueness of solutions to the variational equation}
The following proposition deals with the quasi-accretivity of the sesquilinear form $a_H^{\phi ,\psi}$.
\begin{proposition}\label{p1}
Assume that \eqref{feller-condition} is satisfied. Then, under appropriate conditions on $\rho ,\,\nu ,\,\mu$ and $\omega$, there are constants $c_1>0$ and $c_2\in \R$ such that
\begin{equation}\label{Garding}
\Re a_H^{\phi ,\psi}(v,v)\ge c_1\|v\|_{V_{\phi ,\psi}}+c_2\|v\|_{\phi ,\psi}^2,\quad \forall v\in V^0_{\phi ,\psi}.
\end{equation}

\end{proposition}
\begin{proof}

The real part of the quadratic form $a_H^{\phi,\psi}(v,v)$ is given by
\begin{eqnarray}\label{eq8}
\Re a_H^{\phi,\psi}(v,v)&=&
{\frac{1}{2}}\int_{\Omega}y\Big|{\frac{\partial v}{\partial x}}\Big|^2
\phi^2\psi^2+
{\frac{\sigma^2}{2}}\int_{\Omega}y\Big|{\frac{\partial v}{\partial y}}\Big|^2
\phi^2\psi^2 \nonumber
\\
& & \,+\Re\left(\int_{\Omega}y\,{\frac{\partial v}{\partial x}}\overline{v}\left(\frac{\phi'}{\phi}\right)
\phi^2\psi^2\right)+
\Re \left(\int_{\Omega}\Big({\frac{1}{2}}y-\omega\rho\sigma y^2-r\Big)
{\frac{\partial v}{\partial x}}\overline{v}\phi^2\psi^2\right) \nonumber
\\
& & \,+\Re \left(\int_{\Omega}\Big({\frac{\sigma^2}{2}}-\kappa m)\Big)
{\frac{\partial v}{\partial y}}\overline{v}\phi^2\psi^2\right)
+\kappa \Re \left(\int_{\Omega}y
{\frac{\partial v}{\partial y}}\overline{v}\,\phi^2\psi^2\right) \nonumber
\\
& & \,-\omega\sigma^2
\Re \left(\int_{\Omega}y^2{\frac{\partial v}{\partial y}}\overline{v}\phi^2\psi^2\right)
+\sigma^2 \mu \Re \left(\int_{\Omega}y^2{\frac{\partial v}{\partial y}}\overline{v}
\phi^2\psi^2\right) \nonumber
\\
& & \,+\rho\,\sigma \Re \left(\int_{\Omega}y\,{\frac{\partial v}{\partial x}}
{\frac{\partial \overline{v}}{\partial y}}
\phi^2\psi^2\right)+
2\rho\sigma \Re \left(\int_{\Omega}y{\frac{\partial v}{\partial y}}\overline{v}\left(\frac{\phi'}{\phi}\right)
\phi^2\psi^2\right) \nonumber
\\
& & \,-{\frac{1}{2}}\omega^2\sigma^2\int_{\Omega} y^3 |v|^2\,\phi^2\psi^2-
(\omega \kappa m+{\frac{\omega\sigma^2}{2}})
\int_{\Omega}y\,|v|^2\,\phi^2\psi^2 \nonumber
\\
& & \,+\omega \kappa \int_{\Omega} y^2 |v|^2\,\phi^2\psi^2+
r\int_{\Omega}|v|^2\,\phi^2\psi^2 \nonumber
\\
& & \,= I_1+I_2+I_3+I_4+I_5+I_6+I_7+I_8+I_9+I_{10}+I_{11}+I_{12}+I_{13}+I_{14}.
\end{eqnarray}
By the definition of the $L^2_{\phi,\psi}$ - norm
\begin{equation}\label{eq9}
I_1+I_2={\frac{1}{2}}\Big\|\sqrt{y}{\frac{\partial v}{\partial x}}\Big\|^2_{\phi,\psi}+
{\frac{\sigma^2}{2}}\Big\|\sqrt{y}{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi}.
\end{equation}
To estimate the next integrals we use H\"older's and Young's
inequalities as well as integration by parts taking in mind that
$\Re \left({\frac{\partial v}{\partial x}}\overline{v}\right)={\frac{1}{2}}
{\frac{\partial |v|^2}{\partial x}}$,
$\Re \left({\frac{\partial v}{\partial y}}\overline{v}\right)={\frac{1}{2}}
{\frac{\partial |v|^2}{\partial y}}$, $\phi'=(sign\,x)\nu \phi$ and
$\psi'=\mu y \psi$.

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_3$ }:
\begin{equation}\label{eq10}
|I_3| \le{\frac{1}{2}}\epsilon_1
\Big\|\sqrt{y}{\frac{\partial v}{\partial x}}\Big\|^2_{\phi,\psi}+
{\frac{\nu^2}{2\epsilon_1}}\|\sqrt{y} v\|^2_{\phi,\psi},
\qquad \epsilon_1>0.
\end{equation}

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_4$ }:
\begin{equation}\label{eq11}
|I_4|  \le  {\frac{\nu}{2}}\|\sqrt{y} v\|^2_{\phi,\psi} +
\omega\rho\sigma\nu
\int_{\Omega}y^2 |v|^2\phi^2\psi^2
+r\nu\| v\|^2_{\phi,\psi}.
\end{equation}

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_5$ }:
\begin{equation}\label{eq12}
I_5 =\big(\kappa m -{\frac{\sigma^2}{2}}\big  )\mu
\|\sqrt{y} v\|^2_{\phi,\psi}.
\end{equation}

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_6$ and $I_{10}$ }:
\begin{equation}\label{eq13}
I_6+I_{10}\ge
-\left({\frac{\kappa}{2}}+\rho\sigma\nu\right)
\|v\|^2_{\phi,\psi}-
\left(\kappa \mu+2\rho\sigma\nu\mu\right)\int_\Omega y^2|v|^2\phi^2\psi^2.
\end{equation}

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_7$ and $I_{8}$ }:
\begin{equation}\label{eq14}
I_7+I_8=
\sigma^2(\mu-\omega)
\Re \left(\int_{\Omega}y^2{\frac{\partial v}{\partial y}}\overline{v}\phi^2\psi^2\right).
\end{equation}

\bigskip\noindent
$\bullet\;$
{\it Estimate of $I_9$ }:
\begin{equation}\label{eq15}
|I_9|\le
{\frac{1}{2}}\epsilon_2
\Big\|\sqrt{y}{\frac{\partial v}{\partial x}}\Big\|^2_{\phi,\psi}+
{\frac{\rho^2\sigma^2}{2\epsilon_2}}
\Big\|\sqrt{y}{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi},
\qquad \epsilon_2>0.
\end{equation}
On the other hand, it follows from (\ref{eq7}) that
\begin{equation}\label{eq16}
\|\sqrt{y} v\|^2_{\phi,\psi}=-\Re \left(\int_\Omega y^2\frac{\partial v}{\partial y}\overline{v}\phi^2\psi^2\right)
-\mu\|y^{\frac {3}{2}} v\|^2_{\phi,\psi}.
\end{equation}
It follows from (\ref{eq8})-(\ref{eq16}) that
\begin{eqnarray*}
\begin{split}
\Re a_H^{\phi,\psi}(v,v)&\ge
\alpha_1
\Big\|\sqrt{y}{\frac{\partial v}{\partial x}}\Big\|^2_{\phi,\psi}+
\alpha_2
\Big\|\sqrt{y}{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi}+
\alpha_3
\|v\|_{\phi,\psi}^2
\\&
+\alpha_4
\int_{\Omega}y^2 |v|^2\phi^2\psi^2
+\alpha_5
\Re \left(\int_{\Omega}y^2\,{\frac{\partial v}{\partial y}}\overline{v}
\phi^2\psi^2\right)
\\&
+\alpha_6
\|y^{\frac {3}{2}} v\|^2_{\phi,\psi},
\end{split}
\end{eqnarray*}
where

\medskip

\begin{itemize}

\medskip
\item[ ]
$\alpha_1={\frac{1}{2}}\Big(1-\epsilon_1-\epsilon_2\Big)$,

\medskip
\item[ ]
$\alpha_2={\frac{\sigma^2}{2}}\big(1-{\frac{\rho^2}{\epsilon_2}}\big)=:\frac{\sigma^2}{2}\tau$,

\medskip
\item[ ]
$\alpha_3=(-r\nu -\frac{\kappa}{2}-\rho \sigma \nu +r)$,

\medskip
\item[ ]
$\alpha_4=(\omega \kappa -\kappa \mu -\omega\rho\sigma\nu -2\rho\sigma\nu \mu)$,

\medskip
\item[ ]
$\alpha_5=
\omega\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)+\sigma^2\mu +\beta -\left(\kappa m-\frac{\sigma^2}{2}\right)\mu $,

\medskip
\item[ ]
$\alpha_6=
\omega \mu \Big(\kappa m+{\frac{\sigma^2}{2}}\Big)
-\omega^2{\frac{\sigma^2}{2}}
+\mu\Big(\beta -\left(\kappa m-\frac{\sigma^2}{2}\right)\mu\Big)$

\medskip

\item[ ]
$\quad\>\,=
\mu\alpha_5+\omega\mu\sigma^2
-\sigma^2\mu^2-\omega^2{\frac{\sigma^2}{2}}$
\end{itemize}
and
\[\beta=\Big({\frac{\nu^2}{2\epsilon_1}}+{\frac{\nu}{2}}\Big).
\]

\medskip\noindent
In order to ensure that the coefficients
$\alpha_1$, $\alpha_2$ are nonnegative we use the assumption $|\rho |<1$ and we take
$\epsilon_1$ and $\epsilon_2$
such that
\[
\rho^2<\epsilon_2<1-\epsilon_1.
\]
Furthermore we take $\omega >\mu$, and
\begin{equation}\label{eq18}
\nu\le{\frac{\kappa(\omega -\mu)}{\rho\sigma(\omega+2\mu)}},
\end{equation}
when $0<\rho <1$ in order to obtain that $\alpha_4\ge0$ for any $|\rho |<1$.

To prove the lemma, we need first to show that $\Big|\int_{\Omega}y^2\,{\frac{\partial v}{\partial y}}\overline{v}
\phi^2\psi^2\Big|$  can be estimated by
$\Big\|\sqrt y{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi}$.
Indeed, by means of H\"older's and Young's inequalities,
\begin{equation}\label{eq19}
\begin{split}
\Big|\int_{\Omega}y^2\,{\frac{\partial v}{\partial y}}\overline{v}
\phi^2\psi^2\Big|&=
\Big|\int_{\Omega}\sqrt y\,{\frac{\partial v}{\partial y}}y^{{\frac {3}{2}}}\overline{v}
\phi^2\psi^2\Big|
\\&
\le {\frac{\epsilon_3}{2}}
\Big\|\sqrt{y}{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi}+
{\frac{1}{2\epsilon_3}}\|y^{{\frac {3}{2}}} v\|^2_{\phi,\psi}
\end{split}
\end{equation}
with any $\epsilon_3>0$.

On the other hand, using the assumption $\kappa m>\frac{\sigma^2}{2}$ and $\omega >\mu$, we deduce $\alpha_5>0$ and hence
$$\omega>{\frac{\Big(\kappa m-{\frac{3}{2}}\sigma^2\Big){\mu}-\beta}
{\kappa m-{\frac{\sigma^2}{2}}}}.$$ So, by (\ref{eq19}), we obtain
\begin{eqnarray}\label{eq-new}

\Re a_H^{\phi,\psi}(v,v)&\ge &
\alpha_1
\Big\|\sqrt{y}{\frac{\partial v}{\partial x}}\Big\|^2_{\phi,\psi}+
\Big(\alpha_2-\alpha_5{\frac{\epsilon_3}{2}}\Big)
\Big\|\sqrt{y}{\frac{\partial v}{\partial y}}\Big\|^2_{\phi,\psi}\nonumber
\\& &
\quad +\alpha_3
\|v\|^2_{\phi,\psi}+
\Big(\alpha_6-{\frac{\alpha_5}{2\epsilon_3}}\Big)\|y^{{\frac {3}{2}}} v\|^2_{\phi,\psi}.

\end{eqnarray}
Choosing
\begin{equation}\label{eq20'}
\epsilon_3<{\frac{2\alpha_2}{\alpha_5}},
\end{equation}
we deduce that $\alpha_2-\alpha_5{\frac{\epsilon_3}{2}}>0$.\\
The next step is to prove that
\begin{equation}\label{eq21}
\alpha_6-{\frac{\alpha_5}{2\epsilon_3}}\ge 0.
\end{equation}
This is equivalent to show that $\omega$ satisfies the inequality
\begin{equation}\label{eq22}
\begin{split}
{\frac{\sigma^2}{2}}\omega^2-&
\Big[\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+\sigma^2\mu\Big]\omega+
\sigma^2\mu^2 -\beta\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+
\\&
+\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)\mu
-\sigma^2\mu\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)\le 0.
\end{split}
\end{equation}
So we need to have
$$
\Delta_{\omega}:=\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)^2
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)^2+
\mu\sigma^4\Big(\mu-{\frac{1}{\epsilon_3}}\Big)+
2\beta\sigma^2\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)\ge 0.
$$
Let us observe that (\ref{eq21}) can be rewritten in the following way
$$
\left(\mu-{\frac{1}{2\epsilon_3}}\right)
\alpha_5+\omega\mu\sigma^2
-\sigma^2\mu^2-\omega^2{\frac{\sigma^2}{2}}\ge 0,
$$
from which we can deduce that
$$
\epsilon_3>{\frac{1}{2\mu}},
$$
since $\omega^2{\frac{\sigma^2}{2}} -\omega\mu\sigma^2
+\sigma^2\mu^2=\frac{\sigma^2}{2}\left((\omega -\mu)^2+\mu^2\right)>0$. Thus,
\begin{equation}\label{eq25}
\Delta_{\omega}\ge0 \Longleftrightarrow
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)^2\ge
{\frac{2\epsilon_3\mu}{2\epsilon_3\mu-1}}
\left[{\frac{2-2\epsilon_3\mu}{2\epsilon_3\mu-1}}-
{\frac{2\beta}{\mu\sigma^2}}\right]\sigma^4=:
g(2\epsilon_3\mu)\sigma^4,
\end{equation}
where \[
g(t)={\frac{(2+c)t-(1+c)t^2}{(t-1)^2}}
\]
with $c={\frac{2\beta}{\mu\sigma^2}}$. On the other hand, by \eqref{feller-condition}, there exists $\delta >0$ such that $\kappa m>(1+2\sqrt{\delta})\frac{\sigma^2}{2}$. Thus, it follows that
\begin{equation}\label{eq25bis}
\left(\kappa m-\frac{\sigma^2}{2}\right)^2>\delta \sigma^4.
\end{equation}
Hence, (\ref{eq25}) holds if $g(2\epsilon_3\mu)\le \delta$. An easy computation shows that if
\begin{equation}\label{eq27}
2\epsilon_3\mu >\overline{t}:=1+\frac{1}{\sqrt{1+\delta}}
\end{equation}
then $g(2\epsilon_3\mu)< \delta$ and therefore $\Delta_\omega > 0$. On the other hand, it follows from (\ref{eq20'}) and (\ref{eq27}) that $\alpha_5<\frac{4\mu\alpha_2}{\overline{t}}$ and therefore, using (\ref{eq18}),
\begin{equation}\label{eq28}
\mu < \omega<{\frac{\Big(\kappa m-{\frac{3}{2}}\sigma^2\Big)\mu+
{\frac{4}{\overline t}}\mu\alpha_2-\beta}{\kappa m-{\frac{\sigma^2}{2}}}}=
\mu+{\frac{\gamma\sigma^2\mu-\beta}{\kappa m-{\frac{\sigma^2}{2}}}},
\end{equation}
where
$\gamma={\frac{2\tau}{\overline t}}-1$.
This implies in particular that $\gamma >0$ and
\begin{equation}\label{eq30}
\mu >\frac{\beta}{\gamma \sigma^2}.
\end{equation}
Thus, using conditions (\ref{eq18}) and (\ref{eq28}), we deduce that (\ref{eq22}) holds if $\omega \in (M,N)$, where
\[
M=\hbox{max}\left\{
{\frac{
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+\sigma^2\mu\
-{\sqrt\Delta_\omega}}
{\sigma^2}},
\mu\right\}
\]
and
\[
N=\hbox{min}\left\{
{\frac{
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+\sigma^2\mu\
+{\sqrt\Delta_\omega}}
{\sigma^2}},
\mu+{\frac{\gamma\sigma^2\mu-\beta}{\kappa m-{\frac{\sigma^2}{2}}}}
\right\}.
\]
Let us observe that
\[
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+\sigma^2\mu\
>{\sqrt\Delta_\omega}
\]
if and only if
\begin{equation}\label{eq30'}
\beta<\mu \Big(\kappa m-{\frac{\sigma^2}{2}}\Big)+
{\frac{\mu\sigma^2}{2\epsilon_3\mu-1}}.
\end{equation}
Moreover, it is easy to see that $\mu \le N$.\\
To get
\[
{\frac{
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)+\sigma^2\mu\
-{\sqrt\Delta_\omega}}
{\sigma^2}}
<
\mu+{\frac{\gamma\sigma^2\mu-\beta}{\kappa m-{\frac{\sigma^2}{2}}}}
\]
or, equivalently,
\begin{equation}\label{eq31}
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)
\Big(\mu-{\frac{1}{2\epsilon_3}}\Big)-
{\frac{\sigma^2}{\kappa m-{\frac{\sigma^2}{2}}}}
\left(\gamma\sigma^2 \mu-\beta\right)
<{\sqrt\Delta_\omega},
\end{equation}
we firstly require that
\begin{equation}\label{eq32}
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)^2\ge
{\frac{2\epsilon_3\mu}{2\epsilon_3\mu-1}}
\left(\gamma-
{\frac{\beta}{\mu\sigma^2}}\right)\sigma^4=:
f(2\epsilon_3\mu)\sigma^4
\end{equation}
to have that the left side in (\ref{eq31}) is nonnegative. \\
It follows from (\ref{eq27}) and (\ref{eq30}) that $0<f(2\epsilon_3\mu)$. Thus, from (\ref{eq25bis}) we obtain (\ref{eq32}) if
$f(2\epsilon_3\mu)\le \delta$.
From the definition of $\overline{t}$ and since $\tau <1$ one can see that $\delta >\gamma$.
Using again $\tau <1$, we obtain
$2\tau -1<1<\sqrt{1+\delta}=\frac{\delta}{\sqrt{1+\delta}}+\frac{1}{\sqrt{1+\delta}}$ and so,
\begin{eqnarray*}
\gamma -\frac{c}{2} &< & \gamma =\frac{2\tau}{\overline{t}}-1\\
&<& \frac{\delta}{\overline{t}\sqrt{1+\delta}}\\
&=& \frac{\delta}{1+\sqrt{1+\delta}}.
\end{eqnarray*}
Hence,
$$\sqrt{1+\delta}<\frac{\delta}{\gamma -(c/2)}-1.$$ This implies that
 $\overline{t}> \frac{\delta}{\delta -\gamma +(c/2)}$. This together with (\ref{eq27}) imply that
$f(2\epsilon_3\mu)\le \delta .$ Thus, (\ref{eq32}) holds.\\
Using now the definition of $\Delta_\omega$, one can see that proving (\ref{eq31}) is equivalent to show
\begin{equation}\label{eq33}
\Big(\kappa m-{\frac{\sigma^2}{2}}\Big)^2>
{\frac{2\epsilon_3\mu}{2\epsilon_3\mu(1+2\gamma)-
(2+2\gamma)}}
\left(\gamma-
{\frac{\beta}{\mu\sigma^2}}\right)^2\sigma^4=
{\tilde f}(2\epsilon_3\mu)\sigma^4.
\end{equation}
Since $\overline{t}<2$ and
$$\overline{t}<\inf_{\gamma \in (0,\frac{2}{\overline{t}}-1)}\left(1+\frac{1}{1+2\gamma}\right)=\frac{4}{4-\overline{t}},$$
one deduces that ${\tilde f}(2\epsilon_3\mu)<0$ and hence (\ref{eq33}) holds, provided that
$$
\overline{t}<2\epsilon_3\mu < 1+\frac{1}{1+2\gamma}.
$$
Therefore, if $\omega \in (M,N),\, \nu$ satisfies (\ref{eq18}) when $\rho >0$, and
$$\beta <\min\left\{\mu \gamma \sigma^2,\mu\left(\kappa m-\frac{\sigma^2}{2}\right)+\frac{\mu \sigma^2}{2\epsilon_3\mu -1}\right\}$$
from (\ref{eq30}) and (\ref{eq30'}), with $0<\gamma <\delta$. Then \eqref{eq-new} can be written as
$$\Re a_H^{\phi ,\psi}(v,v)\ge c_1\|v\|_{V_{\phi ,\psi}}+\alpha_3\|v\|^2_{\phi ,\psi},\quad \forall v\in C_c^\infty(\Omega),$$
provided that
$$ \frac{2\rho^2}{2-\overline{t}}<\epsilon_2<1-\epsilon_1  \hbox{\ and }
\epsilon_3\in\left({\frac{\overline t}{2\mu}},
\hbox{min}\left\{
{\frac{2\alpha_2}{\alpha_5}},
{\frac{1}{2\mu}}
\left(1+{\frac{1}{1+2\gamma}}\right)\right\}\right),
$$
where $c_1:=\min\{\alpha_1,\alpha_2-\alpha_5\frac{\epsilon_3}{2},a^3(\alpha_6-\frac{\alpha_5}{2\epsilon_3})\}>0$.
We note that the above first inequality satisfied by $\epsilon_2$ is a consequence of $\gamma >0$. On the other hand, by assuming $|\rho|<\sqrt{\frac{1}{2}-\frac{1}{2\sqrt{1+\delta}}}$, there exists a $\epsilon_1$ satisfying the above condition, since
$\sqrt{\frac{1}{2}-\frac{1}{2\sqrt{1+\delta}}}=\sqrt{\frac{2-\overline{t}}{2}}.$
\end{proof}
\begin{remark}\label{r1}
It follows from Lemma \ref{l1} and Proposition \ref{p1} that the form norm defined by $$\|u\|_{a_H}:=\sqrt{\Re a_H^{\phi ,\psi}(u,u)+(1-c_2)\|u\|_{\phi ,\psi}},$$
is equivalent to the norm $\|\cdot \|_{V_{\phi ,\psi}}$. So, by Lemma \ref{l0}, the sesquilinear form $a_H^{\phi ,\psi}$ with domain $V^0_{\phi ,\psi}$ is closed.
\end{remark}

We define the operator associated to $a_H^{\phi ,\psi}$ by
\begin{eqnarray*}
D(A) &=& \{u\in V^0_{\phi ,\psi}\,s.t.\,\exists v\in L^2_{\phi ,\psi}(\Omega): a_H^{\phi ,\psi}(u,\varphi)=\int_\Omega v\overline{\varphi}\phi^2\psi^2,\,\forall \varphi \in C_c^\infty(\Omega)\} \\
Au &=& v.
\end{eqnarray*}

The estimate \eqref{Garding} is known as Garding's inequality. Applying \cite[Section 4.4, Theorem 4.1]{LM} we obtain the existence of a unique weak solution to the problem \eqref{eq2}.
\begin{theorem}
Assume the same conditions as in Proposition \ref{p1}. Then, there is a unique weak solution $u\in L^2([0,T],V^0_{\phi ,\psi})\cap C([0,T],L^2_{\phi ,\psi}(\Omega))$ to the parabolic problem \eqref{eq2}.
\end{theorem}

Applying the Lumer-Phillips theorem we obtain the following generation result.
\begin{theorem}
Assume the same conditions as in Proposition \ref{p1}. Then, the operator $-A$ defined above generates a positivity preserving and quasi-contractive analytic semigroup on $L^2_{\phi ,\psi}(\Omega)$.
\end{theorem}
\begin{proof}
It follows form Lemma \ref{l0}, Lemma \ref{l1}, Proposition \ref{p1} and Remark \ref{r1} that the form $a_H^{\phi ,\psi}$ with domain $V^0_{\phi ,\psi}$ is densely defined, closed, continuous and quasi-accretive sesquilinear form on $L^2_{\phi ,\psi}(\Omega)$. Thus, $-A$ generates a quasi-contractive analytic semigroup $(e^{-tA})_{t\ge 0}$ on $L^2_{\phi ,\psi}(\Omega)$ (cf. \cite[Theorem 1.52]{Ouhabaz}).

For the positivity, we note first that the semigroup $(e^{-tA})_{t\ge 0}$ is real and one can see that for every
$u\in D(a_H^{\phi ,\psi})\cap L^2_{\phi ,\psi}(\Omega ,\R),\,u^+ \in D(a_H^{\phi ,\psi})$ and $a_H^{\phi ,\psi}(u^+,u^-)=0$,
since $u^-=(-u)^+$ and $\nabla u^+=\chi_{\{u>0\}}\nabla u$ (cf. \cite[Proposition 4.4]{Ouhabaz}). Thus, by the first Beurling-Deny criteria, $(e^{-tA})_{t\ge 0}$ is a positivity preserving semigroup on $L^2_{\phi ,\psi}(\Omega)$ (cf. \cite[Theorem 2.6]{Ouhabaz}).

\end{proof}


TITLE: Derivative of $f(x)=\|Ax\|_2^2$
QUESTION [0 upvotes]: I'm trying to find the derivative of $f(x)=\|Ax\|_2^2$ where $A$ is some matrix and $\|u\|_2$ is the euclidean norm of $u$, $\|u\|_2 = \sqrt{u_1^2+u_2^2+\cdots+u_n^2}$
I know how to do this by expanding the terms, using a lot of $\sum$ signs etc, but I am trying to avoid all that by using the definition.
$$f'(x) = \lim_{t \to 0} \frac{f(x+th)-f(x)}{t} = \lim_{t \to 0} \frac{\|Ax+Ath\|_2^2-\|Ax\|_2^2}{t}=\lim_{t \to 0} \frac{(\|Ax+Ath\|_2+\|Ax\|_2)(\|Ax+Ath\|_2-\|Ax\|_2)}{t}$$
And I'm stuck here, don't know how to proceed.
Is there a way of doing this without actually writing each norm as a sum and writing $Ax$ explicitly etc?

REPLY [3 votes]: We have
$$f(x)=\langle Ax,Ax\rangle =\varphi\circ\psi(x)$$
where
$$\varphi(u,v)=\langle u,v\rangle$$
is a bilinear map
and
$$\psi(x)=(Ax,Ax)$$
is a linear map, hence by the chain rule  we have
$$Df(x)h=D\varphi(\psi(x))D\psi(x)h=D\varphi(\psi(x))(Ah,Ah)=\langle Ax,Ah\rangle+\langle Ah,Ax\rangle\\=2\langle Ax,Ah\rangle$$


text:
From space to healthcare, energy to transportation, manufacturing to agriculture, autonomous systems are gathering increased attention and importance. The synthesis and analysis of autonomous systems pose formidable challenges to overcome which a systematic theory of risk-aware autonomous systems is necessary. A crucial building block of this theory forms the focus of this paper, and pertains to a new tool for designing risk-aware algorithms for use in autonomous systems.

Safety-critical autonomous systems abound in a variety of sectors including transportation, energy, robotics, and manufacturing. A central property of these systems is self-governance in the presence of abrupt changes in the system environment. Many of these abrupt changes can be modeled in the form of parametric changes in a dynamic system. The challenge is to minimize the risk that occurs in this context using real-time tools. The new tool that we propose is paper is the use of sub-Gaussian spectral lines for parameter estimation. We will show in this paper that this tool (a)  can be employed in finite-time, (b) has the ability to accurately estimate the unknown parameters, and (c) enables minimization of risk of failure during online performance of the autonomous system.

The specific class of dynamic systems we will focus on is a linear time-invariant systems whose parameters are to be estimated, a problem that has been investigated at length in recent years \cite{Abbasi2011, Dean_2018a, Dean_2018, Foster_2020, Matni2019, Sarkar_2019, Sarkar_2019a, Simchowitz_2019, Simchowitz_2018, Tsiamis_2019, Wagenmaker2020}.  In contrast to the approaches taken in these papers where the exogenous input is chosen using independent realizations of Gaussian noise, we choose a deterministic signal constructed using the theory of spectral lines \cite{Boyd_1986,Boyd_1983}, which has been demonstrated to be effective in learning the parameters of the system, c.f. \cite{Anderson_1977,Anderson_1982,Narendra_1987,Willems2005}.

While randomization of the control input allows for clean analysis of estimation using well-known tools, it is undesirable for several reasons in safety-critical autonomous systems. First and foremost, in safety-critical systems, the addition of intentional randomness of exogenous inputs is undesirable as it may excite unmodeled dynamics \cite{Dydek2008, Gorinevsky2012}.  Such unmodeled dynamics are almost always present due to several reasons in any physical system \cite{DoyleStein81}. No dynamic system can be perfectly modeled; modeling errors due to nonlinearities, higher-order linear dynamics, and/or unknown underlying mechanisms are inevitable. Second, any exogenous input that is synthesized using a computational algorithm has to be physically realizable.  Typically actuators are the entities in an autonomous system that perform this role of transduction from a digital signal to a physical signal in the appropriate energetic domain (ex. position, torque, heat, current). All actuators have limited bandwidth  and therefore poor fidelity in reproducing high frequencies (see Figure \ref{fig:inputs}).  Finally, Gaussian noise in principle is unbounded. This poses two obvious problems in light of the two issues mentioned above – they can excite any unmodeled dynamics thereby introducing significant inaccuracies in the parameter estimation which in turn can pose a risk for any estimation-based closed-loop control decisions. It may not be simply possible to accurately realize the prescribed input $u_k$ \cite{Lavretsky2013} thereby introducing additional inaccuracies in the estimation.

\begin{figure}
    \centering
    \includegraphics[width = 0.8\textwidth]{imgs/inputs.png}
    \caption{Examples of inputs dictated to a physical system (blue) and their realized counterparts (red), represented by feeding the planned inputs through a low pass filter to simulate physical constraints on an actuator. While the frequency content of the spectral-lines based signal (bottom) is unchanged by the low pass filter, the realized white noise signal (top) no longer consists of independent Gaussian noise.}
    \label{fig:inputs}
\end{figure}

This paper proposes a new tool for designing risk-aware algorithms for use in autonomous systems, in the form of sub-gaussian spectral lines. This represents a finite-time tool and  leads to estimates of the unknown parameter in the underlying dynamic model of the autonomous system. A deterministic choice of the exogenous signal is proposed, and constructed using a combination of spectral lines. We show that using this tool, a tunable parameter error bound can be determined. We also show that reduced regret can be achieved, and therefore proactively quantify and mitigate risks against task goals and safety. Formal guarantees both on the parameter error bounds and on the risk of failure are provided.

\section{Problem Formulation}

This work is motivated by physical systems that are governed by non-linear dynamics and perturbed by unobserved noise, where observations are made at discrete time steps.
That is, the general system-model which is considered is of the form
\begin{equation} \label{eq:intro-nonlinear-general}
    x_{k+1} = f(x_k, u_k) + \eta_k\,, \quad \eta_k \stackrel{i.i.d.}{\sim} \subG(\sigma^2 I) \,,
\end{equation}
where $x_k \in \R^n$ represents the state of a dynamical system, $u_k \in \R^{m}$ represents an exogenous input, and $\eta_k \in \R^n$ represents unobserved disturbances.
In practice, the system above can have multiple equilibrium points, and a practitioner may have the objective of steering the system towards a particular equilibrium point.
In a region around the equilibrium point, one would expect the dynamics of the system to be dominated by linear dynamics, and it is reasonable to model the system as being a linear system in the presence of unmodeled dynamics.
Hence, the starting point for this paper is a system-model of the form
\begin{align}
x_{k+1} &= A_* x_k + B_* u_k + w_k+ \eta_k,\label{unmodeled-intro-x} \\
&\eta_k \stackrel{i.i.d.}{\sim} \subG(\sigma^2 I)\,, \label{unmodeled-intro-eta} \\
w_{k} &= f(x_0, w_{k-1}, \dots, w_0, u_k, \dots u_0 ) \label{unmodeled-intro-w}\,.
\end{align}
In this setting, the observations $x_k$ are measured, $A_*$ and $B_*$ are fixed but unknown, $\eta_k$ is unobserved, and the control input $u_k$ is selected by the practitioner.
The values $w_k \in \R^n$ then represents the effect of all unmodeled components in the system and is therefore unknown.
In practice, the presence of $w_k$ may be due to higher-order linear dynamics, nonlinearities, and/or due to other effects that cannot be precisely accounted for \cite{DoyleStein81, Khalil2002}.
Typically $w_k$ remains small for low amplitudes and/or low frequencies and large if either amplitudes or frequencies become large.
It is therefore often desired to keep the frequency content of $u_k$ small (see descriptions of $l_m(\omega)$ in \cite{DoyleStein81}) and amplitude small \cite{Khalil2002}.
The unmodeled dynamics in \eqref{unmodeled-intro-w} could be even more complex  with dependence on $x_k$ for all $k$.
Together with $w_k$ and $\eta_k$, we note that the actual state has unmodeled components both due to deterministic mechanisms due to \eqref{unmodeled-intro-w} and stochastic mechanisms represented in \eqref{unmodeled-intro-eta}.

In contrast to the above representation of a model of a safety-crticial system, the machine learning community has focused on modeling of a linear dynamical system and learning its parameters using independent Gaussian noise as the exogenous input \cite{Abbasi2011, Dean_2018a, Dean_2018, Foster_2020, Matni2019, Sarkar_2019, Sarkar_2019a, Simchowitz_2019, Simchowitz_2018, Tsiamis_2019, Wagenmaker2020}.
Specifically, these works consider a system-model of the form
\begin{equation}
\label{lti-noisy-intro}
x_{k+1} = A_* x_k + B_* u_k + \eta_k, \quad \eta_k \stackrel{i.i.d.}{\sim} \subG(\sigma^2 I) \,.
\end{equation}
In the machine learning literature, the control input $u_k \in \R^m$ is either selected solely according to independent realizations of $\cN(0, \sigma_u^2 I)$, or is perturbed by independent realizations of Gaussian noise. More importantly, the underlying analysis in these papers neglects the presence of $w_k$ as in \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w} altogether.

As discussed above, while randomization of the control input allows for clean analysis of estimation using well-known tools, it is undesirable for several reasons.
In safety-critical systems, the addition of intentional randomness of the exogenous input is undesirable as it may excite unmodeled dynamics \cite{Dydek2008, Gorinevsky2012}, and a noise-based signal may not be physically realizable due to constraints of physical actuators (Figure \ref{fig:inputs}).

Here, we propose a new approach for parameter estimation of \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w} based on the theory of spectral lines, proposed in \cite{Boyd_1986,Boyd_1983}, in which a deterministic exogenous signal may be used to learn the parameters of the system, c.f. \cite{Anderson_1977,Anderson_1982,Narendra_1987,Willems2005}.
These methods have been explored in depth in the field of adaptive control  \cite{Astrom_1995,Ioannou1996,Krstic_1995,Narendra2005,Sastry_1989}.
Our results prove useful for both learning the system \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, as well as controlling the system, and we present theoretical results in the context of the Linear Quadratic Regular for the idealized system \eqref{lti-noisy-intro} which show competitive guarantees on Regret as considered in the literature \cite{Cohen2019, Mania2019}.

\paragraph{Related Work} The recent machine learning literature has addressed parameter estimation in linear dynamical systems in the context of control \cite{Dean_2018a, Dean_2018, Matni2019, Simchowitz_2019} and system identification \cite{Abbasi2011, Hardt_2016, Sarkar_2019, Sarkar_2019a, Farandobeh_2017,  Simchowitz_2018, Wagenmaker2020}.
In the former, the goal is to show high-probability guarantees on the regret of the algorithm together with a Linear Quadratic Regulator in finite time \cite{Dean_2018a, Dean_2018, Matni2019, Simchowitz_2019}.
In the latter,  papers such as \cite{Hardt_2016, Sarkar_2019,Farandobeh_2017,  Simchowitz_2018, Wagenmaker2020} have focused on system identification and provide high-probability guarantees of parameter estimates in finite time.
Here, we show that the toolkit based on spectral lines can be used for both applications, and present our theorem statements in terms of both high probability guarantees for the systems \eqref{lti-noisy-intro} and \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w} as well as in terms of Regret for the Linear Quadratic Regulator.

A closer examination of the results of two specific papers in the above list, \cite{Sarkar_2019, Wagenmaker2020}, is in order. Both of these works show estimation rates that decay as $\Tilde{O}(1/\sqrt{T})$. In Sarkar and Rakhlin \cite{Sarkar_2019}, the control input is taken to be a Gaussian input,
\begin{equation} \label{white-noise-input}
u_k = s_k, \quad s_k \overset{i.i.d.}{\sim} \cN(0, \sigma_u^2 I) \,, \quad  \forall k \in \{1, \dots, T \}  \,.
\end{equation}
In contrast, Wagenmaker and Jamieson \cite{Wagenmaker2020} add a deterministic, periodic $\tilde{u}_k$ in addition to $s_k$.
A numerical optimization procedure is used to actively determine $\tilde{u}_k$ in Wagenmaker and Jamieson \cite{Wagenmaker2020} and it is shown that it is advantageous to the passive approach in Sarkar and Rakhlin \cite{Sarkar_2019}.
In contrast to these methods, our approach entirely removes the stochastic component, and proposes a spectral lines-based construction of the control input \cite{Boyd_1986, Boyd_1983}.
The advantage of choosing the spectral lines-based input over the Gaussian input lies in robustness, avoidance of large inputs even at low probabilities, and active reduction in the parameter estimation error.
The primary advantage of choosing the spectral line method of analysis over that suggested in Wagenmaker and Jamieson \cite{Wagenmaker2020} is its generalization to an arbitrary dynamic system, nonlinear, with unmodeled higher-order dynamics, as in \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, that has a property of preserving spectral lines at its output.
We leverage this property in providing estimation rates for this generalized class of dynamic systems.
Algorithm \ref{alg:example} summarizes our approach.

\begin{algorithm}[H]

        \caption{Example of LQR Control with Sub-Gaussian Spectral Lines}

        \label{alg:example}
        \begin{algorithmic}[1]

        \STATE{ {\bfseries Require:} Frequency Constraint Set $\mathcal{F}$, Stabilizing Controller $K^{(0)}$, failure probability $\delta \in (0, 1)$, Amplitude Constraint $M$, Cost Matrices $Q, R$} \\
        \FOR{$i=0,1,2,\ldots$}

        \STATE{\textbf{Set} Epoch Time $T_i = C(A_*, B_*, Q, R, \delta) \times 2^i$, where $C(A_*, B_*, Q, R, \delta)$ is a constant function of underlying system parameters, \\
        Amplitude Constraint $\bar{M}^{(i)} = M T_i^{1/4}$}
        \STATE {\textbf{Choose} Distinct $f^{(i)}_1, \dots, f^{(i)}_{\lceil d / 2 \rceil} \in \mathcal{F},$\\ \qquad \qquad $M^{(i)}_1, \dots, M^{(i)}_{\lceil d / 2 \rceil}$, \\
        \qquad \qquad such that $\frac{1}{2} \bar{M}^{(i)}\leq M^{(i)}_j \leq \bar{M}^{(i)}$.}
        \FOR{$k = \sum_{\ell=0}^{i-1} T_\ell + 1, \dots, \sum_{\ell=0}^{i-1} T_\ell + T_i$}

        \STATE {\textbf{Define} $u_{spec, k} = \sum_{j = 1}^{\lceil d / 2 \rceil} M^{(i)}_j \cos(2 \pi f^{(i)}_j k)$;}
        \STATE {\textbf{Assign} $u_{k} = K^{(i)} x_k + u_{spec, k}$.}
        \STATE{ \textbf{Receive} $x_{k + 1} = A_*x_{k} + B_*u_{k} + w_k + \eta_{k}$}
        \ENDFOR
        \STATE{ \textbf{Estimate} \[(\hat{A}, \hat{B}) = \argmin_{A \in \R^{n\times n}, B \in \R^{n \times m}} \sum_{k = \sum_{\ell = 0}^{i-1} T_i + 1}^{\sum_{\ell=0}^{i-1} T_\ell + T_i} \norm{x_{k+1} - Ax_k - Bu_k}_2^2 \] }
        \STATE{ \textbf{Set} \[K^{(i+1)} = -(R + \hat{B}^\top \hat{P} \hat{B})^{-1} \hat{B}^\top \hat{P} \hat{A} \] for $\hat{P}$ which satisfies
        \[ \hat{P} = \hat{A}^\top \hat{P} \hat{A} - \hat{A}^\top \hat{P} \hat{B}  (R + \hat{B}^\top \hat{P} \hat{B})^{-1} \hat{B}^\top \hat{P} \hat{A} + Q\]}
        \ENDFOR
        \STATE{(Optional) In Line 4, select $M^{(i)}_1, \dots, M^{(i)}_{\lceil d / 2 \rceil}$, $f^{(i)}_1, \dots, f^{(i)}_{\lceil d / 2 \rceil}$ to optimize $\norm{\bar{\Phi}^{-1}}^{-1}$ as to minimize the bound in Theorem \ref{unmodeled-estimation}.}
        \STATE{Note: In Lines 4-6, the specific form of $u_k$ can be altered as to include any signal which has sub-Gaussian spectral lines, such as pseudo-random binary sequences, as long as the amplitude of the signal is made to decay appropriately as in Line 3.}
        \end{algorithmic}
\end{algorithm}

It should be noted that the computational burden associated with the input selection is non-existent, and that the frequencies need not be constrained; the amplitude selection in Line 4 is to constrain the excitation of the unmodeled dynamics, and therefore a better control design, and is otherwise not required for successful parameter estimation in \eqref{lti-noisy-intro}.
This is in contrast to the active learning requirement imposed in \cite{Wagenmaker2020}.
Other problem specific requirements that stem from magnitude and rate constraints on the exogenous input can be easily integrated into the algorithm if needed \cite{Morelli_2005}.
It should also be noted that the proposed method has been analyzed at length in the system identification and adaptive control literature \cite{Goodwin_1984, Ljung_1987, Narendra2005} and has been highly successful in flight control applications \cite{Morelli_2005}.

\subsection{Summary of Results}
Our contributions in this work are as follows, where parentheses reference the specific section or result which details the contribution.

\begin{itemize}
\item We develop a new theory of spectral lines in a discrete-time and stochastic setting over a finite-time interval, bridging the gap between adaptive control and non-asymptotic estimation theory (Section \ref{s:spectral}).

\item We apply our results for the ideal system in \eqref{lti-noisy-intro}, and achieve competitive estimation rates with deterministic inputs as compared to the stochastic inputs in previous literature \cite{Abbasi2011, Sarkar_2019, Wagenmaker2020}.
In particular, for the system \eqref{lti-noisy-intro}, we show that the user of the system has the ability to tune the estimation rate by selecting the spectral lines of the deterministic control input appropriately.
Such flexibility is not provided in the previous literature that advocates the use of a stochastic input \cite{Abbasi2011, Dean_2018a, Dean_2018, Foster_2020, Matni2019, Sarkar_2019, Sarkar_2019a, Simchowitz_2019, Simchowitz_2018, Wagenmaker2020} (Section \ref{s:unmodeled}, Example \ref{ex:lti-estimation}).

\item In the case where $u_k$ is prescribed as a stochastic input for the system in \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, we provide a lower bound which quantifies the extent to which the stochastic input can excite unmodeled dynamics ,resulting in inconsistent estimation.
Although the system in \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w} is representative of true dynamics of physical systems, it has received little attention in recent literature.
This indicates that existing results which hold for the idealized model \eqref{lti-noisy-intro} have limitations in practice, when unmodeled dynamics which have a deterministic relationship with the input are introduced (Section \ref{s:lower-bound}, Theorem \ref{lower-bound}).

\item In contrast, the approach proposed in this paper where $u_k$ is chosen appropriately using deterministic spectral lines for the system \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, provides explicit estimation rates which depend on the frequency content $w_k$, and in practice can be minimized through proper choice of the spectrum of the exogenous signal.
As an illustrative example, we show that when $w_k$ is a high pass filter, parameter estimation error can be made arbitrarily small when the spectrum of $u_k$ is selected carefully, whereas the white noise input results in inconsistent estimation.
To our knowledge, we provide the first non-asymptotic estimation bound for a system of this form (Section \ref{s:unmodeled}, Theorem \ref{unmodeled-estimation}).

\item We show that, when the system dynamics are of the form \eqref{lti-noisy-intro} and the input $u_k$ is selected appropriately, in particular as in Algorithm \ref{alg:example}, the exploration results in $\tilde{O}(\sqrt{T})$ Regret with a Linear Quadratic Regulator based feedback controller, which is competitive in the literature (Section \ref{s:lqr-regret}, Theorem \ref{thm:regret}).

\item We provide experimental results which indicate the efficacy of using a spectral-lines based exogenous input compared to an input based on white noise, in terms of both parameter estimation error and closed-loop control design using the Linear Quadratic Regulator (Section \ref{s:experiments}).

\end{itemize}

Throughout this work, we will make the following assumption on the systems \eqref{lti-noisy-intro} and \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}.
\begin{assumption} \label{assumption-stability}
In \eqref{lti-noisy-intro} and \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, the matrix $A_*$ is assumed to be Schur-stable.
\end{assumption}
To ensure that the signals of interest are well behaved, we make this standard assumption, commonly satisfied by physical systems. As articulated in \cite{Ljung_1987}, closed-loop system identification based methods can be used to relax this requirement. It is also worth noting that the developments in \cite{Sarkar_2019} suggest that Assumption \ref{assumption-stability} is not required for the statistical analysis of parameters in the system \eqref{lti-noisy-intro}. As our goal is to focus on methods that are of interest in physical dynamic systems, we retain this assumption; relaxations of this assumption using methods in \cite{Ljung_1987, Sarkar_2019} are straight forward.

We begin with a discussion of preliminaries in Section \ref{s:Preliminaries} to introduce notions from adaptive control, including the theory of spectral lines and how they elicit excitation, as well as notions from non-asymptotic statistics, which have been used widely in recent literature \cite{Abbasi2011, Dean_2018, Sarkar_2019, Sarkar_2019a}.
In Section \ref{s:spectral}, we then provide our new definitions regarding spectral lines in discrete-time, stochastic settings.
Section \ref{s:unmodeled} the key estimation theorem leveraging the new notions of deterministic spectral lines for the system in \eqref{unmodeled-intro-x}-\eqref{unmodeled-intro-w}, and provide the corresponding lower bound for when the input is chosen according to white noise.
Section \ref{s:lqr-regret} then applies our results to the context of the Linear Quadratic Regulator, in which we show competitive regret bounds using the spectral-lines based approach.
Section \ref{s:experiments} concludes with simulated results indicating that selecting a control input based on spectral lines outperforms a white noise-based control input in the presence of unmodeled dynamics.

config: arxiv


text:
\begin{document}

\maketitle

\begin{abstract}
Recently, the author, together with L. Leu\c stean and A. Nicolae, introduced the notion of jointly firmly nonexpansive families of mappings in order to investigate in an abstract manner the convergence of proximal methods. Here, we further the study of this concept, by giving a characterization in terms of the classical resolvent identity, by improving on the rate of convergence previously obtained for the uniform case, and by giving a treatment of the asymptotic behaviour at infinity of such families.

\noindent {\em Mathematics Subject Classification 2010}: 90C25, 46N10, 47J25, 47H09, 03F10.

\noindent {\em Keywords:} Convergence of resolvents, proximal point algorithm, CAT(0) spaces, jointly firmly nonexpansive families, proof mining, rates of convergence.
\end{abstract}

\section{Introduction}

In the paper \cite{LeuNicSip18}, Leu\c stean, Nicolae and the author introduced a unifying framework for studying the proximal point algorithm, a fundamental tool of convex optimization going back to Martinet \cite{Mar70}, Rockafellar \cite{Roc76} and Br\'ezis and Lions \cite{BreLio78} (for a detailed history of the relevant proximal methods, see the introduction to \cite{LeuNicSip18}). Even though maximal monotone operators already provided such a unified view in the realm of Hilbert spaces, recent developments in optimization techniques in nonlinear generalizations thereof such as geodesic spaces of non-positive curvature \cite{Bac13,Bac14,BacRei14} demanded higher levels of abstraction. Specifically, what the aforementioned three authors did was (i) to introduce the notion of {\it jointly firmly nonexpansive families of mappings}; (ii) to show that all the possible variants of mappings (usually called ``resolvents'') that are involved in the construction of the corresponding proximal iterations fit the definition; and (iii) to prove that the weak convergence of the iteration can be derived just from this joint firm nonexpansiveness condition.

In addition, it is known that in the so-called uniform cases of the proximal point algorithm (uniformly monotone operators, uniformly convex functions) one has uniqueness and strong convergence to the optimizing point (zero and minimizer, respectively). This ties into the area of {\it proof mining}, an applied subfield of mathematical logic primarily developed in the last decades by Ulrich Kohlenbach and his collaborators (the standard introduction is \cite{Koh08}, while a recent survey is \cite{Koh19}) that aims to analyze proofs in mainstream mathematics using proof-theoretical tools. More precisely, results due to Kohlenbach \cite{Koh90} and Kohlenbach and Oliva \cite{KohOli03} show that usually such an uniqueness property may be made quantitative in such a way as to yield as a consequence a convergence rate for an asymptotically regular iteration. By appropriately tweaking the notion of asymptotic regularity, such a rate was extracted in \cite{LeuNicSip18} that was independent of the sequence of step-sizes used in the construction of the iterative sequence.

{\it In this paper, we continue this study of jointly firmly nonexpansive families of mappings by providing a conceptual characterization of them and by giving new applications.}

Specifically, after reviewing in Section~\ref{sec:prelim} the basic facts that we need about geodesic spaces and firm nonexpansiveness, we present in Section~\ref{sec:relid} a definition of joint firm nonexpansiveness that is, we hope, more flexible than the one in \cite{LeuNicSip18}, and its immediate consequences that we shall need. The main result of this section, Theorem~\ref{th-res-id}, shows that a family of mappings is jointly firmly nonexpansive if and only if it satisfies the resolvent identity and each member of it is nonexpansive. In Section~\ref{sec:uniform}, we show how a recent quantitative result due to Kohlenbach and Powell \cite{KohPowXX} may be used to improve the conditions under which a rate of convergence may be obtained in the uniform case of the proximal point algorithm. Finally, in Section~\ref{sec:as-beh} we show how with minimal boundedness assumptions one can show that for any point, the curve that is obtained by applying to it all mappings in a jointly firmly nonexpansive family strongly converges to the projection of that point onto the common fixed point set of the family. This latter result, Theorem~\ref{t2}, unifies a number of results pertaining to the convergence of approximating curves going back to the 1960s.

\section{Preliminaries}\label{sec:prelim}

We say that a metric space $(X,d)$ is {\it geodesic} if for any two points $x$, $y \in X$ there is a geodesic that joins them, i.e. a mapping $\gamma : [0,1] \to X$ such that $\gamma(0)=x$, $\gamma(1)=y$ and for any $t$, $t' \in [0,1]$ we have that
$$d(\gamma(t),\gamma(t')) = |t-t'| d(x,y).$$
Among geodesic spaces, a subclass that is usually considered (e.g. in convex optimization) to be the proper nonlinear analogue of Hilbert spaces is the class of CAT(0) spaces, introduced by A. Aleksandrov \cite{Ale51} and named as such by M. Gromov \cite{Gro87}, defined as those geodesic spaces $(X,d)$ such that for any geodesic $\gamma : [0,1] \to X$ and for any $z \in X$ and $t \in [0,1]$ we have that
$$d^2(z,\gamma(t)) \leq (1-t)d^2(z,\gamma(0)) + td^2(z,\gamma(1)) - t(1-t)d^2(\gamma(0),\gamma(1)).$$
Another well-known fact about CAT(0) spaces is that each such space $(X,d)$ is {\it uniquely geodesic} -- that is, for any $x$, $y \in X$ there is a unique such geodesic $\gamma : [0,1] \to X$ that joins them -- and in this context we shall denote, for any $t \in [0,1]$, the point $\gamma(t)$ by $(1-t)x + ty$.

In 2008, Berg and Nikolaev proved (see \cite[Proposition 14]{BerNik08}) that in any metric space $(X,d)$, the function $\langle\cdot,\cdot\rangle : X^2 \times X^2 \to \mathbb{R}$, defined, for any $x$, $y$, $u$, $v \in X$, by
$$\langle \vv{xy}, \vv{uv} \rangle := \frac12(d^2(x,v) + d^2(y,u) - d^2(x,u) -d^2(y,v))$$
(where an ordered pair of points $(p,z) \in X^2$ is denoted by $\vv{pz}$), called the {\it quasi-linearization function}, is the unique one such that, for any $x$, $y$, $u$, $v$, $w \in X$, we have that:
\begin{enumerate}[(i)]
\item $\langle\vv{xy},\vv{xy}\rangle = d^2(x,y)$;
\item $\langle\vv{xy},\vv{uv}\rangle = \langle\vv{uv},\vv{xy}\rangle$;
\item $\langle\vv{yx},\vv{uv}\rangle = -\langle\vv{xy},\vv{uv}\rangle$;
\item $\langle\vv{xy},\vv{uv}\rangle + \langle\vv{xy},\vv{vw}\rangle = \langle\vv{xy},\vv{uw}\rangle$.
\end{enumerate}
The inner product notation is justified by the fact that if $X$ is a (real) Hilbert space, for any $x$, $y$, $u$, $v \in X$,
\begin{equation}\label{eq-quasi-inner}
\langle\vv{xy},\vv{uv}\rangle = \langle x-y,u-v \rangle = \langle y-x,v-u \rangle.
\end{equation}
The main result of \cite{BerNik08}, Theorem 1, characterized CAT(0) spaces as being exactly those geodesic spaces $(X,d)$ such that the corresponding Cauchy-Schwarz inequality is satisfied, i.e. for any $x$, $y$, $u$, $v \in X$,
\begin{equation}\label{CauchySchwartz}
\langle\vv{xy},\vv{uv}\rangle \leq d(x,y)d(u,v).
\end{equation}

Firmly nonexpansive mappings were first introduced by Browder \cite{Bro67} in the context of Hilbert spaces and then by Bruck \cite{Bru73} in the context of Banach spaces (this later definition was also studied, e.g., in \cite{Rei77}). The following generalization to geodesic spaces, inspired by the study of firmly nonexpansive mappings in the Hilbert ball \cite{GoeRei82, GoeRei84, ReiSha87, ReiSha90} was introduced in \cite{AriLeuLop14}.

\begin{definition}
Let $X$ be a CAT(0) space. A mapping $T : X \to X$ is called {\em firmly nonexpansive} if for any $x,y \in X$ and any $t \in [0,1]$ we have that
$$d(Tx,Ty) \leq d((1-t)x + tTx,(1-t)y+tTy).$$
\end{definition}

As mentioned in \cite{AriLopNic15} (see also \cite{KohLopNic17}), if $X$ is a CAT(0) space, every firmly nonexpansive mapping $T:X \to X$ satisfies the so-called {\em property $(P_2)$}, i.e. that for all $x,y \in X$,
$$2d^2(Tx,Ty) \leq d^2(x,Ty) + d^2(y,Tx) - d^2(x,Tx) - d^2(y,Ty),$$
or, using the quasi-linearization function,
\begin{equation}\label{eq-quasi-P2}
d^2(Tx,Ty) \leq \langle\vv{TxTy},\vv{xy}\rangle.
\end{equation}
If $X$ is a Hilbert space, property $(P_2)$ coincides with firm nonexpansiveness as \eqref{eq-quasi-P2} and \eqref{eq-quasi-inner} yield $\|Tx - Ty\|^2 \leq \langle Tx-Ty,x-y \rangle$, which is equivalent to it e.g. by \cite[Proposition 4.2]{BauCom17}. Moreover, from this formulation given by \eqref{eq-quasi-P2} one immediately obtains, using \eqref{CauchySchwartz}, that a self-mapping of a CAT(0) space satisfying property $(P_2)$ is nonexpansive.

Throughout the paper, for any self-mapping $T$ (of an arbitrary set), we denote the set of its fixed points by $\Fix(T)$.

In the remainder of this section, we shall introduce some notions that are needed in Section~\ref{sec:as-beh}. If $(X,d)$ is a metric space and $(x_n)_{n \in \N}$ is a sequence in $X$, then $(x_n)$ is called {\it metastable} if for any $\eps>0$ and $g:\N\to\N$ there is an $N$ such that for all $i$, $j \in [N,N+g(N)]$, $d(x_i,x_j)\leq\eps$, and that a {\it rate of metastability} for $(x_n)$ is a function $\Psi: (0,\infty) \times \N^\N \to \N$ such that for any $\eps$ and $g$, $\Psi(\eps,g)$ gives an upper bound on the (smallest) corresponding $N$. It is immediate that this is just a reformulation -- actually identifiable in mathematical logic as the Herbrand normal form -- of the Cauchy property; the concept was independently rediscovered by Tao \cite{Tao08} (it was named as such under a suggestion of Jennifer Chayes) and used successfully by him in proving a convergence result for multiple ergodic averages \cite{Tao08A}. The significance of this concept resides in the fact that rates of convergence for iterative sequences which are commonly employed in nonlinear analysis and convex optimization may not be uniform or computable (see \cite{Neu15}) -- in this case, a rate of metastability as introduced above is the next best thing that can be obtained; and the research program of proof mining mentioned in the introduction has achieved non-trivial extraction of such rates from celebrated strong convergence proofs, see, e.g., \cite{Koh11, KohKou15, KohSipXX}.

For all $g: \N \to \N$, we define $\wt{g} : \N \to \N$, for all $n$, by $\wt{g}(n):=n+g(n)$. Also, for all $f:\N \to \N$ and all $n \in \N$, we denote by $f^{(n)}$ the $n$-fold composition of $f$ with itself. Note that for all $g$ and $n$, $\wt{g}^{(n)}(0)\leq\wt{g}^{(n+1)}(0)$.

The following proposition gives a uniform and computable rate of metastability for nondecreasing sequences of nonnegative reals bounded above by a fixed constant.

\begin{proposition}[Quantitative Monotone Convergence Principle, cf. {\cite{Tao08}}]\label{qmcp}
Let $b>0$ and $(a_n)$ be a nondecreasing sequence in $[0,b]$. Then for all $\eps>0$ and $g:\N\to\N$ there is an $N \leq \wt{g}^{\left(\left\lceil\frac b\eps\right\rceil \right)}(0)$ such that for all $i$, $j \in [N,N+g(N)]$, $|a_i-a_j|\leq\eps$.
\end{proposition}

\begin{proof}
Let $\eps>0$ and $g:\N \to \N$. Assume that the conclusion is false, hence in particular for all $i \leq \left\lceil\frac b\eps\right\rceil$, $a_{\wt{g}^{(i+1)}(0)} - a_{\wt{g}^{(i)}(0)} > \eps$. Then
$$b \geq a_{\wt{g}^{\left(\left\lceil\frac b\eps\right\rceil + 1\right)}(0)} \geq a_{\wt{g}^{\left(\left\lceil\frac b\eps\right\rceil + 1\right)}(0)} - a_0 = \sum_{i=0}^{\left\lceil\frac b\eps\right\rceil} a_{\wt{g}^{(i+1)}(0)} - a_{\wt{g}^{(i)}(0)} > \left\lceil\frac b\eps\right\rceil\cdot\eps \geq b,$$
a contradiction.
\end{proof}

\section{The relationship with the resolvent identity}\label{sec:relid}

Fix a CAT(0) space $X$ for the remainder of this paper. If $T$ and $U$ are self-mappings of $X$ and $\lambda$, $\mu>0$, we say that $T$ and $U$ are {\it $(\lambda,\mu)$-mutually firmly nonexpansive} if for all $x$, $y\in X$ and all $\alpha$, $\beta \in [0,1]$ such that
$(1-\alpha)\lambda=(1-\beta)\mu$, one has that
$$ d(Tx,Uy) \leq d((1-\alpha)x+\alpha Tx,(1-\beta)y+\beta Uy).$$
If $(T_n)_{n \in \N}$ is a family of self-mappings of $X$ and $(\gamma_n)_{n\in\N} \subseteq (0,\infty)$, we say that $(T_n)$ is {\it jointly firmly nonexpansive} with respect to $(\gamma_n)$ if for all $n$, $m\in\N$, $T_n$ and $T_m$ are $(\gamma_n,\gamma_m)$-mutually firmly nonexpansive. In addition, if $(T_\gamma)_{\gamma>0}$ is a family of self-mappings of $X$, we say that it is plainly {\it jointly firmly nonexpansive} if for all $\lambda$, $\mu > 0$, $T_\lambda$ and $T_\mu$ are $(\lambda,\mu)$-mutually firmly nonexpansive. It is clear that a family $(T_\gamma)$ is jointly firmly nonexpansive if and only if for every $(\gamma_n)_{n\in\N} \subseteq (0,\infty)$, $(T_{\gamma_n})_{n \in \N}$ is jointly firmly nonexpansive with respect to $(\gamma_n)$. In \cite{LeuNicSip18} it was shown that examples of jointly firmly nonexpansive families of mappings are furnished by resolvent-type mappings used in convex optimization -- specifically, by:
\begin{itemize}
\item the family $(J_{\gamma f})_{\gamma>0}$, where $f$ is a proper convex lower semicontinous function on $X$ and one denotes for any such function $g$ its proximal mapping by $J_g$;
\item the family $(R_{T, \gamma})_{\gamma>0}$, where $T$ is a nonexpansive self-mapping of $X$ and one denotes, for any $\gamma > 0$, its resolvent of order $\gamma$ by $R_{T, \gamma}$;
\item (if $X$ is a Hilbert space) the family $(J_{\gamma A})_{\gamma>0}$, where $A$ is a maximally monotone operator on $X$ and one denotes for any such operator $B$ its resolvent by $J_B$.
\end{itemize}

Again, if $T$ and $U$ are self-mappings of $X$ and $\lambda$, $\mu>0$, one says that $T$ and $U$ are {\it $(\lambda,\mu)$-mutually $(P_2)$} if for all $x$, $y\in X$,
$$\frac1{\mu}(d^2(Tx,Uy) + d^2(y,Uy) - d^2(y,Tx)) \leq \frac1{\lambda}(d^2(x,Uy) - d^2(x,Tx) - d^2(Tx,Uy)),$$
or, using the quasi-linearization function,
$$\frac1{\mu}\langle\vv{TxUy},\vv{yUy}\rangle\leq \frac1{\lambda}\langle\vv{TxUy},\vv{xTx}\rangle.$$

\begin{proposition}[{\cite[Corollary 3.11]{LeuNicSip18}}]\label{same-fixed}
Any two mutually $(P_2)$ self-mappings of $X$ have the same fixed points.
\end{proposition}

\begin{proposition}\label{t-eq-u}
Let $T$ and $U$ be self-mappings of $X$ and $\lambda>0$ such that $T$ and $U$ are $(\lambda,\lambda)$-mutually $(P_2)$. Then $T=U$.
\end{proposition}

\begin{proof}
Let $x \in X$. Then
$$\langle\vv{TxUx},\vv{xUx}\rangle\leq \langle\vv{TxUx},\vv{xTx}\rangle,$$
so
$$d^2(Tx,Ux) = \langle\vv{TxUx},\vv{TxUx}\rangle\leq 0,$$
i.e. $Tx=Ux$.
\end{proof}

One may then similarly state the corresponding definitions for jointly $(P_2)$ families of mappings. As shown in \cite{LeuNicSip18}, all those $(P_2)$ notions generalize their firmly nonexpansive counterparts and coincide with them in the case where $X$ is a Hilbert space. The main result of that paper showed that this condition suffices for the working of the proximal point algorithm, namely that if $X$ is complete, $(T_n)_{n \in \N}$ is a family of self-mappings of $X$ with a common fixed point and $(\gamma_n)_{n\in\N} \subseteq (0,\infty)$ with $\sum_{n=0}^\infty \gamma_n^2 = \infty$, then, assuming that $(T_n)$ is jointly $(P_2)$ with respect to $(\gamma_n)$, any sequence $(x_n) \subseteq X$ such that for all $n$, $x_{n+1}=T_nx_n$, is $\Delta$-convergent (a generalization of weak convergence to arbitrary metric spaces, due to Lim \cite{Lim76}) to a common fixed point of the family.

The following result attempts to elucidate the efficacy of the joint firm nonexpansiveness condition by tying it to the well-known resolvent identity.

\begin{theorem}\label{th-res-id}
Let $(T_\gamma)_{\gamma>0}$ be a family of self-mappings of $X$. Then the following are equivalent:
\begin{enumerate}[(a)]
\item
\begin{enumerate}[(i)]
\item For all $\gamma > 0$, $T_\gamma$ is nonexpansive.
\item For all $\gamma > 0$, $t \in [0,1]$ and $x \in X$,
$$T_{(1-t)\gamma}((1-t)x+tT_\gamma x) = T_\gamma x.$$
\end{enumerate}
\item $(T_\gamma)_{\gamma>0}$ is jointly firmly nonexpansive.
\end{enumerate}
\end{theorem}

\begin{proof}

``$(a)\Rightarrow(b)$'' (This is essentially expressed by \cite[Proposition 3.17]{LeuNicSip18}.) Let $\lambda$, $\mu > 0$, $x$, $y\in X$ and $\alpha$, $\beta \in [0,1]$ be such that
$(1-\alpha)\lambda = (1-\beta)\mu =:\delta.$
We get that
\begin{align*}
d(T_{\lambda}x, T_{\mu} y) &= d(T_{(1-\alpha)\lambda}((1-\alpha)x+\alpha T_{\lambda } x), T_{(1-\beta)\mu}((1-\beta)y+\beta T_{\mu} y)) \\
&= d(T_{\delta}((1-\alpha)x+\alpha T_{\lambda} x), T_{\delta}((1-\beta)y+\beta T_{\mu} y)) \\
&\leq d((1-\alpha)x+\alpha T_{\lambda} x,(1-\beta)y+\beta T_{\mu} y).
\end{align*}

``$(b)\Rightarrow(a)$''
Let $\gamma > 0$. Take $x$, $y \in X$. To show that $d(T_\gamma x, T_\gamma y) \leq d(x,y)$, simply set in the joint firm nonexpansiveness condition $\lambda:=\gamma$, $\mu:=\gamma$, $\alpha:=0$ and $\beta:=0$.

To show that the resolvent identity holds, take $t \in [0,1]$ and $x \in X$. Set $y:=(1-t)x+ t T_\gamma x$, so one has to prove that $T_{(1-t)\gamma} y = T_\gamma x$. Then, if one sets $\lambda:=\gamma$, $\mu:=(1-t)\gamma$, $\alpha:=t$ and $\beta:=0$, since then $(1-\alpha)\lambda=(1-\beta)\mu$, one gets that
$$d(T_\gamma x, T_{(1-t)\gamma} y) \leq d((1-t)x+ t T_\gamma x, y) =0,$$
so $T_{(1-t)\gamma} y = T_\gamma x$.
\end{proof}

\section{An improvement on the uniform case}\label{sec:uniform}

If $T$ is a self-mapping of $X$ and $C$ is a nonempty subset of $X$ such that $T(C) \subseteq C$, we say that $T$ is {\it uniformly firmly nonexpansive} on $C$ with modulus $\vp : (0,\infty) \to (0,\infty)$ if for all $\eps> 0$ and $x$, $y \in C$ with $d(Tx,Ty) \geq \eps$ and all $t \in [0,1]$,
$$d^2(Tx,Ty) \leq d^2((1-t)x+tTx,(1-t)y+tTy) - 2(1-t)\vp(\eps).$$
One says that $T$ is {\it uniformly $(P_2)$} on $C$ with modulus $\vp$ if for all $\eps> 0$ and $x$, $y \in C$ with $d(Tx,Ty) \geq \eps$,
$$2d^2(Tx,Ty) \leq d^2(x,Ty) + d^2(y,Tx) - d^2(x,Tx) - d^2(y,Ty) - 2\vp(\eps),$$
or, equivalently, using the quasi-linearization function,
$$\langle \vv{TxTy},\vv{yTy}\rangle \leq \langle \vv{TxTy} ,\vv{xTx}\rangle - \vp(\eps).$$
(As before, the latter notion is more general than the first, though identical in Hilbert spaces.)

The second main result of the paper \cite{LeuNicSip18} had been the extraction of a rate of convergence for the proximal point algorithm in connection with this uniformity. There, a more restrictive notion of uniform firm nonexpansiveness had been considered  (first used in \cite[Section 3.4]{BarBauMofWan16}), where the modulus $\vp$ is nondecreasing and applied directly to the quantity $d(Tx,Ty)$, as that is the kind of modulus that is commonly used in defining the corresponding uniform notions of monotone operators and convex functions. It is easy, though, to redefine those notions in terms of this more general kind of modulus and to show that their resolvents fit into the definition above. One could also adapt \cite[Lemma 4.4]{LeuNicSip18} and \cite[Theorem 5.1]{LeuNicSip18} to this setting, but we shall not attempt that, as those results will be shortly superseded by the results of this section.

Specifically, the following generalizes \cite[Lemma 4.4]{LeuNicSip18}. (The estimate obtained below had been implicit in the original proof, but its importance had not been apparent at the time.)

\begin{lemma}\label{uniq}
Let $T$ be a self-mapping of $X$ and $C$ be a nonempty subset of $X$ such that $T(C) \subseteq C$. Assume that $T$ is uniformly $(P_2)$ on $C$ with modulus $\vp$. Then for all $x \in C$ and $z \in C \cap \Fix(T)$ with $d(Tx,z) \geq \eps$,
$$ \vp(\eps) \leq \langle \vv{Txz} ,\vv{xTx}\rangle.$$
\end{lemma}

\begin{proof}
Since $T$ is uniformly $(P_2)$ on $C$ with modulus $\vp$,
$$\langle \vv{Txz},\vv{zz}\rangle \leq \langle \vv{Txz} ,\vv{xTx}\rangle - \vp(\eps).$$
so $ \vp(\eps) \leq \langle  \vv{Txz} ,\vv{xTx} \rangle$.
\end{proof}

The following is a particular case of a recent result of Kohlenbach and Powell \cite[Lemma 3.4]{KohPowXX}, which is a quantitative version of an argument going back to e.g. \cite[Lemma 2.2]{AlbReiSho02}. We give its proof for completeness.

\begin{lemma}\label{kp}
Let $(\gamma_n)_{n \in \N}$ and $(w_n)_{n \in \N}$ be sequences of non-negative reals and $b>0$, $\theta:(0, \infty) \to \N$ and $\vp: (0, \infty) \to (0,\infty)$ be such that:
\begin{itemize}
\item for all $n \in \N$, $w_n \leq b$;
\item for all $x>0$, $\sum_{n=0}^{\theta(x)} \gamma_n \geq x$;
\item for all $\eps > 0$ and all $n \in \N$ with $\eps < w_{n+1}$, $w_{n+1} \leq w_n - \gamma_n \vp(\eps)$.
\end{itemize}
Then for all $\eps > 0$ and all $n \geq \theta\left(\frac{b+1}{\vp(\eps)}\right)+1$, $w_n \leq \eps$.
\end{lemma}

\begin{proof}
Let $\eps> 0$. Assume first that for all $n \leq \theta\left(\frac{b+1}{\vp(\eps)}\right)$, $w_{n+1} > \eps$, so for all $n \leq \theta\left(\frac{b+1}{\vp(\eps)}\right)$, $\gamma_n \vp(\eps) \leq w_n - w_{n+1}$. We get that
$$b \geq w_0 \geq w_0 - w_{\theta\left(\frac{b+1}{\vp(\eps)}\right)+1} = \sum_{n=0}^{\theta\left(\frac{b+1}{\vp(\eps)}\right)} (w_n -w_{n+1}) \geq \vp(\eps) \sum_{n=0}^{\theta\left(\frac{b+1}{\vp(\eps)}\right)} \gamma _n \geq \vp(\eps) \cdot \frac{b+1}{\vp(\eps)} = b+1,$$
a contradiction. Thus, there is an $N \leq \theta\left(\frac{b+1}{\vp(\eps)}\right)+1$ such that $w_N \leq \eps$.

We now prove by induction that for all $n \geq N$, $w_n \leq \eps$, from which it will follow that this holds for all $n \geq \theta\left(\frac{b+1}{\vp(\eps)}\right)+1$. Assume that for such an $n$, $w_n \leq \eps$ and $w_{n+1} > \eps$. But then
$$\eps < w_{n+1} \leq w_n - \gamma_n \vp(\eps) \leq w_n \leq \eps,$$
a contradiction.
\end{proof}

The general version of the above lemma has been used in \cite{KohPowXX} to give rates of convergence for iterations associated to uniformly accretive operators in uniformly convex Banach spaces (see the end of this section), following earlier work that yielded rates of convergence for the gradient flow associated to such operators in \cite{KohKou15}, and for the asymptotic behaviour towards infinity of their resolvents and the fixed-step-size proximal point algorithm in \cite{Kou17}. The general notion underlying the strategy is that of a {\it modulus of uniqueness}, which was first introduced by Kohlenbach in the early 1990s \cite{Koh90,Koh93a,Koh93b} in the context of best approximation theory, while its significance in deriving rates of convergence for asymptotically regular iterative sequences was identified later in \cite[Section 4.1]{KohOli03}.

These ideas have indeed been previously applied to our abstract proximal point algorithm in the form of \cite[Theorem 5.1]{LeuNicSip18}, but we will now show how the use of the above lemma allows us to derive the following more powerful version, where we no longer need to assume that the sequence $(d(x_n,x_{n+1})/\gamma_n)$ is nonincreasing, and we may replace the divergence of $\sum_{n=0}^{\infty} \gamma_n^2$ with that of $\sum_{n=0}^{\infty} \gamma_n$.

\begin{theorem}
Let $(T_n)_{n \in \N}$ be a family of self-mappings of $X$ and $p \in \bigcap_{n \in \N} \Fix(T_n)$. Let $(\gamma_n)_{n \in \N} \subseteq (0,\infty)$ and $\theta :(0,\infty) \to \N$ and assume that for all $x>0$,
$$\sum_{n=0}^{\theta(x)} \gamma_n \geq x.$$
Let $b > 0$ and denote by $C$ the closed ball of center $p$ and radius $b$. Let $\vp : (0, \infty) \to (0,\infty)$ and assume that for all $n$, $T_n(C) \subseteq C$ and $T_n$ is uniformly $(P_2)$ on $C$ with modulus $\gamma_n\vp$. Let $(x_n) \subseteq C$ be such that for all $n$, $x_{n+1}=T_nx_n$.

Then for all $\eps > 0$ and all $n \geq \theta\left(\frac{(b+1)^2}{\vp(\eps)}\right)+1$, $d(x_n,p) \leq \eps$.
\end{theorem}

\begin{proof}
We seek to apply Lemma~\ref{kp} with the sequence $(d(x_n,p))$ playing the role of $(w_n)$ and with $\vp/(b+1)$ playing the role of $\vp$. We only need to show that for all $\eps>0$ and $n \in \N$ with $d(x_{n+1},p) > \eps$, we have that
$$d(x_{n+1},p) \leq d(x_n,p) - \frac{\gamma_n \vp(\eps)}{b+1}.$$
Let, then, $\eps>0$ and $n \in \N$ be such that $d(x_{n+1},p) > \eps$. Since $T_n$ is uniformly $(P_2)$ on $C$ with modulus $\gamma_n\vp$ and $x_{n+1}=T_nx_n$, we get by Lemma~\ref{uniq} that
$$\gamma_n\vp(\eps) \leq \langle \vv{x_{n+1}p},\vv{x_nx_{n+1}}  \rangle,$$
and thus we have that
$$d^2(x_{n+1},p) = \langle \vv{x_{n+1}p},\vv{x_{n+1}p} \rangle = \langle \vv{x_{n+1}p},\vv{x_np} \rangle - \langle \vv{x_{n+1}p},\vv{x_nx_{n+1}}\rangle \leq d(x_{n+1},p)d(x_n,p) - \gamma_n\vp(\eps).$$
Since $d(x_{n+1},p) > \eps > 0$, we can divide by it, so
$$d(x_{n+1},p) \leq d(x_n,p) - \frac{\gamma_n\vp(\eps)}{d(x_{n+1},p)} \leq d(x_n,p) - \frac{\gamma_n\vp(\eps)}{b+1},$$
which was what we needed to show.
\end{proof}

We see that the same phenomenon that occurred in \cite[Theorem 5.1]{LeuNicSip18} also occurs here (and already did in \cite[Lemma 3.4]{KohPowXX}) -- namely, the resulting rate of convergence does not depend in any way on the sequence of step-sizes $(\gamma_n)$, even though they are not said to belong to a compact interval in which case the fact would be explainable by general logical metatheorems.

Let us briefly remark a bit about the context in which the quantitative lemma was first introduced. One of its applications, \cite[Theorem 4.2]{KohPowXX}, deals with sequences $(x_n)$ inside a Banach space $X$ that are associated to a uniformly accretive operator $A$ and to a divergent sequence $(\alpha_n)$ of nonnegative reals in the sense that for each $n$ there is an $u \in Ax_{n+1}$ such that
$$x_{n+1}=x_n-\alpha_nu.$$
In the case where all resolvents of the operator exist (e.g. when $X$ is uniformly convex), it is immediate that the above relation simply means that for each $n$, $x_{n+1}=J_{\alpha_nA}x_n$, i.e. $(x_n)$ is a sequence generated by the proximal point algorithm with inputs $A$ and $(\alpha_n)$.

\section{The asymptotic behaviour at infinity}\label{sec:as-beh}

We now deal with what is classically denoted by {\it resolvent convergence}, i.e. the behaviour of resolvent mappings as their order tends to infinity. In the case of Hilbert spaces \cite[Lemma 1]{Bru74}, the essential idea of the proof goes back to Minty \cite{Min63} and was later popularized by Halpern \cite{Hal67}. A logical analysis of the latter result yielding a rate of metastability was first undertaken by Kohlenbach \cite[Section 4]{Koh11}. (For the extension due to Reich \cite{Rei80} to more general Banach spaces such as $L^p$ spaces, where the proof and its corresponding analysis require vastly different techniques, a rate of metastability was recently obtained by Kohlenbach and the author in \cite{KohSipXX}.)

\begin{lemma}\label{halp}
Let $T$ and $U$ be self-mappings of $X$ and $\lambda$, $\mu>0$ with $\lambda \leq \mu$. Assume that $T$ and $U$ are $(\lambda,\mu)$-mutually $(P_2)$. Let $x \in X$. Then
$$d^2(x,Ux) \geq d^2(x,Tx) + d^2(Tx,Ux).$$
In particular, $d(x,Ux) \geq d(x,Tx)$.
\end{lemma}

\begin{proof}
If $\lambda=\mu$, then, by Proposition~\ref{t-eq-u}, $Tx=Ux$ and the conclusion immediately follows. Assume, then, that $\lambda < \mu$. Since $T$ and $U$ are $(\lambda,\mu)$-mutually $(P_2)$, we have that
$$\frac1{\mu}\langle\vv{TxUx},\vv{xUx}\rangle\leq \frac1{\lambda}\langle\vv{TxUx},\vv{xTx}\rangle,$$
so
$$\frac1{\mu}\langle\vv{TxUx},\vv{xTx}\rangle + \frac1{\mu}\langle\vv{TxUx},\vv{TxUx}\rangle\leq \frac1{\lambda}\langle\vv{TxUx},\vv{xTx}\rangle,$$
from which we get that
$$0 \leq \frac1{\mu} d^2(Tx,Ux) \leq \left( \frac1\lambda - \frac1\mu \right) \langle\vv{TxUx},\vv{xTx}\rangle.$$
Since $\lambda < \mu$, $\frac1\lambda - \frac1\mu >0$, so $\langle\vv{xTx},\vv{TxUx}\rangle \geq 0$.
Thus,
$$d^2(x,Ux) = \langle\vv{xUx},\vv{xUx}\rangle = d^2(x,Tx) + d^2(Tx,Ux) + 2\langle\vv{xTx},\vv{TxUx}\rangle \geq d^2(x,Tx) + d^2(Tx,Ux),$$
and we are done.
\end{proof}

\begin{theorem}\label{t1}
Let $(T_n)_{n \in \N}$ be a family of self-mappings of $X$ and $(\gamma_n)_{n\in\N} \subseteq (0,\infty)$ a nondecreasing sequence and assume that $(T_n)$ is jointly $(P_2)$ with respect to $(\gamma_n)$. Put $F:=\bigcap_{n \in \N} \Fix(T_n)$. Let $x\in X$ and $b>0$ and assume that for all $n$, $d(x,T_nx) \leq b$. Then:
\begin{enumerate}[(a)]
\item for all $\eps > 0$ and all $g: \N \to \N$ there is an $N \leq \wt{g}^{\left(\left\lceil\frac {b^2}{\eps^2}\right\rceil \right)}(0)$ such that for all $i$, $j \in [N,N+g(N)]$, $d(T_ix,T_jx)\leq\eps$;
\item if in addition $X$ is complete and $\lim_{n \to \infty} \gamma_n = \infty$, then $F \neq \emptyset$ and $(T_nx)$ converges to the unique point in $F$ which is closest to $x$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{enumerate}[(a)]
\item Let $\eps>0$ and $g:\N \to \N$. For all $n$, $p \in \N$ with $n \leq p$, $\gamma_n \leq \gamma_p$, and so, by Lemma~\ref{halp}, $d(x,T_px) \geq d(x,T_nx)$. Thus, $(d^2(x,T_nx))$ is a nondecreasing sequence in $[0,b^2]$ and by Proposition~\ref{qmcp}, there is an $N \leq \wt{g}^{\left(\left\lceil\frac {b^2}{\eps^2}\right\rceil \right)}(0)$ such that for all $i$, $j \in [N,N+g(N)]$, $|d^2(x,T_ix) - d^2(x,T_jx)|\leq\eps^2$.

Let $i$, $j \in [N,N+g(N)]$. Again, by Lemma~\ref{halp},
$$d^2(T_ix,T_jx) \leq |d^2(x,T_ix) - d^2(x,T_jx)|\leq\eps^2,$$
so $d(T_ix,T_jx)\leq\eps$.
\item We have that $(T_nx)$ is metastable, hence Cauchy. Since $X$ is complete, $(T_nx)$ is convergent. Denote its limit by $p$. We have that for all $m$, $n \in \N$,
$$\frac1{\gamma_m}\langle\vv{T_nxT_mT_nx},\vv{T_nxT_mT_nx}\rangle\leq \frac1{\gamma_n}\langle\vv{T_nxT_mT_nx},\vv{xT_nx}\rangle,$$
so for all $m$, $n \in \N$,
$$\frac1{\gamma_m} d^2(T_nx,T_mT_nx) \leq \frac1{\gamma_n} d(T_nx,T_mT_nx)d(x,T_nx).$$
For all $m$, $n \in \N$, either $d(T_nx,T_mT_nx) \neq 0$, so we can divide the above by it and get that
$$ d(T_nx,T_mT_nx) \leq \frac{\gamma_m}{\gamma_n}d(x,T_nx) \leq \frac{b\gamma_m}{\gamma_n},$$
or $d(T_nx,T_mT_nx)= 0$, so clearly then $d(T_nx,T_mT_nx)\leq \frac{b\gamma_m}{\gamma_n}$. Thus, for all $m \in \N$,
$$d(p,T_mp) = \lim_{n \to \infty} d(T_nx,T_mT_nx) \leq \lim_{n \to \infty} \frac{b\gamma_m}{\gamma_n} = 0,$$
so for all $m \in \N$, $p \in \Fix(T_m)$, i.e. $p \in F$ (so $F \neq \emptyset$).

Now let $q \in F$ with $q \neq p$. Then, for all $n \in \N$, since $T_n$ is $(P_2)$ and $q \in \Fix(T_n)$,
$$2d^2(T_nx,q) \leq d^2(x,q) + d^2(T_nx,q) - d^2(x,T_nx),$$
i.e.
$$d^2(x,q) -d^2(T_nx,q) - d^2(x,T_nx) \geq 0.$$
By passing to the limit, we get that
$$d^2(x,q) - d^2(p,q) - d^2(x,p) \geq 0,$$
i.e.
$$d^2(x,q) \geq d^2(x,p) + d^2(p,q) > d^2(x,p),$$
so $p$ is the unique point in $F$ which is closest to $x$.
\end{enumerate}
\end{proof}

\begin{theorem}\label{t2}
Assume that $X$ is complete. Let $(T_\gamma)_{\gamma>0}$ be a jointly $(P_2)$ family of self-mappings of $X$. Put $F:=\bigcap_{\gamma > 0} \Fix(T_\gamma)$. Let $x\in X$, $b>0$, and $(\lambda_n)_{n \in \N} \subseteq (0, \infty)$ with $\lim_{n \to \infty} \lambda_n = \infty$ and assume that for all $n$, $d(x,T_{\lambda_n}x) \leq b$. Then $F \neq \emptyset$ and the curve $(T_\gamma x)_{\gamma>0}$ is continuous and converges to the unique point in $F$ which is closest to $x$.
\end{theorem}

\begin{proof}
For all $\gamma > 0$ there is an $n$ such that $\lambda_n \geq \gamma$, and so, by Lemma~\ref{halp}, $d(x,T_\gamma x) \leq d(x,T_{\lambda_n}x) \leq b$. In addition, by Proposition~\ref{same-fixed}, for all $(\gamma_n)_{n \in \N} \subseteq (0, \infty)$, $F=\bigcap_{n \in \N} \Fix(T_{\gamma_n})$.

To show continuity, we shall show that for any $\Gamma > 0$, the curve $(T_\gamma x)_{\gamma\geq \Gamma}$ is uniformly continuous. Let $\Gamma > 0$ and $\lambda$, $\mu \geq \Gamma$ with $\lambda \leq \mu$. Then
$$\frac1{\mu}\langle\vv{T_\lambda xT_\mu x},\vv{xT_\mu x}\rangle\leq \frac1{\lambda}\langle\vv{T_\lambda xT_\mu x},\vv{xT_\lambda x}\rangle,$$
so
$$\frac1\mu d^2(T_\lambda x,T_\mu x) \leq \frac{\mu-\lambda}{\lambda\mu} \langle\vv{T_\lambda xT_\mu x},\vv{xT_\lambda x}\rangle \leq \frac{\mu-\lambda}{\lambda\mu} \cdot d(T_\lambda x,T_\mu x)d(x,T_\lambda x) \leq \frac{\mu-\lambda}{\lambda\mu} \cdot 2b^2,$$
from which we get
$$d(T_\lambda x, T_\mu x) \leq \sqrt{\frac{\mu -\lambda}\lambda} \cdot b\sqrt{2} \leq \sqrt{\mu-\lambda}\cdot \frac{b\sqrt{2}}{\sqrt{\Gamma}},$$
which implies the sought-after uniform continuity.

By applying Theorem~\ref{t1}, we get that $F \neq \emptyset$ and that for all nondecreasing $(\gamma_n)_{n \in \N} \subseteq (0, \infty)$ such that $\lim_{n \to \infty} \gamma_n = \infty$, the sequence $(T_{\gamma_n}x)_{n \in \N}$ converges to the unique point in $F$ which is closest to $x$, so the curve $(T_\gamma x)_{\gamma>0}$ converges to that same point.
\end{proof}

We see that the above result subsumes \cite[Theorem 1]{Hal67}, \cite[Lemma 1]{Bru74}, \cite[Theorem 24.1]{GoeRei84}, \cite[Theorem 3.1.1]{Jos97} and \cite[Theorem 1.4]{BacRei14}.

\mbox{}

\mbox{}

Thus, these examples have shown, in addition to the results in \cite{LeuNicSip18}, that jointly firmly nonexpansive families of mappings unify a number of algorithms involving resolvent-type mappings, and further work in this direction may increase the area of applicability even more. A promising avenue would be to investigate how the notion may be extended to Banach spaces which are more general than Hilbert spaces, allowing the abstract treatment of results such as the ones in \cite{BruRei77, ReiSha87, ReiSab11, MarReiSab12, MarReiSab13a, MarReiSab13b, MarReiSab13c}.

\section{Acknowledgements}

This work has been supported by the German Science Foundation (DFG Project KO 1737/6-1) and by a grant of the Romanian National Authority for Scientific Research, CNCS - UEFISCDI, project number PN-III-P1-1.1-PD-2019-0396.

I would like to thank Liviu P\u aunescu for suggesting to investigate continuity in Theorem~\ref{t2}.


TITLE: Is this a valid proof to show $\frac{n^5}{2^n}$ diverges?
QUESTION [0 upvotes]: Claim: $a_n = \frac{n^5}{2^n}$ diverges
Let M be arbitrary
Then
$$
\forall \; n \ge \text{max} \big\{ \big[ \sqrt[3]{M} \, \big] + 1 , 3 \big\} \\
n > \sqrt[3]{M} \\
\implies n^3 > M
$$
And Since
$$
\forall \; n \ge 3 \\
n^2 > 2^n
$$
It is true that
$$
\frac{n^5}{2^n} > \frac{n^5}{n^2} = n^3 > M
$$
$ \therefore \; a_n $ diverges

REPLY [0 votes]: If you're familiar with computational mathematics, you'll know that exponential running time ($O(a^n)$, for $a>1$) has a much faster order of growth than polynomial time, $O(n^c)$, for $c>1$. And so your quotient must vanish to zero.


TITLE: Isoperimetric constant on random graph
QUESTION [3 upvotes]: I have the following problem.
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $\mathcal{G}_{n,p}$ verify the following property : for each subset $X \in V(G)$ with cardinality $|X|\leq n/2$,
$$ e(X, V\backslash X) \geq c |X| $$
Where $ e(X, V\backslash X)$ denotes the number of edges connecting $X$ and $V\backslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant :
$$ \forall p, \ \exists c(p)>0, \ s.t. \ \mathbb{P}[ i(G) > c] \rightarrow 1 \text{ when }n\rightarrow \infty $$
And for any graph $G$, we know a lower bound for $i(G)$:
$$ \mu_2 /2 \leq i(G)$$
With $\mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $\mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $\mu_2 > 0$. But can we find similar argument for $\mu_2 > c$ for some constant $c$ ? in term of connectivity surely?
Thanks for the help!

REPLY [1 votes]: From this paper we can estimate the normalized Laplacian spectrum of $\mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$\bar{L} = I - \bar{D}^{-1/2} \bar{A}\bar{D}^{-1/2}$$
where $\bar{D} = (n-1)pI$ is the expected value of $D$, and $\bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $\bar{D}$ commutes with everything, we can rewrite this as $I - \bar{D}^{-1}\bar{A}$ which simplifies to$$\frac{n}{n-1}I - \frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,\dots,0,0$ and so the eigenvalues of $\bar{L}$ are $0, \frac{n}{n-1}, \frac{n}{n-1}, \dots, \frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $\epsilon>0$, we have $$|\lambda_i(L) - \lambda_i(\bar{L})| \le \mathcal O\left(\sqrt{\frac{\log(n/\epsilon)}{(n-1)p}}\right)$$ provided $(n-1)p > k(\epsilon)\log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $\lambda_2(L) \ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)