Iterative Optimization in Inverse Problems

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 − xfor 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