**footnotetext: Equal contribution

# Robust Hypothesis Testing with Moment Constrained Uncertainty Sets

Akshayaa Magesh∗, Zhongchang Sun∗, Venugopal V. Veeravalli, Shaofeng Zou A.
Magesh and V.V. Veeravalli are with the University of Illinois at Urbana-
Champaign, IL, 61820 USA. (email<EMAIL_ADDRESS>vvv@illinois.edu). Z.
Sun and S. Zou are with the University at Buffalo, the State University of New
York, NY 14260, USA. (email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The problem of robust binary hypothesis testing is studied. Under both
hypotheses, the data-generating distributions are assumed to belong to
uncertainty sets constructed through moments; in particular, the sets contain
distributions whose moments are centered around the empirical moments obtained
from training observations. The goal is to design a test that performs well
under all distributions in the uncertainty sets, i.e., one that minimizes the
worst-case error probability over the uncertainty sets. In the finite-alphabet
case, the optimal test is obtained. In the infinite-alphabet case, a tractable
approximation to the worst-case error is derived that converges to the optimal
value. A test is further constructed to generalize to the entire alphabet. An
exponentially consistent test for testing batch samples is also proposed.
Numerical results are provided to demonstrate the performance of the proposed
robust tests.

##  I Introduction

Binary hypothesis testing is a fundamental problem in statistical decision-
making, in which the goal is to decide between two given hypotheses based on
observed data [1, 2, 3]. The two hypotheses $H_{0}$ and $H_{1}$ are generally
referred to as the null and the alternative hypotheses, respectively. The
likelihood ratio between the distributions under the two hypotheses can be
used to construct the optimal test under various settings. However, in
general, these distributions may be unknown and may need to be estimated from
historical data. Deviations from the true distributions can result in
significant performance degradation in likelihood ratio tests. The _robust_
hypothesis testing framework [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19] can be used to alleviate this performance degradation. In the
robust setting, it is assumed that the distributions belong to certain
uncertainty sets, and the goal is to build a detector that performs well under
all distributions in the uncertainty sets.

The uncertainty sets are generally constructed as a collection of
distributions that lie within the neighbourhood (with respect to some
discrepancy measure) of certain _nominal_ distributions. Huber [4] pioneered
the study of robust hypothesis testing; the uncertainty sets in [4] were
constructed as epsilon-contamination sets around the nominal distribution, and
a censored likelihood ratio test was proposed and proved to be minimax
optimal. Moment-constrained uncertainty sets under the Neyman-Pearson setting
were studied in [12]. The above works assume the nominal distributions to be
known or well-estimated from historical data. More recent works have studied
the problem of constructing uncertainty sets using a data-driven approach [18,
19], where the nominal distributions are the empirical distributions derived
from training observations. In [18], the Wasserstein distance was used to
construct uncertainty sets. The minimax problem in the Bayesian setting was
considered, and a computationally tractable reformulation and the optimal
robust test were characterized [18]. In [19] the maximum mean discrepancy
(MMD) distance was used to construct uncertainty sets. In the Bayesian
setting, a tractable approximation to the minimax problem was proposed, and in
the Neyman-Pearson setting, an asymptotically optimal test was proposed [19].

In this paper, we study the problem of robust hypothesis testing with moment-
constrained uncertainty sets, i.e., the sets contain distributions whose
moments are centered around the empirical moments. Mean constrained and
variance constrained uncertainty sets can be viewed as special cases of this
setting. Moment constrained sets are practical since it is generally
computationally easy to calculate empirical moments. Our focus is on the
minimax robust formulation in the Bayesian setting. First, we present the
results for the case when the distributions under the two hypotheses are
supported on a finite alphabet set $\mathcal{X}$. We then extend the study to
the case when $\mathcal{X}$ is infinite***The infinite-alphabet case includes
both the continuous-alphabet and discrete infinite-alphabet cases.. In the
infinite-alphabet case, we provide a tractable approximation of the worst-case
error that converges to the optimal value, and propose a test that generalizes
to the entire alphabet. We also propose an exponentially consistent test for
testing i.i.d. batch samples. Furthermore, we extend our results to the cases
where the uncertainty sets are constructed through matrix-valued moment
functions, and investigate a special case of the asymptotic Neyman-Pearson
setting and propose an asymptotic optimal test for this setting. We provide
numerical results to demonstrate the performance of our proposed algorithms.

##  II Problem Setup

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a compact set denoting the sample
space, where $d$ is the dimension of the data. Let $\mathcal{P}$ denote the
set of all Borel probability measures on $\mathcal{X}$. Let
$\mathcal{P}_{0},\mathcal{P}_{1}\subset\mathcal{P}$ denote the uncertainty
sets under the null and alternative hypotheses, respectively. We construct the
uncertainty sets using general moment constraints derived from observations
from the two hypotheses. Let
$\mathbf{\hat{x}_{0}}=(\hat{x}_{0,0},\ldots,\hat{x}_{0,m})$ and
$\mathbf{\hat{x}_{1}}=(\hat{x}_{1,0},\ldots,\hat{x}_{1,n})$ denote the
training sequences under the two hypotheses. Let
$\hat{Q}_{0}=\frac{1}{m}\sum_{j=1}^{m}\delta_{\hat{x}_{0,j}}$ and
$\hat{Q}_{1}=\frac{1}{n}\sum_{j=1}^{n}\delta_{\hat{x}_{1,j}}$ denote the
empirical distributions corresponding to the training observations, where
$\delta_{x}$ corresponds to the Dirac measure on $x$. We use the empirical
distributions as the nominal distributions in the construction of the
uncertainty sets. Let

$\psi_{k}:\mathcal{X}\to\mathbb{R};\;k\in[K]$

denote $K$ real-valued, continuous functions defined on the sample space,
where $[K]=\\{1,...,K\\}$. The uncertainty sets for $i=0,1$ are defined as
follows:

$\mathcal{P}_{i}^{\eta}=\left\\{P\in\mathcal{P}:\left|E_{P}[\psi_{k}]-E_{\hat{Q}_{i}}[{\psi_{k}}]\right|\leq\eta,\;\;k\in[K]\right\\},$
(1)

where $\eta$ is the pre-specified radius of the uncertainty sets, and
$E_{P}[\psi_{k}]$ denotes the expectation of the function $\psi_{k}$ under the
distribution $P$. It is assumed that the uncertainty sets do not overlap,
i.e.,

$\eta<\mathop{\max}\limits_{k\in[K]}\frac{\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|}{2}.$

Given a new sample $x\in\mathcal{X}$, the robust hypothesis problem is defined
as follows:

$\displaystyle\begin{split}&H_{0}:x\sim
P_{0},\;\;\;P_{0}\in\mathcal{P}^{\eta}_{0}\\\ &H_{1}:x\sim
P_{1},\;\;\;P_{1}\in\mathcal{P}^{\eta}_{1}.\end{split}$ (2)

A test $\phi:\mathcal{X}\rightarrow[0,1]$ accepts $H_{0}$ with probability
$1-\phi(x)$, and accepts $H_{1}$ with probability $\phi(x)$. In the Bayesian
setting with equal priors, the probability of error is given by:

$\displaystyle
P_{E}(\phi;P_{0},P_{1})\triangleq\frac{1}{2}E_{P_{0}}\big{[}\phi(x)\big{]}+\frac{1}{2}E_{P_{1}}\big{[}1-\phi(x)\big{]}.$
(3)

Note that the methods proposed in this paper and their analyses can be easily
extended to the setting with unequal priors, as explained in the following
section. The goal in the Bayesian setting is to solve

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}P_{E}(\phi;P_{0},P_{1}).$
(4)

In this paper, we assume that any distributions
$P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}$ admit
probability density functions (PDFs) $p_{0},p_{1}$, with respect to a common
reference measure $\mu$.

##  III Finite Alphabet: Optimal Test

An important result in arriving at a solution to the minimax robust hypothesis
testing problem involves interchanging the infimum and supremum in (4).

######  Theorem 1.

$\inf_{\phi}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}P_{E}(\phi;P_{0},P_{1})=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\inf_{\phi}P_{E}(\phi;P_{0},P_{1}).$
(5)

###### Proof.

The uncertainty sets $\mathcal{P}^{\eta}_{0}$ and $\mathcal{P}^{\eta}_{1}$ are
convex. Indeed, for some $\lambda\in(0,1)$, $P,Q\in\mathcal{P}^{\eta}_{i}$ for
$i=0,1$, and $k=1,\ldots,K$, we have that

$\begin{split}\left|E_{\lambda
P+(1-\lambda)Q}\left[\psi_{k}\right]-E_{\hat{Q}_{i}}\left[\psi_{k}\right]\right|&=\left|\lambda
E_{P}\left[\psi_{k}\right]+(1-\lambda)E_{Q}\left[\psi_{k}\right]-E_{\hat{Q}_{i}}\left[\psi_{k}\right]\right|\\\
&\leq\lambda\left|E_{P}\left[\psi_{k}\right]-E_{\hat{Q}_{i}}\left[\psi_{k}\right]\right|+(1-\lambda)\left|E_{Q}\left[\psi_{k}\right]-E_{\hat{Q}_{i}}\left[\psi_{k}\right]\right|\\\
&\leq\eta.\end{split}$ (6)

Thus, $\lambda P+(1-\lambda)Q\in\mathcal{P}^{\eta}_{i}$, and we have that
$\mathcal{P}^{\eta}_{0}$ and $\mathcal{P}^{\eta}_{1}$ are convex. Note that it
follows that $\mathcal{P}^{\eta}_{0}\times\mathcal{P}^{\eta}_{1}$ is also
convex. Since $\mathcal{X}$ is compact, we have that the set of all decision
rules is compact and convex. Finally, the error probability
$P_{E}(\phi;P_{0},P_{1})$ is continuous, real-valued and linear in
$\phi,P_{0},P_{1}$. Thus, applying Sion’s minimax theorem [20], we have our
result. ∎

The advantage of applying Theorem 1 is that the inner minimization problem in
(5) corresponds to the optimal Bayes error in classical binary hypothesis
testing, and is achieved by the likelihood ratio test. The problem then
reduces to a single maximization problem as follows:

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}P_{E}(\phi;P_{0},P_{1})$
$\displaystyle=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\inf_{\phi}P_{E}(\phi;P_{0},P_{1})$
(7)
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx$
(8)
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}1-\text{TV}(P_{0},P_{1}),$
(9)

where $\text{TV}(P_{0},P_{1})$ is the total variation between $P_{0}$ and
$P_{1}$.

To simplify the notation, we only consider the case of equal priors in our
paper. We note that our analysis is easily generalized to unequal priors. Let
$\pi_{0}$ denote the prior of $H_{0}$. The corresponding error probability is
given by

$\displaystyle
P_{E}(\phi;P_{0},P_{1})\triangleq\pi_{0}E_{P_{0}}\big{[}\phi(x)\big{]}+(1-\pi_{0})E_{P_{1}}\big{[}1-\phi(x)\big{]}.$
(10)

After applying the Sion’s minimax theorem [20], we have that

$\displaystyle\inf_{\phi}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}P_{E}(\phi;P_{0},P_{1})=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\inf_{\phi}P_{E}(\phi;P_{0},P_{1})$
(11)
$\displaystyle=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{\pi_{0}p_{0}(x),(1-\pi_{0})p_{1}(x)\right\\}dx.$
(12)

Our analysis can be easily extended to the case where $0<\pi_{0}<1$ by using
the above expression for the minimax error instead of (5).

We first consider the case when the alphabet size is finite, i.e.,
$|\mathcal{X}|<\infty$. Let $\mathcal{X}=\\{z_{1},\ldots,z_{N}\\}$. The
following theorem gives the optimal test in this case.

######  Theorem 2.

Let $|\mathcal{X}|=N<\infty$. Let
$P_{0}^{*}=(p_{0}^{*}(z_{1}),\ldots,p_{0}^{*}(z_{N}))$,
$P_{1}^{*}=(p_{1}^{*}(z_{1}),\ldots,p_{1}^{*}(z_{N}))$ be the optimal solution
to the following optimization problem:

$\begin{split}\max_{P_{0},P_{1}\in\mathbb{R}^{N}}&\sum_{j=1}^{N}\min\\{p_{0}(z_{j}),p_{1}(z_{j})\\}\\\
s.t.\;\;\;&\left|\sum_{j=1}^{N}p_{i}(z_{j})\psi_{k}(z_{j})-E_{\hat{Q}_{i}}[{\psi_{k}}]\right|\leq\eta,\;\;k\in[K]\;\;\;\\\
&\sum_{j=1}^{N}p_{i}(z_{j})=1\;\;\;\\\ &0\leq p_{i}(z_{j})\leq
1,\;\;\;j=1,\ldots,N,\;\;\;i=0,1.\end{split}$ (13)

Then, the likelihood ratio test between $P_{0}^{*}$ and $P_{1}^{*}$ achieves
the optimal minimax Bayes risk in (7).

The result in the above theorem follows from using (8) in the finite alphabet
case, which characterizes the minimax Bayes error for the likelihood ratio
test. Note that the optimization problem in Theorem 2 can be solved
effectively using available solvers for finite dimension convex optimization
problem with linear constraints.

##  IV Infinite Alphabet

In this section, we consider the case when $\mathcal{X}$ is infinite. Recall
that $\mathcal{X}$ is a compact set in $\mathbb{R}^{d}$. For the sake of
simplicity, and without loss of generality, we assume that
$\mathcal{X}\subseteq[0,1]^{d}$. In this case, the minimax formulation in (8)
is in general an infinite-dimensional optimization problem, and closed form
solutions are difficult to derive. We propose a tractable finite dimension
optimization problem as an approximation to the minimax problem, and construct
a robust detection test based on the solution to the approximation. In
addition, we also quantify the error arising from the approximation of the
original problem formulation.

First, note that the moment defining functions $\psi_{k},\;k=1,\ldots,K$ are
continuous functions on a compact set. Thus, they are Lipschitz functions with
constants $L_{1},\ldots,L_{K}$, and without loss of generality, we can set
$L=\max\limits_{k}L_{k}=1$. In addition, we consider values of
$\eta\in[\Delta,\eta_{0}]$, where

$\eta_{0}<\eta_{\mathrm{max}}=\mathop{\max}\limits_{k\in[K]}\frac{\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|}{2},$
(14)

and $0<\Delta<\eta_{0}$. Let $\epsilon>0$ such that
$\eta+\epsilon\leq\eta_{0}$. Consider a discretization of the space
$\mathcal{X}$ through an $\epsilon$-net or a covering set. Indeed we can
consider a simple and efficient construction by considering a grid of equally
spaced $N=\lceil\frac{1}{\epsilon^{d}}\rceil$ points
$\mathcal{S}_{N}=\\{z_{1},\ldots,z_{N}\\}$ such that for any
$x\in\mathcal{X}$,

$\min_{i=1,\ldots,N}\|z_{i}-x\|\leq\epsilon.$ (15)

Here, $N$ depends on $\epsilon$, but we drop the dependence on $\epsilon$ in
the notation for $N$ for readability. Let $\mathcal{P}_{N}$ denote all the
distributions that are supported on the set $\mathcal{S}_{N}$. Define the
relaxed uncertainty sets as follows for $i=0,1$:

$\mathcal{P}^{\eta+\epsilon}_{i,N}=\left\\{P\in\mathcal{P}_{N}:\left|E_{P}[\psi_{k}]-E_{\hat{Q}_{i}}[{\psi_{k}}]\right|\leq\eta+\epsilon,\;\;k\in[K]\right\\}.$
(16)

Consider the maximization problem in (8) with the uncertainty sets
$\mathcal{P}^{\eta+\epsilon}_{0,N},\mathcal{P}^{\eta+\epsilon}_{1,N}$:

$\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\},$
(17)

which can be written as

$\displaystyle\sup_{P_{0},P_{1}\in\mathbb{R}^{N}}$
$\displaystyle\sum_{j=1}^{N}\min\\{p_{0}(z_{j}),p_{1}(z_{j})\\}$
$\displaystyle s.t.\;\;\;$
$\displaystyle\left|\sum_{j=1}^{N}p_{i}(z_{j})\psi_{k}(z_{j})-E_{\hat{Q}_{i}}[{\psi_{k}}]\right|\leq\eta+\epsilon,\;\;\;k\in[K],$
$\displaystyle\sum_{j=1}^{N}p_{i}(z_{j})=1,$ $\displaystyle 0\leq
p_{0}(z_{j})\leq 1,\;\;\;j=1,\ldots,N,\;\;\;i=0,1.$ (18)

This is a finite dimension convex optimization problem with linear constraints
that can be solved efficiently. We first show that the optimal value of the
tractable relaxation in (17) converges to the optimal value of our original
problem (8), and quantify the error introduced by the relaxation. We then
propose a robust detection test for our original problem based on the solution
to (17), and quantify the error due to the approximation. The following lemma
will be useful in the proof of convergence of the approximation in (17).

######  Lemma 1.

The function $g(\eta)$ defined as

$g(\eta):=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(19)

is concave in $\eta$ on the open interval $(0,\eta_{\mathrm{max}})$.

The proof of the above lemma is similar to the analogous result in Appendix C
of [19]. Thus, we have that $g(\eta)$ is a concave function on the open
interval $(0,\eta_{\mathrm{max}})$, and hence Lipschitz on the closed interval
$[\Delta,\eta_{0}]\subset(0,\eta_{\mathrm{max}})$. Let the Lipschitz constant
be denoted by $L_{0}$. Define

$\displaystyle\gamma$
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx,$
(20) $\displaystyle\gamma_{\epsilon}$
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}.$
(21)

######  Theorem 3.

With the optimal values of the minimax Bayes formulation and its approximation
denoted as in (20) and (21), respectively, as $\epsilon\to 0$ (equivalently
$N\to\infty$), $\gamma_{\epsilon}$ converges to $\gamma$, with
$|\gamma_{\epsilon}-\gamma|\leq L_{0}\epsilon$.

###### Proof.

Consider the optimization problem in (8). Since $\mathcal{X}$ is compact, we
have that the uncertainty sets $\mathcal{P}^{\eta}_{0},\mathcal{P}^{\eta}_{1}$
are compact metric spaces that are compatible with weak convergence of
measures, i.e., $\mathcal{P}^{\eta}_{0},\mathcal{P}^{\eta}_{1}$ are weak
compact [21]. This follows from the fact that the set of all distributions
$\mathcal{P}$ is compact, and $\mathcal{P}^{\eta}_{0},\mathcal{P}^{\eta}_{1}$
are closed subsets of $\mathcal{P}$. Since the objective is upper semi-
continuous [19, Lemma 1], the supremum in (8) is attained. Let

$(P_{0}^{*},P_{1}^{*})\in\mathop{\arg\max}\limits_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(22)

Consider the partition $\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{N}\\}$ defined
by the set $\mathcal{S}_{N}$ on $\mathcal{X}$ such that for any
$j=1,\ldots,N$, if $x\in\mathcal{A}_{j}$, then

$\|x-z_{j}\|\leq\epsilon.$ (23)

Let $P_{0,N}^{*},P_{1,N}^{*}$ be distributions defined on $\mathcal{S}_{N}$ as
$p^{*}_{i,N}(z_{j})=P^{*}_{i}(\mathcal{A}_{j})$ for $j=1,\ldots,N$ and
$i=0,1$. Recall that $L=1$ is the maximum of the Lipschitz constants of the
$K$ moment defining functions. Then for $i=0,1$ we have that,

$\begin{split}\left|E_{P^{*}_{i,N}}[\psi_{k}]-E_{P^{*}_{i}}[\psi_{k}]\right|&=\left|\sum_{j=1}^{N}p^{*}_{i,N}(z_{j})\psi_{k}(z_{j})-\sum_{j=1}^{N}\int_{\mathcal{A}_{j}}\psi_{k}(x)p_{i}^{*}(x)dx\right|\\\
&=\left|\sum_{j=1}^{N}\int_{\mathcal{A}_{j}}(\psi_{k}(z_{j})-\psi_{k}(x))p_{i}^{*}(x)dx\right|\\\
&\leq\sum_{j=1}^{N}\int_{\mathcal{A}_{j}}\left|\psi_{k}(z_{j})-\psi_{k}(x)\right|p_{i}^{*}(x)dx\\\
&\leq\sum_{j=1}^{N}\int_{\mathcal{A}_{j}}L\|z_{j}-x\|p_{i}^{*}(x)dx\\\
&\leq\sum_{j=1}^{N}\int_{\mathcal{A}_{j}}\epsilon p_{i}^{*}(x)dx\\\
&=\epsilon.\end{split}$ (24)

It follows that $P_{i,N}^{*}\in\mathcal{P}^{\eta+\epsilon}_{i,N}$ for $i=0,1$,
where $\mathcal{P}^{\eta+\epsilon}_{i,N}$ are as defined in (16). We also have
from Jensen’s inequality that

$\sum_{i=1}^{N}\min\left\\{p^{*}_{0,N}(z_{i}),p^{*}_{1,N}(z_{i})\right\\}\geq\int_{\mathcal{X}}\min\left\\{p^{*}_{0}(x),p^{*}_{1}(x)\right\\}dx.$
(25)

Thus, we have that

$\begin{split}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}&\geq\int_{\mathcal{X}}\min\left\\{p^{*}_{0}(x),p^{*}_{1}(x)\right\\}dx\\\
&=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.\end{split}$
(26)

Consider the expanded uncertainty sets
$\mathcal{P}^{\eta+\epsilon}_{0},\mathcal{P}^{\eta+\epsilon}_{1}$:

$\mathcal{P}^{\eta+\epsilon}_{i}=\left\\{P\in\mathcal{P}:\left|E_{P}[\psi_{k}]-E_{\hat{Q}_{i}}[{\psi_{k}}]\right|\leq\eta+\epsilon,\;\;k=1,\ldots,K\right\\}.$
(27)

By definition,
$\mathcal{P}^{\eta+\epsilon}_{i,N}\subseteq\mathcal{P}^{\eta+\epsilon}_{i}$,
and thus,

$\begin{split}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx&\geq\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}\\\
&\geq\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.\end{split}$
(28)

We will show that

$\begin{split}\lim_{\epsilon\to
0}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx,\end{split}$
(29)

and thus

$\begin{split}\lim_{N\to\infty}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.\end{split}$
(30)

Recall that

$g(\eta)=\sup_{P_{0}\in\mathcal{P}_{0},P_{1}\in\mathcal{P}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(31)

Then, we have that

$g(\eta+\epsilon)=\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(32)

We have from Lemma 1 that $g(\eta)$ is concave and Lipschitz with constant
$L_{0}$. Also, $g(\eta)$ is continuous on $[\Delta,\eta_{\mathrm{max}}]$. From
continuity of $g(\eta)$, we have $\lim_{\epsilon\to
0}g(\eta+\epsilon)=g(\eta)$, i.e., the equality in (29). Thus, we have the
result in (30). Additionally, the error in the approximation can be quantified
as:

$\displaystyle\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}-\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}^{\eta}\in\mathcal{P}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx$
$\displaystyle\leq\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx-\sup_{P_{0}^{\eta}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx$
(33) $\displaystyle=g(\eta+\epsilon)-g(\eta)$ (34) $\displaystyle\leq
L_{0}\epsilon.$ (35)

∎

Let $P^{*}_{0,N},P^{*}_{1,N}$ be the solution to the optimization problem in
(IV). Recall the partition $\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{N}\\}$
defined by the set $\mathcal{S}_{N}$ on $\mathcal{X}$ such that for any
$j=1,\ldots,N$, if $x\in\mathcal{A}_{j}$, then

$\|x-z_{j}\|\leq\epsilon.$ (36)

In order to construct a robust detection test, we extend these discrete
distributions defined on $\mathcal{S}_{N}$ to the whole space $\mathcal{X}$ as
$P^{*}_{0},P_{1}^{*}$. For $i=0,1$, we distribute the probability mass of the
point $z_{j}$ onto points in the set $\mathcal{A}_{j}$ through a common
channel. For instance, we can distribute the mass $p^{*}_{i,N}(z_{j})$
uniformly on all points in the set $\mathcal{A}_{j}$ for $j=1,\ldots,N$, i.e.,
for $x\in\mathcal{X}$

$\begin{split}p_{i}^{*}(x)&=\sum_{j=1}^{N}\frac{p^{*}_{i,N}(z_{j})\mathbf{1}_{\\{x\in\mathcal{A}_{j}\\}}}{\int_{\mathcal{A}_{j}}dx}.\end{split}$
(37)

Then, we can define the robust test with
$\ell(x)=\frac{p_{1}^{*}(x)}{p_{0}^{*}(x)}$ as:

$\phi^{*}(x)=\begin{cases}&1,\;\;\;\text{if}\;\;\;\log{\ell(x)}\geq 0\\\
&0,\;\;\;\text{if}\;\;\;\log{\ell(x)}<0.\end{cases}$ (38)

Let the Bayes error for the test $\phi^{*}$ be denoted by
$P_{E}(\phi^{*};P_{0}^{*},P_{1}^{*})$. The following theorem quantifies the
optimality gap between $P_{E}(\phi^{*};P_{0}^{*},P^{*}_{1})$ and the optimal
minimax error in (20).

######  Theorem 4.

With the optimal value of the minimax Bayes formulation $\gamma$ denoted as in
(20), let the robust test $\phi^{*}$ be as defined in (38). Then,

$|P_{E}(\phi^{*};P^{*}_{0},P^{*}_{1})-\gamma|\leq L_{0}\epsilon.$ (39)

###### Proof.

We have from Theorem 3 that $|\gamma_{\epsilon}-\gamma|\leq L_{0}\epsilon$. It
then suffices to show that

$P_{E}(\phi^{*};P^{*}_{0},P^{*}_{1})=\gamma_{\epsilon}.$ (40)

Note that

$\displaystyle\gamma_{\epsilon}=\frac{1}{2}\sum_{j=1}^{N}\min\left\\{p^{*}_{0,N}(z_{j}),p^{*}_{1,N}(z_{j})\right\\}=\frac{1}{2}(1-\text{TV}(P^{*}_{0,N},P^{*}_{1,N})),$
(41) $\displaystyle
P_{E}(\phi^{*};P^{*}_{0},P^{*}_{1})=\frac{1}{2}\int_{\mathcal{X}}\min\left\\{p^{*}_{0}(x),p^{*}_{1}(x)\right\\}dx=\frac{1}{2}(1-\text{TV}(P_{0}^{*}.P_{1}^{*})).$
(42)

The equality in (40) can be obtained from seeing that
$\text{TV}(P^{*}_{0,N},P^{*}_{1,N})=\text{TV}(P_{0}^{*}.P_{1}^{*})$. Indeed,

$\text{TV}(P^{*}_{0,N},P^{*}_{1,N})\geq\text{TV}(P_{0}^{*}.P_{1}^{*})$ (43)

from data-processing inequality of f-divergences. Also, we have that

$\text{TV}(P^{*}_{0,N},P^{*}_{1,N})=\sup_{E\in\mathcal{E}}|P^{*}_{0,N}(E)-P^{*}_{1,N}(E)|,$
(44)

where $\mathcal{E}$ is the set of all measurable sets. Let $E^{*}$ be the set
achieving the above supremum (note that ${E}^{*}$ is a finite set). Let
${E}^{*}=\\{x_{1}^{*},\ldots,x_{L}^{*}\\}.$ Then,

$\displaystyle\text{TV}(P^{*}_{0,N},P^{*}_{1,N})$
$\displaystyle=|P^{*}_{0,N}(E^{*})-P^{*}_{1,N}(E^{*})|$ (45)
$\displaystyle=|P^{*}_{0}(\cup_{i=1}^{L}\mathcal{A}_{i}^{*})-P^{*}_{1}(\cup_{i=1}^{L}\mathcal{A}_{i}^{*})|$
(46) $\displaystyle\leq\text{TV}(P_{0}^{*}.P_{1}^{*}),$ (47)

where the second equality is from the definition of the smoothing operator,
and the last inequality is from the definition of the total variation
distance. The theorem follows. ∎

##  V Direct Robust Test for Batch Samples

Let $x_{1}^{s}=(x_{1},\ldots,x_{s})$ be a sequence of i.i.d. observations,
where $s$ is the sample size. One way to test this batch sample is to extend
the log-likelihood ratio test proposed in (38) to the batch. However, it is
difficult to analyze the error exponent of this test. In this section, we
propose an alternative test for testing batch samples, and show that it is
exponentially consistent as $s\to\infty$ in the Bayesian setting.

Let $\hat{P}_{s}=\frac{1}{s}\sum_{j=1}^{s}\delta_{{x}_{j}}$ be the empirical
distribution of the batch sample, and consider the test statistic

$\displaystyle
T(x_{1}^{s})=\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|^{2}-\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{1}}[\psi_{k}]\right|^{2}.$
(48)

We propose the following test for the batch sample:

$\phi_{s}(x_{1}^{s})=\begin{cases}&1,\;\;\;\text{if}\;\;\;T(x_{1}^{s})\geq
0\\\ &0,\;\;\;\text{if}\;\;\;T(x_{1}^{s})<0.\end{cases}$ (49)

######  Theorem 5.

The test in (49) is exponentially consistent.

###### Proof.

For any $P_{0}\in\mathcal{P}^{\eta}_{0}$, we have that

$\displaystyle
P_{0}\left(\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|^{2}\geq\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{1}}[\psi_{k}]\right|^{2}\right)$
(50)
$\displaystyle=P_{0}\left(2\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}])E_{\hat{P}_{s}}[\psi_{k}]\geq\sum_{k=1}^{K}(E_{\hat{Q}_{1}}^{2}[\psi_{k}]-E_{\hat{Q}_{0}}^{2}[\psi_{k}])\right)$
(51)
$\displaystyle=P_{0}\left(F(x_{1},\ldots,x_{s})-E[F(x_{1},\ldots,x_{s})]\geq\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}-(E_{\hat{Q}_{0}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}\right)$
(52)

where
$F(x_{1},\ldots,x_{s})=2\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}])E_{\hat{P}_{s}}[\psi_{k}]$.
Recall that

$\max\limits_{k=1,\ldots,K}\sup\limits_{x\in\mathcal{X}}\psi_{k}(x)\leq M.$
(53)

Thus, $F(x_{1},\ldots,x_{s})$ satisfies the bounded differences property,
i.e.,

$\displaystyle\sup\limits_{x\in\mathcal{X}}\left|F(x_{1},\ldots,x_{i},\ldots,x_{s})-F(x_{1},\ldots,x_{i}^{\prime},\ldots,x_{s})\right|$
$\displaystyle=\sup\limits_{x\in\mathcal{X}}\left|\frac{2}{s}\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}])(\psi_{k}(x_{i})-\psi_{k}(x_{i}^{\prime}))\right|$
$\displaystyle\leq\frac{4M}{s}\sum_{k=1}^{K}\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|.$
(54)

Also, since $P_{0}\in\mathcal{P}^{\eta}_{0}$,

$\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}-(E_{\hat{Q}_{0}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}>0.$
(55)

Thus, using Mcdiarmid’s inequality [22],

$\displaystyle
P_{0}\left(\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|^{2}\geq\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{1}}[\psi_{k}]\right|^{2}\right)$
(56)
$\displaystyle\leq\exp{\left(\frac{-s\left(\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}-(E_{\hat{Q}_{0}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}\right)^{2}}{8M^{2}\left(\sum_{k=1}^{K}\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|\right)^{2}}\right)}.$
(57)

Thus, we have that

$\displaystyle\sup\limits_{P_{0}\in\mathcal{P}^{\eta}_{0}}P_{0}\left(\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|^{2}\geq\sum_{k=1}^{K}\left|E_{\hat{P}_{s}}[\psi_{k}]-E_{\hat{Q}_{1}}[\psi_{k}]\right|^{2}\right)$
(58)
$\displaystyle\leq\sup\limits_{P_{0}\in\mathcal{P}^{\eta}_{0}}\exp{\left(\frac{-s\left(\sum_{k=1}^{K}(E_{\hat{Q}_{1}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}-(E_{\hat{Q}_{0}}[\psi_{k}]-E_{{P}_{0}}[\psi_{k}])^{2}\right)^{2}}{8M^{2}\left(\sum_{k=1}^{K}\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|\right)^{2}}\right)}$
(59)
$\displaystyle\leq\exp{\left(\frac{-s\left(\sum_{k=1}^{K}\left(E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]+2\eta\right)\left(E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right)\right)^{2}}{8M^{2}\left(\sum_{k=1}^{K}\left|E_{\hat{Q}_{1}}[\psi_{k}]-E_{\hat{Q}_{0}}[\psi_{k}]\right|\right)^{2}}\right)}.$
(60)

∎

##  VI Matrix Valued Constraints

In this section, we consider the setting where the constraint functions are
matrix valued. The uncertainty sets are defined as

$\displaystyle\mathcal{P}_{i}^{\eta}:=\big{\\{}P\in\mathcal{P}:\big{|}\lambda_{\text{min}}\big{(}E_{P}[\Psi_{k}]-E_{\hat{Q}_{i}}[\Psi_{k}]\big{)}\big{|}\leq\eta,\;\;k\in[K]\big{\\}},$
(61)

where $\Psi_{k}:\mathcal{X}\rightarrow\mathbb{R}^{d_{k}\times d_{k}}$ is a
continuous symmetric matrix function with measurable random components and
$\lambda_{\text{min}}$ denotes the smallest eigenvalue of a matrix. The
uncertainty sets are defined as collections of all distributions $P$ such that
the smallest eigenvalue of the symmetric matrix
$E_{P}[\Psi_{k}(x)]-E_{\hat{Q}_{i}}[\Psi_{k}(x)]$ lies in $[-\eta,\eta]$. Let
$\eta_{\text{max}}$ denote the largest radius such that the uncertainty sets
do not overlap. We consider values of $\eta$ in $(0,\eta_{\text{max}})$. When
$d_{k}=1$, $\Psi_{k}$ reduces to a scalar valued function. In this section, we
focus on the Bayesian setting.

As in the setting with scalar valued functions, we have the following result
for both finite-alphabet and infinite-alphabet cases:

######  Theorem 6.

$\inf_{\phi}\sup_{P_{0}\in\mathcal{P}_{0}^{\eta},P_{1}\in\mathcal{P}_{1}^{\eta}}P_{E}(\phi;P_{0},P_{1})=\sup_{P_{0}\in\mathcal{P}_{0}^{\eta},P_{1}\in\mathcal{P}_{1}^{\eta}}\inf_{\phi}P_{E}(\phi;P_{0},P_{1}).$
(62)

###### Proof.

For some $\alpha\in(0,1)$, $P,Q\in\mathcal{P}_{i}^{\eta}$ for $i=0,1$, and
$k=1,\ldots,K$, we have

$\begin{split}\lambda_{\text{min}}\big{(}E_{\lambda
P+(1-\lambda)Q}\left[\Psi_{k}\right]\big{)}&=\lambda_{\text{min}}\big{(}\alpha
E_{P}\left[\Psi_{k}\right]+(1-\alpha)E_{Q}\left[\Psi_{k}\right]\big{)}\\\
&\geq\lambda_{\text{min}}\big{(}\alpha
E_{P}\left[\Psi_{k}\right]\big{)}+\lambda_{\text{min}}\big{(}(1-\alpha)E_{Q}\left[\Psi_{k}\right]\big{)}\\\
&\geq 0,\end{split}$ (63)

where the first inequality is from Weyl’s inequality [23] and the fact that
$\Psi_{k}$ is symmetric. Thus, $\alpha
P+(1-\alpha)Q\in\mathcal{P}_{i}^{\eta}$, and we have $\mathcal{P}_{0}^{\eta}$
and $\mathcal{P}_{1}^{\eta}$ are convex. The rest of the proof follows the
same steps as in the proof of Theorem 1. ∎

We present the optimal test for the finite alphabet case in the following
theorem.

######  Theorem 7.

Let $P_{0}^{*}=(p_{0}^{*}(z_{1}),\ldots,p_{0}^{*}(z_{N}))$,
$P_{1}^{*}=(p_{1}^{*}(z_{1}),\ldots,p_{1}^{*}(z_{N}))$ be the optimal solution
to the following optimization problem:

$\begin{split}\max_{P_{0},P_{1}\in\mathbb{R}^{N}}&\sum_{j=1}^{N}\min\\{p_{0}(z_{j}),p_{1}(z_{j})\\}\\\
s.t.\;\;\;&\Big{|}\lambda_{\min}\big{(}\sum_{j=1}^{N}p_{i}(z_{j})\Psi_{k}(z_{j})-E_{\hat{Q}_{i}}[\Psi_{k}]\big{)}\Big{|}\leq\eta,\;\;k\in[K]\;\;\;\\\
&\sum_{j=1}^{N}p_{i}(z_{j})=1\;\;\;\\\ &0\leq p_{i}(z_{j})\leq
1,\;\;\;j=1,\ldots,N,\;\;\;i=0,1.\end{split}$ (64)

Then, the likelihood ratio test between $P_{0}^{*}$ and $P_{1}^{*}$ achieves
the optimal minimax Bayes risk in (7).

This result can be generalized directly from the setting in Section IV. Note
that the constraint
$\Big{|}\lambda_{\min}\big{(}\sum_{j=1}^{N}p_{i}(z_{j})\Psi_{k}(z_{j})-E_{\hat{Q}_{i}}[\Psi_{k}]\big{)}\Big{|}\leq\eta$
is equivalent to
$\sum_{j=1}^{N}p_{i}(z_{j})\Psi_{k}(z_{j})-E_{\hat{Q}_{i}}[\Psi_{k}]+\eta
I\succeq 0$ and
$\sum_{j=1}^{N}p_{i}(z_{j})\Psi_{k}(z_{j})-E_{\hat{Q}_{i}}[\Psi_{k}]-\eta
I\preceq 0$ where $I$ denotes the identity matrix. Therefore, the optimization
problem in Theorem 7 is a semidefinite programming and can be solved
efficiently.

For the infinite-alphabet case, as in Section IV, we define the relaxed
uncertainty sets as follows for $i=0,1$:

$\mathcal{P}^{\eta+\epsilon}_{i,N}=\left\\{P\in\mathcal{P}_{N}:\big{|}\lambda_{\text{min}}\big{(}E_{P}[\Psi_{k}]-E_{\hat{Q}_{i}}[\Psi_{k}]\big{)}\big{|}\leq\eta+\epsilon,\;\;k\in[K]\right\\}.$
(65)

Consider the maximization problem in (8) with the uncertainty sets
$\mathcal{P}^{\eta+\epsilon}_{0,N},\mathcal{P}^{\eta+\epsilon}_{1,N}$:

$\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}.$
(66)

In this section, we show that the results in Section IV can be generalized to
the case where the constraints are matrix valued functions.

######  Lemma 2.

The function $g(\eta)$ defined as

$g(\eta):=\sup_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(67)

is continuous on the open interval $(0,\eta_{\max})$.

The above Lemma follows from showing that $g(\eta)$ is concave in $\eta$
(whose proof is similar to the analogous result in Appendix C of [19]). Let

$\displaystyle\gamma$
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}_{0}^{\eta},P_{1}\in\mathcal{P}_{1}^{\eta}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx,$
(68) $\displaystyle\gamma_{\epsilon}$
$\displaystyle=\frac{1}{2}\sup_{P_{0}\in\mathcal{P}^{\eta+\epsilon}_{0,N},P_{1}\in\mathcal{P}^{\eta+\epsilon}_{1,N}}\sum_{i=1}^{N}\min\left\\{p_{0}(z_{i}),p_{1}(z_{i})\right\\}.$
(69)

We present the convergence of the approximation in (66) to the optimal minimax
error in the following theorem.

######  Theorem 8.

With the optimal values of the minimax Bayes formulation and its approximation
denoted as in (68) and (69) respectively, as $\epsilon\to 0$ (equivalently
$N\to\infty$), $\gamma_{\epsilon}$ converges to $\gamma$.

###### Proof.

We construct $P_{0,N}^{*},P_{1,N}^{*}$ as in the proof of Theorem 3 and let

$(P_{0}^{*},P_{1}^{*})\in\mathop{\arg\max}_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\int_{\mathcal{X}}\min\left\\{p_{0}(x),p_{1}(x)\right\\}dx.$
(70)

Since $\Psi_{k}$ is a continuous matrix function, we have that

$\lim_{N\rightarrow\infty}\big{\|}E_{P^{*}_{0,N}}[\Psi_{k}]\\\
-E_{P_{0}^{*}}[\Psi_{k}]\big{\|}\rightarrow 0.$

Since
$\lambda_{\text{min}}\big{(}E_{P_{0}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}\leq\eta$,
let $E_{P_{0}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]=V\Lambda V^{-1}$ be the
eigenvalue decomposition of $E_{P_{0}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]$.
From the Bauer-Fike Theorem [24], we have that

$\displaystyle\min_{\lambda\in\Lambda\big{(}E_{P_{0}^{*}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}}\Big{|}\lambda_{\text{min}}\big{(}E_{P_{0,N}^{*}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}-\lambda\Big{|}$
$\displaystyle\leq\|V\|\|V^{-1}\|\big{\|}E_{P_{0,N}^{*}}[\Psi_{k}]-E_{P_{0}^{*}}[\Psi_{k}]\big{\|}$
$\displaystyle=\big{\|}E_{P_{0,N}^{*}}[\Psi_{k}]-E_{P_{0}^{*}}[\Psi_{k}]\big{\|},$
(71)

where $\Lambda(\cdot)$ denotes the collection of all eigenvalues of a matrix.
Therefore, as $N\rightarrow\infty$, we have that
$\min_{\lambda\in\Lambda\big{(}E_{P_{0}^{*}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}}\Big{|}\lambda_{\text{min}}\big{(}E_{P_{0,N}^{*}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}-\lambda\Big{|}\rightarrow
0$. It follows that for any $\epsilon>0$, there exists $N^{*}$ such that
$\big{|}\lambda_{\text{min}}\big{(}E_{P_{0,N}^{*}}[\Psi_{k}]-E_{\hat{Q}_{0}}[\Psi_{k}]\big{)}\big{|}\leq\eta+\epsilon$
for $N>N^{*}$. Thus, we have that
$P_{0,N}^{*}\in\mathcal{P}_{0,N}^{\eta+\epsilon}$, and similarly
$P_{1,N}^{*}\in\mathcal{P}_{1,N}^{\eta+\epsilon}$. We can then follow the same
steps as in (25)-(32) and show that $\gamma_{\epsilon}$ converges to $\gamma$
as $\epsilon\to 0$. ∎

As in Section IV, the robust test defined on the entire space $\mathcal{X}$
can be extended from the solution of the approximation problem in (66).

##  VII Neyman-Pearson Setting

We now study the robust hypothesis testing problem in the asymptotic Neyman-
Pearson setting. Our goal is to maximise the worst-case type-II error
exponent, subject to a constraint on the worst-case type-I error probability,
i.e.,

$\displaystyle\sup_{\phi:P_{F}(\phi)\leq\alpha}\inf_{P_{1}\in\mathcal{P}^{\eta}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})],$ (72)

where $P_{F}(\phi)$ is the worst-case type-I error probability for a batch
sample test $\phi(x^{n}):\mathcal{X}^{n}\to[0,1]$:

$P_{F}(\phi)\triangleq\sup_{P_{0}\in\mathcal{P}^{\eta}_{0}}E_{P_{0}}\big{[}\phi(x^{n})\big{]},$
(73)

and $\alpha\in(0,1]$ is a pre-specified upper bound on $P_{F}(\phi)$. We
consider the special case where there is only one continuous real valued
moment function to define the uncertainty sets, i.e.,

$\displaystyle\mathcal{P}_{i}^{\eta}:=\big{\\{}P\in\mathcal{P}:E_{P}[\psi_{0}(x)]-E_{\hat{Q}_{i}}[\psi_{0}(x)]\leq\eta\big{\\}}.$
(74)

For the asymptotic Neyman-Pearson setting, the best achievable type-II error
exponent is
$\inf_{P_{0}\in\mathcal{P}_{0}^{\eta},P_{1}\in\mathcal{P}^{\eta}_{1}}D(P_{0}\|P_{1})$.
This motivates us to find the optimal solution to

$\inf_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}^{\eta}_{1}}\\\
D(P_{0}\|P_{1})$

and design the robust test accordingly. We present the asymptotic robust test
in the following theorem.

######  Theorem 9.

Define the robust test

$\displaystyle\phi(x^{n})=\left\\{\begin{array}[]{ll}1,&\text{if
}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})\geq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\\\ 0,&\text{if
}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})<E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n},\end{array}\right.$
(77)

where $\gamma_{n}=\sqrt{\frac{-c^{2}\ln\alpha}{2n}}$ for some constant $c$.

The test is asymptotically optimal under the Neyman-Pearson setting defined in
(72):
1) under $H_{0}$,

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}^{\eta}}E_{P_{0}}[\phi(x^{n})]=\sup_{P_{0}\in\mathcal{P}_{0}^{\eta}}P_{0}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{n})\geq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\Big{)}\leq\alpha;$ (78)

2) and under $H_{1}$,

$\displaystyle\inf_{P_{1}\in\mathcal{P}^{\eta}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
E_{P_{1}}[1-\phi(x^{n})]$
$\displaystyle=\inf_{P_{1}\in\mathcal{P}^{\eta}_{1}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})<E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\Big{)}$
$\displaystyle=\inf_{P_{0}\in\mathcal{P}^{\eta}_{0},P_{1}\in\mathcal{P}_{1}^{\eta}}D(P_{0}\|P_{1}).$
(79)

###### Proof.

Let $F(x_{1},x_{2},\cdots,x_{n})=\frac{1}{n}\sum_{i=0}^{n}\psi_{0}(x_{i})$.
Since $\mathcal{X}$ is bounded and $\psi_{0}(x)$ is continuous, there exists
$c<\infty$ such that
$c=\max_{x,x^{\prime}}|\psi_{0}(x)-\psi_{0}(x^{\prime})|$. For every
$(x_{1},x_{2},\cdots,x_{n}),(x_{1}^{\prime},x_{2}^{\prime},\cdots,x_{n}^{\prime})$
that differ only in the $i$-th coordinate, we have that
$|F(x_{1},x_{2},\cdots,x_{n})-F(x_{1}^{\prime},x_{2}^{\prime},\cdots,x_{n}^{\prime})|\leq\frac{c}{n}$.
From McDiarmid’s inequality [22], we have that for any
$P_{0}\in\mathcal{P}^{\eta}_{0}$ and $t>0$,

$\displaystyle
P_{0}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})-E_{P_{0}}[\psi_{0}(x)]\geq
t\Big{)}\leq e^{-\frac{2nt^{2}}{c^{2}}}.$ (80)

Since $E_{P_{0}}[\psi_{0}(x)]\leq E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta$, we have
that

$\displaystyle\sup_{P_{0}\in\mathcal{P}_{0}^{\eta}}P_{0}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})\geq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\Big{)}$
$\displaystyle\leq\sup_{P_{0}\in\mathcal{P}_{0}^{\eta}}P_{0}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})\geq
E_{P_{0}}[\psi_{0}(x)]+\gamma_{n}\Big{)}$ $\displaystyle\leq\alpha.$ (81)

We now analyze the type-II error exponent. We have that as
$n\rightarrow\infty$, $\gamma_{n}\rightarrow 0$. Therefore, for any
$\gamma>0$, there exists $n_{0}$ such that for all $n>n_{0}$,
$\gamma_{n}<\gamma$. We then have that

$\displaystyle\inf_{P_{1}\in\mathcal{P}_{1}^{\eta}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})<E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\Big{)}$
$\displaystyle\geq\inf_{P_{1}\in\mathcal{P}_{1}^{\eta}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})<E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma\Big{)}$
$\displaystyle\geq\inf_{P_{1}\in\mathcal{P}_{1}^{\eta}}\inf_{\\{P:E_{P}[\psi_{0}(x)]\leq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma\\}}D(P\|P_{1}).$ (82)

Given $P_{1}$, let
$f(\eta)=\inf_{\\{P:E_{P}[\psi_{0}(x)]-E_{\hat{Q}_{0}}[\psi_{0}(x)]\geq\eta\\}}D(P\|P_{1})$.
It is easy to show that $f(\eta)$ is continuous in $\eta$ by showing that
$f(\eta)$ is convex in $\eta$ for $\eta\in(0,\eta_{max})$. Therefore, for any
$\epsilon>0$, there exists $\gamma^{\prime}>0$ such that for
$0<\gamma<\gamma^{\prime}$,

$\inf_{\\{P:E_{P}[\psi_{0}(x)]\leq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma\\}}D(P\|P_{1})\geq\inf_{\\{P:E_{P}[\psi_{0}(x)]\leq
E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta\\}}D(P\|P_{1})-\epsilon.$

Since $\epsilon$ can be arbitrarily small, we have that

$\inf_{P_{1}\in\mathcal{P}_{1}^{\eta}}\lim_{n\rightarrow\infty}-\frac{1}{n}\log
P_{1}\Big{(}\frac{1}{n}\sum_{i=1}^{n}\psi_{0}(x_{i})<E_{\hat{Q}_{0}}[\psi_{0}(x)]+\eta+\gamma_{n}\Big{)}\geq\inf_{P_{0}\in\mathcal{P}_{0}^{\eta},P_{1}\in\mathcal{P}_{1}^{\eta}}D(P_{0}\|P_{1}).$

Therefore, $\phi$ is asymptotically optimal under the Neyman-Pearson setting.
∎

##  VIII Simulation Results

In this section, we provide some numerical results. We first compare our
moment robust test $\phi^{*}$ with the direct robust test $\phi_{s}$ using
synthetic data. For hypothesis $H_{0}$, the uncertainty set is constructed
using 20 observations collected from a multi-variate Gaussian distribution
with mean $[0,0,0,0]$ and covariance matrix $\mathbf{I}$, where $\mathbf{I}$
is the identity matrix. For $H_{1}$, the uncertainty set is constructed using
$20$ observations collected from a multi-variate Gaussian distribution with a
different mean $[0.8,0.8,0.8,0.8]$ and covariance matrix $0.5\mathbf{I}$. The
constraint functions are chosen as the mean and variance of each of the
dimensions. We define the uncertainty sets as the collections of distributions
such that the mean and variance for each of the dimensions lie in a certain
range centered around the empirical mean and variance, respectively. We use
the true distributions to generate the test sample and plot the error
probability as a function of testing sample size $n$.

From Fig. 1(a), it can be seen that the error probabilities for the moment
robust test and the direct robust test decay exponentially with the testing
sample size, which demonstrates the exponentially consistency of the direct
robust test. Moreover, the moment robust test performs better than the direct
robust test.

(a) Synthetic Data

(b) Real Data

Figure 1: Comparison of the Moment Robust Test and the Direct Robust Test

Additionally, we compare the moment robust test $\phi^{*}$ with the direct
robust test $\phi_{s}$ using real datasets. We use a dataset collected with
the Actitracker system [25, 26, 27]. For hypothesis $H_{0}$, the jogging data
of person 685 is used to construct the uncertainty sets. For hypothesis
$H_{1}$, the walking data of person 669 is used to construct the uncertainty
set. The uncertainty sets are defined as in the synthetic data case. We plot
the error probability as a function of sample size $n$. In Fig. 1(b), it can
be seen that the moment robust test performs better than the direct robust
test. The error probabilities for the moment robust test and the direct robust
test decay exponentially with the testing sample size.

##  IX Conclusion

In this paper, we studied the robust hypothesis testing problem, with
uncertainty sets constructed through general moment functions. We focused on
the Bayesian setting, where the goal is to minimize the worst-case error
probability over the uncertainty sets. We proposed the optimal test for the
finite-alphabet case, and a tractable approximation of the worst-case error
probability that converges to the optimal value of the original problem for
the infinite-alphabet case. Based on the tractable approximation, we proposed
a robust test extending to the entire alphabet. In addition, we proposed an
exponentially consistent test for testing batch samples and provided numerical
results to demonstrate the performance of the proposed robust tests. We also
extended our results to uncertainty sets constructed through matrix-valued
moment functions. For the asymptotic Neyman-Pearson setting, we proposed an
asymptotically optimal test.

## References

  * [1] P. Moulin and V. V. Veeravalli, _Statistical Inference for Engineers and Data Scientists_. Cambridge University Press, 2018.
  * [2] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. New York, NY, USA: John Wiley & Sons, 2006.
  * [3] S. M. Kay, _Fundamentals of Statistical Signal Processing_. Prentice Hall PTR, 1993.
  * [4] P. J. Huber, “A robust version of the probability ratio test,” _The Annals of Mathematical Statistics_ , pp. 1753–1758, 1965.
  * [5] H. Rieder, “Least favorable pairs for special capacities,” _The Annals of Statistics_ , vol. 5, no. 5, pp. 909–921, 1977.
  * [6] F. Österreicher, “On the construction of least favourable pairs of distributions,” _Z. Wahrscheinlichkeitstheorie verw Gebiete_ , vol. 43, pp. 49–55, 1978.
  * [7] T. Bednarski, “On solutions of minimax test problems for special capacities,” _Z. Wahrscheinlichkeitstheorie verw Gebiete_ , vol. 58, pp. 397–405, 1981\.
  * [8] R. Hafner, “Simple construction of least favourable pairs of distributions and of robust tests for prokhorov-neighbourhoods,” _Series Statistics_ , vol. 13, no. 1, pp. 33–46, 1982.
  * [9] S. Kassam, “Robust hypothesis testing for bounded classes of probability densities (corresp.),” _IEEE Transactions on Information Theory_ , vol. 27, no. 2, pp. 242–247, 1981.
  * [10] R. Hafner, “Construction of minimax-tests for bounded families of probability-densities,” _Metrika_ , vol. 40, no. 1, pp. 1–23, 1993.
  * [11] K. Vastola and H. Poor, “On the p-point uncertainty class (corresp.),” _IEEE Transactions on Information Theory_ , vol. 30, no. 2, pp. 374–376, 1984\.
  * [12] C. Pandit, S. Meyn, and V. Veeravalli, “Asymptotic robust neyman-pearson hypothesis testing based on moment classes,” in _Proceedings of International Symposium on Information Theory._ IEEE, 2004, p. 220.
  * [13] B. C. Levy, “Robust hypothesis testing with a relative entropy tolerance,” _IEEE Transactions on Information Theory_ , vol. 55, no. 1, pp. 413–421, 2009\.
  * [14] M. Barni and B. Tondi, “The source identification game: An information-theoretic perspective,” _IEEE Transactions on Information Forensics and Security_ , vol. 8, no. 3, pp. 450–463, 2013.
  * [15] G. Gül and A. M. Zoubir, “Minimax robust hypothesis testing,” _IEEE Transactions on Information Theory_ , vol. 63, no. 9, pp. 5572–5587, 2017.
  * [16] R. Gao, L. Xie, Y. Xie, and H. Xu, “Robust hypothesis testing using wasserstein uncertainty sets,” in _Proceedings of Advances Neural Information Processing Systems_ , 2018, pp. 7902–7912.
  * [17] Y. Jin and L. Lai, “On the adversarial robustness of hypothesis testing,” _IEEE Transaction on Signal Processing_ , to appear, 2020.
  * [18] L. Xie, R. Gao, and Y. Xie, “Robust hypothesis testing with wasserstein uncertainty sets,” _arXiv preprint arXiv:2105.14348_ , 2021.
  * [19] Z. Sun and S. Zou, “Kernel robust hypothesis testing,” _arXiv preprint arXiv:2203.12777_ , 2022.
  * [20] M. Sion, “On general minimax theorems.” _Pacific Journal of Mathematics_ , vol. 8, no. 1, pp. 171 – 176, 1958.
  * [21] Y. V. Prokhorov, “Convergence of random processes and limit theorems in probability theory,” _Theory of Probability & Its Applications_, vol. 1, no. 2, pp. 157–214, 1956.
  * [22] C. McDiarmid, “On the method of bounded differences,” in _Surveys in combinatorics_. Cambridge Univ. Press, 1989, vol. 141, pp. 148–188.
  * [23] H. Weyl, “Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung),” _Mathematische Annalen_ , vol. 71, no. 4, pp. 441–479, 1912.
  * [24] F. Bauer and C. Fike, “Norms and exclusion theorems.” _Numerische Mathematik_ , vol. 2, pp. 137–141, 1960.
  * [25] J. W. Lockhart, G. M. Weiss, J. C. Xue, S. T. Gallagher, A. B. Grosner, and T. T. Pulickal, “Design considerations for the wisdm smart phone-based sensor mining architecture,” in _Proceedings of the Fifth International Workshop on Knowledge Discovery from Sensor Data_ , 2011, p. 25–33.
  * [26] J. R. Kwapisz, G. M. Weiss, and S. A. Moore, “Activity recognition using cell phone accelerometers,” _ACM SigKDD Explorations Newsletter_ , vol. 12, no. 2, p. 74–82, 2011.
  * [27] G. M. Weiss and J. W. Lockhart, “The impact of personalization on smartphone-based activity recognition,” _AAAI Workshop on Activity Context Representation: Techniques and Languages_ , pp. 98–104, 2012.


# Viscosity approximation method for a variational problem

Ramzi May  Mathematics Department, College of Science, King Faisal University,
P.O. 380, Ahsaa 31982, Kingdom of Saudi Arabia<EMAIL_ADDRESS>
(Date: July 02, 2022)

###### Abstract.

Let $Q$ be a nonempty closed and convex subset of a real Hilbert space
$\mathcal{H}$, $S:Q\rightarrow Q$ a nonexpansive mapping, $A:Q\rightarrow Q$
an inverse strongly monotone operator, and $f:Q\rightarrow Q$ a contraction
mapping. We prove, under appropriate conditions on the real sequences
$\\{\alpha_{n}\\}$ and $\\{\lambda_{n}\\},$ that for any starting point
$x_{1}$ in $Q,$ the sequence $\\{x_{n}\\}$ generated by the iterative process

(0.1)
$x_{n+1}=\alpha_{n}f(x_{n})+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n})$

converges strongly to a particular element of the set $F_{ix}(S)\cap
S_{VI(A,Q)}$ which we suppose that it is nonempty, where $F_{ix}(S)$ is the
set of fixed point of the mapping $S$ and $S_{VI(A,Q)}$ is the set of $q\in Q$
such that $\langle Aq,x-q\rangle\geq 0$ for every $x\in Q.$ Moreover, we study
the strong convergence of a perturbed version of the algorithm generated by
the above process. Finally, we apply the main result to construct an algorithm
associated to a constrained convex optimization problem and we provide a
numerical experiment to emphasize the effect of the parameter
$\\{\alpha_{n}\\}$ on the convergence rate of this algorithm.

###### Key words and phrases:

Hilbert space; Variational inequality problem; nonexpansive mapping; Inverse
strongly monotone mappings

###### 1991 Mathematics Subject Classification:

47H09;47j05;47J25

##  1\. Introduction

Let $\mathcal{H}$ be a real Hilbert space with inner product
$\langle.,.\rangle$ and associated norm $\left\|.\right\|$. Throughout this
paper, we assume the following assumptions:

(A1) $Q$ is a nonempty, closed and convex subset of $\mathcal{H}$.

(A2) $S:Q\rightarrow Q$ is a nonexpansive mapping which means that $\left\|Sx-
Sy\right\|\leq\left\|x-y\right\|$ for every $x,y\in Q$.

(A3) $A:Q\rightarrow\mathcal{H}$ is a $\nu$ inverse strongly monotone operator
which means that there exists a real $\nu>0$ such that

$\langle Ax-Ay,x-y\rangle\geq\nu\left\|Ax-Ay\right\|^{2}~{}\forall x,y\in Q;$

(A4) $f:Q\rightarrow Q$ is a contraction with coefficient $\rho\in[0,1[,$ that
is

$\left\|f(x)-f(y)\right\|\leq\rho\left\|x-y\right\|~{}\forall x,y\in Q.$

We denote by $F_{ix}(S)=\\{x\in Q:Sx=x\\}$ the set of fixed points of the
operator $S$ and by $S_{VI(A,Q)}$ the set of solutions of the following
variational inequality

(1.1) $\text{Find }q\in Q\text{ such that }\langle Aq,x-q\rangle\geq 0\text{
for every }x\in Q.$

It is easy to prove that the sets $F_{ix}(S)$ and $S_{VI(A,Q)}$ are closed and
convex subsets of $\mathcal{H}$ (see Lemma 2.3 and Lemma 2.4 in the next
section); hence the set

$\Omega:=F_{ix}(S)\cap S_{VI(A,Q)}$

is also closed and convex subset of $\mathcal{H}.$ Hereafter, we assume
moreover that:

(A5): The set $\Omega$ is nonempty.

In this paper, we are interested in the numerical approximation of some
particular elements of $\Omega$. We recall that Takahashi and Toyoda [7]
introduced the following algorithm

(1.2) $\left\\{\begin{array}[]{l}x_{1}\in Q\\\
x_{n+1}=\alpha_{n}x_{n}+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n}),~{}n\geq
1,\end{array}\right.$

where $P_{Q}:\mathcal{H}\rightarrow Q$ is the metric projection from
$\mathcal{H}$ onto $Q$ (see Lemma 2.1 for the definition. They proved that if
the sequence $\\{(\alpha_{n},\lambda_{n})\\}$ remains in a fixed compact
subset of $]0,1[\times]0,2\nu[,$ then any sequence $\\{x_{n}\\}$ generated by
the process (1.2) converges weakly to some element $q_{\infty}$ of $\Omega.$
To overcome the drawback of the weak convergence and the non specification of
the limit point $q_{\infty}$ in the algorithm (1.2) , Iiduka and Tokahashi [4]
have introduced in 2005 the following iterative process:

(1.3) $\left\\{\begin{array}[]{l}x_{1}\in Q\\\
x_{n+1}=\alpha_{n}u+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n}),~{}n\geq
1,\end{array}\right.$

where $u$ is a fixed element of $Q.$ They established that if
$\\{\lambda_{n}\\}\in[a,b]$, with $0<a<b<2\nu$, $\\{\alpha_{n}\\}\in[0,1],$
$\alpha_{n}\rightarrow 0,$ $\sum_{n\geq 1}\alpha_{n}=+\infty$ and $\sum_{n\geq
1}\left(\left|\alpha_{n+1}-\alpha_{n}\right|+\left|\lambda_{n+1}-\lambda_{n}\right|\right)<\infty$,
then any sequence $\\{x_{n}\\}$ generated by the algorithm (1.3) converges
strongly in $\mathcal{H}$ the closed element of $\Omega$ to $u.$

In 2011, Yao, Liou and Chen [10] studied two averaged version the algorithm
(LABEL:AL2). Precisely, they of introduced the following two algorithms

(1.4) $\left\\{\begin{array}[l]{l}x_{1}\in Q\\\
x_{n+1}=\beta_{n}x_{n}+(1-\beta_{n})P_{Q}(\alpha_{n}u+(1-\alpha_{n})SP_{Q}\left(x_{n}-\lambda_{n}Ax_{n}\right)),~{}n\geq
1;\end{array}\right.$ (1.5) $\left\\{\begin{array}[l]{l}x_{1}\in Q\\\
x_{n+1}=\beta_{n}x_{n}+(1-\beta_{n})SP_{Q}(\alpha_{n}u+(1-\alpha_{n})\left(x_{n}-\lambda_{n}Ax_{n}\right)),~{}n\geq
1.\end{array}\right.$

They proved that if the sequence $\\{\alpha_{n}\\}$ and $\\{\lambda_{n}\\}$
satisfy the same assumptions as in the Theorem of Iiduka and Tokahashi and
$\\{\beta_{n}\\}$ belongs to a sub-interval $[0,b]$ of $[0,1[$ and satisfies
$\sum_{n\geq 1}\left|\beta_{n+1}-\beta_{n}\right|<\infty$, then any sequence
$\\{x_{n}\\}$ generated by (1.4) or (1.5) converges strongly in $\mathcal{H}$
to the closed element of $\Omega$ to $u.$

In this paper, inspired by the viscosity approximation method due to A.
Moudafi [5], we introduce the following iterative process

(1.6) $\left\\{\begin{array}[]{l}x_{1}\in Q\\\
x_{n+1}=\alpha_{n}f(x_{n})+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n}),~{}n\geq
1,\end{array}\right.$

which is a generalization of the algorithm (1.3). Under the same assumptions
on the sequences $\\{\lambda_{n}\\}$ and $\\{\alpha_{n}\\}$ in the above
convergence result of Iiduka and Tokahashi, we prove that any sequence
generated by the algorithm (1.6) converges strongly to $q^{\ast}$ the unique
solution of the variational problem

(VP) $\left\\{\begin{array}[]{l}q^{\ast}\in\Omega,\\\ \langle
f(q^{\ast})-q^{\ast},x-q^{\ast}\rangle\leq 0,~{}\forall
x\in\Omega.\end{array}\right.$

Moreover, we establish the strong convergence of the implicit version of the
algorithm (1.6). Precisely, we will prove that if
$\lambda:]0,1]\rightarrow[a,b]$, with $[a,b]\subset]0,2\nu[,$ then for every
$t\in]0,1]$ there exists a unique $x_{t}$ in $Q$ such that

(1.7) $x_{t}=t~{}f(x_{t})+(1-t)~{}SP_{Q}(x_{t}-\lambda(t)Ax_{t}).$

Then we show that $x_{t}$ converges strongly in $\mathcal{H}$ to $q^{\ast}$ as
$t\rightarrow 0^{+}.$

The sequel of the paper is organized as follows: In the next section, we
recall some well-known results from convex analysis that will be useful in the
proof of the main results of the paper. In the third section, we establish the
strong convergence of the implicit algorithm (1.7). In the fourth section, we
study the strong convergence of the explicit algorithm (1.6). Then we prove
the stability of the process (1.7) under the effect of small perturbations and
we apply the obtained results to the study of a constrained optimization
problem. The last section is devoted to the study of a numerical experiment
that highlight the effect of the sequence $\\{\alpha_{n}\\}$ on the
convergence rate of a particular example of the perturbed version of the
algorithm (1.7).

##  2\. Preliminaries

In this section, we recall some results that will be helpful in the next
sections. Most of these results can be found in any good book on convex
analysis as [1], [2] and [6]. Let us first recall the definition of the metric
projection onto a nonempty, closed and convex subset of $\mathcal{H}$.

######  Lemma 2.1 ([1, Theorem 3.14]).

Let $K$ be a nonempty, closed and convex subset of $\mathcal{H}$. For every
$x\in\mathcal{H},$ there exists a unique $P_{K}(x)\in Q$ such that

$\left\|x-P_{K}(x)\right\|\leq\left\|x-y\right\|\ ~{}\forall y\in K.$

The operator $P_{K}:\mathcal{H}\rightarrow K$ is called the metric projection
onto $K$.

The following classical properties of the projection operator $P_{K}$ are very
useful.

######  Lemma 2.2 ([1, Corollary 4.18]).

Let $K$ be a nonempty, closed and convex subset of $\mathcal{H}$.

  1. (1)

For every $x\in\mathcal{H},$ $P_{K}(x)$ is the unique element of $K$ which
satisfies

(2.1) $\langle P_{K}(x)-x,P_{K}(x)-y\rangle\leq 0,\text{ for every }y\in K.$

  2. (2)

The operator $P_{K}:\mathcal{H}\rightarrow K$ is firmly nonexpansive i.e.,

(2.2) $\langle
P_{K}(x)-P_{K}(y),x-y\rangle\geq\left\|P_{K}(x)-P_{K}(y)\right\|^{2},\text{
for all }x,y\in\mathcal{H}.$

In particular

(2.3) $\left\|P_{K}(x)-P_{K}(y)\right\|\leq\left\|x-y\right\|,\text{ for all
}x,y\in\mathcal{H}.$

######  Lemma 2.3 ([1, Theorem 3.13]).

Let $C$ be a closed convex and nonempty subset of $\mathcal{H}$, and
$T:C\rightarrow C$ a nonexpansive mapping. Then $F_{ix}(T)=\\{x\in
C:T(x)=x\\}$ is a closed and convex subset of $\mathcal{H}$.

######  Lemma 2.4.

Let $\lambda\in]0,2\nu].$ Then the following assertions hold true

  1. (i)

For every $x,y\in Q,$

(2.4) $\left\|(x-\lambda Ax)-(y-\lambda
Ay)\right\|^{2}\leq\left\|x-y\right\|^{2}-\lambda(2\nu-\lambda)\left\|Ax-
Ay\right\|^{2}.$

  2. (ii)

The operator $\Theta_{\lambda}:=P_{Q}\circ(I-\lambda A):Q\rightarrow Q$ is
nonexpansive and $F_{ix}(\Theta_{\lambda})=S_{VI(A,Q)}.$

  3. (iii)

$S_{VI(A,Q)}$ is a closed and convex subset of $\mathcal{H}.$

###### Proof.

(i) Let $x,y\in Q.$ A simple computation gives

$\displaystyle\left\|(x-\lambda Ax)-(y-\lambda Ay)\right\|^{2}$
$\displaystyle=\left\|x-y\right\|^{2}-2\lambda\langle Ax-
Ay,x-y\rangle+\lambda^{2}\left\|Ax-Ay\right\|^{2}$
$\displaystyle\leq\left\|x-y\right\|^{2}-\lambda(2\nu-\lambda)\left\|Ax-
Ay\right\|^{2}.$

(ii) Combining (2.3) and (2.4) yields $\Theta_{\lambda}$ is nonexpansive. Now
let $q\in Q.$ Clearly $q\in S_{VI(A,Q)}$ if and only if

$\langle q-(q-\lambda Aq),q-x\rangle\leq 0~{}\forall x\in Q,$

which, thanks to the first assertion of Lemma 2.2, is equivalent to
$q=P_{Q}(q-\lambda Aq)=\Theta_{\lambda}(q).$

The last assertion (iii) follows directly from (ii) and Lemma 2.3. ∎

The next result is a particular case of the well-known demi-closedness
principle.

######  Lemma 2.5 ([1, Corollary 4.18]).

Let $C$ be a closed convex and nonempty subset of $\mathcal{H}$, and
$T:C\rightarrow C$ a nonexpansive mapping. If $\\{x_{n}\\}$ is a sequence in
$C$ weakly converging to some $\bar{x}$ such that $x_{n}-Tx_{n}$ converges
strongly to $0$ in $\mathcal{H}$, then $\bar{x}\in F_{ix}(T).$

The last result of this section is a powerful lemma which is a generalization
due to Xu [8] of a lemma proved by Berstrekas ([3, Lemma 1.5.1])

######  Lemma 2.6.

let $\\{a_{n}\\}$ be a sequence of non negative real numbers such that:

(2.5) $a_{n+1}\leq(1-\gamma_{n})a_{n}+\gamma_{n}r_{n}+\delta_{n},\text{ }n\geq
0,$

where $\\{\gamma_{n}\\}\in[0,1]$ and $\\{r_{n}\\}$and $\\{\delta_{n}\\}$ are
three real sequences such that:

  1. (1)

$\sum_{n=0}^{+\infty}\gamma_{n}=+\infty;$

  2. (2)

$\sum_{n=0}^{+\infty}\left|\delta_{n}\right|<+\infty;$

  3. (3)

$\lim\sup_{n\rightarrow+\infty}r_{n}\leq 0.$

Then the sequence $\\{a_{n}\\}$ converges to $0.$

###### Proof.

We give here a proof different from the original one due to Xu [8]. Set
$s_{n}=\sum_{k=n}^{+\infty}\delta_{k},$ $e_{n}=a_{n}+s_{n},$ and
$\beta_{n}=\max\\{r_{n},0\\}+s_{n}.$ Using the fact that
$\delta_{n}=s_{n}-s_{n+1},$ we easily obtain from (2.5)

(2.6) $e_{n+1}\leq(1-\gamma_{n})e_{n}+\gamma_{n}\beta_{n},~{}n\geq 0.$

Let $\varepsilon>0.$ Since $\beta_{n}\rightarrow 0$ as $n\rightarrow\infty,$
there exists $n_{0}\in\mathbb{N}$ such that
$\beta_{n}\leq\frac{\varepsilon}{2}$ for every $n\geq n_{0}.$ Let us suppose
that $e_{n}\geq\varepsilon$ for every $n\geq n_{0}.$ Hence, from (2.6), we
infer that, for every $n\geq n_{0},$

$\displaystyle e_{n}-e_{n+1}$ $\displaystyle\geq$
$\displaystyle\gamma_{n}(e_{n}-\beta_{n})$ $\displaystyle\geq$
$\displaystyle\frac{\varepsilon}{2}\gamma_{n},$

which implies that $\sum_{n\geq n_{0}}\gamma_{n}<\infty.$ This is a
contradiction. Then there exists $n_{1}\geq n_{0}$ such that
$e_{n_{1}}\leq\varepsilon.$ Therefore

$\displaystyle e_{n_{1}+1}$ $\displaystyle\leq$
$\displaystyle(1-\gamma_{n_{1}})\varepsilon+\gamma_{n_{1}}\frac{\varepsilon}{2}$
$\displaystyle\leq$ $\displaystyle\varepsilon.$

And so on we get $e_{n}\leq\varepsilon$ for every $n\geq n_{1}$. Hence
$e_{n}\rightarrow 0$ as $n\rightarrow\infty,$ which clearly implies that
$a_{n}\rightarrow 0$ as $n\rightarrow\infty$ since $s_{n}\rightarrow 0$ as
$n\rightarrow\infty$. ∎

We close this section by proving that the problem (VP) has a unique solution.

######  Lemma 2.7.

The problem (VP) has a unique solution $q^{\ast}$. Moreover, $q^{\ast}$ is the
unique fixed point of the contraction $P_{\Omega}\circ
f:\Omega\rightarrow\Omega$.

###### Proof.

Let us first recall that the set $\Omega$ is nonempty, closed and convex
subset of $\mathcal{H}$. Then from the variational characterization of the
metric projection $P_{\Omega}$ (see the first assertion of Lemma 2.2), the
problem (VP) is equivalent to the identity $q^{\ast}=P_{\Omega}(f(q^{\ast}))$.
This, thanks to Banach fixed point theorem, guarantees the existence and the
uniqueness of $q^{\ast}$ since the application $P_{\Omega}\circ
f:\Omega\rightarrow\Omega$ is clearly a contraction. ∎

##  3\. The convergence of the implicit algorithm (1.7)

The following section is devoted to the proof of the strong convergence of the
implicit algorithm (1.7).

######  Theorem 3.1.

Let $a$ and $b$ be two reals such that $0<a<b<2\nu$ and let
$\lambda:]0,1[\rightarrow[a,b]$ be a mapping. Then, for every $t\in]0,1[,$
there exists a unique $x_{t}\in Q$ such that

$x_{t}=tf(x_{t})+(1-t)SP_{Q}(x_{t}-\lambda(t)Ax_{t}).$

Moreover $\\{x_{t}\\}$ converges strongly in $\mathcal{H}$ as $t\rightarrow
0^{+}$ to $q^{\ast}$ the unique solution of the variational problem (VP).

The following simple lemma, which is an immediate consequence of the second
assertion of Lemma 2.4, will be very useful in the proof of the previous
theorem and also in the proof of the main result of the next section.

######  Lemma 3.1.

Let $t\in]0,1]$ and $\mu\in[0,2\nu].$ Then the application
$T_{t,\mu}:Q\rightarrow Q$ defined by

$T_{t,\mu}(x)=tf(x)+(1-t)SP_{Q}(x-\mu Ax),$

satisfies

$\left\|T_{t,\mu}(x)-T_{t,\mu}(y)\right\|\leq(1-\sigma
t)\left\|x-y\right\|,~{}\forall x,y\in Q,$

where $\sigma=1-\rho.$

Let us start the proof of Theorem 3.1.

###### Proof.

Let $t\in]0,1].$ According to Lemma 3.1 and the classical Banach fixed point
theorem, there exists a unique $x_{t}\in Q$ such that
$x_{t}=T_{t,\lambda(t)}(x_{t}).$ Let us now prove that the family
$\\{x_{t}\\}_{0<t\leq 1}$ is bounded in $\mathcal{H}.$ Let $q\in\Omega.$ In
view of the last assertion of Lemma 2.4,

$\displaystyle T_{t,\lambda(t)}(q)$ $\displaystyle=t~{}f(q)+(1-t)Sq$ (3.1)
$\displaystyle=t~{}f(q)+(1-t)q$

for every $t\in]0,1].$ Hence, Lemma 3.1 yields

$\displaystyle\left\|x_{t}-q\right\|$
$\displaystyle\leq\left\|T_{t,\lambda(t)}(x_{t})-T_{t,\lambda(t)}(q)\right\|+t\left\|f(q)-q\right\|$
$\displaystyle\leq(1-\sigma t)\left\|x_{t}-q\right\|+t\left\|f(q)-q\right\|,$

which implies

$\sup_{0<t\leq
1}\left\|x_{t}-q\right\|\leq\frac{1}{\sigma}\left\|f(q)-q\right\|.$

Hence $\\{x_{t}\\}_{0<t\leq 1}$ is a bounded family in $\mathcal{H}.$

In the sequel, in order to simplify the notations, we will use $M$ to denote a
real constant independent of $t\in]0,1]$ that may change from line to another.
Moreover, $\varepsilon(t)$ will simply denotes a real quantity that converges
to $0$ as the variable $t$ tends to $0.$ By the way, let us notice here this
simple result that will be often implicitly used in the sequel: since
$\\{x_{t}\\}_{0<t\leq 1}$ is a bounded in $\mathcal{H}$, then for every
Lipschitz continuous function $g:Q\rightarrow\mathcal{H}$ the family
$\\{g(x_{t})\\}_{0<t\leq 1}$ is also bounded in $\mathcal{H}$.

For $t\in]0,1],$ we set $z_{t}=P_{Q}(x_{t}-\lambda(t)Ax_{t}).$ Let
$q\in\Omega.$ Clearly, by using the classical identity

(3.2) $\left\|tu+(1-t)v\right\|^{2}\leq
t\left\|u\right\|^{2}+(1-t)\left\|v\right\|^{2},\forall u,v\in\mathcal{H},$

the fact that $S$ and $P_{Q}$ are nonexpansive operators, and Lemma 2.4, we
obtain

$\displaystyle\left\|x_{t}-q\right\|^{2}$ $\displaystyle\leq
t\left\|f(x_{t})-q\right\|^{2}+(1-t)\left\|Sz_{t}-q\right\|^{2}$ (3.3)
$\displaystyle\leq tM+\left\|z_{t}-q\right\|^{2}$ $\displaystyle\leq
tM+\left\|\left(x_{t}-\lambda(t)Ax_{t}\right)-\left(q-\lambda(t)Aq\right)\right\|^{2}$
$\displaystyle\leq
tM+\left\|x_{t}-q\right\|^{2}-\lambda(t)(2\nu-\lambda(t))\left\|Ax_{t}-Aq\right\|^{2}.$

We then deduce that

(3.4) $a(b-2\nu)\left\|Ax_{t}-Aq\right\|^{2}\leq tM.$

Therefore, thanks to (2.2), we have

$\displaystyle\left\|z_{t}-q\right\|^{2}$ $\displaystyle\leq\langle
z_{t}-q,\left(x_{t}-\lambda(t)Ax_{t}\right)-\left(q-\lambda(t)Aq\right)\rangle$
$\displaystyle\leq\langle
z_{t}-q,x_{t}-q\rangle+\lambda(t)\left\|z_{t}-q\right\|\left\|Ax_{t}-Aq\right\|$
$\displaystyle=\langle z_{t}-q,x_{t}-q\rangle+\varepsilon(t)$
$\displaystyle=\frac{1}{2}\left(\left\|z_{t}-q\right\|^{2}+\left\|x_{t}-q\right\|^{2}-\left\|x_{t}-z_{t}\right\|^{2}\right)+\varepsilon(t).$

The last inequality implies

$\left\|z_{t}-q\right\|^{2}\leq\left\|x_{t}-q\right\|^{2}-\left\|x_{t}-z_{t}\right\|^{2}+2\varepsilon(t).$

Hence, by going back to the estimate (3.3), we deduce that

$\left\|x_{t}-z_{t}\right\|^{2}\leq tM+2\epsilon(t),$

which implies

(3.5) $x_{t}-z_{t}\rightarrow 0\text{ as }t\rightarrow 0^{+}.$

The last inequality in turn implies that

(3.6) $x_{t}-Sx_{t}\rightarrow 0\text{ as }t\rightarrow 0^{+}$

Indeed,

$\displaystyle\left\|x_{t}-Sx_{t}\right\|$
$\displaystyle\leq\left\|x_{t}-Sz_{t}\right\|+\left\|Sx_{t}-Sz_{t}\right\|$
$\displaystyle=\left\|T_{t,\lambda(t)}(x_{t})-Sz_{t}\right\|+\left\|Sx_{t}-Sz_{t}\right\|$
$\displaystyle\leq t\left\|f(x_{t})-Sz_{t}\right\|+\left\|x_{t}-z_{t}\right\|$
$\displaystyle\leq tM+\left\|x_{t}-z_{t}\right\|.$

Now we are in position to prove the following key result:

(3.7) $\kappa:=\lim\sup_{t\rightarrow 0^{+}}\langle
f(q^{\ast})-q^{\ast},x_{t}-q^{\ast}\rangle\leq 0,$

where $q^{\ast}$ is the unique solution of the variational problem (VP).

From the definition of $\kappa,$ there exists a sequence $\\{t_{n}\\}$ in
$]0,1]$ converging to $0$ such that

$\kappa=\lim_{n\rightarrow+\infty}\langle
f(q^{\ast})-q^{\ast},x_{t_{n}}-q^{\ast}\rangle.$

On the other hand, since the family $\\{x_{t_{n}}\\}_{0<t\leq 1}$ is a bounded
subset of the closed and convex subset $Q$ of $\mathcal{H}$, we can assume, up
to a subsequence, that $\\{x_{t_{n}}\\}$ converges weakly in $\mathcal{H}$ to
some $x_{\infty}\in Q.$ This fact implies

$\kappa=\langle f(q^{\ast})-q^{\ast},x_{\infty}-q^{\ast}\rangle.$

Therefore, in order to prove that $\kappa\leq 0,$ we just need to verify that
$x_{\infty}\in\Omega.$ Firstly, from Lemma 2.5 and (3.6), we have
$x_{\infty}\in F_{ix}(S).$ Secondly, up to a subsequence, we can assume that
the real sequence $\\{\lambda_{t_{n}}\\}$ converges to some real
$\lambda^{\ast}$ which belongs to $]0,2\nu[.$ Let
$\Theta_{\lambda^{\ast}}=P_{Q}\circ(I-\lambda^{\ast}A)$ be the nonexpansive
operator introduced in Lemma 2.5. Since
$z_{n}=\Theta_{\lambda_{n}}(x_{t_{n}}),$ we have

$\displaystyle\left\|x_{t_{n}}-\Theta_{\lambda^{\ast}}(x_{t_{n}})\right\|$
$\displaystyle\leq\left\|x_{t_{n}}-z_{t_{n}}\right\|+\left\|\Theta_{\lambda_{n}}(x_{t_{n}})-\Theta_{\lambda^{\ast}}(x_{t_{n}})\right\|$
$\displaystyle\leq\left\|x_{t_{n}}-z_{t_{n}}\right\|+\left|\lambda_{t_{n}}-\lambda^{\ast}\right|\left\|Ax_{t_{n}}\right\|$
$\displaystyle\leq\left\|x_{t_{n}}-z_{t_{n}}\right\|+\left|\lambda_{t_{n}}-\lambda^{\ast}\right|M.$

Hence, by combining (3.5) and Lemma 2.5, we deduce that $x_{\infty}$ is a
fixed point of $\Theta_{\lambda^{\ast}}.$ Thus, thanks to the second assertion
of Lemma 2.4, we deduce that $x_{\infty}\in VI(A,Q).$ The claim (3.7) is then
proved.

Let us finally prove that $x_{t}\rightarrow q^{\ast}$ in $\mathcal{H}$ as $t$
goes to $0^{+}.$ Let $t\in]0,1].$ First, from the identity (3.1), we have

$x_{t}-q^{\ast}=u+v,$

with

$\displaystyle u$
$\displaystyle=T_{t,\lambda(t)}(x_{t})-T_{t,\lambda(t)}\left(q^{\ast}\right),$
$\displaystyle v$ $\displaystyle=t(f(q^{\ast})-q^{\ast}).$

Hence, by applying the inequality

$\left\|u+v\right\|^{2}\leq\left\|u\right\|^{2}+2\langle v,u+v\rangle$

and Lemma 3.1, we get the inequality

$\left\|x_{t}-q^{\ast}\right\|^{2}\leq(1-\sigma
t)^{2}\left\|x_{t}-q^{\ast}\right\|^{2}+2t\langle
f(q^{\ast})-q^{\ast},x_{t}-q^{\ast}\rangle$

which implies

$\displaystyle\left\|x_{t}-q^{\ast}\right\|^{2}$
$\displaystyle\leq\frac{\sigma
t}{2}\left\|x_{t}-q^{\ast}\right\|^{2}+\frac{1}{\sigma}\langle
f(q^{\ast})-q^{\ast},x_{t}-q^{\ast}\rangle$ $\displaystyle\leq
tM+\frac{1}{\sigma}\langle f(q^{\ast})-q^{\ast},x_{t}-q^{\ast}\rangle.$

Hence, by letting $t\rightarrow 0^{+}$ and using (3.7), we obtain the desired
result. ∎

##  4\. The convergence of the explicit algorithm (1.6).

In this section, we study the strong convergence property of the process
(1.6). We prove the following theorem.

######  Theorem 4.1.

Let $\\{\alpha_{n}\\}\in]0,1]$ and $\\{\lambda_{n}\\}\in[0,2\nu]$ two real
sequences such that:

  1. (i)

$\alpha_{n}\rightarrow 0$ and $\sum_{n=0}^{+\infty}\alpha_{n}=+\infty$

  2. (ii)

$0<\lim\inf_{n\rightarrow+\infty}\lambda_{n}\leq\lim\sup_{n\rightarrow+\infty}\lambda_{n}<2\nu.$

  3. (iii)

$\frac{\alpha_{n+1}-\alpha_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\alpha_{n+1}-\alpha_{n}\right|<\infty.$

  4. (iv)

$\frac{\lambda_{n+1}-\lambda_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\lambda_{n+1}-\lambda_{n}\right|<\infty.$

Then for every initial data $x_{1}\in Q$, the sequence $\\{x_{n}\\}$ generated
by the iterative process

$x_{n+1}=\alpha_{n}f(x_{n})+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n}),~{}n\geq
1,$

converges strongly in $\mathcal{H}$ to $q^{\ast}$ the unique solution of the
variational inequality problem (VP).

###### Proof.

Since we are only interested on the asymptotic behavior of the sequence
$\\{x_{n}\\},$ we can replace hypothesis (ii) by the stronger one: there exist
two real $a$ and $b$ in $]0,2\nu[$ such that the sequence $\\{\lambda_{n}\\}$
is in $[a,b].$

For every $n\in\mathbb{N},$ we set $T_{n}:=T_{\alpha_{n},\lambda_{n}}$ where
$T_{\alpha_{n},\lambda_{n}}$ is the application defined by Lemma 3.1. First,
we will prove that the sequence $\\{x_{n}\\}$ is bounded in $\mathcal{H}.$ Let
$q\in\Omega.$ Thanks to the identity (3.1) and Lemma 3.1, we have

$\displaystyle\left\|x_{n+1}-q\right\|$
$\displaystyle\leq\left\|T_{n}(x_{n})-T_{n}(q)\right\|+\alpha_{n}\left\|f(q)-q\right\|$
$\displaystyle\leq(1-\sigma\alpha_{n})\left\|x_{n}-q\right\|+\alpha_{n}\left\|f(q)-q\right\|$
$\displaystyle\leq\max\\{\left\|x_{n}-q\right\|,\frac{1}{\sigma}\left\|f(q)-q\right\|\\}.$

Hence, we deduce by induction that

$\left\|x_{n}-q\right\|\leq\max\\{\left\|x_{0}-q\right\|,\frac{1}{\sigma}\left\|f(q)-q\right\|\\},\forall
n\in\mathbb{N}.$

Therefore $\\{x_{n}\\}$ is bounded in $\mathcal{H}.$ Hence, for every
Lipschitz function $g:Q\rightarrow\mathcal{H},$ the sequence $\\{g(x_{n})\\}$
is also bounded in $\mathcal{H}.$

From hereon, as we have done in the proof of Theorem 3.1, $M$ will denotes a
constant independent of $n$ and $\\{\varepsilon_{n}\\}$ a real sequence that
converges to $0.$ $M$ and $\\{\varepsilon_{n}\\}$ may change from line to an
other.

Let us now show that the sequence $\\{\Delta x_{n}=x_{n+1}-x_{n}\\}$ converges
strongly to $0.$ For every $n\in\mathbb{N},$ we clearly have

$\displaystyle\left\|\Delta x_{n}\right\|$
$\displaystyle\leq\left\|T_{n}(x_{n})-T_{n}(x_{n-1})\right\|+\left\|T_{n}(x_{n-1})-T_{n-1}(x_{n-1})\right\|$
$\displaystyle\leq(1-\sigma\alpha_{n})\left\|\Delta
x_{n-1}\right\|+M\left[\left|\Delta\alpha_{n-1}\right|+\left|\Delta\lambda_{n-1}\right|\right],$

where

$\Delta\alpha_{n}=\alpha_{n+1}-\alpha_{n},$

and

$\Delta\lambda_{n}=\lambda_{n+1}-\lambda_{n}.$

Hence, by applying Lemma 2.6, we deduce that

(4.1) $\left\|\Delta x_{n}\right\|\rightarrow 0\text{ as }n\rightarrow\infty.$

For every $n\in\mathbb{N},$ we set $z_{n}=P_{Q}(x_{n}-\lambda_{n}Ax_{n}).$ Let
$q\in\Omega.$ As we have proceeded in the proof of Theorem 3.1, by using the
classical identity (3.2) with $t=\alpha_{n}$, the fact that $S$ and $P_{Q}$
are nonexpansive operators, and Lemma 2.4, we get

$\displaystyle\left\|x_{n+1}-q\right\|^{2}$
$\displaystyle\leq\alpha_{n}\left\|f(x_{n})-q\right\|^{2}+(1-\alpha_{n})\left\|Sz_{n}-q\right\|^{2}$
(4.2) $\displaystyle\leq\varepsilon_{n}+\left\|z_{n}-q\right\|^{2}$
$\displaystyle\leq\varepsilon_{n}+\left\|\left(x_{n}-\lambda_{n}Ax_{n}\right)-\left(q-\lambda_{n}Aq\right)\right\|^{2}$
$\displaystyle\leq\varepsilon_{n}+\left\|x_{n}-q\right\|^{2}-\lambda_{n}(2\nu-\lambda_{n})\left\|Ax_{n}-Aq\right\|^{2}.$

Therefore, we have

$\displaystyle a(2\nu-b)\left\|Ax_{n}-Aq\right\|^{2}$
$\displaystyle\leq\varepsilon_{n}+\left\|x_{n}-q\right\|^{2}-\left\|x_{n+1}-q\right\|^{2}$
$\displaystyle=\varepsilon_{n}-\langle\Delta x_{n},x_{n+1}+x_{n}-2q\rangle$
$\displaystyle\leq\varepsilon_{n}+\left\|\Delta
x_{n}\right\|\left\|x_{n+1}+x_{n}-2q\right\|$
$\displaystyle\leq\varepsilon_{n}+M\left\|\Delta x_{n}\right\|.$

Hence, thanks to (4.1), we deduce that

(4.3) $Ax_{n}-Aq\rightarrow 0\text{ as }n\rightarrow\infty.$

Therefore, by using the fact that the operator $P_{Q}$ is firmly nonexpansive
(see (2.2)), we get

$\displaystyle\left\|z_{n}-q\right\|^{2}$ $\displaystyle\leq\langle
z_{n}-q,\left(x_{n}-\lambda_{n}Ax_{n}\right)-\left(q-\lambda_{n}Aq\right)\rangle$
$\displaystyle\leq\langle
z_{n}-q,x_{n}-q\rangle+\lambda_{n}\left\|z_{n}-q\right\|\left\|Ax_{n}-Aq\right\|$
$\displaystyle=\langle z_{n}-q,x_{n}-q\rangle+\varepsilon_{n}$
$\displaystyle=\frac{1}{2}\left(\left\|z_{n}-q\right\|^{2}+\left\|x_{n}-q\right\|^{2}-\left\|z_{n}-x_{n}\right\|^{2}\right)+\varepsilon_{n}.$

Thus, we obtain

$\left\|z_{n}-q\right\|^{2}\leq\left\|x_{n}-q\right\|^{2}-\left\|z_{n}-x_{n}\right\|^{2}+\varepsilon_{n}.$

Inserting this inequality into (4.2) yields

$\displaystyle\left\|z_{n}-x_{n}\right\|^{2}$
$\displaystyle\leq\left\|x_{n}-q\right\|^{2}-\left\|x_{n+1}-q\right\|^{2}+\varepsilon_{n}$
$\displaystyle=-\langle\Delta x_{n},x_{n+1}+x_{n}-2q\rangle+\varepsilon_{n}$
$\displaystyle\leq M\left\|\Delta x_{n}\right\|+\varepsilon_{n}.$

Hence, by using (4.1), we deduce that

$x_{n}-z_{n}\rightarrow 0\text{ as }n\rightarrow\infty.$

Therefore, by proceeding exactly as in the proof of Theorem 3.1, we first
infer that

$x_{n}-Sx_{n}\rightarrow 0\text{ as }n\rightarrow\infty,$

then we deduce the key result:

(4.4) $\lim\sup_{n\rightarrow\infty}\langle
f(q^{\ast})-q^{\ast},x_{n}-q^{\ast}\rangle\leq 0.$

Let us finally prove that the sequence $\\{x_{n}\\}$ converges strongly in
$\mathcal{H}$ to $q^{\ast}.$ For every $n\in\mathbb{N},$

$x_{n+1}-q^{\ast}=T_{n}(x_{n})-T_{n}(q^{\ast})+\alpha_{n}(f(q^{\ast})-q^{\ast}).$

Hence, by using the inequality

$\left\|u+v\right\|^{2}\leq\left\|u\right\|^{2}+2\langle v,u+v\rangle,$

with

$\displaystyle u$ $\displaystyle=T_{n}(x_{n})-T_{n}(q^{\ast}),$ $\displaystyle
v$ $\displaystyle=\alpha_{n}(f(q^{\ast})-q^{\ast}),$

we obtain

$\displaystyle\left\|x_{n+1}-q^{\ast}\right\|^{2}$
$\displaystyle\leq\left\|T_{n}(x_{n})-T_{n}(q^{\ast})\right\|^{2}+2\alpha_{n}\langle
f(q^{\ast})-q^{\ast},x_{n+1}-q^{\ast}\rangle$
$\displaystyle\leq(1-\sigma\alpha_{n})^{2}\left\|x_{n}-q^{\ast}\right\|^{2}+2\alpha_{n}\langle
f(q^{\ast})-q^{\ast},x_{n+1}-q^{\ast}\rangle$
$\displaystyle\leq(1-2\sigma\alpha_{n})\left\|x_{n}-q^{\ast}\right\|^{2}+\alpha_{n}\left[2\langle
f(q^{\ast})-q^{\ast},x_{n+1}-q^{\ast}\rangle+M\alpha_{n}\right].$

Therefore, by applying Lemma 2.6 and using the key result (4.4), we deduce
that the sequence $\\{x_{n}\\}$ converges strongly in $\mathcal{H}$ to
$q^{\ast}.$ The proof is then achieved. ∎

Now we prove that the algorithm (1.6) is stable under small perturbations.
Precisely, we establish the following result.

######  Theorem 4.2.

Let $\\{\alpha_{n}\\}\in]0,1]$, $\\{\lambda_{n}\\}\in[0,2\nu]$ and
$\\{e_{n}\\}\in\mathcal{H}$ three sequences such that:

  1. (i)

$\alpha_{n}\rightarrow 0$ and $\sum_{n=0}^{+\infty}\alpha_{n}=+\infty$

  2. (ii)

$0<\lim\inf_{n\rightarrow+\infty}\lambda_{n}\leq\lim\sup_{n\rightarrow+\infty}\lambda_{n}<2\nu.$

  3. (iii)

$\frac{\alpha_{n+1}-\alpha_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\alpha_{n+1}-\alpha_{n}\right|<\infty.$

  4. (iv)

$\frac{\lambda_{n+1}-\lambda_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\lambda_{n+1}-\lambda_{n}\right|<\infty.$

  5. (v)

$\frac{\left\|e_{n}\right\|}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left\|e_{n}\right\|<\infty.$

Then for every initial data $x_{1}\in Q$, the sequence $\\{x_{n}\\}$ generated
by the iterative process

(4.5)
$x_{n+1}=P_{Q}(\alpha_{n}f(x_{n})+(1-\alpha_{n})SP_{Q}(x_{n}-\lambda_{n}Ax_{n})+e_{n}),~{}n\geq
1,$

converges strongly in $\mathcal{H}$ to $q^{\ast}$ the unique solution of the
variational inequality problem (VP)

###### Proof.

Let $\\{y_{n}\\}$ the sequence defined by

$\left\\{\begin{array}[]{l}y_{1}=x_{1},\\\
y_{n+1}=\alpha_{n}f(y_{n})+(1-\alpha_{n})SP_{Q}(y_{n}-\lambda_{n}Ay_{n}),~{}n\geq
1.\end{array}\right.$

Since the sequence $\\{y_{n}\\}$ is in $Q,$

$\displaystyle\left\|x_{n+1}-y_{n+1}\right\|$ $\displaystyle=$
$\displaystyle\left\|x_{n+1}-P_{Q}(y_{n+1})\right\|$ $\displaystyle\leq$
$\displaystyle\left\|T_{\alpha_{n},\lambda_{n}}(x_{n})-T_{\alpha_{n},\lambda_{n}}(y_{n})\right\|+\left\|e_{n}\right\|,$

where $T_{\alpha_{n},\lambda_{n}}$ is the operator defined in Lemma 3.1.
Hence, for every $n\geq 1,$

$\left\|x_{n+1}-y_{n+1}\right\|\leq(1-\sigma\alpha_{n})\left\|x_{n}-y_{n}\right\|+\left\|e_{n}\right\|,$

where $\sigma=1-\rho.$ Therefore, by invoking Lemma 2.5., we deduce that

$\left\|x_{n}-y_{n}\right\|\rightarrow 0\text{ as }n\rightarrow\infty,$

which implies that $\\{x_{n}\\}$ converges strongly in $\mathcal{H}$ to
$q^{\ast}$ since, from Theorem 4.1, the sequence $\\{y_{n}\\}$ converges
strongly in $\mathcal{H}$ to $q^{\ast}.$ ∎

As a direct consequence of Theorem 4.2, we have the following result which
improves and generalizes ([9, Theorem 5.2]).

######  Corollary 4.1.

Let $\varphi:Q\longrightarrow\mathcal{H}$ be $C^{1}$ convex function such that
its gradient $\nabla\varphi:Q\longrightarrow\mathcal{H}$ is Lipschitz with
coefficient $L>0.$ We assume that the set $F_{ix}(S)\cap\arg\min_{Q}\varphi$
is nonempty, where $\arg\min_{Q}\varphi=\\{q\in
Q:\varphi(q)\leq\varphi(x)~{}\forall x\in Q\\}.$ Let
$\\{\alpha_{n}\\}\in]0,1]$, $\\{\lambda_{n}\\}\in[0,\frac{2}{L}]$ and
$\\{e_{n}\\}\in\mathcal{H}$ three sequences such that:

  1. (i)

$\alpha_{n}\rightarrow 0$ and $\sum_{n=0}^{+\infty}\alpha_{n}=+\infty$

  2. (ii)

$0<\lim\inf_{n\rightarrow+\infty}\lambda_{n}\leq\lim\sup_{n\rightarrow+\infty}\lambda_{n}<\frac{2}{L}.$

  3. (iii)

$\frac{\alpha_{n+1}-\alpha_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\alpha_{n+1}-\alpha_{n}\right|<\infty.$

  4. (iv)

$\frac{\lambda_{n+1}-\lambda_{n}}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left|\lambda_{n+1}-\lambda_{n}\right|<\infty$

  5. (v)

$\frac{\left\|e_{n}\right\|}{\alpha_{n}}\rightarrow 0$ or
$\sum_{n=0}^{+\infty}\left\|e_{n}\right\|<\infty.$

Then for every $z_{1}\in Q$ the sequence $\\{z_{n}\\}$ defined iteratively by

(4.6)
$z_{n+1}=P_{Q}(\alpha_{n}f(z_{n})+(1-\alpha_{n})SP_{Q}(z_{n}-\lambda_{n}\nabla\varphi(z_{n}))+e_{n})),~{}n\geq
1,$

converges strongly in $\mathcal{H}$ to $q^{\ast}$ the unique element of
$F_{ix}(S)\cap\arg\min_{Q}\varphi$ satisfying the variational inequality

(4.7) $\langle f(q^{\ast})-q^{\ast},x-q^{\ast}\rangle\leq 0$

for all $x\in F_{ix}(S)\cap\arg\min_{Q}\varphi.$

###### Proof.

The proof follows directly from Theorem 4.2. In fact, according to the famous
Baillon-Haddad Theorem ([6, Theorem 3.13]), the operator
$\nabla\varphi:Q\rightarrow$ $\mathcal{H}$ is $\frac{1}{L}$ inverse strongly
monotone and , from the classical varational characterization of constrained
convex problem solutions ([2, Theorem 3.13]), we have

$S_{VI(\nabla\varphi,Q)}=\\{q\in Q:\langle\nabla\varphi(q),x-q\rangle\geq
0~{}\forall x\in Q\\}=\arg\min_{Q}\varphi.$

∎

##  5\. Numerical experiments

In this section, we investigate through some numerical experiments the effect
of the sequence $\\{\alpha_{n}\\}$ on the rate convergence of sequences
$\\{z_{n}\\}$ generated by a particular example of the process (4.6) studied
in the previous section. Here we consider the simple case where:

  1. (1)

The Hilbert space $\mathcal{H}$ is $\mathbb{R}^{2}$ endowed with its natural
inner product $\langle x,y\rangle=x_{1}y_{1}+x_{2}y_{2}.$

  2. (2)

The closed and convex subset $Q$ is given by:
$Q=\\{x=(x_{1},x_{2})^{t}\in\mathbb{R}^{2}:x_{1},x_{2}\geq 0\\}.$

  3. (3)

The contraction mapping $f:Q\rightarrow Q$ is defined by
$f(x)=\frac{1}{2}(5+\cos(x_{1}+x_{2}),6-\sin(x_{1}+x_{2}))^{t}$ for all
$x=(x_{1},x_{2})^{t}\in Q.$ Using the mean value theorem, one can easily
verify that $f$ is Lipschitz continuous function with Lipschitz constant
$\rho\leq\frac{\sqrt{2}}{2}.$

  4. (4)

The non expansive mapping $S:Q\rightarrow Q$ is the identity.

  5. (5)

The convex function $\varphi:Q\rightarrow\mathbb{R}$ is defined by:
$\varphi(x)=\frac{1}{2}\left\|Bx-b\right\|^{2}$ where

$B=\left(\begin{array}[]{cc}1&1\\\
2&2\end{array}\right),~{}b=\left(\begin{array}[]{c}3\\\ 5\end{array}\right).$

A simple calculation yields

$\nabla\varphi(x)=B^{t}(Bx-b)=\left(\begin{array}[]{c}5x_{1}+5x_{2}-13\\\
5x_{1}+5x_{2}-13\end{array}\right),~{}\forall x=(x_{1},x_{2})^{t}\in Q.$

Hence $\nabla\varphi$ is Lipschitz continuous with Lipschitz constant $L=10.$
Moreover,

$\Omega=F_{ix}(S)\cap\arg\min_{Q}\varphi=\\{x=(x_{1},x_{2})^{t}\in
Q:x_{1}+x_{2}=2.6\\}=\Delta_{2.6}^{2}$

where, for $a>0$ and $n\in\mathbb{N},$

$\Delta_{a}^{n}=\\{x=(x_{1},\cdots,x_{n})^{t}\in\mathbb{R}^{n}:x_{1},\cdots,x_{n}\geq
0,~{}x_{1}+\cdots+x_{n}=a\\}.$

Let us notice that, by using KKT Theorem, one can easily verify that the
projection onto $\Delta_{a}^{n}$ is given by

$P_{\Delta_{a}^{n}}(x)=(\max(x_{1}-\alpha(x),0),\cdots,\max(x_{n}-\alpha(x),0))$

for every $x=(x_{1},\cdots,x_{n})^{t}\in\mathbb{R}^{n},$ where $\alpha(x)$ is
the unique real solution $\alpha$ of the equation
$\sum_{k=1}^{n}\max(x_{k}-\alpha,0)=a.$ Hence a simple routine on Matlab,
using the fact that the unique solution $q^{\ast}$ to the variational problem
(4.7) is the fixed point of the contraction $P_{\Omega}\circ f:Q\rightarrow
Q,$ provides a precise numerical approximation of $q^{\ast}:$

$q^{\ast}\simeq(0.9647,1.6353)^{t}.$

  6. (6)

The sequence $\\{\lambda_{k}\\}$ is constant and equal to $\frac{1}{L}=0.1.$

  7. (7)

The sequence $\\{\theta_{k}\\}$ is given by $\theta_{k}=\frac{1}{k^{\theta}}$
where $\theta$ is a constant which belongs to $]0,1].$

  8. (8)

The perturbation term $\\{e_{k}\\}$ is given by $e_{k}=\frac{X_{k}}{k^{2}}$
where $\\{X_{k}\\}$ is a sequence of independent random variables such that
every $X_{k}$ is uniform on the square $[-1,1]\times[-1,1].$

  9. (9)

The initial value is $z_{1}=\left(\begin{array}[]{c}2\\\ 3\end{array}\right).$

  10. (10)

$N_{\max}$ the maximal number of iterations $k$ is $N_{\max}=6000.$

We aim to study numerically the relation between $\theta$ and the rate of
convergence of the sequence $\\{z_{k}\\}$ to $q^{\ast}.$ We can summarize our
numerical results in the following two points:

(A): The convergence of the sequence $\\{z_{k}\\}$ to $q^{\ast}$ is very slow
for small values of the parameter $\theta$ as the following table shows:

$\theta$ | $\min_{k\leq N_{\max}}\frac{\left\|z_{k}-q^{\ast}\right\|}{\left\|q^{\ast}\right\|}$
---|---
$0.1$ | 0.4774
$0.2$ | 0.1810
$0.3$ | 0.0742
$0.4$ | 0.0309
Table 1. Slow convergence of $\\{z_{k}\\}$ for small values of $\theta$

(B) : The convergence of $\\{z_{k}\\}$ to $q^{\ast}$ is more clear if $\theta$
is close to $1$ as it is shown by the following two tables:

$\theta$ | $\min_{k\leq N_{\max}}\frac{\left\|z_{k}-q^{\ast}\right\|}{\left\|q^{\ast}\right\|}$
---|---
$0.6$ | 0.0055
$0.8$ | 0.0010
$0.9$ | 0.0005
$1.0$ | 0.0008
Table 2. Convergence of $\\{z_{k}\\}$ for some values of $\theta$ closed to 1

The second table indicates, for some values of $\varepsilon>0$ and $\theta,$
$N(\varepsilon,\theta)$ the first iteration $k\leq N_{\max}$ such that
$\frac{\left\|z_{k}-q^{\ast}\right\|}{\left\|q^{\ast}\right\|}\leq\varepsilon.$

$\varepsilon$ | $\theta=0.6$ | $\theta=0.8$ | $\theta=0.9$ | $\theta=1.0$
---|---|---|---|---
0.5 | 6 | 5 | 4 | 4
0.10 | 53 | 23 | 14 | 17
0.05 | 158 | 56 | 36 | 42
0.01 | 2200 | 372 | 249 | 314
0.005 | ND | 854 | 533 | 716
0.001 | ND | ND | 2989 | 4742
Table 3. $N(\varepsilon,\theta)$

Remark: $N(\varepsilon,\theta)=$ ND (Not Defined) means that
$\frac{\left\|z_{k}-q^{\ast}\right\|}{\left\|q^{\ast}\right\|}>\varepsilon$
for all the iterations $k\leq N_{\max}.$

Finally, the schema (Figure 1) shows the convergence of $\\{z_{k}\\}$ to
$q^{\ast}$ for some values of the parameter $\theta$ close to $1$.

Figure 1. the effect of $\theta$ on the convergence of the algorithm (4.6)

## References

  * [1] H.H. Bauschke, P.L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, CMS Books in Mathematics, Springer, New York, (2011).
  * [2] O. Guler, Foundations of optimization, Graduate Texts in Mathematics 258, SpringerScience+Bisiness Media, LLC 2010.
  * [3] D.P. Bertsekas, Nonlinear programming, Athena Scientific, Belmont, Massachusetts, 1995.
  * [4] H. Iiduka, W. Takahashi, Strong convergence theorems for nonexpansive mapping and inverse-strongly monotone mappings, Nonlinear Anal., 61 (2005), 341-350.
  * [5] A. Moudafi, Viscosity approximation methods for fixed points problemes, J. Math. Anal. Appl. 241 (2000), 46-55.
  * [6] J. Peypoquet, Convex optimization in normed spaces Theory, Methods, and Examples, Springer Briefs in Optimization.
  * [7] W. Takahashi, M. Toyoda, Weak convergence theorems for noexpansive mappings and monotone mapping, J. Optim. Theory Appl., 118 (2003), 417-428.
  * [8] H.K Xu, Iterative algorithms or nonlinear operators, J. Lond. Math. Soc. 65 (2002), 240-256.
  * [9] H.K Xu, Avearged mapping and the gradient-projection algorithm, J. Optimi. Theory Appl. 150 (2011), 360-378.
  * [10] Y.Y. Yao, YC. Liou, C.P. Chen, Algorithms construction for nonexpansive mapping and inverse-strongly monotone mapping, Taiwanese J. Math. 15 (5) (2011), 1979-1998.