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 deﬁnitions.

A function f : R

J

→ [−∞, +∞]isproper if there is no x with f (x)=

−∞ and some x with f(x) < +∞.Theeﬀective domain of f, denoted

dom(f), is the set of all x for which f(x) is ﬁnite. If f is a proper convex

function on R

J

, then the sub-diﬀerential ∂f(x), deﬁned 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 diﬀerentiable at x if ∂f(x) is a singleton set, in which

case we have ∂f(x)={∇f(x)}.

Deﬁnition 15.1 An operator T : R

J

→ R

J

is monotone if

Tx− Ty,x− y≥0,

for all x and y.

Deﬁnition 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 diﬀerentiable. Then the operator T = ∇f

is monotone. If f(x) is convex, but not diﬀerentiable, 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.

Deﬁnition 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: ﬁnd 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

} satisﬁes 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 ﬁnd 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.