# An inexact proximal point method for variational
inequality on Hadamard manifolds

G. C. Bento Instituto de Matemática e Estatística, Universidade Federal de
Goiás, CEP 74001-970 - Goiânia, GO, Brazil, E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>The authors was supported in part by CNPq grants 423737/2016-3,
310864/2017-8, 305158/2014-7, 408151/2016-1 and 302473/2017-3, FAPEG/PRONEM-
201710267000532. O. P. Ferreira 11footnotemark: 1 E.A. Papa Quiroz Universidad
Nacional Mayor de San Marcos and Universidad Privada del Norte, Lima, Peru,
<EMAIL_ADDRESS>
###### Abstract

In this paper we present an inexact proximal point method for variational
inequality problem on Hadamard manifolds and study its convergence properties.
The proposed algorithm is inexact in two sense. First, each proximal
subproblem is approximated by using the enlargement of the vector field in
consideration and then the next iterated is obtained by solving this
subproblem allowing a suitable error tolerance. As an application, we obtain
an inexact proximal point method for constrained optimization problems,
equilibrium problems and nonlinear optimization problems on Hadamard
manifolds.

Keywords: Inexact proximal method, equilibrium problem, optimization problem,
Hadamard manifold

##  1 Introduction

Extensions of concepts and techniques of optimization from the Euclidean space
to the Riemannian context have been a subject of intense research in recent
years. An special attention has been given to methods of Riemannian
mathematical programming; papers published on this topic involving proximal
point methods include, but are not limited to, [2, 6, 3, 7, 29, 35, 42, 46,
47]. It is well known that one of the reasons for this extension is the
possibility of transforming non-convex or non-monotone problems in the
Euclidean context into Riemannian convex or monotone problems, by introducing
a suitable metric, which enables modified numerical methods to find solutions
for these problems; see [7, 8, 20, 12, 15, 37]. Moreover, constrained
optimization problems can be viewed as unconstrained ones from a Riemannian
geometry point of view. In particular, many Euclidean optimization problems
are naturally posed on the Riemannian context; see, e.g., [1, 18, 25, 26, 31,
34, 40, 41, 45, 49, 13].

In this paper, we consider the problem of finding a solution of a variational
inequality problem defined on Riemannian manifolds. Variational inequality on
Riemannian manifolds were first introduced and studied by Németh in [33], for
univalued vector fields on Hadamard manifolds, and for multivalued vector
fields on general Riemannian manifolds by Li and Yao in [29]; for recent works
addressing this subject see [19, 30, 43, 44]. It is worth noting that
constrained optimization problems and the problem of finding the zero of a
multivalued vector field on Riemannian manifolds, which were studied in [2, 7,
16, 21, 28, 46], are particular instances of the variational inequality
problem.

The aim of this paper is to introduce an inexact proximal point method for
variational inequality problem in Hadamard manifolds and to study its
convergence properties. The proposed algorithm combine ideas from the papers
[4] and [46] to obtain in inexact algorithm in two sense. First, each proximal
subproblem is approximated by using the enlargement of the vector field in
consideration and then the next iterated is obtained by solving this
subproblem allowing a suitable error tolerance. This algorithm has as
particular instances some algorithms previously studied. For instance, it
generalize the algorithm studied in [38] to Riemannian setting, by considering
two of the four errors considered there. Considering that the Riemannian
algorithm studied in [46, 47] does not use the enlargement of the vector field
in consideration, then in this sense our algorithm has it as particular
instance. Moreover, our algorithm also merges into algorithms studied in [5,
42]. It is worth highlighting that the use of enlargement in the proximal
subproblem to define the next iteration of the algorithm has the advantage of
providing more latitude and more robustness to the algorithm, as explained in
[11]. The concept of enlargement of monotone operators in linear spaces has
been successfully employed for a wide range of purposes; see [10] and its
reference therein. The extension of this concept to Riemannian context has
been presented in [5]. As an application, from the our iterative scheme we
obtain an inexact proximal point method for constrained optimization problems,
equilibrium problems and nonlinear optimization problems on Hadamard
manifolds. To the best of our knowledge, our approach brings a first proposal
of an inexact proximal method for equilibrium problems on Hadamard manifolds.

It is important to note that an exact version was first introduced in [12]
and, by using the theory of variational inequality, has been reaffirmed for
genuine Hadamard manifolds in [48].

The organization of the paper is as follows. In Section 2, notations basic
results used thought the paper are presented. In Section 3, the inexact
proximal point method for variational inequalities is presented and its
convergence properties are studied. As an application, in Section 4, an
inexact proximal point method for constrained optimization problems,
equilibrium problems and nonlinear optimization problems are obtained. In
Section 5 concluding remarks are presented.

##  2 Preliminaries

The aim of the section is to recall some fundamental properties and notations
of Riemannian geometry, as well as the notions of monotonicity and maximal
monotonicity and enlargement of multivalued vector fields on Hadamard
manifolds; for more details see [4].

###  2.1 Notation and terminology

In this paper, all manifolds $M$ are assumed to be Hadamard finite
dimensional. Next we recall a fundamental inequality of Hadamard manifolds
that we will need

$d^{2}(p_{1},p_{3})+d^{2}(p_{3},p_{2})-2\left\langle\exp_{p_{3}}^{-1}p_{1},\exp_{p_{3}}^{-1}p_{2}\right\rangle\leq
d^{2}(p_{1},p_{2}),\qquad p_{1},p_{2},p_{3}\in M,$ (1)

where $\exp_{p}(\cdot)$ denotes the exponential map, $\exp^{-1}_{q}(\cdot)$
its inverse and $d(\cdot,\cdot)$ is the Riemannian distance. The function
$f\mathrel{\mathop{\mathchar 58\relax}}M\to\mathbb{R}\cup\\{+\infty\\}$ is
said to be proper if $\mbox{dom}f\mathrel{\mathop{\mathchar 58\relax}}=\\{p\in
M\mathrel{\mathop{\mathchar 58\relax}}~{}f(p)<+\infty\\}\neq\varnothing$ and
it is convex on a convex set $\Omega\subset\mbox{dom}\,~{}f$ if for any
geodesic segment $\gamma$ in $\Omega$, the composition $f\circ\gamma$ is
convex. It is well known that $d^{2}(q,\cdot)$ is convex. The subdifferential
of $f$ at $p$ de defined by $\partial f(p)=\\{f(q)\geq f(p)+\langle
s,\,\exp^{-1}_{p}q\rangle,~{}q\in M\\}$. The function $f$ is lower
semicontinuous at $\bar{p}\in\mbox{dom}f$ if for each sequence $\\{p^{k}\\}$
converging to $\bar{p}$, we have $\liminf_{k\rightarrow\infty}f(p^{k})\geq
f(\bar{p}).$ Denotes by $X\mathrel{\mathop{\mathchar
58\relax}}M\rightrightarrows TM$ with $X(p)\subset T_{p}M$ a multivalued
vector field and by $\mbox{dom}X\mathrel{\mathop{\mathchar
58\relax}}=\left\\{p\in M~{}\mathrel{\mathop{\mathchar
58\relax}}~{}X(p)\neq\varnothing\right\\},$ its domain. We say that $X$ is
bounded on bounded sets  if for all bounded set $V\subset M$ such that its
closure $\overline{V}\subset\mbox{int}(\mbox{dom}\,X)$ it holds that
$m_{X}(V)\mathrel{\mathop{\mathchar 58\relax}}=\sup_{q\in
V}\left\\{\|u\|~{}\mathrel{\mathop{\mathchar 58\relax}}~{}u\in
X(q)\right\\}<+\infty$; see an equivalent definition in [28]. For two
multivalued vector fields $X,Y$ on $M$, the notation $X\subset Y$ implies that
$X(p)\subset Y(p)$, for all $p\in M$. Denotes by $P_{pq}$ the parallel
transport along the geodesic from $p$ to $q$. A multivalued vector field $X$
satisfying $\langle P_{qp}^{-1}u-v,\,\exp_{q}^{-1}p\rangle\geq 0$ and $\langle
P_{qp}^{-1}u-v,\,\exp_{q}^{-1}p\rangle\geq\rho d^{2}(p,q)$, for some $\rho>0$
and all $p,\,q\in\mbox{dom}\,X$ and $u\in X(p),~{}v\in X(q)$, is said to be
monotone, respectively, strongly monotone. Moreover, a monotone vector field
$X$ is said to be maximal monotone, if for each $p\in\mbox{dom}\,X$ and all
$u\in T_{p}M$, there holds:

$\langle P_{qp}^{-1}u-v,\,\exp_{q}^{-1}p\rangle\geq
0,q\in\mbox{dom}\,X,\quad~{}v\in X(q)~{}\Rightarrow~{}u\in X(p).$

For more details about monotonicity of vector field; see [32, 14, 28]. The
proof of the next result can be found in [28, Theorem 5.1].

######  Theorem 1.

Let $f$ be a proper, lower semicontinuous and convex function on $M$. The
subdifferential $\partial f$ is a monotone multivalued vector field.
Furthermore, if $\emph{dom}\,f=M$, then the subdifferential $\partial f$ of
$f$ is a maximal monotone vector field.

Let $\Omega\subset\mathbb{R}^{n}$ be a convex set, and $p\in\Omega$. From
[28], we define the normal cone to $\Omega$ at $p$ by

$N_{\Omega}(p)\mathrel{\mathop{\mathchar 58\relax}}=\left\\{w\in
T_{p}M~{}\mathrel{\mathop{\mathchar 58\relax}}~{}\left\langle
w,\exp_{p}^{-1}q\right\rangle\leq 0,~{}q\in\Omega\right\\}.$ (2)

The indicator function $\delta_{\Omega}\mathrel{\mathop{\mathchar
58\relax}}M\to\mathbb{R}\cup\\{+\infty\\}$ of the set $\Omega$ is defined by
$\delta_{\Omega}(p)=0$, for $p\in\Omega$ and $\delta_{\Omega}(p)=+\infty$
otherwise. The next result can be found in [28, Proposition 5.4].

######  Proposition 2.

Let $\Omega\subset M$ be a closed and convex set and
$f\mathrel{\mathop{\mathchar 58\relax}}M\to\mathbb{R}$ be a convex function.
Then, $\partial\delta_{\Omega}(p)=N_{\Omega}(p)$ and
$\partial(f+\delta_{\Omega})(p)=\partial f(p)+N_{\Omega}(p)$, for all
$p\in\Omega$.

The proof of the next result follows from [29, Corollary 3.14].

######  Lemma 3.

Let $X$ be a maximal monotone vector field such that $\emph{dom}\,X=M$. For
each $q\in M$ and $\lambda>0$, the inclusion problem $0\in
X(p)+N_{\Omega}(p)-\lambda\exp^{-1}_{p}q,$ for $p\in M$, has an unique
solution.

Since the exponential mapping is continuous in both arguments, the next
proposition is an immediate consequence of definition (2), for that its proof
wil be omite.

######  Proposition 4.

Let $C\subset M$ be a closed set. If
$\overline{p}=\lim_{k\rightarrow\infty}p^{k}$,
$\overline{u}=\lim_{k\rightarrow\infty}u^{k}$, and $u^{k}\in
N_{\Omega}(p^{k})$ for all $k$, then $\overline{u}\in
N_{\Omega}(\overline{p})$.

We end this section with a real analysis result, see the proof in [36, Lemma
2, pp. 44].

######  Lemma 5.

Let $\left\\{\zeta_{k}\right\\}$,$\left\\{\gamma_{k}\right\\}$,
$\left\\{\beta_{k}\right\\}$ be sequences of nonnegative real numbers
satisfying $\sum_{k=1}^{\infty}\gamma_{k}<\infty$ and
$\sum_{k=1}^{\infty}\beta_{k}<\infty$. If
$\zeta_{k+1}\leq\left(1+\gamma_{k}\right)\zeta_{k}+\beta_{k}$, then
$\left\\{\zeta_{k}\right\\}$ converges.

###  2.2 Enlargement of Monotone Vector Fields

In this section we recall some concepts and results related to enlargement of
vector fields in the Hadamard manifolds setting, for details see [5].
Throughout this section $X$ and $Y$ denote multivalued monotone vector fields
on $M$ and $\epsilon\geq 0$.

######  Definition 1.

The enlargement of vector field $X^{\epsilon}\mathrel{\mathop{\mathchar
58\relax}}M\rightrightarrows TM$ associated to $X$ is defined by

$X^{\epsilon}(p)\mathrel{\mathop{\mathchar 58\relax}}=\left\\{u\in
T_{p}M~{}\mathrel{\mathop{\mathchar 58\relax}}~{}\left\langle
P_{qp}^{-1}u-v,\,\exp_{q}^{-1}p\right\rangle\geq-\epsilon,~{}q\in\mbox{dom}\,X,~{}v\in
X(q)\right\\},\quad p\in\mbox{dom}\,X.$

Next proposition shows that $X^{\epsilon}$ effectively constitutes an
enlargement to $X$.

######  Proposition 6.

$X\subset X^{\epsilon}$ and $\emph{dom}\,X\subset\emph{dom}\,X^{\epsilon}$. In
particular, if $\emph{dom}\,X=M$ then
$\emph{dom}\,X^{\epsilon}=\emph{dom}\,X$. Moreover, if $X$ is maximal then
$X^{0}=X$.

In the next three propositions we state the main properties used throughout
our presentation, which are extensions to the Riemannian context of the
corresponding one of linear setting; see [11].

######  Proposition 7.

$X^{\epsilon_{2}}\subset X^{\epsilon_{1}}$, for all
$\epsilon_{1}\geq\epsilon_{2}\geq 0$, and
$X^{\epsilon_{1}}+Y^{\epsilon_{2}}\subset(X+Y)^{\epsilon_{1}+\epsilon_{2}}$.

######  Proposition 8.

Let $\\{\epsilon^{k}\\}$ be a sequence of positive numbers, and
$\\{(p^{k},\,u^{k})\\}$ be a sequence in $TM$. If
$\overline{\epsilon}=\lim_{k\rightarrow\infty}\epsilon^{k}$,
$\overline{p}=\lim_{k\rightarrow\infty}p^{k}$,
$\overline{u}=\lim_{k\rightarrow\infty}u^{k}$, and $u^{k}\in
X^{\epsilon_{k}}(p^{k})$ for all $k$, then $\overline{u}\in
X^{\overline{\epsilon}}(\overline{p})$;

######  Proposition 9.

If $X$ is maximal monotone and $\emph{dom}\,X=M$, then $X^{\epsilon}$ is
bounded on bounded sets, for all $\epsilon\geq 0$.

##  3  Inexact Proximal Point Method for Variational Inequalities

In this section, we introduce an inexact version of the proximal point method
for variational inequalities in Hadamard manifolds. It is worth noting that,
the variational inequality problem was first introduced in [33], for single-
valued vector fields on Hadamard manifolds, and in [29] for multivalued vector
fields in Riemannian manifolds.

Let $X\mathrel{\mathop{\mathchar 58\relax}}M\rightrightarrows TM$ be a
multivalued vector field and $\Omega\subset M$ be a nonempty set. The
variational inequality problem for $X$ and $C$, denoted by VIP(X,$\Omega$),
consists of finding $p^{*}\in\Omega$ such that there exists $u\in X(p^{*})$
satisfying

$\langle u,\,\exp^{-1}_{p^{*}}q\rangle\geq 0,\qquad q\in\Omega.$ (3)

Using (2), i.e., the definition of normal cone to $\Omega$, VIP(X,$\Omega$)
becomes the problem of finding an $p^{*}\in\Omega$ that satisfies the
inclusion

$0\in X(p)+N_{\Omega}(p).$ (4)

######  Remark.

In particular, if $\Omega=M$, then $N_{\Omega}(p)=\\{0\\}$ and VIP
(X,$\Omega$) are problems with regard to finding $p^{*}\in\Omega$ such that
$0\in X(p^{*}).$

Hereafter, $S(X,\,\Omega)$ denotes the solution set of the inclusion (4). We
require the following three assumptions:

  * A1.

$\mbox{dom}\,X=M$ and $\Omega$ closed and convex;

  * A2.

$X$ is maximal monotone;

  * A3.

$S(X,\,\Omega)\neq\varnothing$.

In the following we state two algorithms to solve (3) or equivalently (4). To
state the algorithms take two real numbers $\hat{\lambda}$ and
$\tilde{\lambda}$ satisfying $0<\hat{\lambda}\leq\tilde{\lambda}$ and four
exogenous sequences of positive real numbers, $\\{\lambda_{k}\\}$,
$\\{\sigma_{k}\\}$, $\\{\theta_{k}\\}$ and $\\{\epsilon_{k}\\}$ satisfying

$\hat{\lambda}\leq\lambda_{k}\leq\tilde{\lambda},\qquad\qquad\sum_{k=1}^{+\infty}\epsilon_{k}<+\infty,\qquad\qquad\sum_{k=1}^{+\infty}\sigma_{k}<+\infty,\qquad\qquad\sum_{k=1}^{+\infty}\theta_{k}<+\infty.$
(5)

The first version of inexact proximal point method for solving (4) is defined
as follows:

######  Algorithm 1.

Inexact proximal point method with absolute error tolerance

0.

Take $\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\theta_{k}\\}$
satisfying (5), and $p^{0}\in\Omega$. Set $k=0$.

1.

Given $p^{k}\in\Omega$, compute $p^{k+1}\in\Omega$ and $e^{k+1}\in
T_{p^{k+1}}M$ such that

$e^{k+1}\in
X^{\epsilon_{k}}(p^{k+1})+N_{\Omega}(p^{k+1})-\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k},$
(6) $\|e^{k+1}\|\leq\theta_{k}.$ (7)

2.

If $p^{k}=p^{k+1}$, then stop; otherwise, set $k\leftarrow k+1$, and go to
step 1.

It is worth to noting that Algorithm 1 is inexact in two sense, namely,
$X^{\epsilon_{k}}$ is an enlargement of the vector field $X$ and each
iteration $p^{k+1}$ is an approximated solution of the vectorial inclusion
$0\in X^{\epsilon_{k}}(p)+N_{\Omega}(p)-\lambda_{k}\exp^{-1}_{p}p^{k}$
satisfying the error criterion (7). Note that for $\theta_{k}=0$ in (7),
Algorithm 1 merges into algorithm introduced in [5]. The error criterion (7)
was introduced in the celebrated paper [38] to analyze an inexact version of
the proximal point method to find zeroes of maximal monotone operators in
linear context; see [46, 47] for a generalization to Riemannian setting.

The second version of inexact proximal point method for solving (4) is defined
as follows:

######  Algorithm 2.

Inexact proximal point method with relative error tolerance

0.

Take $\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$
satisfying (5), and $p^{0}\in\Omega$. Set $k=0$.

1.

Given $p^{k}\in\Omega$, compute $p^{k+1}\in\Omega$ and $e^{k+1}\in
T_{p^{k+1}}M$ such that

$e^{k+1}\in
X^{\epsilon_{k}}(p^{k+1})+N_{\Omega}(p^{k+1})-\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k},$
(8) $\|e^{k+1}\|\leq\sigma_{k}d(p^{k},p^{k+1}).$ (9)

2.

If $p^{k}=p^{k+1}$, then stop; otherwise, set $k\leftarrow k+1$, and go to
step 1.

First we remark that Algorithm 2 differs from Algorithm 1 only in the errors
criterion adopted, more precisely, between (7) and (9). The error criterion
(9) was also introduced in [38] in linear setting. When $\sigma_{k+1}=0$ in
(9), Algorithm 2 merges into algorithm introduced in [5]. A variant of error
criterium (9) to analyze (8), for the particular case $\epsilon_{k}\equiv 0$,
has appeared in [42].

In the following we present the well-definedness and convergence properties of
the sequence $\\{p^{k}\\}$ generated by Algorithms 1 and 2. We begin with the
well-definition.

######  Theorem 10.

Each sequence $\\{p^{k}\\}$ generated by Algorithms 1 or 2 is well defined.

###### Proof.

First of all note that for each $p^{k}\in\Omega$ and $\lambda_{k}>0$, Lemma 3
implies that

$0\in X(p)+N_{\Omega}(p)-\lambda_{k}\exp^{-1}_{p}p^{k},$ (10)

has an unique solution in $\Omega$. Since $\mbox{dom}\,X=M$, Proposition 6 and
item (i) of Proposition 9 imply that $X(p)\subseteq X^{\epsilon}(p)$ for all
$p\in M$ and $\epsilon\geq 0$. Therefore, letting $e^{k+1}=0$ and $p^{k+1}$ as
the solution of (10), we conclude they also satisfy (6)-(9), which proof the
well definition. ∎

######  Remark.

Using Proposition 6 we conclude that $N_{\Omega}\subset N_{\Omega}^{0}$. Thus,
from second. part of Proposition 7, we have
$X^{\epsilon_{k}}+N_{\Omega}\subset(X+N_{\Omega})^{\epsilon_{k}}$, for all
$k=0,1,\ldots$. Therefore, using (8), the following inequality holds

$e^{k+1}\in(X+N_{\Omega})^{\epsilon_{k}}(p^{k+1})-\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k},\qquad
k=0,1,\ldots.$ (11)

Note that the condition (11) is less restrictive than (6) and (8).

From now on, unless explicitly stated, $\\{p^{k}\\}$ denotes the sequence
generated by Algorithm 1 or 2. It is worth to noting that $p^{k}=p^{k+1}$
implies $p^{k+1}\in S(X,\,\Omega)$. Thus, without loss of generality, we
assume that $\\{p^{k}\\}$ is infinite.

###  3.1 Convergence analysis

In this section our aim is to prove the convergence of the sequence
$\\{p^{k}\\}$ to a point in $S(X,\,\Omega)$. For that we first need some
auxiliary results. We begin establishing a useful inequality.

######  Lemma 11.

For all $\eta>0$, the following inequality holds

$\left[1-\frac{\eta}{\lambda_{k}}\right]d^{2}(q,p^{k+1})\leq
d^{2}(q,p^{k})-d^{2}(p^{k},p^{k+1})+\frac{1}{\eta\lambda_{k}}\|e^{k+1}||^{2}+\frac{2}{\lambda_{k}}\epsilon_{k},\qquad
k=0,1,\ldots.$

###### Proof.

First we note that (8) or (6) is equivalent to

$e^{k+1}+\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k}\in(X+N_{\Omega})^{\epsilon_{k}}(p^{k+1}),\qquad
k=0,1,\ldots.$ (12)

Considering that $P_{qp^{k+1}}^{-1}\exp^{-1}_{q}p^{k+1}=-\exp^{-1}_{p^{k+1}}q$
and the parallel transport being isometric, the last inclusion together with
Definition 1 yields

$-\left\langle
e^{k+1}+\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k},~{}\exp^{-1}_{p^{k+1}}q\right\rangle+\left\langle
v,~{}-\exp^{-1}_{q}p^{k+1}\right\rangle\geq-\epsilon_{k},\quad$

for all $q\in\Omega$, $v\in(X+N_{\Omega})(q)$ and all $k=0,1,\ldots$. In
particular, if $q\in S(X,\,\Omega)$, then $0\in(X+N_{\Omega})(q)$ and the last
inequality becomes

$\displaystyle-\left\langle
e^{k+1}+\lambda_{k}\exp^{-1}_{p^{k+1}}p^{k},\exp^{-1}_{p^{k+1}}q\right\rangle\geq-\epsilon_{k},$

for all $q\in S(X,\,\Omega)$ and all $k=0,1,\ldots$. Using the last inequality
and (1) with $p_{1}=p^{k}$, $p_{2}=q$, and $p_{3}=p^{k+1}$, along with some
algebraic calculations, we obtain

$\frac{2}{\lambda_{k}}\left(\left\langle
e^{k+1},\exp^{-1}_{p^{k+1}}q\right\rangle-\epsilon_{k}\right)\leq
d^{2}(q,p^{k})-d^{2}(p^{k},p^{k+1})-d^{2}(q,p^{k+1}),$

for all $q\in S(X,\,\Omega)$ and all $k=0,1,\ldots$. The last inequality gives

$d^{2}(q,p^{k+1})\leq
d^{2}(q,p^{k})-d^{2}(p^{k},p^{k+1})-\frac{2}{\lambda_{k}}\left\langle
e^{k+1},\exp^{-1}_{p^{k+1}}q\right\rangle+\frac{2\epsilon_{k}}{\lambda_{k}}$

for all $q\in S(X,\,\Omega)$ and all $k=0,1,\ldots$. On the other hand, some
algebraic manipulations yields

$-\left\langle
e^{k+1},\exp^{-1}_{p^{k+1}}q\right\rangle\leq\frac{1}{2\eta}\|e^{k+1}||^{2}+\frac{1}{2}\eta
d^{2}(p^{k+1},q).$

Therefore, combining two previous last inequalities yields the inequality of
the lemma. ∎

######  Corollary 12.

Let $\\{p^{k}\\}$ be generated by Algorithms 1. Then, there exists a
${\bar{k}}\in\mathbb{N}$ such that, for all $k\geq{\bar{k}}$, there holds

$\displaystyle
d^{2}(q,p^{k+1})\leq\left(1+\frac{2\theta_{k}}{\hat{\lambda}}\right)d^{2}(q,p^{k})-d^{2}(p^{k+1},p^{k})+\frac{2}{\hat{\lambda}}\left({\theta_{k}}+2\epsilon_{k}\right).$

###### Proof.

First, applying Lemma 11 with $\eta=\theta_{k}$ and then using (7) yields

$\left(1-\frac{\theta_{k}}{\lambda_{k}}\right)d^{2}(q,p^{k+1})\leq
d^{2}(q,p^{k})-d^{2}(p^{k},p^{k+1})+\frac{\theta_{k}}{\lambda_{k}}+\frac{2}{\lambda_{k}}\epsilon_{k},\qquad
k=0,1,\ldots.$

It follows from (5) that there exists a ${\bar{k}}\in\mathbb{N}$ such that
$0\leq\theta_{k}<\lambda_{k}/2$, for all $k\geq{\bar{k}}$. Thus, we conclude
from the last inequality that

$d^{2}(q,p^{k+1})\leq\left(1+\frac{\frac{\theta_{k}}{\lambda_{k}}}{1-\frac{\theta_{k}}{\lambda_{k}}}\right)d^{2}(q,p^{k})-\frac{\lambda_{k}}{\lambda_{k}-\theta_{k}}d^{2}(p^{k+1},p^{k})+\frac{1}{\lambda_{k}-\theta_{k}}\left({\theta_{k}}+2\epsilon_{k}\right),\quad
k\geq{\bar{k}},$ (13)

and the deride inequality follows by using again
$0\leq\theta_{k}<\lambda_{k}/2$ and first inequality in (5). ∎

######  Corollary 13.

Let $\\{p^{k}\\}$ be generated by Algorithms 2. Then, there exists a
${\bar{k}}\in\mathbb{N}$ such that, for all $k\geq{\bar{k}}$, there holds

$\displaystyle
d^{2}(q,p^{k+1})\leq\left(1+\frac{2\sigma_{k}}{\hat{\lambda}}\right)d^{2}(q,p^{k})-d^{2}(p^{k+1},p^{k})+\frac{4}{\hat{\lambda}}\epsilon_{k}.$

###### Proof.

Applying Lemma 11 with $\eta=\sigma_{k}$ and using (9), we conclude that

$\left(1-\frac{\sigma_{k}}{\lambda_{k}}\right)d^{2}(q,p^{k+1})\leq
d^{2}(q,p^{k})-\left(1-\frac{\sigma_{k}}{\lambda_{k}}\right)d^{2}(p^{k+1},p^{k})+\frac{2}{\lambda_{k}}\epsilon_{k},\qquad
k=0,1,\ldots.$ (14)

On the other hand, the forth inequality in (5) implies that there exists a
${\bar{k}}\in\mathbb{N}$ such that $0<\sigma_{k}<\lambda_{k}/2$, for all
$k\geq{\bar{k}}$. Hence, using (14) together with the first inequality in (5),
we obtain the desired inequality. ∎

######  Proposition 14.

Let $\\{p^{k}\\}$ be a sequence generated by Algorithms 1 or 2. Then, the
following statement hold:

  1. $(a)$

The sequence $\\{d(p^{k},q)\\}$ converges, for all $q\in S(X,\,\Omega)$;

  2. $(b)$

The sequence $\\{p^{k}\\}$ is bounded;

  3. $(c)$

$\lim_{k\to\infty}d(p^{k+1},p^{k})=0.$

###### Proof.

If $\\{p^{k}\\}$ is generated by Algorithm 1, then Corollary 12 implies that

$\displaystyle
d^{2}(q,p^{k+1})\leq\left(1+\frac{2\theta_{k}}{\hat{\lambda}}\right)d^{2}(q,p^{k})+\frac{2}{\hat{\lambda}}\left[{\theta_{k}}+2\epsilon_{k}\right].$

Hence, item $(a)$ follows by applying Lemma 5 with
$\gamma_{k}=2\theta_{k}/{\hat{\lambda}}$,
$\beta_{k}=2[{\theta_{k}}+2\epsilon_{k}]{\hat{\lambda}}$,
$\zeta_{k}=d^{2}(q,p^{k})$ and $\zeta_{k+1}=d^{2}(q,p^{k+1})$. On the other
hand, if $\\{p^{k}\\}$ is a sequence generated by Algorithm 2, then Corollary
13 gives

$\displaystyle
d^{2}(q,p^{k+1})\leq\left(1+\frac{2\sigma_{k}}{\hat{\lambda}}\right)d^{2}(q,p^{k})+\frac{4}{\hat{\lambda}}\epsilon_{k}.$

Thus, item $(a)$ follows by applying Lemma 5 with
$\gamma_{k}=2\sigma_{k}/{\hat{\lambda}}$,
$\beta_{k}=4\epsilon_{k}/{\hat{\lambda}}$, $\zeta_{k}=d^{2}(q,p^{k})$ and
$\zeta_{k+1}=d^{2}(q,p^{k+1})$. The item $(b)$ is an immediate consequence of
item $(a)$. The next task is to prove item $(c)$. If $\\{p^{k}\\}$ is
generated by Algorithm 1, then using again Corollary 12 we have

$\displaystyle d^{2}(p^{k+1},p^{k})\leq
d^{2}(q,p^{k})-d^{2}(q,p^{k+1})+\frac{2\theta_{k}}{\hat{\lambda}}d^{2}(q,p^{k})+\frac{2}{\hat{\lambda}}\left[{\theta_{k}}+2\epsilon_{k}\right].$

Now, note that (5) implies $\lim_{k\to\infty}\sigma_{k}=0$ and
$\lim_{k\to\infty}\epsilon_{k}=0$. Therefore, item $(a)$ together with the
last inequality imply item $(c)$. If $\\{p^{k}\\}$ is generated by Algorithm
2, then it foolows from Corollary 13 that

$d^{2}(p^{k+1},p^{k})\leq
d^{2}(q,p^{k})-d^{2}(q,p^{k+1})+\frac{2\sigma_{k}}{\hat{\lambda}}d^{2}(q,p^{k})+\frac{4}{\hat{\lambda}}\epsilon_{k}.$

On the other hand, using (5) we have $\lim_{k\to\infty}\sigma_{k}=0$ and
$\lim_{k\to\infty}\epsilon_{k}=0$. Therefore, item $(a)$ together with the
late inequality imply item $(c)$. ∎

######  Theorem 15.

Let $\\{p^{k}\\}$ be generated by Algorithms 1 or 2. Then, $\\{p^{k}\\}$
converges to a point $p^{*}\in S(X,\,\Omega)$.

###### Proof.

Since $\\{p^{k}\\}\subset\Omega$ and $\Omega$ is closed, item $(b)$ of
Proposition 14 implies that there exists ${\bar{p}}\in\Omega$ a cluster point
of $\\{p^{k}\\}$. Let $\\{p^{k_{j}}\\}$ be a subsequence of $\\{p^{k}\\}$ such
that $\lim_{j\to\infty}p^{k_{j}}={\bar{p}}$. Our first aim is to prove that
${\bar{p}}\in S(X,\,\Omega)$. For that, using inclusion (8) or (6), there
exist $u^{k_{j}+1}\in X^{\epsilon_{k_{j}}}(p^{k_{j}+1})$ such that

$e^{k_{j}+1}+\lambda_{k_{j}}\exp^{-1}_{p^{k_{j}+1}}p^{k_{j}}-u^{k_{j}+1}\in
N_{\Omega}(p^{k_{j}+1}),\qquad j=0,1,\ldots.$ (15)

On the other hand, item $(c)$ of Proposition 14 implies that
$\lim_{j\to\infty}p^{k_{j}+1}={\bar{p}}$. Moreover, considering that
$\\{\theta_{k}\\}$ and $\\{\sigma_{k}\\}$ are bounded, it follows from (7),
respectively (9), and item (c) of Proposition 14 that
$\lim_{k\to\infty}e^{k}=0$. Letting ${\bar{\epsilon}}=\sup_{k}\epsilon_{k}$,
the first part of Proposition 7 implies that $u^{k_{j}+1}\in
X^{\epsilon_{k_{j}}}(p^{k_{j}+1})\subset X^{\bar{\epsilon}}(p^{k_{j}+1})$, for
all $j=0,1,\ldots$. Thus, considering that $\\{p^{k}\\}$ is bounded, we
conclude from Proposition 9 that $\\{u^{k_{j}+1}\\}$ is also bounded. Without
loss of generality we assume that $\lim_{j\to\infty}u^{k_{j}+1}={\bar{u}}$.
Hence, taking into account that $\lim_{k\to\infty}\epsilon_{k}=0$,
$\lim_{j\to\infty}p^{k_{j}+1}={\bar{p}}$ and $u^{k_{j}+1}\in
X^{\epsilon_{k_{j}}}(p^{k_{j}+1})$, for all $j=0,1,\ldots$, it follows from
Proposition 6 and Proposition 8 that ${\bar{u}}\in
X^{0}({\bar{p}})=X({\bar{p}})$. Therefore, taking limit in (15) and
considering Proposition 4 we conclude that $-{\bar{u}}\in
N_{\Omega}({\bar{p}})$. Due to ${\bar{u}}\in X({\bar{p}})$ we have $0\in
X({\bar{p}})+N_{\Omega}({\bar{p}})$, which implies that $\bar{p}\in
S(X,\,\Omega)$. Moreover, using item $(a)$ of Proposition 14 que obtain that
the sequence $\\{d(p^{k},{\bar{p}})\\}$ converges. Considering that
$\lim_{j\to\infty}p^{k_{j}}={\bar{p}}$, we have
$\lim_{k\to\infty}d(p^{k_{j}},{\bar{p}})=0$. Therefore, we conclude that
$\lim_{k\to\infty}d(p^{k},{\bar{p}})=0$, or equivalently,
$\lim_{k\to\infty}p^{k}={\bar{p}}$, which concludes the proof. ∎

######  Remark.

In [46, 47] is presented an inexact version of the proximal point method for
to find singularity of a vector field on Hadamard manifolds. These papers
differs from the present paper in two ways, namely, [46, 47] use only absolute
summable error criteria and the enlargement $X^{\epsilon}$ of $X$ was not
considered. It is worth noting that, the enlargement $X^{\epsilon}$ is an
(outer) approximation to $X$. Consequently, even in the linear setting, the
proximal subproblem using the enlargement has the advantage of providing more
latitude and more robustness to the methods used for solving it; see [11, 10].

##  4 Applications

The general Problem (4) has as particular instances the optimization problem,
equilibrium problem and nonlinear optimization problem. The aim of this
section is to apply the results obtained in the previous section to these
particular instances. For each problem studied, a version of the Algorithm 2
is stated to solve it. Since a version of the Algorithm 1 can be stated
following the same idea, it will be omitted.

###  4.1  Inexact proximal point method for optimization

In this section, we apply the results of the previous section to obtain an
inexact proximal point method for the constrained optimization problems in
Hadamard manifolds. Given a closed and convex set $\Omega\subset M$ and a
convex function $f\mathrel{\mathop{\mathchar
58\relax}}M\rightarrow\mathbb{R}$, the constrained optimization problem
consists of

$\min~{}f(p),\qquad~{}p\in\Omega.$ (16)

The problem in (16) is equivalently stated as follows

$\displaystyle\min~{}(f+\delta_{\Omega})(p),\qquad~{}p\in M.$ (17)

where $\delta_{\Omega}$ is the indicate functionof $\Omega$. Hereafter,
$S(f,\Omega)$ denotes the solution set of the problem in (16). It well know
that (17) can be stated as the variational inequality problem (4). In fact,
first note that due to convexity of the set $\Omega$ and of the function $f$
we conclude that $f+\delta_{\Omega}$ is also convex. Thus, by using
Proposition 2 we have

$\partial(f+\delta_{\Omega})(p)=\partial f(p)+N_{\Omega}(p),\qquad
p\in\Omega.$

Therefore, $p^{*}\in S(f,\Omega)$ if, and only if, $0\in\partial
f(p^{*})+N_{\Omega}(p^{*})$. Therefore, (17) is equivalent to find an
$p^{*}\in\Omega$ satisfying the inclusion

$0\in\partial f(p)+N_{\Omega}(p).$ (18)

In order to present a version of Algorithm 2 to solve (16) or equivalently
(18), we need to consider the enlargement of the subdifferential of $f$,
denoted by $\partial^{\epsilon}f\mathrel{\mathop{\mathchar
58\relax}}M\rightrightarrows TM$, which is defined by

$\partial^{\epsilon}f(p)\mathrel{\mathop{\mathchar 58\relax}}=\left\\{u\in
T_{p}M~{}\mathrel{\mathop{\mathchar
58\relax}}~{}\left\langle\mbox{P}_{qp}^{-1}u-v,\,\exp_{q}^{-1}p\right\rangle\geq-\epsilon,~{}q\in
M,~{}v\in\partial f(q)\right\\},\qquad\epsilon\geq 0.$

To state the version of Algorithm 2 to solve (16) or equivalently (18), take
three exogenous sequences of nonnegative real numbers, $\\{\lambda_{k}\\}$,
$\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$ satisfying (5). Then, the inexact
proximal point method for the optimization problem (18) is introduced as
follows:

######  Algorithm 3.

Inexact proximal point method for optimization problems

0.

Take $\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$
satisfying (5) and $p^{0}\in\Omega$. Set $k=0$.

1.

Given $p^{k}\in\Omega$, compute $p^{k+1}\in\Omega$ and $e^{k+1}\in
T_{p^{k+1}}M$ such that

$e^{k+1}\in\partial^{\epsilon_{k}}f(p^{k+1})+N_{\Omega}(p^{k+1})-2\lambda_{k}\exp^{-1}_{p^{k+1}}x^{k},$
(19) $\|e^{k+1}\|\leq\sigma_{k}d(p^{k},p^{k+1}),$ (20)

2.

If $p^{k}=p^{k+1}$, then stop; otherwise, set $k\leftarrow k+1$, and go to
step 1.

######  Remark.

In case, $\epsilon_{k}\equiv 0$, $e^{k+1}\equiv 0$ and $\Omega=M$, the
Algorithm 3 generalize the algorithm proposed by Ferreira and Oliveira [21],
and the method (5.15) of Chong Li et. al. [28]. For $\epsilon_{k}=0$, inexact
variations of (19) with absolute erros can be found in [46] and [42] for
relative erro. Finally, letting $e^{k+1}\equiv 0$, the Algorithm 3 retrieves
the one presented in [5].

In the following we state a convergence result for the sequence generated by
(19) and (20). First note that, for considering that $\mbox{dom}f=M$, Theorem
1 implies that $\partial f$ is maximal monotone. Hence, from Proposition 2 we
have $N_{\Omega}=\partial\delta_{\Omega}$. Therefore, by applying Theorems 10
and 15 with $X=\partial f$ we obtain the following theorem.

######  Theorem 16.

Assume that $S(f,\,\Omega)\neq\varnothing$. Then, the sequence $\\{p^{k}\\}$
generated by (19) and (20) is well defined and converges to a point $p^{*}\in
S(f,\,\Omega)$.

In the next remark, we highlight the advantage of using the enlargement of the
subdifferential instead of the $\epsilon$-subdifferential of $f$.

######  Remark.

The $\epsilon$-subdifferential of $f$, denoted by
$\partial_{\epsilon}f\mathrel{\mathop{\mathchar 58\relax}}M\rightrightarrows
TM$, is given by

$\partial_{\epsilon}f(p)\mathrel{\mathop{\mathchar 58\relax}}=\left\\{u\in
T_{p}M~{}\mathrel{\mathop{\mathchar 58\relax}}~{}f(q)\geq f(p)+\left\langle
u,\exp^{-1}_{p}q\right\rangle-\epsilon,~{}q\in M\right\\},\qquad\epsilon\geq
0.$

As can be seen in [5], the enlargement of the subdifferential of $f$ is bigger
than its $\epsilon$-subdifferential, i.e., for each $p\in M$, there holds
$\partial_{\epsilon}f(p)\subseteq\partial^{\epsilon}f(p)$. Taking into account
that this inclusion may be strict, we can to state that the iteration in (19)
using the enlargement of $\partial f(\cdot)$ has the advantages of providing
more latitude and more robustness than a method using the
$\epsilon$-subdifferential of $f$.

###  4.2 Inexact proximal point method for equilibrium problems

In this section, by using the results of Section 3, we present a version of
the inexact proximal point method for equilibrium problems in Hadamard
manifolds. For that we need some preliminaries. Let $C\subset M$ be a
nonempty, closed and convex set and $F\mathrel{\mathop{\mathchar
58\relax}}M\times M\to\mbox{${I\\!\\!R}$}$ be a bifunction satisfying the
following standard assumptions:

  1. H1.

$F(\cdot,y)\mathrel{\mathop{\mathchar
58\relax}}M\rightarrow\mbox{${I\\!\\!R}$}$ is upper semicontinuous for all
$y\in M;$

  2. H2.

$F(x,\cdot)\mathrel{\mathop{\mathchar
58\relax}}M\rightarrow\mbox{${I\\!\\!R}$}$ is convex, for all $x\in M.$;

  3. H3.

$F$ is monotone on ${C}$, i.e., $F(x,y)+F(y,x)\leq 0$, for all $x,y\in{C}$;

  4. H4.

$F(x,x)=0,$ for all $x\in{C}.$

The equilibrium problem associated to the set $C$ and the bifunction $F$,
denoted by $\mbox{EP}(F,{C})$, is stated as follows: Find $x^{*}\in{C}$ such
that

$F(x^{*},y)\geq 0,\qquad y\in{C}.$ (21)

Denote by $S(F,{C})$ the solution set of the $\mbox{EP}(F,{C})$. By using [48,
Proposition 3.3] we obtain that (21) is equivalent to find an $p^{*}\in\Omega$
satisfying the inclusion

$0\in\partial_{2}F(p,\cdot)(p)+N_{\Omega}(p),$ (22)

where $\partial_{2}F(p,\cdot)$ denotes the subdifferential of $F$ with respect
to the second argument. We also assume that

  1. H5.

The set $S(F,C)$ is nonempty.

######  Remark.

Assumptions H1-H4 are standard for the study of equilibrium problems in linear
spaces, see [23, 22, 24]. It is worth to notting that assumption H5 can be
reached under suitable condition on the set $C$ or the bifunction $F$; papers
addressing this issue include, but are not limited to, [4, 27, 12, 48, 50]. To
the best of our knowledge, our approach brings a first proposal of an inexact
proximal method for equilibrium problems. It is worth noting that an exact
version has been first introduced in [12] and, by using variational inequality
theory, reaffirmed for genuine Hadamard manifolds in [48].

Before presenting a version of Algorithm 2 to solve (21), or equivalently
(22), we need to consider the enlargement of the subdifferential of $F$ with
respect to the second argument, denoted by
$\partial_{2}^{\epsilon}F(z,\cdot)\mathrel{\mathop{\mathchar
58\relax}}M\rightrightarrows TM$, for each fixed $z\in{C}$, which is
introduced as follows

$\partial_{2}^{\epsilon}F(z,x)\mathrel{\mathop{\mathchar
58\relax}}=\left\\{w\in T_{p}M\mathrel{\mathop{\mathchar
58\relax}}~{}F(z,y)\geq F(z,x)+\left\langle
w,\exp^{-1}_{x}y\right\rangle-\epsilon,~{}y\in M\right\\}.$ (23)

To state the version of Algorithm 2 to solve the equilibrium problem (21) or
equivalently (22), take three exogenous sequences of nonnegative real numbers,
$\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$ satisfying
(5). In case, the inexact proximal point method for solving (21) is introduced
as follows:

######  Algorithm 4.

Inexact proximal point method for equilibrium problems

0.

Take $\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$
satisfying (5), $x^{0}\in{C}$ and $\sigma>1$. Set $k=1$.

1.

Given $x^{k}\in{C}$, compute $x^{k+1}\in{C}$ and $e^{k}\in T_{x^{k}}M$ such
that

$e^{k+1}\in\partial_{2}^{\epsilon_{k}}F(x^{k+1},x^{k+1})+N_{\Omega}(x^{k+1})-\lambda_{k}{\rm
exp}_{x^{k+1}}^{-1}x^{k},$ (24) $\|e^{k+1}\|\leq\sigma_{k}d(p^{k},p^{k+1}).$
(25)

2.

If $x^{k-1}=x^{k}$ or $x^{k}\in$, then stop; otherwise, set $k\leftarrow k+1$,
and go to step 1.

######  Remark.

The Algorithm 4 can be seen as an inexact version of the following iterative
scheme considered in [12]: For $x^{k}\in{C}$, compute $x^{k+1}\in{C}$ such
that

$F(x^{k+1},x)-\lambda_{k}\langle{\rm exp}_{x^{k+1}}^{-1}x^{k},{\rm
exp}_{x^{k+1}}^{-1}x\rangle\geq 0,\qquad x\in{C}.$ (26)

Indeed, given $x^{k}$ and $x^{k+1}\in{C}$ satisfying (26) we have

$F(x^{k+1},x)+\delta_{C}(x)-\left(F(x^{k+1},x^{k+1})+\delta_{C}(x^{k+1})+\left\langle\lambda_{k}{\rm
exp}_{x^{k+1}}^{-1}x^{k},{\rm exp}_{x^{k+1}}^{-1}x\right\rangle\right)\geq 0,$
(27)

for all $x\in M$. Since the function
$p\mapsto(F(p^{k+1},\cdot)+\delta_{C}(\cdot))(p)$ is convex, it follows from
the definition of the subdifferential that $\lambda_{k}{\rm
exp}_{x^{k+}}^{-1}x^{k}\in\partial_{2}(F(x^{k+1},\cdot)+\delta_{C}(\cdot))(x^{k+1})$.
Hence, by using Proposition 2 we obtain

$0\in\partial_{2}F(x^{k+1},x^{k+1})-\lambda_{k}{\rm
exp}_{x^{k+1}}^{-1}x^{k}+N_{\Omega}(x^{k+1}),$

which implies that $x^{k}$ and $x^{k+1}$ also satisfy (24) and (25) with
$e^{k+1}=0$ and $\epsilon_{k}=0$.

In the following we state a convergence result for the sequence generated by
(24) and (25). First note that, for considering that $\mbox{dom}F(p,\cdot)=M$,
Theorem 1 implies that $\partial_{2}F(p,\cdot)$ is maximal monotone, for all
$p\in M$. Moreover, Proposition 2 implies that
$N_{\Omega}=\partial\delta_{\Omega}$. Therefore, by applying Theorems 10 and
15 with $X=\partial_{2}F(p,\cdot)$ we obtain the following theorem.

######  Theorem 17.

The sequence $\\{p^{k}\\}$ generated by (24) and (25) is well defined and
converges to a point $p^{*}\in S(f,\,\Omega)$.

###### Proof.

First note that, for considering that $\mbox{dom}F(p,\cdot)=M$, Theorem 1
implies that $\partial_{2}F(p,\cdot)$ is maximal monotone, for all $p\in M$.
Moreover, Proposition 2 implies that $N_{\Omega}=\partial\delta_{\Omega}$.
Therefore, by applying Theorems 10 and 15 with $X=\partial_{2}F(p,\cdot)$ we
obtain the following theorem. ∎

###  4.3  Inexact proximal point method for nonlinear optimization problem

In this section, we apply the results of the previous section to obtain an
inexact proximal point method for the nonlinear optimization problem in the
form

$\min~{}f(p),\qquad\quad~{}p\in\left\\{p\in M\mathrel{\mathop{\mathchar
58\relax}}~{}g(p)\leq 0,~{}h(p)=0\right\\},$ (28)

where $M$ is a Hadamard manifol, the objective function
$f\mathrel{\mathop{\mathchar 58\relax}}M\rightarrow\mathbb{R}$ and the
constraint functions $g=(g_{1},\ldots,g_{m})\mathrel{\mathop{\mathchar
58\relax}}M\rightarrow\mathbb{R}^{m}$ and
$h=(h_{1},\ldots,h_{\ell})\mathrel{\mathop{\mathchar
58\relax}}M\rightarrow\mathbb{R}^{\ell}$ are assumed to be continuously
differentiable and convex. In order to state the problem (28) as the
variational inequality problem in (4), we first recall the first-order
necessary optimality conditions in Karush-Kuhn-Tucker (KKT) form. It is worth
noting that recently the KKT conditions were addressed in [9]. Let ${\cal
L}\mathrel{\mathop{\mathchar
58\relax}}M\times\mathbb{R}_{+}^{m}\times\mathbb{R}^{\ell}\to\mathbb{R}$ be
the Lagrangian associated with (28) defined by

${\cal L}(p,\mu,\lambda)\mathrel{\mathop{\mathchar
58\relax}}=f(p)+\sum_{i=1}^{m}\mu_{i}g_{i}(p)+\sum_{j=1}^{\ell}\lambda_{j}h_{j}(p).$
(29)

Since the functions $f$, $g$ and $h$ are continuously differentiable, it
follows from (29) that KKT conditions are given by

$\displaystyle\operatorname{grad}_{p}{\cal
L}(p,\mu,\lambda)\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{grad}f(p)+\sum_{i=1}^{m}\mu_{i}\operatorname{grad}g_{i}(p)+\sum_{j=1}^{\ell}\lambda_{j}\operatorname{grad}h_{j}(p)$
$\displaystyle=0$ (30) $\displaystyle g_{i}(p)$ $\displaystyle\leq 0,\quad
i=1,\ldots m$ (31) $\displaystyle h_{j}(p)$ $\displaystyle=0,\quad
j=1,\ldots\ell$ (32) $\displaystyle\mu_{i}g_{i}(p)$ $\displaystyle=0,\quad
i=1,\ldots$ (33) $\displaystyle\mu_{i}$ $\displaystyle\geq 0,\quad i=1,\ldots
m$ (34)

Let ${\widetilde{M}}\mathrel{\mathop{\mathchar
58\relax}}=M\times\mathbb{R}^{m}\times\mathbb{R}^{\ell}$ be the product
manifold with the induced product metric, for more details see [39]. Then, the
tangent plane at ${\tilde{p}}\mathrel{\mathop{\mathchar
58\relax}}=(p,\mu,\lambda)\in{\widetilde{M}}$ is
$T_{\tilde{p}}{\widetilde{M}}\mathrel{\mathop{\mathchar
58\relax}}=T_{p}M\times\mathbb{R}^{m}\times\mathbb{R}^{\ell}$ and the
exponential map ${\widetilde{\rm exp}}_{\tilde{p}}\mathrel{\mathop{\mathchar
58\relax}}T_{\tilde{p}}{\widetilde{M}}\to{\widetilde{M}}$ is given by

${\widetilde{\rm exp}}_{\tilde{p}}{\tilde{w}}\mathrel{\mathop{\mathchar
58\relax}}=\left(\exp_{p}{w},~{}\mu+u,~{}\lambda+v\right),\qquad\quad{\tilde{w}}\mathrel{\mathop{\mathchar
58\relax}}=(w,u,v)\in T_{{\tilde{p}}}{\widetilde{M}}.$

where $\exp_{p}$ is the exponential map of $M$ a $p\in M$. Consequently, the
inverse of ${\widetilde{\rm exp}}_{\tilde{p}}$ is given by

${\widetilde{\rm exp}}_{\tilde{p}}^{-1}{\tilde{q}}\mathrel{\mathop{\mathchar
58\relax}}=\left(\exp_{p}^{-1}{q},~{}{\nu}-\mu,~{}{\zeta}-\lambda\right),\qquad\quad{\tilde{q}}\mathrel{\mathop{\mathchar
58\relax}}=({q},{\nu},{\zeta})\in{\widetilde{M}}.$

Let ${\tilde{\Omega}}\mathrel{\mathop{\mathchar
58\relax}}=M\times\mathbb{R}_{+}^{m}\times\mathbb{R}^{\ell}\subset{\widetilde{M}}$,
which is convex set in ${\widetilde{M}}$. In this case, the normal cone of the
set ${\tilde{\Omega}}$ at a point ${\tilde{p}}\in\Omega$ is given by

$N_{\tilde{\Omega}}({\tilde{p}})\mathrel{\mathop{\mathchar
58\relax}}=\left\\{{\tilde{w}}\in
T_{\tilde{p}}{\widetilde{M}}\mathrel{\mathop{\mathchar
58\relax}}~{}\left\langle{\tilde{w}},{\widetilde{\rm
exp}}_{\tilde{p}}^{-1}{\tilde{q}}\right\rangle\leq
0,~{}{\tilde{q}}\in\Omega\right\\}.$

Since the functions $f$, $g$ and $h$ are continuously differentiable and
convex, the definition (29) implies that the vector field
$X\mathrel{\mathop{\mathchar
58\relax}}M\times\mathbb{R}_{+}^{m}\times\mathbb{R}^{\ell}\to
TM\times\mathbb{R}^{m}\times\mathbb{R}^{\ell}$ defined by

$X({\tilde{p}})\mathrel{\mathop{\mathchar
58\relax}}=\begin{bmatrix}\operatorname{grad}_{p}{\cal L}({\tilde{p}})\\\
-g(p)\\\ h(p)\end{bmatrix}\in
T_{\tilde{p}}{\widetilde{M}},\qquad{\tilde{p}}\mathrel{\mathop{\mathchar
58\relax}}=(p,\mu,\lambda)\in{\widetilde{M}}.$ (35)

is maximal monotone. Moreover, using the definition of normal cone of the set
${\tilde{\Omega}}$ we conclude that (30)-(34) is equivalent to

$0\in
X({\tilde{p}})+N_{\tilde{\Omega}}({\tilde{p}}),\qquad{\tilde{p}}\mathrel{\mathop{\mathchar
58\relax}}=(p,\mu,\lambda)\in{\widetilde{M}}.$ (36)

To the definition of enlargement of $X$, consider the parallel transport on
${\widetilde{M}}$ from ${\tilde{p}}$ to ${\tilde{q}}$ as being

${\tilde{P}}_{{\tilde{p}}{\tilde{q}}}{\tilde{w}}\mathrel{\mathop{\mathchar
58\relax}}=\left({P}_{pq}{w},u,v\right),\qquad{\tilde{w}}\mathrel{\mathop{\mathchar
58\relax}}=(w,u,v)\in T_{{\tilde{p}}}{\widetilde{M}}.$

where ${P}_{pq}$ is the parallel transport on ${M}$ from ${p}$ to ${q}$. Then,
the enlargement of vector field $X^{\epsilon}\mathrel{\mathop{\mathchar
58\relax}}M\rightrightarrows TM$ associated to $X$ is defined by

$X^{\epsilon}({\tilde{p}})\mathrel{\mathop{\mathchar
58\relax}}=\left\\{{\tilde{w}}\mathrel{\mathop{\mathchar 58\relax}}=(w,u,v)\in
T_{{\tilde{p}}}{\widetilde{M}}\mathrel{\mathop{\mathchar
58\relax}}~{}\left\langle{\tilde{P}}_{{\tilde{q}}{\tilde{p}}}^{-1}{\tilde{w}}-{\tilde{z}},\widetilde{\rm
exp}_{\tilde{q}}^{-1}{\tilde{p}}\right\rangle\geq-\epsilon,~{}{\tilde{q}}\in
M,~{}{\tilde{z}}\in X({\tilde{q}})\right\\},$ (37)

for all ${\tilde{p}}\mathrel{\mathop{\mathchar
58\relax}}=(p,\mu,\lambda)\in{\widetilde{M}}$. Finally, taking three exogenous
sequences of nonnegative real numbers, $\\{\lambda_{k}\\}$,
$\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$ satisfying (5), the inexact
proximal point method for solving (28)  is introduced as follows:

######  Algorithm 5.

Inexact proximal point method for nonlinear optimization problem

0.

Take $\\{\lambda_{k}\\}$, $\\{\epsilon_{k}\\}$ and $\\{\sigma_{k}\\}$
satisfying (5), ${\tilde{p}}^{0}\in{\tilde{\Omega}}$ and $\sigma>1$. Set
$k=1$.

1.

Given ${\tilde{p}}^{k}\in{\tilde{\Omega}}$, compute ${\tilde{p}}^{k+1}\in{C}$
and $e^{k}\in T_{{\tilde{p}}^{k}}M$ such that

${\tilde{e}}^{k+1}\in
X^{\epsilon}({\tilde{p}}^{k+1})+N_{\tilde{\Omega}}({\tilde{p}}^{k+1})-\lambda_{k}{\widetilde{\rm
exp}}_{{\tilde{p}}^{k+1}}^{-1}{\tilde{p}}^{k},$ (38)
$\|{\tilde{e}}^{k+1}\|\leq\sigma_{k}d({\tilde{p}}^{k},{\tilde{p}}^{k+1}).$
(39)

2.

If ${\tilde{p}}^{k-1}={\tilde{p}}^{k}$ or ${\tilde{p}}^{k}\in$, then stop;
otherwise, set $k\leftarrow k+1$, and go to step 1.

First note that $X$ defined in (35) satisfies A1 and A2. Moreover, under
suitable constraint qualifications $X$ also satisfies A2, see [9, Theorem 11].
Therefore, we can apply Theorem 15 to obtain the following result.

######  Theorem 18.

The sequence $\\{p^{k}\\}$ generated by (38) and (39) is well defined and
converges to a point $p^{*}\in S(f,\,\Omega)$.

##  5 Conclusions

In this paper we combine the ideas in [38] and [11] to introduce an inexact
proximal point method for solving variational inequality problems on Hadamard
manifolds. As a proposal of future work it would be interesting to study local
version of our results on arbitrary Riemannian manifolds. Note that for this
purpose, a local version of the formula (1) will be required.

## References

  * [1] R. L. Adler, J.-P. Dedieu, J. Y. Margulies, M. Martens, and M. Shub.  Newton’s method on Riemannian manifolds and a geometric model for the human spine.  IMA J. Numer. Anal., 22(3):359–390, 2002.
  * [2] P. Ahmadi and H. Khatibzadeh.  On the convergence of inexact proximal point algorithm on Hadamard manifolds.  Taiwanese J. Math., 18(2):419–433, 2014.
  * [3] M. Bačák.  The proximal point algorithm in metric spaces.  Israel J. Math., 194(2):689–701, 2013.
  * [4] E. E. A. Batista, G. C. Bento, and O. P. Ferreira.  An existence result for the generalized vector equilibrium problem on Hadamard manifolds.  J. Optim. Theory Appl., 167(2):550–557, 2015.
  * [5] E. E. A. Batista, G. d. C. Bento, and O. P. Ferreira.  Enlargement of monotone vector fields and an inexact proximal point method for variational inequalities in Hadamard manifolds.  J. Optim. Theory Appl., 170(3):916–931, 2016.
  * [6] G. C. Bento, J. X. Cruz Neto, and P. R. Oliveira.  A new approach to the proximal point method: convergence on general Riemannian manifolds.  J. Optim. Theory Appl., 168(3):743–755, 2016.
  * [7] G. C. Bento, O. P. Ferreira, and P. R. Oliveira.  Proximal point method for a special class of nonconvex functions on Hadamard manifolds.  Optimization, 64(2):289–319, 2015.
  * [8] G. C. Bento and J. G. Melo.  Subgradient method for convex feasibility on Riemannian manifolds.  J. Optim. Theory Appl., 152(3):773–785, 2012.
  * [9] R. Bergmann and R. Herzog.  Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds.  SIAM J. Optim., 29(4):2423–2444, 2019.
  * [10] R. S. Burachik and A. N. Iusem.  Set-valued mappings and enlargements of monotone operators, volume 8 of Springer Optimization and Its Applications.  Springer, New York, 2008.
  * [11] R. S. Burachik, A. N. Iusem, and B. F. Svaiter.  Enlargement of monotone operators with applications to variational inequalities.  Set-Valued Anal., 5(2):159–180, 1997.
  * [12] V. Colao, G. López, G. Marino, and V. Martín-Márquez.  Equilibrium problems in Hadamard manifolds.  J. Math. Anal. Appl., 388(1):61–77, 2012.
  * [13] Q. Cui, L. Deng, and X. Zhang.  Second order optimality conditions for optimal control problems on Riemannian manifolds.  ESAIM Control Optim. Calc. Var., 25:Paper No. 35, 48, 2019.
  * [14] J. X. da Cruz Neto, O. P. Ferreira, and L. R. Lucambio Pérez.  Monotone point-to-set vector fields.  Balkan J. Geom. Appl., 5(1):69–79, 2000.  Dedicated to Professor Constantin Udrişte.
  * [15] J. X. Da Cruz Neto, O. P. Ferreira, L. R. L. Pérez, and S. Z. Németh.  Convex- and monotone-transformable mathematical programming problems and a proximal-like point method.  J. Global Optim., 35(1):53–69, 2006.
  * [16] J. X. Da Cruz Neto, O. P. Ferreira, L. R. L. Pérez, and S. Z. Németh.  Convex- and monotone-transformable mathematical programming problems and a proximal-like point method.  J. Global Optim., 35(1):53–69, 2006.
  * [17] M. P. do Carmo.  Riemannian geometry.  Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1992.  Translated from the second Portuguese edition by Francis Flaherty.
  * [18] A. Edelman, T. A. Arias, and S. T. Smith.  The geometry of algorithms with orthogonality constraints.  SIAM J. Matrix Anal. Appl., 20(2):303–353, 1999.
  * [19] C.-j. Fang and S.-l. Chen.  A projection algorithm for set-valued variational inequalities on Hadamard manifolds.  Optim. Lett., 9(4):779–794, 2015.
  * [20] O. P. Ferreira, M. S. Louzeiro, and L. F. Prudente.  Gradient method for optimization on Riemannian manifolds with lower bounded curvature.  SIAM J. Optim., 29(4):2517–2541, 2019.
  * [21] O. P. Ferreira and P. R. Oliveira.  Proximal point algorithm on Riemannian manifolds.  Optimization, 51(2):257–270, 2002.
  * [22] A. N. Iusem, G. Kassay, and W. Sosa.  On certain conditions for the existence of solutions of equilibrium problems.  Math. Program., 116(1-2, Ser. B):259–273, 2009.
  * [23] A. N. Iusem and W. Sosa.  New existence results for equilibrium problems.  Nonlinear Anal., 52(2):621–635, 2003.
  * [24] A. N. Iusem and W. Sosa.  On the proximal point method for equilibrium problems in Hilbert spaces.  Optimization, 59(8):1259–1274, 2010.
  * [25] B. Jeuris, R. Vandebril, and B. Vandereycken.  A survey and comparison of contemporary algorithms for computing the matrix geometric mean.  Electron. Trans. Numer. Anal., 39:379–402, 2012.
  * [26] N. Karmarkar.  Riemannian geometry underlying interior-point methods for linear programming.  In Mathematical developments arising from linear programming (Brunswick, ME, 1988), volume 114 of Contemp. Math., pages 51–75. Amer. Math. Soc., Providence, RI, 1990.
  * [27] I. Konnov.  Generalized monotone equilibrium problems and variational inequalities.  In Handbook of generalized convexity and generalized monotonicity, volume 76 of Nonconvex Optim. Appl., pages 559–618. Springer, New York, 2005.
  * [28] C. Li, G. López, and V. Martín-Márquez.  Monotone vector fields and the proximal point algorithm on Hadamard manifolds.  J. Lond. Math. Soc. (2), 79(3):663–683, 2009.
  * [29] C. Li and J.-C. Yao.  Variational inequalities for set-valued vector fields on Riemannian manifolds: convexity of the solution set and the proximal point algorithm.  SIAM J. Control Optim., 50(4):2486–2514, 2012.
  * [30] S.-L. Li, C. Li, Y.-C. Liou, and J.-C. Yao.  Existence of solutions for variational inequalities on Riemannian manifolds.  Nonlinear Anal., 71(11):5695–5706, 2009.
  * [31] D. G. Luenberger.  The gradient projection method along geodesics.  Management Sci., 18:620–631, 1972.
  * [32] S. Z. Németh.  Monotone vector fields.  Publ. Math. Debrecen, 54(3-4):437–449, 1999.
  * [33] S. Z. Németh.  Variational inequalities on Hadamard manifolds.  Nonlinear Anal., 52(5):1491–1498, 2003.
  * [34] Y. E. Nesterov and M. J. Todd.  On the Riemannian geometry defined by self-concordant barriers and interior-point methods.  Found. Comput. Math., 2(4):333–361, 2002.
  * [35] E. A. Papa Quiroz and P. R. Oliveira.  Full convergence of the proximal point method for quasiconvex functions on Hadamard manifolds.  ESAIM Control Optim. Calc. Var., 18(2):483–500, 2012.
  * [36] B. T. Polyak.  Introduction to optimization.  Translations Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York, 1987.  Translated from the Russian, With a foreword by Dimitri P. Bertsekas.
  * [37] T. Rapcsák.  Smooth nonlinear optimization in $\mathbb{R}^{n}$, volume 19 of Nonconvex Optimization and its Applications.  Kluwer Academic Publishers, Dordrecht, 1997.
  * [38] R. T. Rockafellar.  Monotone operators and the proximal point algorithm.  SIAM J. Control Optim., 14(5):877–898, 1976.
  * [39] T. Sakai.  Riemannian geometry, volume 149 of Translations of Mathematical Monographs.  American Mathematical Society, Providence, RI, 1996.  Translated from the 1992 Japanese original by the author.
  * [40] S. T. Smith.  Optimization techniques on Riemannian manifolds.  In Hamiltonian and gradient flows, algorithms and control, volume 3 of Fields Inst. Commun., pages 113–136. Amer. Math. Soc., Providence, RI, 1994.
  * [41] S. Sra and R. Hosseini.  Conic geometric optimization on the manifold of positive definite matrices.  SIAM J. Optim., 25(1):713–739, 2015.
  * [42] G.-j. Tang and N.-j. Huang.  An inexact proximal point algorithm for maximal monotone vector fields on Hadamard manifolds.  Oper. Res. Lett., 41(6):586–591, 2013.
  * [43] G.-j. Tang, X. Wang, and H.-w. Liu.  A projection-type method for variational inequalities on Hadamard manifolds and verification of solution existence.  Optimization, 64(5):1081–1096, 2015.
  * [44] G.-j. Tang, L.-w. Zhou, and N.-j. Huang.  The proximal point algorithm for pseudomonotone variational inequalities on Hadamard manifolds.  Optim. Lett., 7(4):779–790, 2013.
  * [45] C. Udrişte.  Convex functions and optimization methods on Riemannian manifolds, volume 297 of Mathematics and its Applications.  Kluwer Academic Publishers Group, Dordrecht, 1994.
  * [46] J. Wang, C. Li, G. Lopez, and J.-C. Yao.  Convergence analysis of inexact proximal point algorithms on Hadamard manifolds.  J. Global Optim., 61(3):553–573, 2015.
  * [47] J. Wang, C. Li, G. Lopez, and J.-C. Yao.  Proximal point algorithms on Hadamard manifolds: linear convergence and finite termination.  SIAM J. Optim., 26(4):2696–2729, 2016.
  * [48] X. Wang, G. López, C. Li, and J.-C. Yao.  Equilibrium problems on Riemannian manifolds with applications.  J. Math. Anal. Appl., 473(2):866–891, 2019.
  * [49] H. Zhang, S. J. Reddi, and S. Sra.  Fast stochastic optimization on Riemannian manifolds.  ArXiv e-prints, pages 1–17, 2016.
  * [50] L.-w. Zhou and N.-j. Huang.  A revision on geodesic pseudo-convex combination and Knaster-Kuratowski-Mazurkiewicz theorem on Hadamard manifolds.  J. Optim. Theory Appl., 182(3):1186–1198, 2019.


# Explainability of Deep Learning models for Urban Space perception

###### Abstract

Deep learning based computer vision models are increasingly used by urban
planners to support decision making for shaping urban environments. Such
models predict how people perceive the urban environment quality in terms of
e.g. its safety or beauty. However, the blackbox nature of deep learning
models hampers urban planners to understand what landscape objects contribute
to a particularly high quality or low quality urban space perception. This
study investigates how computer vision models can be used to extract relevant
policy information about peoples’ perception of the urban space. To do so, we
train two widely used computer vision architectures; a Convolutional Neural
Network and a transformer, and apply GradCAM -a well-known ex-post explainable
AI technique- to highlight the image regions important for the model’s
prediction. Using these GradCAM visualizations, we manually annotate the
objects relevant to the models’ perception predictions. As a result, we are
able to discover new objects that are not represented in present object
detection models used for annotation in previous studies. Moreover, our
methodological results suggest that transformer architectures are better
suited to be used in combination with GradCAM techniques. Code is available on
Github111https://github.com/rsangers/explainable_perception.

###### Index Terms:

Explainability, Deep Learning, Convolutional Neural Network, Transformer,
Urban Space perception

##  I Introduction

In urban planning, computer vision models are increasingly being used to
create maps of cities showing what areas are perceived as being safe/unsafe,
beautiful/ugly, and lively/boring, see e.g. [5, 12]. Such computer vision
models are trained on survey data in which respondents are asked to score the
safety and beauty level for a series of streetview images presented to them.
The results of these studies provide urban planners and policy makers with
important insights about areas that need policy attention, e.g. because
perceived safety levels are deemed too low.

Current computer vision models to predict urban space perceptions, however,
provide little guidance for urban planners to improve the urban environment.
In particular, due to the blackbox nature of deep learning based computer
vision models, such models do not directly reveal what the relevant landscape
objects are, based on which the model geared its predictions. In light of
this, some recent studies, e.g. [11], use computer vision models to extract
objects to use these in turn in readily (ex-ante) explainable regression
models. However, this leads to a constrained abstraction of the image as it
does not include all objects present. Important objects might therefore go
unnoticed and the predictive performance might degrade.

It is increasingly realised that being able to explain and interpret the inner
workings of the models is indispensable [13]. Two types of explainability are
distinguished in the literature: ex-ante (’before the event’) and ex-post
(’after the event’) explainability [16]. Ex-ante explainability aims to
specifically incorporate explainable modules into the model; ex-post
explainability aims to interpret models without constraining their design. An
important drawback of the former over the latter is that the explainable
modules are often fairly constrained representations, leading to high model
biases and thereby degrading the model performance[18].

This study aims to shed light on how computer vision models can be used to
extract relevant policy information about peoples’ perception of the urban
space, without relying on ex-ante explainability. To do so, we train two
widely used computer vision architectures; a ResNet50 Convolutional Neural
Network [8] (CNN) and a Data Efficient Image Transformer (DeiT) [17]. As a
data set we use a widely used used urban perception set [5]. For
explainability, we apply a GradCAM [14] -a successful ex-post explainable AI
technique- to highlight what part of an image is important for the model’s
prediction. GradCAM exploits the gradients of the last convolutional layer to
create heatmaps of image pixels that were the most important for its
prediction [14]. Using the heatmaps provided by the GradCAM, we manually
annotate and keep score of the objects relevant to the models’ safety and
beauty predictions for the 50 highest and lowest scoring images.

The first contribution of our paper is that we extract landscape objects
explaining urban perceptions using an ex-post explainability technique,
without relying on additional object detection or segmentation modules. To the
best of the authors’ knowledge, this not been tried before. Hitherto studies
using computer vision to understand urban space perceptions use ex-ante
explainability techniques either in their model design [11][20][21] or in
their analysis [15]. As our approach does not rely on object detection models,
we are able to discover new landscape objects that are not represented in
present object detection models. This will thereby give urban planners a more
complete overview of the landscape objects that affect perception.

The second contribution of this study is that we test and compare the
suitability of two widely used computer vision architectures to explain urban
perceptions. The first architecture we study is a conventional Convolutional
Neural Network (CNN)[8] and the second computer vision architecture we study
is the transformer[4]. Transformers are based on self-attention instead of
convolutions. A series of recent papers suggest that CNN models over rely on
local features [2], such as textures [6], while transformers do better in
capturing global relationships. By assessing both architectures vis-a-vis we
hope to shed light on which architecture is best suited for predicting and
explaining urban space perception.

##  II Methods

###  II-A Place Pulse 2.0 dataset and preprocessing

For the analyses of this study we use the Place Pulse 2.0 dataset [5]. The
Place Pulse dataset consists of more than 1.5 million pairwise comparisons for
over 100,000 images in 56 cities, collected using the Google Street View Image
API. The data are collected using crowd-sourcing. Each participant is shown a
pair of images and asked to choose which one of the two images corresponds
most with a queried perceptual attribute, which could be safety, liveliness,
wealthiness, boringness, depressiveness and beauty (Figure 1). In this study,
we particularly focus on three the perceptual attributes, namely safety,
wealthiness and depressiveness.

Figure 1: An example of the urban space perception assessment task.
Participants are given pairwise image comparisons for a perceptual attribute,
such as safety, wealthiness and depressiveness.

###  II-B Problem formulation

The problem of predicting a perceptual attribute is mathematically defined as
follows: we have an image set $I=\\{x_{i}\\}^{m}_{i=1}\in\mathbb{R}^{n}$
containing $m$ images, and a set consisting of $N$ pairwise comparison tuples
$P=\\{(i_{k},j_{k},y_{k})\\}^{N}_{k=1}$, $i,j\in\\{1,...,m\\}$,
$y\in\\{-1,+1\\}$, where -1 means that image $j_{k}$ is preferred, while +1
denotes that image $i_{k}$ is preferred. We want the model to predict an
attribute score $f(x_{i})\in\mathbb{R}$ for an image $x_{i}$ such that the
amount of correct image comparisons is maximized, formulated as

$y\cdot(f(x_{i})-f(x_{j}))>0,\quad\forall{(i,j,y)\in P}.$ (1)

To be able to approximate a solution for this problem, we need a loss function
that punishes the model whenever an wrong prediction is made. Therefore, in
line with the work by Dubey [5] and Chapelle [3] we use a ranking loss.
Ranking loss penalizes incorrect comparison scores by their difference,
defined as:

$L(x_{i},x_{j},y)=\max(0,-y\cdot(f(x_{i})-f(x_{j}))).$ (2)

###  II-C Explainability study

Training details. We compare two current state-of-the-art networks, which are
the ResNet50 [7] and the Data-efficient image Transformer (DeiT) [17]. To keep
training time within feasible bounds, ImageNet-pretrained versions of these
networks were used, after which a transfer learning procedure was applied with
a small learning rate ($\mu=10^{-3}$) for 20 epochs on the Place Pulse 2.0
dataset.

Explainability models To study the ability of these computer vision
architectures to explain urban perceptions, we exploit the heatmaps of GradCAM
[14]. We also tested other explainable AI techniques, including: GradCAM[14],
Eigen-CAM[9], Ablation-CAM[10] and Attention Rollout[1] (only for the
transformer model). Based on initial results, we choose GradCAM for further
analysis as it empirically showed -for both architectures- to give rise to
highlighted regions that most closely overlap with the objects.

Annotating the heatmaps Using the heatmaps provided by the GradCAM, we
manually annotate and keep score of the objects relevant to the models’
safety, wealthy and depression predictions for the 50 highest and lowest
scoring images. We do this without a predefined list of annotatable objects,
as to not limit ourselves to the currently know object relations. Moreover, we
only count an object once per image.

##  III Experiments and discussion

###  III-A Object analysis

Table I and II show the main results of our study. They list the objects
identified as being important for the models’ predictions for the CNN based
model and the Transformer respectively. Below we highlight the most important
results for the CNN model and the transformer:

CNN model

  * •

Overhanging cables show a strong association with a high perception of
depressiveness and a low perception of safety and wealthiness.

  * •

Trees are associated with a low perception of depressiveness and a high
perception of safety and wealthiness.

  * •

Building elements, such as roofs, blinds and corrugated sheets are
occasionally found to be of importance for the CNN model’s predictions. This
is noteworthy as most previous studies consider buildings as a whole.

Transformer model

  * •

Tunnel roofs are often associated with a high perception of depressiveness and
a low perception of safety.

  * •

Regarding perceived wealthiness, ’air’ is found to be of particular importance
for the model’s predictions.

  * •

Trees are associated with a high perception of safety and a low perception of
depressiveness.

TABLE I: Annotation of the objects highlighted by GradCAM in the 50 highest
and lowest ranking images of each category for the CNN model. The most
interesting correlations, such as the importance of power cables and
vegetation, are shown in bold. The signs + and - denote images with a
respectively high or low score for that perceptual attribute.

Depressing | Safety | Wealthy
---|---|---
+ | - | + | - | + | -
Power cable | 18 | Tree | 16 | Tree | 30 | Cable | 21 | Grass | 14 | Roof | 17
Blinds | 4 | Road | 9 | Car | 7 | Roof | 17 | Road | 14 | Sidewalk | 10
Corrugated sheets | 4 | Car | 8 | Sidewalk | 4 | Wall | 7 | Tree | 10 | Cable | 10
Window | 2 | Bush | 3 | Roof | 4 | Sidewalk | 2 | Fence | 8 | Wall | 7
Gutter | 2 | Grass | 3 | Road | 3 | Car | 2 | Bush | 6 | Tree | 4
Curb | 2 | Sidewalk | 2 | Grass | 3 | Door | 2 | Car | 2 | Car | 4
Sidewalk | 2 | Stairs | 2 | Bush | 3 | Flat | 1 | Logo | 1 | Fence | 3
Fence | 2 |  |  |  |  | Bush | 1 | Flat | 1 | Grass | 2
Car | 1 |  |  |  |  |  |  |  |  | Bush | 1
Clouds | 1 |  |  |  |  |  |  |  |  |  |
Pole | 1 |  |  |  |  |  |  |  |  |  |
Door | 1 |  |  |  |  |  |  |  |  |  |
Rails | 1 |  |  |  |  |  |  |  |  |  |
Bus stop | 1 |  |  |  |  |  |  |  |  |  |
Overpass | 1 |  |  |  |  |  |  |  |  |  |

TABLE II: Annotation of the objects highlighted by GradCAM in the 50 highest
and lowest ranking images of each category for the transformer model. The
signs + and - denote images with a respectively high or low score for that
perceptual attribute. Interestingly, tunnel roofs appear to have a high
influence on the decision making of the model for depressiveness and safety,
while wealthiness is highly determined by the sky.

Depressing | Safety | Wealthy
---|---|---
+ | - | + | - | + | -
Tunnel roof | 20 | Tree | 42 | Tree | 41 | Tree | 18 | Sky | 49 | Sky | 21
Bush | 5 | Road | 6 | Car | 18 | Tunnel roof | 16 | Road | 8 | Sidewalk | 10
Road | 4 | Bush | 5 | Bush | 8 | Bush | 4 | Sidewalk | 4 | Road | 5
Window | 3 | Car | 4 | Road | 6 | Road | 3 | Car | 1 | Wall | 3
Tree | 3 | Viaduct | 3 | Hedge | 4 | Car | 3 |  |  | Window | 2
Water | 2 | Sidewalk | 2 | Rails | 2 | Grass | 2 |  |  | Lantern | 1
Wall | 2 | Gate | 1 | Flat | 2 | Gate | 2 |  |  |  |
Car | 1 | Grass | 1 | Trash container | 2 | Window | 1 |  |  |  |
Gate | 1 |  |  | Grass | 2 |  |  |  |  |  |
|  |  |  | Sign | 1 |  |  |  |  |  |
|  |  |  | Shop | 1 |  |  |  |  |  |
|  |  |  | Window | 1 |  |  |  |  |  |

Figure 2: Example images of the three most important objects for each category
for the CNN model. The highlighted areas for this model are often small and
not well overlapping with objects. Figure 3: Example images of the three most
important objects for each category for the transformer model. The important
regions for this model generally take up a large part of the image, and
overlap relatively well with the objects in an image.

###  III-B Explainability patterns

Figures 2 and 3 show examples of images in which the three most often
encountered objects relevant for the models’ prediction are present. Figure 2
shows images with GradCAM heatmap for the CNN model; Figure 3 shows the same
for the transformer. Comparing the GradCAM overlays across the two models,
reveals that the sizes of the highlighted regions in the images are
dissimilar. It can be seen that CNN model often attributes importance to a few
relatively small areas in the image, while the transformer often attributes
importance to a large area. Moreover, the highlighted areas of the transformer
model often closely overlapped with objects present in the image, while this
is much less the case for the CNN model. This finding is in line with recent
literature, e.g. [2][6].

###  III-C Discussion

Our methodology also has some disadvantages. Firstly, it is important to keep
in mind that results presented in this paper depend on a manual analysis of
only 100 images per perceptual attribute and only one annotator. Especially
because the explainability of images often comprise highlighted regions that
do not always clearly overlap with objects, possible biases in the analysis
may be present. To establish our findings more firmly, a larger scale study
with multiple annotators is recommended.

Secondly, our substantive findings may be biased towards objects that are
present in street imagery, such as cars, roads and trees. Objects that often
appear in street imagery have an a priori higher probability to be annotated
and identified as important for the model’s perception prediction than objects
that appear less frequently. Hence, objects that are important for urban
perceptions, but are rare to find in street imagery may go undetected in our
analysis.

Moreover, our research may not generalise towards other models or
applications. In this study we considered only two computer vision models:
ResNet50 and DeiT. As such, we need to be cautious to draw strong conclusions
regarding the differences between the two model architectures. Noteworthy in
this regard is also the work of Shi et al.[15] and Viering et al. [19]. Shi et
al. show that different architectures may generate different explanations.
Viering et al. even show that it is possible to manipulate this sort of
computer vision models in such a way that they generate any desirable
explainability output generated by GradCAM, without degrading the accuracy of
the model.

Finally, the landscape objects and attributes that are important for a
computer vision model to predict urban space perception, do not necessarily
coincide with the objects, attributes and what more, that humans sense to
perceive their surroundings. Ultimately, our models only establish
associations between objects visible in images and perception scores, they do
not establish causality. As such, one should act cautious when using results
of our, and similar studies, for urban planning decisions. For instance, there
may be objects important to human perceptions that go undetected in street
imagery but happen to correlate with objects that are detected. In that case,
the policy information extracted from the model may be misguided. More
concretely, the presence of small birds, like tomtits, may positively
associate with human’s perception of wealthiness of a place, but they may go
unnoticed due to their small size in computer vision based studies, like ours.
In case tomtits avoid open urban spaces, a computer vision model will
(correctly) learn that open urban spaces are associated with a low perception
of wealthiness. But, reducing the number of open urban space, may not be
sufficient to improve perceived wealthiness, without policies to support bird
wildlife.

##  IV Conclusion

This study has shed light on how computer vision models can be used to extract
relevant policy information about peoples’ perception of the urban space,
without relying on ex-ante explainability. To gain a better understanding of
the objects that are associated with human’s perception of the urban space,
computer vision models were trained to predict perception based on street
imagery. By subsequently analyzing the decision making of these models using
GradCAM, we have been able to list the objects that are the most important for
the predictions of perceived safety, wealthiness and depressiveness. Some of
the discovered objects are well known and reported in earlier studies, such as
trees and cars, while other objects are new, such as power cables, blinds and
corrugated sheets. The fact that new objects have been detected suggests that
our approach can be useful for future studies with a similar substantive
objective.

In this study we have considered two different computer vision architectures:
a CNN and a transformer. We find that objects that are important for the
models’ predictions are different. In particular, the highlighted areas by the
GradCAM turned out to be better interpretable for the transformer than for the
CNN model, The highlighted regions for the transformer are often larger and
better shaped around visible objects. We believe further research is needed to
more deeply understand the differences between the explainability of the two
studies computer vision architectures. Relatedly, we believe it would be
beneficial to have human participants (as opposed to the machine learning
researcher) assess the degree of explainability provided by CNN and
transformer models.

## Acknowledgement

This work is supported by the TU Delft AI Labs programme. We would like to
thank Tomás Ramírez and Hans Löbel for sharing their code and data with us.

## References

  * [1] Samira Abnar and Willem Zuidema.  Quantifying attention flow in transformers.  arXiv preprint arXiv:2005.00928, 2020.
  * [2] Wieland Brendel and Matthias Bethge.  Approximating cnns with bag-of-local-features models works surprisingly well on imagenet.  arXiv preprint arXiv:1904.00760, 2019.
  * [3] Olivier Chapelle and S Sathiya Keerthi.  Efficient algorithms for ranking with svms.  Information retrieval, 13(3):201–215, 2010.
  * [4] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [5] Abhimanyu Dubey, Nikhil Naik, Devi Parikh, Ramesh Raskar, and César A Hidalgo.  Deep learning the city: Quantifying urban perception at a global scale.  In European conference on computer vision, pages 196–212. Springer, 2016.
  * [6] Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Matthias Bethge, Felix A Wichmann, and Wieland Brendel.  Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness.  arXiv preprint arXiv:1811.12231, 2018.
  * [7] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [8] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [9] Mohammed Bany Muhammad and Mohammed Yeasin.  Eigen-cam: Visual explanations for deep convolutional neural networks.  SN Computer Science, 2(1):1–14, 2021.
  * [10] Harish Guruprasad Ramaswamy et al.  Ablation-cam: Visual explanations for deep convolutional network via gradient-free localization.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 983–991, 2020.
  * [11] Tomás Ramírez, Ricardo Hurtubia, Hans Lobel, and Tomás Rossetti.  Measuring heterogeneous perception of urban space with massive data and machine learning: An application to safety.  Landscape and Urban Planning, 208:104002, 2021.
  * [12] Tomás Rossetti, Hans Lobel, Víctor Rocco, and Ricardo Hurtubia.  Explaining subjective perceptions of public spaces as a function of the built environment: A massive data approach.  Landscape and urban planning, 181:169–178, 2019.
  * [13] Cynthia Rudin.  Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead.  Nature Machine Intelligence, 1(5):206–215, 2019.
  * [14] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra.  Grad-cam: Visual explanations from deep networks via gradient-based localization.  In Proceedings of the IEEE international conference on computer vision, pages 618–626, 2017.
  * [15] Xiangwei Shi, Seyran Khademi, and Jan van Gemert.  Deep visual city recognition visualization.  In CVPR Workshops, pages 57–62, 2019.
  * [16] Kacper Sokol and Peter Flach.  Explainability fact sheets: a framework for systematic assessment of explainable approaches.  In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 56–67, 2020.
  * [17] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou.  Training data-efficient image transformers & distillation through attention.  In International Conference on Machine Learning, pages 10347–10357. PMLR, 2021.
  * [18] Andrés Cádiz Vidal.  Deep Neural Network Models with Explainable Components for Urban Space Perception.  PhD thesis, Pontificia Universidad Catolica de Chile (Chile), 2021.
  * [19] Tom Viering, Ziqi Wang, Marco Loog, and Elmar Eisemann.  How to manipulate cnns to make them lie: the gradcam case.  arXiv preprint arXiv:1907.10901, 2019.
  * [20] Yao Yao, Zhaotang Liang, Zehao Yuan, Penghua Liu, Yongpan Bie, Jinbao Zhang, Ruoyu Wang, Jiale Wang, and Qingfeng Guan.  A human-machine adversarial scoring framework for urban perception assessment using street-view images.  International Journal of Geographical Information Science, 33(12):2363–2384, 2019.
  * [21] Fan Zhang, Bolei Zhou, Liu Liu, Yu Liu, Helene H Fung, Hui Lin, and Carlo Ratti.  Measuring human perceptions of a large-scale urban region using machine learning.  Landscape and Urban Planning, 180:148–160, 2018.