טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAviv Gibali
SubjectAlgorithms for Solving Monotone Variational Inequalities
and Applications
DepartmentDepartment of Mathematics
Supervisors Professor Emeritus Reich Simeon
Full Professor Yair Censor
Full Thesis textFull thesis text - English Version


Abstract

In this thesis we study iterative algorithms for solving the Variational Inequality Problem (VIP) in an infinite dimensional Hilbert space. Several results are also presented in Euclidean space.

The thesis is divided into two major parts.

In the first part we study Korpelevich's extragradient method for solving the VIP. This method involves projecting twice onto the feasible set of the VIP at each iterative step. Our novelty is the development of several extensions of this method. We were able to replace the second orthogonal projection onto the feasible set of the VIP in Korpelevich's extragradient method with a projection onto a specific half-space (subgradient half-space). Another extension allows projections onto the members of an infinite sequence of subsets which epi-converges to the feasible set of the VIP. Several other extensions are also presented and the convergence analysis of the algorithms is given.

In the second part we propose a prototypical Split Inverse Problem (SIP). The SIP is a modeling paradigm for handling problems in which different parts of the model reside in different spaces that are linked by a known operator between the spaces. This approach already found use in intensity-modulated radiation therapy (IMRT) treatment planning and more recently in the area of adaptive filtering. Two new special cases of the SIP are the Split Common Null Point Problem (SCNPP) and the Split Variational Inequality Problem (SVIP).

The SCNPP entails finding a zero of a maximal monotone mapping in one space, the image of which under a given bounded linear transformation is a zero of another maximal monotone mapping. The SVIP entails finding a solution of one VIP, the image of which under a given bounded linear transformation is a solution of another VIP.

We present four iterative algorithms that solve such problems in Hilbert spaces, and establish weak convergence for one and strong convergence for the other three. Special cases of the SCNPP and the SVIP are discussed, some of which are new even in Euclidean space.