Non Expansive

|
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
 4 views
of 32

Please download to get full document.

View again

Description
Methods for …nding …xed points of nonexpansive operators in a Hilbert space Andrzej Cegielski Faculty of Mathematics, Computer Sciences and Econometrics University of Zielona Góra A series of lectures presented at the Institute of Mathematics Technical University Ilmenau, July 2008 1 Contents 1 Introduction 3 1.1 Notation and basic facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Convex subsets and convex functions . . . . . . . . . . . . . . . . . .
Share
Tags
Transcript
  Methods for …nding …xed pointsof nonexpansive operators in a Hilbert space Andrzej Cegielski Faculty of Mathematics,Computer Sciences and EconometricsUniversity of Zielona GóraA series of lecturespresented at the Institute of MathematicsTechnical University Ilmenau,July 2008 1  Contents 1 Introduction 3 1.1 Notation and basic facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Convex subsets and convex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Metric projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4.1 Characterization and basic properties of the metric projection . . . . . . . . . 61.5 Fixed points theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Problems 10 2.1 Convex minimization problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Variational inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 Convex feasibility problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3.1 Linear feasibility problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4 Split feasibility problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.1 Linear split feasibility problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Convergence theorems 12 3.1 Weak convergence in a Hilbert space . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.1.1 Properties of the weak convergence . . . . . . . . . . . . . . . . . . . . . . . . 123.2 Opial’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Krasnoselskii–Mann Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Algorithmic operators 16 4.1 Properties of a …rmly nonexpansive operator . . . . . . . . . . . . . . . . . . . . . . . 164.1.1 Correspondences between FNE and NE and FM operators . . . . . . . . . . . 164.2 Asymptotically regular operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5 Projection methods 24 5.1 Cyclic projection method (ART) for CFP . . . . . . . . . . . . . . . . . . . . . . . . . 245.2 Simultaneous projection method (SPM) for CFP . . . . . . . . . . . . . . . . . . . . . 275.3 Surrogate constraints method (SCM) for LFP . . . . . . . . . . . . . . . . . . . . . . 295.4 CQ -method for the SFP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302  1 Introduction 1.1 Notation and basic facts  The elements of  R n are column vectors, e.g., x = (   1 ;:::;  n ) > , y = (  1 ;::: n ) > .For vectors x;y 2 R n :  x  0 denotes that all coordinates of  x are nonnegative,  f  = max i 2 I  f  i denotes that for all x there holds the equality f  ( x ) = max f f  i ( x ) : i 2 I  g x + = max f x; 0 g = (max f   1 ; 0 g ;:::; max f   n ; 0 g ) > ,  e  j = (0 ;:::; 0 ; 1 ; 0 ;:::; 0) > 2 R m with 1 at the j -th coordinate,  e = (1 ;:::; 1) >  R m + = f x 2 R n : x  0 g – nonnegative orthant,   m = f u 2 R m : e > u = 1 ;u  0 g – the standard simplex  B ( x; ) = f y 2 H : k y  x k   g – the ball with centre x 2 H and radius   0 ,   D – closure of  D  H ,  Fix T  = f z 2 H : Tz = z g – the subset of …xed points of an operator T  : D ! D , where D  H ,  Argmin x 2 D f  ( x ) = f z 2 D : f  ( z )  f  ( x ) for all x 2 D }, where D  H and f  : D ! R – asubset on which the function f  attains its minimum on D ,  argmin x 2 D f  ( x ) – a minimizer of a function f  : D ! R , i.e., an element of  Argmin x 2 D f  ( x ) ,  a function f  : H ! R is said to be coercive if  lim k x k!1 f  ( x ) = + 1 ,  a continuous and coercive function f  : H ! R attains its minimum,  N  D ( x ) = f y 2 H : h y;z  x i  0 for all z 2 D g – the normal cone to a convex subset D  H in the point x 2 D ,  H  ( a;  ) = f x 2 H : h a;x i =   g , where a 2 H and   2 R – a hyperplane in H ,  H  + ( a;  ) = f x 2 H : h a;x i    g and H   ( a;  ) = f x 2 H : h a;x i    g half-spaces in H ,  S  ( f; ) = f x 2 H : f  ( x )   g – the sublevel set of a function f  : H ! R at a level  2 R .  d( x;D ) = inf  y 2 D k x  y k – the distance of  x 2 H to a subset D  H ,  T  1 = T  , T  m = T  m  1  T  , m = 2 ; 3 ;::: , where T  : D ! D for D  H ,  diag v – a diagonal matrix, with a vector v 2 R on the main diagonal.Let x;y 2 H The Schwarz inequality h x;y i 2  k x k 2 k y k 2 ,The equality holds if and only if the vectors x and y are linear dependent3   Parallelogram law k x + y k 2 + k x  y k 2 = 2( k x k 2 + k y k 2 ) .  Strict convexity k x + y k = k x k + k y k () k x k y = k y k x 1.2 Convex subsets and convex functions Let X;Y  be linear spaces.  The intersection T  2  C   of a family f C   g  2  of convex subsets of  X  is a convex subset.  Any norm k  k in X  is a convex function  If  f  : X  ! R is a convex function and g : R ! R is a convex and nondecreasing function, then g  f  is a convex function.  For any norm k  k in X  the function k  k 2 is convex  If  f  i : X  ! R , i = 1 ;:::;m , are convex functions and F  : R m ! R is a convex function whichis nondecreasing with respect to any coordinate, then f  = F  ( f  1 ;:::;f  m ) is a convex function.  If  f  : Y  ! R is a convex function and A : X  ! Y  is a linear operator, then f   A is a convexfunction.  The sublevel set S  ( f; ) of a convex function f  : X  ! R is a convex subset.Let H be a Hilbert space and let D  H be closed and convex.  The distance function d (  ;D ) : H ! R , d ( x;D ) = inf  z 2 D k x  z k , is convex.  The function d 2 (  ;D ) is convex as a composition of a convex function d (  ;D ) and a convex anda nondecreasing function g : R + ! R , g ( u ) = u 2 .  The function 12 d 2 (  ;D ) is di¤erentiable and its derivative has the form D (12 d 2 ( x;D )) = x  P  D x . 1.3 Operators In methods for the CFP the important role play nonexpansive operators, …rmly nonexpansive oper-ators and the Fejér monotone operators.Let D  H be closed and convex subset. De…nition 1 We say that an operator T  : D ! H is nonexpansive  (NE) if for all x;y 2 D k Tx  Ty k  k x  y k : If the inequality is strict for x 6 = y then T  is said to be strictly nonexpansive  . De…nition 2 We say that an operator T  : D ! H is a contraction  if for some  2 (0 ; 1) and forall x;y 2 D k Tx  Ty k   k x  y k : 4
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks