Chapter 15
Variational Inequality Problems
and Algorithms
15.1 Monotone Functions ............................................. 213
15.2 The Split-Feasibility Problem .................................... 214
15.3 The Variational Inequality Problem ............................. 215
15.4 Korpelevich’s Method for the VIP ............................... 216
15.4.1 The Special Case of C = R
J
............................ 216
15.4.2 The General Case ........................................ 218
15.5 On Some Algorithms of Noor .................................... 220
15.5.1 A Conjecture ............................................ 220
15.6 Split Variational Inequality Problems ........................... 221
15.7 Saddle Points ..................................................... 223
15.7.1 Notation and Basic Facts ................................ 224
15.7.2 The Saddle-Point Problem as a VIP .................... 224
15.7.3 Example: Convex Programming ......................... 224
15.7.4 Example: Linear Programming .......................... 225
15.7.5 Example: Game Theory ................................. 225
15.8 Exercises ......................................................... 226
15.1 Monotone Functions
Variational inequality problems (VIP) generalize the problem of mini-
mizing a convex function over a closed convex set. Saddle-point problems
can be reformulated as variational inequality problems (VIP) for monotone
functions, and iterative algorithms used for their solution. Throughout this
chapter the norm is the Euclidean norm. We begin with some definitions.
A function f : R
J
[−∞, +]isproper if there is no x with f (x)=
−∞ and some x with f(x) < +.Theeffective domain of f, denoted
dom(f), is the set of all x for which f(x) is finite. If f is a proper convex
function on R
J
, then the sub-differential ∂f(x), defined to be the set
∂f(x)={u|f(z) f(x)+u, z xfor all z}, (15.1)
is a closed convex set, and nonempty for every x in the interior of dom(f).
213
214 Iterative Optimization in Inverse Problems
This is a consequence of applying the Support Theorem to the epi-graph of
f.Wesaythatf is differentiable at x if ∂f(x) is a singleton set, in which
case we have ∂f(x)={∇f(x)}.
Definition 15.1 An operator T : R
J
R
J
is monotone if
Tx Ty,x y≥0,
for all x and y.
Definition 15.2 An operator T : R
J
R
J
is strongly monotone if
Tx Ty,x y≥νx y
2
,
for all x and y.
As we saw previously, an operator G : R
J
R
J
is ν-inverse strongly
monotone (ν-ism) if
Gx Gy, x y≥νGx Gy
2
,
for all x and y.
Let f : R
J
R be convex and differentiable. Then the operator T = f
is monotone. If f(x) is convex, but not differentiable, then B(x)=∂f(x)
is a monotone set-valued function; we shall discuss set-valued functions in
Chapter 16. Not all monotone operators are gradient operators, as Exercise
15.1 will show. In fact, if A is a non-zero, skew-symmetric matrix, then
Tx= Ax is a monotone operator, but is not a gradient operator.
It is easy to see that if N is ne, then I N is monotone.
Definition 15.3 An operator G : R
J
R
J
is weakly ν-inverse strongly
monotone if
Gx, x y≥νGx
2
, (15.2)
whenever Gy =0.
15.2 The Split-Feasibility Problem
The split-feasibility problem (SFP) is the following: find x in C with
Ax in Q,whereA is an I by J matrix, and C and Q nonempty, closed
Variational Inequality Problems and Algorithms 215
convex sets in R
J
and R
I
, respectively. The CQ algorithm [58, 59] has the
iterative step
x
k+1
= P
C
(I γA
T
(I P
Q
)A)x
k
. (15.3)
For 0 <
2
ρ(A
T
A)
, the sequence {x
k
} converges to a minimizer, over x
in C, of the convex function
f(x)=
1
2
P
Q
Ax Ax
2
,
whenever such minimizers exist. From Theorem 8.1 we know that the gra-
dient of f(x)is
f(x)=A
T
(I P
Q
)Ax,
so the iteration in Equation (15.3) can be written as
x
k+1
= P
C
(I γf )x
k
. (15.4)
The limit x
of the sequence {x
k
} satisfies the inequality
∇f(x
),c x
≥0, (15.5)
for all c in C.
15.3 The Variational Inequality Problem
Now let G be any operator on R
J
.Thevariational inequality problem
(VIP), with respect to G and C, denoted VIP(G, C), is to find an x
in C
such that
Gx
,c x
≥0,
for all c in C. The form of the CQ algorithm suggests that we consider
solving the VIP(G, C) using the following iterative scheme:
x
k+1
= P
C
(I γG)x
k
. (15.6)
The sequence {x
k
} solves the VIP(G, C) whenever there are solutions, if
G is ν-ism and 0 <2ν; this is sometimes called Dolidze’s Theorem,
and is proven in [59] (see also [133]). A good source for related algorithms
is the paper by Censor, Iusem and Zenios [90].
In [90] the authors mention that it has been shown that, if G is strongly
monotone and L-Lipschitz, then the iteration in Equation (15.6) converges
to a solution of VIP(G, C) whenever γ (0, 2ν/L
2
). Then we have a strict

Get Iterative Optimization in Inverse Problems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.