Monotone Operators Stephen Boyd with help from Neal Parikh EE364b Stanford University 1 Outline 1 Relations 2 Monotone operators 3 Nonexpansive and contractive operators 4 Resolvent and Cayley operator 5 Fixed point iterations 6 Proximal point algorithm and method of multipliers Relations 2 Relations a relation R on a set Rn is a subset of Rn Rn dom R x y x y R overload R x to mean the set R x y x y R n can think of R as set valued mapping i e from dom R into 2R when R x is always empty or a singleton we say R is a function any function or operator f C Rn with C Rn is a relation f x is then ambiguous it can mean f x or f x Relations 2 Examples empty relation full relation Rn Rn identity I x x x Rn zero 0 x 0 x Rn x R2 x21 x22 1 x R2 x1 x2 subdifferential relation f x f x x Rn Relations 3 Operations on relations inverse relation R 1 y x x y R inverse exists for any relation coincides with inverse function when inverse function exists composition RS x y z x z S z y R scalar multiplication R x y x y R addition R S x y z x y R x z S Relations 4 Example Resolvent of operator for relation R and R resolvent much more on this later is relation S I R 1 I R x x y x y R S I R 1 x y x x y R for 6 0 S u v u v R v Relations 5 Generalized equations goal solve generalized equation 0 R x i e find x Rn with x 0 R solution set or zero set is X x dom R 0 R x if R f and f Rn Rn then 0 R x means x minimizes f Relations 6 Outline 1 Relations 2 Monotone operators 3 Nonexpansive and contractive operators 4 Resolvent and Cayley operator 5 Fixed point iterations 6 Proximal point algorithm and method of multipliers Monotone operators 7 Monotone operators relation F on Rn is monotone if u v T x y 0 for all x u y v F F is maximal monotone if there is no monotone operator that properly contains it we ll be informal i e sloppy about maximality other analysis issues solving generalized equations with maximal monotone operators subsumes many useful problems Monotone operators 7 Maximal monotone operators on R F is maximal monotone iff it is a connected curve with no endpoints with nonnegative or infinite slope Monotone operators 8 Some basic properties suppose F and G are monotone sum F G is monotone nonnegative scaling if 0 then F is monotone inverse F 1 is monotone congruence for T Rn m T T F T z is monotone on Rm zero set x Rn 0 F x is convex if F is maximal monotone affine function F x Ax b is monotone iff A AT 0 Monotone operators 9 Subdifferential F x f x is monotone suppose u f x and v f y then f y f x uT y x f x f y v T x y add these and cancel f y f x to get 0 u v T x y if f is convex closed proper CCP then F x f x is maximal monotone Monotone operators 10 KKT operator equality constrained convex problem with A Rm n minimize subject to f x Ax b with Lagrangian L x y f x y T Ax b associated KKT operator on Rn Rm F x y dual f x AT y x L x y r y L x y b Ax rpri zero set of F is set of primal dual optimal points saddle points of L KKT operator is monotone write as sum of monotone operators F x y Monotone operators f x b 0 AT A 0 x y 11 Multiplier to residual mapping same equality constrained convex problem define F y b Ax with x argminz L z y can be set valued F y is primal residual obtained from dual variable y interpretation F y g y where g is dual function zero set is set of dual optimal points multiplier to residual mapping F is monotone quick proof F y b A f 1 AT y or use F y g y Monotone operators 12 Outline 1 Relations 2 Monotone operators 3 Nonexpansive and contractive operators 4 Resolvent and Cayley operator 5 Fixed point iterations 6 Proximal point algorithm and method of multipliers Nonexpansive and contractive operators 13 Nonexpansive and contractive operators F has Lipschitz constant L if kF x F y k2 Lkx yk2 for all x y dom F for L 1 we say F is nonexpansive for L 1 we say F is a contraction with contraction factor L Nonexpansive and contractive operators 13 Properties if F and G have Lipschitz constant L so does F 1 G 0 1 composition of nonexpansive operators is nonexpansive composition of nonexpansive operator and contraction is contraction fixed point set of nonexpansive F with dom f Rn x F x x is convex but can be empty a contraction has a single fixed point more later Nonexpansive and contractive operators 14 Outline 1 Relations 2 Monotone operators 3 Nonexpansive and contractive operators 4 Resolvent and Cayley operator 5 Fixed point iterations 6 Proximal point algorithm and method of multipliers Resolvent and Cayley operator 15 Resolvent and Cayley operator for R resolvent of relation F is R I F 1 when 0 and F monotone R is nonexpansive thus a function when 0 and F maximal monotone dom R Rn Cayley operator of F is C 2R I 2 I F 1 I when 0 and F monotone C is nonexpansive we write RF and CF to explicitly show dependence on F Resolvent and Cayley operator 15 Proof that C is nonexpansive assume 0 and F monotone suppose x u R and y v R i e u F u x v F v y subtract to get u v F u F v x y multiply by u v T and use monotonicity of F to get ku vk22 x y T u v so when x y we must have u v i e R is a function Resolvent and Cayley operator 16 Proof continued now let s show C is nonexpansive kC x C y k22 k 2u x 2v y k22 k2 u v x y k22 4ku vk22 4 u v T x y kx yk22 kx yk22 using inequality above R is nonexpansive since it is the average of I and C R 1 2 I 1 2 2R I Resolvent and Cayley operator 17 Example Linear operators linear mapping F x Ax is monotone iff A AT 0 nonexpansive iff kAk2 1 0 and A AT 0 I A nonsingular kRA k2 k I A 1 k2 1 kCA k2 k2 I A 1 Ik2 1 for matrix case we have alternative …