Graphical Ekeland’s principle for equilibrium problems

Abstract

In this paper, we give a graphical version of the Ekeland’s variational principle (EVP) for equilibrium problems on weighted graphs. This version generalizes and includes other equilibrium types of EVP such as optimization, saddle point, fixed point and variational inequality ones. We also weaken the conditions on the class of bifunctions for which the variational principle holds by replacing the strong triangle inequality property by a below approximation of the bifunctions.

1. Introduction

Ekeland’s variational principle 10111618 is a minimization theorem for a bounded from below proper lower semicontinuous function on complete metric spaces. This result provides one of the most powerful tools in nonlinear analysis, optimization, geometry of Banach spaces, economics, control theory, sensitivity, fixed point theory, and game theory 34591213141519. It is used to approximate the solution through a simple minimization idea. Motivated by its wide applications, many authors have been interested in extending Ekeland’s variational principle to, for instance, weighted graphs 2 and equilibrium problems on complete metric spaces 8. Inspired by these two papers, we aim to get a generalized form of the Ekeland’s variational principle for equilibrium problems on weighted graphs endowed with a metric distance.

First we start by recalling the equilibrium problem.

Definition 1.1 (617).

Let $(X,d)$ be a metric space and $M$ be a nonempty subset of $X$. Let $F: M\times M \rightarrow \mathbb{R}$ be a bifunction such that $F(x,x)=0$ for all $x\in M$. The problem of finding $\overline{x}\in M$ such that

$$\begin{equation*} F(\overline{x},y)\geq 0, \; \text{for all}\; y\in M, \end{equation*}$$

is called an equilibrium problem for $F(\cdot , \cdot )$.

It is clear that the concept of an equilibrium problem as defined in the above definition is not dependent on the distance $d(\cdot ,\cdot )$. Therefore, we may rephrase the above definition in a more abstract form to obtain the following:

Definition 1.2.

Let $M$ be a nonempty set. Let $F: M\times M \rightarrow \mathbb{R}$ be a bifunction such that $F(x,x)=0$ for all $x\in M$. The problem of finding $\overline{x}\in M$ such that

$$\begin{equation*} F(\overline{x},y)\geq 0, \; \text{for all}\; y\in M, \end{equation*}$$

is called an equilibrium problem for $F(\cdot , \cdot )$.

It is well-known that the equilibrium problem is a unified model of several problems, namely, optimization problems, fixed point problems, variational inequality problems, saddle point problem, etc. Let us explain the relation between the equilibrium problem and the fixed point problem since it is not straighforward in the nonlinear metric setting.

Example 1.3.

Let $M$ be a nonempty subset of a metric space $(X,d)$, and $f: M\rightarrow M$ be a given map. The fixed point problem is to find $\overline{x}\in M$ such that $f(\overline{x})=\overline{x}$. Consider the bifunction

$$\begin{equation*} F(x,y)= d^2(y,f(x)) -d^2(x,f(x)) - d^2(y,x),\;\; \text{for any $x, y \in M$}. \end{equation*}$$

Note that we have $F(x,x) = 0$, for any $x \in M$. Moreover if $f(\overline{x}) = \overline{x}$, then we have $F(y, \overline{x}) = 0$, for any $y \in M$. Conversely, assume that $\overline{x}$ is a solution of the equilibrium problem, i.e., $F(\overline{x}, y) \geq 0$, for any $y \in M$. Then we have

$$\begin{equation*} d^2(y,f(\overline{x})) -d^2(\overline{x},f(\overline{x})) - d^2(y,\overline{x}) \geq 0 \end{equation*}$$

which gives $d^2(y,f(\overline{x})) \geq d^2(\overline{x},f(\overline{x})) + d^2(y,\overline{x})$, for any $y \in M$. If we take $y = f(\overline{x})$, we get $d^2(\overline{x},f(\overline{x})) \leq 0$ which gives $f(\overline{x}) = \overline{x}$, i.e., $\overline{x}$ is a fixed point of $f$.

2. Preliminaries

In 1993, W. Oettli and M. Théra introduced the Ekeland’s variational principle for equilibrium problems 17. In 2005, the same result was reproved by using Crandall’s method 7.

Theorem 2.1.

Let $(X,d)$ be a complete metric space and $M$ be a nonempty closed subset of $X$. Let $F: M\times M \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

$F(x, x) = 0$, for every $x\in M$;

(ii)

$F(x,y)\leq F(x,z)+F(z,y)$, for every $x,y,z\in M$;

(iii)

$F(x,.)$ is lower bounded and lower semicontinuous, for every $x\in M$.

Then, for every $\varepsilon \ > 0$ and for every $x_0\in M$ there exists $\overline{x}\in M$ such that

(a)

$F(x_0,\overline{x})+\varepsilon \ d(x_0,\overline{x})\leq 0$;

(b)

$F(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for every $y\in M$ such that $y \neq \overline{x}$.

The conclusion (b) leads to the concept of approximate solution for an equilibrium problem which was introduced in 7 as follows.

Definition 2.2.

Let $M$ be a nonempty subset of a metric space $(X,d)$. Let $F: M\times M \rightarrow \mathbb{R}$ be a bifunction and $\varepsilon \ >0$ be given. The element $\overline{x}\in M$ is said to be an $\varepsilon$-equilibrium element of $F$ if

$$\begin{equation} F(\overline{x},y)\geq -\varepsilon \ d(\overline{x},y), \; \text{for every}\; y\in M. {\tag{2.1}} \end{equation}$$

It is called a strict $\varepsilon$-equilibrium element of $F$ if the inequality 2.1 is strict for every $y\neq \overline{x}$.

Remark 2.3.

(i)

Notice that item (b) of Theorem 2.1 gives the existence of a strict $\varepsilon$-equilibrium element, for every $\varepsilon \ >0$.

(ii)

By conditions (i) & (ii) of Theorem 2.1, we have $F(\overline{x},x_0)\geq -F(x_0, \overline{x})$ and hence by (a)$$\begin{equation*} F(\overline{x},x_0)\geq \varepsilon \ d(\overline{x},x_0), \end{equation*}$$

localizing, in a certain sense, the position of $\overline{x}$.

(iii)

Assume $\inf _{x\in M}F(x_0,x) \in (-\infty , 0)$. Let $\lambda \coloneq - \inf _{x\in M}F(x_0,x)$. Fix $\varepsilon > 0$. Using Theorem 2.1, there exists $\overline{x}\in M$ such that$$\begin{equation*} \left\{\begin{array}{ll} F(x_0,\overline{x})+\varepsilon \ d(x_0,\overline{x})\leq 0,&\\&\\F(\overline{x},x)+\varepsilon \ d(\overline{x},x) > 0, \; \text{for any $x \neq \overline{x}$}.& \end{array}\right. \end{equation*}$$

The first inequality implies that $F(x_0,\overline{x})\leq 0$, and since $-F(x_0,\overline{x})\leq \lambda$, we have$$\begin{equation*} d(x_0,\overline{x})\leq \frac{\lambda }{\varepsilon } \ . \end{equation*}$$

(iv)

In the particular case, where $F(x, y) = \phi (y) - \phi (x)$ and $\phi : M\rightarrow \mathbb{R}$ a lower semi-continuous and bounded below, Theorem 2.1 turns into the well known Ekeland’s variational principle.

The following result is easy to obtain from Theorem 2.1.

Theorem 2.4.

Let $(X,d)$ be a complete metric space, $M$ be a nonempty closed subset of $X$ and $F: M\times M \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

$F(x, x) = 0$, for every $x\in M$;

(ii)

$F(x,y)\leq F(x,z)+F(z,y)$, for every $x,y,z\in M$;

(iii)

$F(x,.)$ is lower bounded and lower semicontinuous, for every $x\in M$.

Let $G: M\times M \rightarrow \mathbb{R}$ be a bifunction such that $F(x.y) \leq G(x,y)$, for any $x, y \in M$. Then for any $\varepsilon \ > 0$ and $x_0\in M$, there exists $\overline{x}\in M$ such that

(a)

$F(x_0, \overline{x}) \leq -\varepsilon \ d(x_0,\overline{x})$;

(b)

$G(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for any $y\in M$ such that $y \neq \overline{x}$.

As a corollary, we obtain the main result of Castellani and Giuli 8, who claimed that they obtained a more general result than Theorem 2.1.

Corollary 2.5.

Let $(X,d)$ be a complete metric space, $M$ be a nonempty closed subset of $X$ and $F: M\times M \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

there exists $\phi : M\rightarrow \mathbb{R}$ such that$$\begin{equation*} F(x, y) \geq \phi (y) - \phi (x),\; \text{for every}\; x,y\in M; \end{equation*}$$

(ii)

$\phi$ is lower bounded and lower semicontinuous.

Then, for any $\varepsilon \ > 0$ and $x_0\in M$, there exists $\overline{x}\in M$ such that:

(a)

$\phi (\overline{x})\leq \phi (x_0)-\varepsilon \ d(x_0,\overline{x})$;

(b)

$F(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for any $y\in M$ such that $y \neq \overline{x}$.

3. Graphical Ekeland’s principle for equilibrium problems

In this section, we gave the main result of our work. Let us start with the following basic notations and definitions from graph theory that are needed in the sequel.

Definition 3.1.

A directed graph $G$ is an ordered triple $(V(G),E(G),I_G)$ where $V(G)$ is a nonempty set called the set of vertices of $G$, $E(G)$ is a possibly empty set, called the set of edges of $G$ and $I_G$ is an incidence map that associates with each edge of $G$ an ordered pair of vertices of $G$.

(i)

If $e$ is an edge of $G$, and $I_G(e)=(u,u)$ for some $u\in V(G)$, then $e$ is called a loop. If $E(G)$ contains all the loops, then $G$ is said to be reflexive.

(ii)

An oriented graph $G$ is a directed graph with the property that whenever $(u,v)\in E(G)$, then $(v,u)\notin E(G)$.

(iii)

A circuit is a nonempty trail in which the first vertex is equal to the last vertex. A cycle is a circuit in which the only repeated vertex is the first/last vertex. A graph without cycles is called an acyclic graph.

(iv)

A graph $G$ is transitive if $(u,w) \in E(G)$ whenever $(u,v) \in E(G)$ and $(v,w) \in E(G)$, for any $u, v, w \in V(G)$.

(v)

A directed graph $G$ in which each edge $(u,v)$ is given a numerical weight $w(u,v)$ is called a weighted digraph.

(vi)

Let $G = (V(G), E(G),d)$ be a weighted digraph. We say that a mapping $T: V(G) \rightarrow V(G)$ is $G$-monotone if for any $x,y\in V(G)$ we have$$\begin{equation*} (x,y)\in E(G) \Rightarrow (T(x),T(y))\in E(G). \end{equation*}$$

Throughout, we only consider digraphs without multi-edges. We will only consider weighted digraphs in which the weight is a distance function, e.i., $w(\cdot ,\cdot ) = d(\cdot ,\cdot )$. Definition 3.2 which was initially introduced in 1 for partial orders will be needed.

Definition 3.2 (2).

Let $G = (V(G), E(G),d)$ be a weighted digraph. We say that $G$ satisfies the property (OSC) if and only if for any convergent $G$-decreasing sequence $\{x_n\}$ in $V(G)$, i.e. $(x_{n+1}, x_n) \in E(G)$, for all $n \in \mathbb{N}$, we have

(i)

$(\lim _{n \rightarrow \infty } x_n, x_m) \in E(G)$, for any $m \in \mathbb{N}$, and

(ii)

$(x, \lim _{n \rightarrow \infty } x_n) \in E(G)$ whenever $(x, x_n) \in E(G)$, for any $n \in \mathbb{N}$.

Next we give the graphical version of the Ekeland’s variational principle for equilibrium problems on weighted graphs.

Theorem 3.3.

Let $G = (V(G), E(G),d)$ be a reflexive transitive acyclic weighted digraph such that $(V(G),d)$ is G-complete. Assume that $G$ satisfies Property (OSC). Let $F: V(G)\times V(G) \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

$F(x, x) = 0$ for every $x\in V(G)$;

(ii)

$F(x,y)\leq F(x,z)+F(z,y)$ for every $x,y,z\in V(G)$ such that $(y,x) \in E(G)$ and $(z,y) \in E(G)$;

(iii)

$F(x,.)$ is lower bounded and G-lower semicontinuous, for every $x\in V(G)$;

Then, for every $\varepsilon \ >0$ and $x_0 \in V(G)$, there exists $\overline{x} \in V(G)$ such that $(\overline{x}, x_0) \in E(G)$ and

(a)

$F(x_0,\overline{x})+\varepsilon \ d(x_0,\overline{x})\leq 0$;

(b)

$F(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for every $y \in V(G)\setminus \{\overline{x}\}$ with $(y, \overline{x})\in E(G)$.

Proof.

By replacing the distance $d(\cdot ,\cdot )$ by the equivalent distance $\varepsilon \ d(\cdot , \cdot )$, we may assume $\varepsilon = 1$ without loss of any generality. Let $x \in V(G)$. Set

$$\begin{equation*} A(x) = \{y \in V(G);\; (y,x) \in E(G)\; and\; F(x,y) + d(x,y) \leq 0\}. \end{equation*}$$

Since $G$ is reflexive and the property (i), we get $x \in A(x)$ which implies $A(x)$ is not empty, for any $x \in V(G)$. Let $y \in A(x)$ and $z \in A(y)$. Since $G$ is transitive, we get $(z,x) \in E(G)$. Using (ii), we get

$$\begin{equation*} \begin{array}{llll} F(x,z) + d(x,z) &\leq & F(x,y) + F(y,z) + d(x,y) + d(y,z)\\& = & F(x,y) + d(x,y) + F(y,z) + d(y,z)\\& \leq & 0, \end{array} \end{equation*}$$

which implies $A(y) \subset A(z)$. Moreover, for any $x \in V(G)$, set

$$\begin{equation*} r(x) = \sup _{y \in A(x)}\ d(x,y)\;\;\; and\;\; v(x) = \inf _{y \in A(x)} F(x,y). \end{equation*}$$

Note that $v(x) > -\infty$, for any $x \in V(G)$ since $F$ is lower bounded. For any $x \in V(G)$ and $y \in A(x)$, we have $d(x,y) \leq -F(x,y)$ which implies

$$\begin{equation*} r(x) = \sup _{y \in A(x)}\ d(x,y) \leq \sup _{y \in A(x)} -F(x,y) = - \inf _{y \in A(x)} F(x,y) = -v(x). \end{equation*}$$

Fix $x_0 \in V(G)$. By definition of $v(x_0)$, there exists $x_1 \in A(x_0)$ such that

$$\begin{equation*} F(x_0,x_1) \leq v(x_0) + \frac{1}{2} \ . \end{equation*}$$

By induction, we construct a sequence $\{x_n\}$ such that $x_{n+1} \in A(x_n)$ and

$$\begin{equation*} F(x_n,x_{n+1}) \leq v(x_n) + \frac{1}{2^{n+1}} \ , \end{equation*}$$

for any $n \in \mathbb{N}$. Fix $n \in \mathbb{N}$. Since $A(x_{n+1} \subset A(x_n)$, we get

$$\begin{equation*} \inf _{y \in A(x_n)}\ F(x_{n+1},y) \leq \inf _{y \in A(x_{n+1})}\ F(x_{n+1},y) = v(x_{n+1}). \end{equation*}$$

For any $y \in V(G)$, (ii) implies $F(x_n, y) \leq F(x_n, x_{n+1}) + F(x_{n+1}, y)$ which gives

$$\begin{equation*} F(x_n, y) - F(x_n, x_{n+1}) \leq F(x_{n+1}, y). \end{equation*}$$

Hence

$$\begin{equation*} \begin{array}{lll} v(x_n) - F(x_n, x_{n+1}) & = & \displaystyle \inf _{y \in A(x_n)}\ F(x_n, y) - F(x_n, x_{n+1})\\&&\\&\leq &\displaystyle \inf _{y \in A(x_n)}\ F(x_{n+1}, y) \leq v(x_{n+1}). \end{array} \end{equation*}$$

Since $F(x_n,x_{n+1}) \leq v(x_n) + \frac{1}{2^{n+1}}$, we get

$$\begin{equation*} -v(x_n) \leq - F(x_n, x_{n+1}) + \frac{1}{2^{n+1}} \leq v(x_{n+1}) - v(x_n) + \frac{1}{2^{n+1}}, \end{equation*}$$

which implies

$$\begin{equation*} 0 \leq v(x_{n+1}) + \frac{1}{2^{n+1}}. \end{equation*}$$

Therefore, we must have

$$\begin{equation*} r(x_{n+1}) \leq - v(x_{n+1}) \leq \frac{1}{2^{n+1}}. \end{equation*}$$

In particular, we have

$$\begin{equation*} d(x_n, x_{n+1}) \leq r(x_n) \leq \frac{1}{2^n}, \end{equation*}$$

which proves that $\{x_n\}$ is Cauchy. Since this sequence is G-decreasing by construction and $V(G)$ is G-complete, we conclude that $\{x_n\}$ is convergent. Set $\overline{x} = \lim _{n \longrightarrow \infty }\ x_n$. Since $G$ satisfies the property (OSC), we get $(\overline{x}, x_n) \in E(G)$. Since $F(x,\cdot )$ is G-lower semicontinuous, for any $x \in V(G)$, we conclude that

$$\begin{equation*} F(y, \overline{x}) \leq \liminf _{n \longrightarrow \infty }\ F(y, x_n), \end{equation*}$$

for any $y \in V(G)$. By construction of $\{x_n\}$, we know that $x_{n+h} \in A(x_n)$, for any $n, h \in \mathbb{N}$, which implies

$$\begin{equation*} \begin{array}{lll} F(x_n, \overline{x}) + d(x_n, \overline{x}) &\leq &\liminf _{h \longrightarrow \infty }\ F(x_n, x_{n+h}) + d(x_n, x_{n+h})\\&\leq & 0. \end{array} \end{equation*}$$

Hence $\overline{x} \in A(x_n)$, which implies $A(\overline{x}) \subset A(x_n)$, for any $n \in \mathbb{N}$. For any $y \in A(\overline{x})$ and $n \in \mathbb{N}$, we have

$$\begin{equation*} d(\overline{x}, y) \leq d(\overline{x}, x_n) + d(x_n,y) \leq 2 r(x_n) = 2 \frac{1}{2^n}. \end{equation*}$$

Therefore, we must have $A(\overline{x}) = \{\overline{x}\}$. Putting everything together, we get

$$\begin{equation*} F(x_0, \overline{x}) + d(x_0, \overline{x}) \leq 0 \end{equation*}$$

since $\overline{x} \in A(x_0)$, and for any $y \in V(G)\setminus \{\overline{x}\}$ with $(y, \overline{x})\in E(G)$, we have

$$\begin{equation*} F(\overline{x},y)+ d(\overline{x},y)>0, \end{equation*}$$

since $y \not \in A(\overline{x})$. The proof of Theorem 3.3 is complete.

■

The following result is easy to obtain from Theorem 3.3.

Theorem 3.4.

Let $G = (V(G), E(G),d)$ be a reflexive transitive acyclic weighted digraph such that $(V(G),d)$ is G-complete. Assume that $G$ satisfies Property (OSC). Let $F: V(G)\times V(G) \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

$F(x, x) = 0$, for every $x\in V(G)$;

(ii)

$F(x,y)\leq F(x,z)+F(z,y)$, for every $x,y,z\in V(G)$ such that $(y,x) \in E(G)$ and $(z,y) \in E(G)$;

(iii)

$F(x,.)$ is lower bounded and $G$-lower semicontinuous, for every $x\in V(G)$.

Let $H: V(G)\times V(G)\rightarrow \mathbb{R}$ be a bifunction such that $F(x.y) \leq H(x,y)$, for any $x, y \in V(G)$. Then for any $\varepsilon \ > 0$ and $x_0\in V(G)$, there exists $\overline{x}\in V(G)$ such that $(\overline{x}, x_0) \in E(G)$ and

(a)

$F(x_0,\overline{x})+\varepsilon \ d(x_0,\overline{x})\leq 0$;

(b)

$H(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for every $y \in V(G)\setminus \{\overline{x}\}$ with $(y, \overline{x})\in E(G)$.

As a corollary, we obtain the graphical version of Corollary 2.5 which is a major improvement to the main result of 2.

Corollary 3.5.

Let $G = (V(G), E(G),d)$ be a reflexive transitive acyclic weighted digraph such that $(V(G),d)$ is G-complete. Assume that $G$ satisfies Property (OSC). Let $F: V(G)\times V(G) \rightarrow \mathbb{R}$ be a bifunction. Assume that the following conditions hold:

(i)

there exists $\phi : V(G) \rightarrow \mathbb{R}$ such that$$\begin{equation*} F(x, y) \geq \phi (x) - \phi (y),\; \text{for every}\; x,y\in V(G); \end{equation*}$$

(ii)

$\phi$ is lower bounded and $G$-lower semicontinuous.

Then, for every $\varepsilon \ >0$ and $x_0 \in V(G)$, there exists $\overline{x} \in V(G)$ such that $(\overline{x}, x_0) \in E(G)$ and

(a)

$\phi (\overline{x})\leq \phi (x_0)-\varepsilon \ d(x_0,\overline{x})$;

(b)

$F(\overline{x},y)+\varepsilon \ d(\overline{x},y)>0$, for any $y\in V(G)$ such that $y \neq \overline{x}$.

Example 3.6.

Consider the indicator function

$$\begin{equation*} h(x)=\left\{ \begin{array}{ll} 0\;, & \text{for $x\in \mathbb{Q}$}; \\1\;, & \text{for $x\in \mathbb{R}\setminus \mathbb{Q}$.} \end{array} \right. \end{equation*}$$

Let $G$ be the graph with vertex set $V(G)=[1,\infty )$ where two vertices $x,y$ are adjacent (connected by an edge) if either both are rational numbers or both are irrational numbers. The bifunction $F: [1,\infty )\rightarrow \mathbb{R}$ defined by

$$\begin{equation*} F(x,y)=\frac{1}{y}-\frac{1}{x}+ h(y-x) \end{equation*}$$

satisfies the triangle inequality property and all the other assumptions of Theorem 3.4 except the lower semicontinuity of $F(x, .)$, for any fixed $x \in [1,\infty )$. Nevertheless the condition (i) of Corollary 3.5 is verified using the lower bounded continuous function $\phi (t) = 1/t$. Therefore the equilibrium problem for $F(\cdot ,\cdot )$ admits approximate solutions.