Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On properties of projection operators associated with convex sets Bui, Minh 2018

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2018_september_bui_minh.pdf [ 954.53kB ]
Metadata
JSON: 24-1.0369217.json
JSON-LD: 24-1.0369217-ld.json
RDF/XML (Pretty): 24-1.0369217-rdf.xml
RDF/JSON: 24-1.0369217-rdf.json
Turtle: 24-1.0369217-turtle.txt
N-Triples: 24-1.0369217-rdf-ntriples.txt
Original Record: 24-1.0369217-source.json
Full Text
24-1.0369217-fulltext.txt
Citation
24-1.0369217.ris

Full Text

On properties of projection operatorsassociated with convex setsbyMinh BuiB.Sc. (with distinction), Ho Chi Minh City University of Pedagogy, 2016A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July 2018© Minh Bui, 2018The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertationentitled:On properties of projection operators associated with convex setssubmitted byMinh Buiin partial fulfillment of the requirements of the degree ofMASTER OF SCIENCE.Dr. Heinz Bauschke, Department of Mathematics, IKBSASSupervisorDr. Shawn Wang, Department of Mathematics, IKBSASCo-supervisorDr. Yong Gao, Department of Computer Science, IKBSASSupervisory Committee MemberDr. Chen Feng, Faculty of Applied Science, School of EngineeringUniversity ExamineriiAbstractThe aim of this research work is twofold. On the one hand, under mildassumptions, we give an explicit formula for projection operator associatedwith the intersection of a cone and a ball/sphere; nevertheless, this formulaplays a role in determining copositivity of matrices. On the other hand, weprovide a complete answer to the question “When is the sum of projectors aprojector?,” which allows us to fill a gap in the current literature.iiiLay summaryGiven a set C, one often does not have an explicit formula for pointsin C that are closest (in distance) to a given point—especially when C isthe intersection or the sum of sets. On the one hand, we provide formulaefor determining points in the intersection of a cone and a ball/sphere thata closest to a given point under mild assumptions. These formulae havea potential to be useful in optimization problems where a constraint isgiven. Indeed, one of these formulae was a key tool in Lange’s algorithm todetermine copositivity of matrices. On the other hand, we analyze carefullya case where the closest point onto the sum of convex sets of a given pointcan be expressed as a sum of individual closet points, which is not wellunderstood in the current literature of Convex Analysis.ivPrefaceThis thesis is based on the paper [7] (Chapter 4) and the submittedmanuscript [6] (Chapter 5) by Heinz Bauschke, Minh Bui, and XianfuWang.For the aforementioned work, each author contributed equally.vTable of contentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixGlossary of notation and symbols . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiDành cho Mẹ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivChapter 1: What is this thesis about? . . . . . . . . . . . . . . . . . 1Chapter 2: Elements of real analysis . . . . . . . . . . . . . . . . . . 32.1 Notation and symbols . . . . . . . . . . . . . . . . . . . . . . 32.2 Identities and inequalities . . . . . . . . . . . . . . . . . . . . 42.3 Miscellaneous results . . . . . . . . . . . . . . . . . . . . . . . 6Chapter 3: Elements of convex analysis and monotone operatortheory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.1 Convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.2 Convex sets on the real line . . . . . . . . . . . . . . . . . . . 123.3 Convex cones . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.4 Convex functions . . . . . . . . . . . . . . . . . . . . . . . . . 183.5 Subdifferential operators . . . . . . . . . . . . . . . . . . . . . 21viTABLE OF CONTENTS3.6 Monotone operators . . . . . . . . . . . . . . . . . . . . . . . 21Chapter 4: Projecting onto the intersection of a cone and a sphere 234.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.2 Cones and conical hulls revisited . . . . . . . . . . . . . . . . 234.3 Projectors onto cones generated by orthonormal sets . . . . . 294.4 The projector onto the intersection of a cone and a ball . . . . 324.5 The projector onto the intersection of a cone and a sphere . . 354.6 Further examples . . . . . . . . . . . . . . . . . . . . . . . . . 454.7 Copositive matrices: a numerical experiment . . . . . . . . . 53Chapter 5: On the sum of projectors onto convex sets . . . . . . . 565.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.2 Auxiliary results . . . . . . . . . . . . . . . . . . . . . . . . . . 575.3 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595.4 The partial sum property of projectors onto convex cones . . 695.5 The one-dimensional case . . . . . . . . . . . . . . . . . . . . 765.6 On a result by Halmos . . . . . . . . . . . . . . . . . . . . . . 78Chapter 6: Conclusion and future work . . . . . . . . . . . . . . . 80Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81viiList of tablesTable 4.1 Detecting whether a matrix is copositive using a vari-ety of algorithms. Here “iter” means “the average ofthe numbers of iterations.” . . . . . . . . . . . . . . . . 54Table 4.2 Detecting copositivity of the Horn matrix. . . . . . . . 55viiiList of figuresFigure 4.1 Example 4.14 illustrates that the projectors onto acone and ball may fail to commute. . . . . . . . . . . 34Figure 5.1 A GeoGebra [26] snapshot illustrating the sets C (yel-low) and D (green) in the setting of Example 5.16. . . 67ixGlossary of notation andsymbolsReal lineR The set of real numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4N The set of positive integers {0, 1, 2, . . .} . . . . . . . . . . . . . . . . . . . 3R+ The set of positive real number {ξ ∈ R | ξ > 0} . . . . . . . . . . . 3R++ The set of strictly positive real number {ξ ∈ R | ξ > 0} . . . 3R− The set of negative real number {ξ ∈ R | ξ 6 0} . . . . . . . . . . 3R−− The set of strictly negative real number {ξ ∈ R | ξ < 0} . . 3Hilbert spacesH Real Hilbert space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3〈 · | · 〉 Scalar product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3‖ · ‖ Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Id The identity operator onH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3B(x; ρ) Closed ball with center x and radius ρ . . . . . . . . . . . . . . . . . . . . 3S(x; ρ) Sphere with center x and radius ρ . . . . . . . . . . . . . . . . . . . . . . . . 3RN The standard N-dimensional Euclidean space . . . . . . . . . . . . . 31RN+ The positive orthant in RN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31SN Space of real symmetric matrices of size N × N . . . . . . . . . . . 49SN+ Set of real N × N symmetric positive semidefinite matrices 49UN Set of real N × N orthogonal matrices . . . . . . . . . . . . . . . . . . . . 49xGlossary of notation and symbolsSets2X Power set of a set X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3i∈I Ci Cartesian product of (Ci)i∈I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8∑i∈I Ci Minkowski sum of a finite family of sets (Ci)i∈I . . . . . . . . . . . 13C Closure of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3C⊥ Orthogonal complement of a set C . . . . . . . . . . . . . . . . . . . . . . . 3span C Linear span of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79conv C Convex hull of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8conv C Closed convex hull of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8cone C Conical hull of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12cone C Closed conical hull of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12C	 Polar cone of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13pos C Positive span of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13rec C Recession cone of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Operators and functionsran A Range of an operator A : H → 2H . . . . . . . . . . . . . . . . . . . . . . . . 22ran A Closure of the range of an operator A : H → 2H . . . . . . . . . . 22gra A Graph of an operator A : H → 2H . . . . . . . . . . . . . . . . . . . . . . . . 21A−1 Inverse of an operator A : H → 2H . . . . . . . . . . . . . . . . . . . . . . . 21Fix T Set of fixed points of an operator T : H → H . . . . . . . . . . . . . . 59dom f Domain of a function f : H → [−∞,+∞] . . . . . . . . . . . . . . . . . . 18dom f Closure of the domain of a function f : H → [−∞,+∞] . . . 18Γ0(H) Set of proper lower semicontinuous convex functions fromH to ]−∞,+∞] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18f  g Infimal convolution of functions f and g . . . . . . . . . . . . . . . . . 20f  g Exact infimal convolution of functions f and g . . . . . . . . . . . . 20ιC Indicator function of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13σC Support function of a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13dC Distance function to a set C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3PC Set-valued projector associated with a set C . . . . . . . . . . . . . . 9Prox f Proximity operator of a function f . . . . . . . . . . . . . . . . . . . . . . . . 20∂ f Subdifferential of a function f . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21∇ f Gradient operator of a function f . . . . . . . . . . . . . . . . . . . . . . . . . 7f ∗ (Fenchel) Conjugate of a function f . . . . . . . . . . . . . . . . . . . . . . . 19f ∗∗ Biconjugate of a function f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19xiAcknowledgementsTo Heinz and Shawn: From the bottom of my heart, thank you. The lasttwo years were absolutely wonderful and I deeply appreciate your supportand encouragement, which gave me the strength and faith in becoming amathematician. It has been a great honor to be your student. If I was tochoose a place for master’s study again, Kelowna and UBCO would still bemy choice.Anh Nghĩa, anh Minh, và anh Hùng: Em xin cảm ơn các anh đã giúp đỡem từ những ngày đầu tại Canada. Hành trình hai năm ở Kelowna của emcó lẽ sẽ khó khăn hơn rất nhiều nếu không có sự giúp đỡ của các anh. Emhy vọng cả bốn anh em có thể gặp mặt và tán gẫu vào một ngày không xa.To Walaa, Chayne, and Dongying: It is my pleasure to be in ASC 310with you. Many thanks for sharing your knowledge and experience inresearch and coursework. Furthermore, thank you for helping me withthe paperwork during my first year. I wish you all the best wherever yougo.To Ms. Hilda: Thank you for taking care of me since I came to yourhouse. You are my Canadian mom!Anh Tân (Farm): Cảm ơn sư huynh đã giúp đỡ em tận tình từ nhữnggiây phút đầu em đặt chân xuống Vancouver và chỉ dẫn cho em nhiều thứở Canada—rất cảm kích vì điều đó. Kiến thức anh văn của em có lẽ sẽkhông khá hơn được nếu không có sự giúp đỡ của anh trong hai năm qua.Hy vọng chúng ta sẽ gặp nhau thường xuyên và cùng nhau chia sẻ nhữngcâu chuyện trong cuộc sống.Gửi cả nhà thân yêu: Cảm ơn cả nhà đã luôn ủng hộ con theo đuổi giấcmơ của mình từ nửa vòng trái đất trong suốt hai năm vừa qua, và con xinhứa sẽ cố gắng để không khiến cả nhà thất vọng đâu. Con sẽ cố gắng nhữnggì con có thể để giúp đỡ cả nhà mình trong tương lai.Most of all, I wish to thank my girlfriend Nguyễn Nguyệt Anh formaking me become more optimistic and open-minded. My journey inxiiAcknowledgementsCanada would not be complete without her. To Nguyệt Anh: Thank youfor sharing these wonderful years and unforgettable moments with me.Finally, my graduate study at UBCO was partially supported by Mitacsvia a Mitacs Globalink Graduate Fellowship Award and my journey inKelowna was made possible by their highly competitive Globalink Re-search Internship Award in 2016.xiiiDành cho MẹCon xin dành tặng luận văn này cho Mẹ.Cảm ơn Mẹ, vì tất cả những gì Mẹ đã dành cho con.xivChapter 1What is this thesis about?The notion of projection operator in a Hilbert space is fundamental tothe development of Optimization Theory, and in turn, one of the basicproblems is to compute the projection of a given point onto a set. Recently,in [28, Example 5.5.2], Lange presented a closed form for the projectorassociated with the intersection of the orthant and the unit sphere andused it for an algorithm on determining copositivity of a matrix; however,this projection has the potential to be useful in other settings where a prioriconstraints are present (e.g., positivity and energy). This gives rise to thenontrivial problem of projecting onto the intersection of a cone and a sphere(both are centered at the origin); indeed, the projection onto the intersectionof two sets generally does not allow for a closed form even when theindividual projection operators have explicit descriptions. In Chapter 4, wesystematically analyze the projection onto the intersection of a cone witheither a ball or a sphere in the general case. Several cases are providedwhere the projector is available explicitly. Various examples based onfinitely generated cones (as a consequence, we recover Lange’s result), theLorentz cone, and the cone of positive semidefinite matrices are presented.The usefulness of our formulae is illustrated by numerical experimentsfor determining copositivity of real symmetric matrices. Having done asystematic study on the projection onto the intersection of sets, we nowturn to the the projection onto the Minkowski sum of closed convex sets.This projector is generally not equal to the sum of individual projectorsas one may expect. However, if that sum is a projector, we shall see inProposition 5.1 that the aforementioned equality holds. Therefore, one maywish to analyze the question “When is the sum of projectors a projector?.” Ifall the sets are subspaces, an answer to this question dates back to, at least,Halmos [21]. In 1971, Zarantonello [39] extended Halmos’s result to thecase of cones. The general case is, however, not well understood and createsa gap in the literature of Convex Analysis. In Chapter 5, we provide acomplete answer to this question in the general case. Our results unify andextend the case of linear subspaces and Zarantonello’s results for projectors1Chapter 1. What is this thesis about?onto cones. We then establish the partial sum property for projectors ontoconvex cones, which is a connection with the work [4], and we also presentvarious examples as well as a detailed analysis in the univariate case. Forthe sake of self-containedness, basic concepts and well-known results inReal Analysis, Convex Analysis, and Monotone Operator Theory that areused in Chapters 4 and 5 are provided in Chapters 2 and 3. The results inthis thesis are based on [7] and [6], except for facts with explicit references.2Chapter 2Elements of real analysisIn this chapter, we collect a few results and notation of Real Analysisthat will be used later. We assume that the reader is familiar with basicReal Analysis; in particular, real Hilbert spaces.2.1 Notation and symbolsThroughout this thesis,H is a real Hilbert space (2.1)equipped with a scalar product 〈 · | · 〉. The corresponding norm is denotedby ‖ · ‖, i.e.,(∀x ∈ H) ‖x‖ :=√〈x | x〉, (2.2)and the identity operator onH is denoted by Id.The notation used in this thesis is standard and mainly follows [8]. Weset N := {0, 1, 2, . . .}, R+ := [0,+∞[, R++ := ]0,+∞[, R− := ]−∞, 0], andR−− := ]−∞, 0[. Let C be a subset of H. Then the orthogonal complement ofC isC⊥ := {u ∈ H | (∀x ∈ C) 〈x | u〉 = 0}, (2.3)and the closure of C is denoted by C. Next, the distance function to C isdC : H → [0,+∞] : x 7→ inf‖x− C‖. (2.4)(Note that dC ≡ +∞ when C is empty.) Now let x ∈ H and ρ ∈R++. The closed ball and sphere with center x and radius ρ are B(x; ρ) :={y ∈ H | ‖x− y‖ 6 ρ} and S(x; ρ) := {y ∈ H | ‖x− y‖ = ρ}, respectively.Finally, let A : H → 2H be such that dom A := {x ∈ H | Ax 6= ∅} 6= ∅.Assume that, for every x ∈ dom A, Ax is a singleton. Then, for everyx ∈ dom A, without any confusion, we shall identify Ax with its uniqueelement.32.2. Identities and inequalities2.2 Identities and inequalitiesFact 2.1 (Cauchy–Schwarz) Let x and y be inH. Then|〈x | y〉| 6 ‖x‖‖y‖, (2.5)and equality holds if and only if there exists α ∈ R+ such that x = αy ory = αx.Lemma 2.2 Let {αi}i∈I be a finite subset of R such that(∀i ∈ I)(∀j ∈ I) i 6= j⇒ αiαj = 0 (2.6)and that∑i∈Iαi = 1. (2.7)Then there exists i ∈ I such that αi = 1 and (∀j ∈ I r {i}) αj = 0.Proof. Suppose that there exist i and j in I such that i 6= j, that αi 6= 0, andthat αj 6= 0. Then αiαj 6= 0, which violates (2.6). Hence, (αi)i∈I contains atmost one nonzero number. On the other hand, by (2.7), (αi)i∈I must containat least one nonzero number. Altogether, we conclude that there exists i ∈ Isuch that αi 6= 0 and (∀j ∈ I r {i}) αj = 0. Consequently, it follows from(2.7) that αi = 1, as claimed. Lemma 2.3 Let x ∈ H, let (xi)i∈I be a finite family in H, and let (αi)i∈I be afamily in R such that ∑i∈I αi = 1. Then the following hold:(i) ‖∑i∈I αixi‖2 +∑(i,j)∈I×I‖xi − xj‖2/2 = ∑i∈I αi‖xi‖2.(ii) Suppose that I = {1, . . . , m}, where m ∈ {2, 3, . . .}. Then∥∥∥∥∥x−∑i∈I xi∥∥∥∥∥2=∑i∈I‖x− xi‖2 − (m− 1)‖x‖2 + 2 ∑(i,j)∈I×Ii<j〈xi | xj〉. (2.8)(iii) Set x := ∑i∈I αixi and β := ‖x‖. Suppose that(∀i ∈ I) ‖xi‖ = β, (2.9)that(∀i ∈ I) αi > 0, (2.10)42.2. Identities and inequalitiesand that the vectors (xi)i∈I are pairwise distinct, i.e.,(∀i ∈ I)(∀j ∈ I) i 6= j⇒ xi 6= xj. (2.11)Then (∃i ∈ I) x = xi.Proof. (i): See [8, Lemma 2.14(ii)].(ii): We shall proceed by induction on m. The claim is true for m = 2 dueto‖x− (x1 + x2)‖2 = ‖x− x1‖2 − 2〈x− x1 | x2〉+ ‖x2‖2 (2.12a)= ‖x− x1‖2 + (‖x‖2 − 2〈x | x2〉+ ‖x2‖2) (2.12b)− ‖x‖2 + 2〈x1 | x2〉 (2.12c)= ‖x− x1‖2 + ‖x− x2‖2 − ‖x‖2 + 2〈x1 | x2〉. (2.12d)In turn, assume that m ∈ {3, 4, . . .} and that the result holds for familiescontaining m − 1 vectors; furthermore, set J := {1, . . . , m− 1}. We theninfer from the induction hypothesis that∥∥∥∥∥x−∑i∈I xi∥∥∥∥∥2=∥∥∥∥∥(x−∑i∈Jxi)− xm∥∥∥∥∥2(2.13a)=∥∥∥∥∥x−∑i∈J xi∥∥∥∥∥2+ ‖xm‖2 − 2〈x−∑i∈Jxi∣∣∣∣∣ xm〉(2.13b)=∑i∈J‖x− xi‖2 − ((m− 1)− 1)‖x‖2+ 2 ∑(i,j)∈J×Ji<j〈xi | xj〉+ ‖xm‖2 − 2〈x | xm〉+ 2∑i∈J〈xi | xm〉 (2.13c)=∑i∈J‖x− xi‖2 + (‖xm‖2 − 2〈x | xm〉+ ‖x‖2)− (m− 1)‖x‖2 + 2 ∑(i,j)∈I×Ii<j〈xi | xj〉 (2.13d)=∑i∈I‖x− xi‖2 − (m− 1)‖x‖2 + 2 ∑(i,j)∈I×Ii<j〈xi | xj〉, (2.13e)52.3. Miscellaneous resultswhich yields the desired assertion.(iii): Since ∑i∈I αi = 1, we deduce from (i) and (2.9) thatβ2 + ∑(i,j)∈I×Iαiαj‖xi − xj‖2/2 =∑i∈Iαiβ2 = β2, (2.14)which yields ∑(i,j)∈I×I αiαj‖xi − xj‖2 = 0 or, equivalently, by (2.10),(∀i ∈ I)(∀j ∈ I) αiαj‖xi − xj‖2 = 0. (2.15)Thus, we get from (2.11) and (2.15) that (∀i ∈ I)(∀j ∈ I) i 6= j ⇒ ‖xi −xj‖ 6= 0 ⇒ αiαj = 0, and because ∑i∈I αi = 1, Lemma 2.2 guarantees theexistence of i ∈ I such that αi = 1 and (∀j ∈ I r {i}) αj = 0. Consequently,it follows from the very definition of x that x = xi, as desired. Lemma 2.4 Let α be in R, let β be in R++, and let x = (x, ξ) ∈ H ⊕R. SetSα,β := S(0; β)× {α}. Then max〈x | Sα,β〉 = β‖x‖+ ξα.Proof. We shall assume that x 6= 0, since otherwise 〈x | Sα,β〉 = {ξα} andthe assertion is clear. Now, for every y = (y, α) ∈ Sα,β, since ‖y‖ = β, theCauchy–Schwarz inequality yields〈x | y〉 = 〈x | y〉+ ξα 6 ‖x‖‖y‖+ ξα = β‖x‖+ ξα. (2.16)Hence sup〈x | Sα,β〉 6 β‖x‖ + ξα. Consequently, because (βx/‖x‖, α) ∈Sα,β and 〈x∣∣∣∣ ( βx‖x‖ , α)〉=〈x∣∣∣∣ βx‖x‖〉+ ξα = β‖x‖+ ξα, (2.17)we obtain the conclusion. 2.3 Miscellaneous resultsLemma 2.5 Let C and D be subsets ofH. Then C + D = C + D.Proof. Since clearly C + D ⊆ C + D, it suffices to show that C + D ⊆C + D. To this end, take x ∈ C + D. Then, on the one hand, there existsequences (cn)n∈N in C and (dn)n∈N in D such that limn(cn + dn) = x. Onthe other hand, for every n ∈ N, because cn ∈ C, there exists en ∈ C suchthat ‖cn − en‖ < 1/(n + 1); hence, we obtain a sequence (en)n∈N in C that62.3. Miscellaneous resultssatisfies limn‖cn − en‖ = 0. Altogether, en + dn = (en − cn) + (cn + dn) →0 + x = x, and since (en + dn)n∈N is a sequence in C + D, it follows thatx ∈ C + D, as announced. The following is a variant of [40, Lemma 6.1]. We provide a proof forcompleteness.Lemma 2.6 Let f : H → R be Gâteaux differentiable onH, and suppose that∇ fis positively homogeneous. Then(∀x ∈ H) f (x) = 12 〈x | ∇ f (x)〉+ f (0). (2.18)Proof. By assumption(∀x ∈ H)(∀λ ∈ R++) ∇ f (λx) = λ∇ f (x). (2.19)Now fix x ∈ H, and set φ : R → R : t 7→ f (tx). Then, since f is Gâteauxdifferentiable, we see that(∀t ∈ R) lim0 6=α→0φ(t + α)− φ(t)α= lim0 6=α→0f ((t + α)x)− f (tx)α(2.20a)= lim0 6=α→0f (tx + αx)− f (tx)α(2.20b)= 〈x | ∇ f (tx)〉. (2.20c)Hence, φ is differentiable on R and, in view of (2.19)&(2.20c), (∀t ∈R++) φ′(t) = t〈x | ∇ f (x)〉. Consequently,f (x)− f (0) = φ(1)− φ(0) =∫ 10φ′(t)dt (2.21a)=∫ 10t〈x | ∇ f (x)〉dt (2.21b)= 12 〈x | ∇ f (x)〉, (2.21c)from which we obtain the conclusion. 7Chapter 3Elements of convex analysisand monotone operator theoryThis chapter presents known results in Convex Analysis and MonotoneOperator Theory that will be useful in the sequel. The main reference forfacts here is [8], and for basic Convex Analysis, the reader is referred to,e.g., [34, 23, 24, 38].3.1 Convex setsDefinition 3.1 Let C be a subset ofH. Then C is convex if(∀α ∈ ]0, 1[) (1− α)C + αC = C (3.1)or, equivalently,(∀x ∈ C)(∀y ∈ C) ]x, y[ ⊆ C. (3.2)Example 3.2 The following sets are convex:(i) Open and closed balls corresponding to a norm onH.(ii) Affine subspaces.(iii) Half-spaces.(iv) The intersection of a family of convex sets.(v) Let (Hi)i∈I be a finite family of real Hilbert spaces and, for every i ∈ I,let Ci be a convex subset of Hi. Then i∈I Ci is a convex subset of⊕i∈IHi.Definition 3.3 Let C be a subset ofH. Then the convex hull of C, in symbol,conv C, is the intersection of all the convex subsets of H that contain C;83.1. Convex setsin other words, conv C is the smallest convex subset of H containing C.Likewise, the closed convex hull of C, in symbol, conv C, is the smallestclosed convex subset ofH that contains C.Example 3.4 Let ρ ∈ R++, and set C := S(0; ρ). Then conv C = B(0; ρ).Proof. Since B(0; ρ) is convex and C ⊆ B(0; ρ), we obtain conv C ⊆ B(0; ρ).Conversely, take x ∈ B(0; ρ), and we consider the following two conceiv-able cases:(a) x = 0: Fix y ∈ C. Then clearly −y ∈ C and x = 0 = (1/2)y +(1/2)(−y) ∈ conv C.(b) x 6= 0: Set x+ := (ρ/‖x‖)x, x− := (ρ/‖x‖)(−x), and α := (1 +‖x‖/ρ)/2. Then {x+, x−} ⊆ C, and because ‖x‖ 6 ρ, we have α ∈ ]0, 1].Thus, since it is readily verified that x = αx+ + (1 − α)x−, we get x ∈conv C.Hence, x ∈ conv C in both cases, which completes the proof. Fact 3.5 Let C be a subset ofH. Thenconv C ={∑i∈Iαixi∣∣∣∣∣ I is finite, {αi}i∈I ⊆ ]0, 1],∑i∈I αi = 1, {xi}i∈I ⊆ C},(3.3)i.e., conv C is the set of all convex combinations of elements in C.Proof. See, e.g., [34, Theorem 2.3]. Fact 3.6 Let I be a nonempty finite set, and let (Hi)i∈I be a family of realHilbert spaces. In addition, for every i ∈ I, let Ci be a subset ofHi. Thenconv(i∈ICi)=i∈Iconv Ci. (3.4)Definition 3.7 Let C be a nonempty subset of H, let x ∈ H, and let p ∈ H.Then p is a projection of x onto C if ‖x− p‖ = dC(x). Moreover, the projector(or projection operator) onto C is defined byPC : H → 2H : x 7→ {p ∈ C | ‖x− p‖ = dC(x)}. (3.5)Proposition 3.8 Let C be a nonempty subset ofH, and let x and y be inH. ThenPy+Cx = y + PC(x− y).93.1. Convex setsProof. Let us first show thaty + PC(x− y) ⊆ Py+Cx. (3.6)Towards this goal, take p ∈ PC(x − y). Then, on the one hand, clearlyy + p ∈ y + C. On the other hand, because p ∈ PC(x − y), we have(∀z ∈ C) ‖x− (y + p)‖ = ‖(x− y)− p‖ 6 ‖(x− y)− z‖ = ‖x− (y + z)‖.Altogether, y + p ∈ Py+Cx, as announced in (3.6). Consequently, replacing(C, x, y) in (3.6) by (y+ C, x− y,−y), it follows that −y+ Py+C(x) = −y+Py+C((x− y)− (−y)) ⊆ P(y+C)−y(x− y) = PC(x− y), which completes theproof. We now turn to projectors onto subsets of spheres.Lemma 3.9 Let C be a nonempty subset ofH consisting of vectors of equal norm,let x ∈ H, and let p ∈ C. Then the following hold:(i) p ∈ PCx ⇔ 〈x | p〉 = max〈x |C〉.(ii) PCx 6= ∅ if and only if 〈x | · 〉 achieves its supremum over C.Proof. (i): Indeed, since p ∈ C and (∀y ∈ C) ‖y‖ = ‖p‖ by our assumption,we see thatp ∈ PCx ⇔ (∀y ∈ C) ‖x− p‖2 6 ‖x− y‖2 (3.7a)⇔ (∀y ∈ C) − 2〈x | p〉 6 −2〈x | y〉 (3.7b)⇔ (∀y ∈ C) 〈x | y〉 6 〈x | p〉 (3.7c)⇔ 〈x | p〉 = max〈x |C〉, (3.7d)which verifies the claim.(ii): This follows from (i). The following example provides an instance in which PCx 6= ∅, whereC and x are as in Lemma 3.9.Example 3.10 Consider the setting of Lemma 3.9 and suppose, in addition,that C is weakly closed. Then PCx 6= ∅.Proof. Since, by assumption, C is bounded and since C is weakly closed,we deduce that C is weakly compact (see, for instance, [8, Lemma 2.36]).Therefore, because 〈x | · 〉 is weakly continuous, its supremum over C isachieved, and the assertion therefore follows from Lemma 3.9(ii). 103.1. Convex setsFact 3.11 (Projection theorem) Let C be a nonempty closed convex subsetofH. Then PC is single-valued and, for every x ∈ H and every p ∈ H,p = PCx ⇔ [ p ∈ C and (∀y ∈ C) 〈y− p | x− p〉 6 0 ]. (3.8)Proof. See, for instance, [8, Theorem 3.16]. Example 3.12 Let C be a nonempty closed interval in R. Then(∀ξ ∈ R) PCξ =inf C, if ξ < inf C;ξ, if ξ ∈ C;sup C, if ξ > sup C.(3.9)Proof. See [8, Example 24.34(i)]. Example 3.13 (Projectors onto Lorentz cones) Let α be in R++ and setKα := {(x, ξ) ∈ H⊕R | ‖x‖ 6 αξ}. (3.10)Then, for every (x, ξ) ∈ H⊕R,PKα(x, ξ) =(x, ρ), if ‖x‖ 6 αξ;(0, 0), if α‖x‖ 6 −ξ;α‖x‖+ ξα2 + 1(α‖x‖ x, 1), otherwise.(3.11)Proof. See [5, Theorem 3.3.6]. Example 3.14 Let u ∈ H r {0}, let η ∈ R, and set C :={x ∈ H | 〈x | u〉 = η}. Then(∀x ∈ H) PCx = x + η − 〈x | u〉‖u‖2 u. (3.12)Proof. See, for instance, [8, Example 3.23]. 113.2. Convex sets on the real line3.2 Convex sets on the real lineProposition 3.15 Let C and D be nonempty intervals in R such that C 6= {0}and D 6= {0}. Suppose that C ∩ D = {0}. Then exactly one of the followingcases occurs:(i) C ⊆ R−. Then D ⊆ R+ and max C = min D = 0.(ii) C ∩R++ 6= ∅. Then C ⊆ R+, D ⊆ R−, and min C = max D = 0.Proof. (i): Since C ⊆ R− and 0 ∈ C, it follows that max C = 0. Let us nowverify that D ⊆ R+. Assume to the contrary that there exists ξ ∈ D ∩R−−.Then, on the one hand, by the convexity of D and the fact that 0 ∈ D,it follows that ]ξ, 0[ ⊆ D. On the other hand, because {0} 6= C ⊆ R−and C is convex, there exists η ∈ R−− satisfying ]η, 0[ ⊆ C. Altogether,]max{ξ, η}, 0[ ⊆ C ∩ D, and we reach a contradiction. Thus, D ⊆ R+, andsince 0 ∈ D, we conclude that min D = 0, as desired.(ii): We first argue by contradiction that D ⊆ R−. Towards this goal,assume that there exists η ∈ D ∩R++, and take ξ ∈ C ∩R++. Since 0 ∈ Cand ξ ∈ C, the convexity of C yields ]0, ξ[ ⊆ C, and likewise, ]0, η[ ⊆ D.Thus, ]0, min{ξ, η}[ ⊆ C ∩ D, which contradicts our assumption. Hence,D ⊆ R−. Consequently, by interchanging the roles of C and D in (i), weobtain the conclusion. Here is a direct consequence of Proposition 3.15.Corollary 3.16 Let C and D be nonempty intervals in R such that C ∩ D 6= ∅.ThenC ∩ D = {0} ⇔ CD ⊆ R−, (3.13)where CD := {ξη | ξ ∈ C and η ∈ D}.3.3 Convex conesDefinition 3.17 Let C be a subset of H. Then C is a cone if C = ⋃λ∈R++ λC.The conical hull of C is the intersection of all the cones in H containing Cand is denoted by cone C; in other words, cone C is the smallest cone in Hthat contains C. Finally, the closed conical hull of C, in symbol, cone C, is thesmallest closed cone inH containing C.123.3. Convex conesFor the sake of clarity, let us point out the following.Remark 3.18 Let K be a nonempty cone in H. Then 0 ∈ K, and if K 6= {0},then (∀ρ ∈ R++) K ∩ S(0; ρ) 6= ∅.Fact 3.19 Let C be a subset ofH. Then the following hold:(i) cone C =⋃λ∈R++ λC.(ii) cone C = cone C.(iii) cone(conv C) is the smallest convex cone containing C.Proof. See, e.g., [8, Proposition 6.2(i)–(iii)]. We shall require the following notation.Notation Let C be a nonempty subset ofH. Define its positive span bypos C :={∑i∈Iαixi∣∣∣∣∣ I is finite, {αi}i∈I ⊆ R+, and {xi}i∈I ⊆ C}. (3.14)We observe that if C is finite, then pos C coincides1 with the Minkowskisum of the sets (R+c)c∈C, i.e.,pos C = ∑c∈CR+c. (3.15)Definition 3.20 Let C be a subset ofH. The polar cone of C isC	 := {u ∈ H | sup〈C | u〉 6 0}, (3.16)the indicator function of C isιC : H → [−∞,+∞] : x 7→{0, if x ∈ C;+∞, otherwise,(3.17)and the support function of C isσC : H → [−∞,+∞] : u 7→ sup〈C | u〉. (3.18)Fact 3.21 Let C be a subset ofH. Then the following hold:1This readily follows from (3.14).133.3. Convex cones(i) Suppose that C is a subspace. Then C	 = C⊥.(ii) C	 is a nonempty closed convex cone.(iii) Suppose that C is a nonempty cone. Then σC = ιC	 .Lemma 3.22 Let C be a nonempty subset of H, and set K := pos C. Then thefollowing hold:(i) x ∈ K	 ⇔ sup〈x |C〉 6 0.(ii) K = cone(conv(C ∪ {0})) = cone({0} ∪ conv C) = cone(conv C) ∪{0}.(iii) K is the smallest convex cone containing C ∪ {0}.Proof. (i): This follows from the definition of polar cones and (3.14).(ii): Set D := cone(conv(C ∪ {0})), E := cone({0} ∪ conv C), and F :=cone(conv C) ∪ {0}. We shall establish thatK ⊆ D ⊆ E = F ⊆ K. (3.19)First, take x ∈ K, say x = ∑i∈I αixi, where I is finite, {αi}i∈I ⊆ R+, and{xi}i∈I ⊆ C; in addition, set α := ∑i∈I αi. If α = 0, then, because {αi}i∈I ⊆R+, we obtain (∀i ∈ I) αi = 0 and thus x = 0 ∈ D; otherwise, we haveα > 0 and x = α∑i∈I(αi/α)xi ∈ cone(conv C) ⊆ D. Next, fix y ∈ D.Then Fact 3.19(i) and (3.3) yield the existence of λ ∈ R++, a finite subset{βi}i∈J of R+, and a finite subset {xi}i∈J of C such that y = λ∑i∈J βixi. Inturn, if ∑i∈J βi = 0, then (∀i ∈ J) βi = 0 and so y = 0 ∈ E; otherwise,∑i∈J βi > 0 and, upon setting β := ∑i∈J βi, we get y = λβ∑i∈J(βi/β)xi ∈cone(conv C) ⊆ E. Let us now prove that E = F. To do so, we infer fromFact 3.19(i) thatE =⋃λ∈R++λ({0} ∪ conv C) (3.20a)= {0} ∪( ⋃λ∈R++λ conv C)(3.20b)= {0} ∪ cone(conv C) (3.20c)= F. (3.20d)Finally, take z ∈ F. If z = 0, then clearly z ∈ K; otherwise, z ∈ cone(conv C)and, by Fact 3.19(i) and (3.3), there exist µ ∈ R++, a finite subset {δi}i∈T143.3. Convex conesof ]0, 1], and a finite subset {xi}i∈T of C such that z = µ∑i∈T δixi =∑i∈T(µδi)xi ∈ K. Altogether, (3.19) holds.(iii): Since K = cone(conv(C ∪ {0})) by (ii), the conclusion thus followsfrom Fact 3.19(iii). Example 3.23 (Lorentz cone) Let α and β be in R++, setH := H⊕R, setKα := {(x, ξ) ∈H | ‖x‖ 6 αξ}, (3.21)and setCα,β := S(0; β)× {β/α} ⊆H. (3.22)Then Kα is a nonempty closed convex cone inH andKα = posCα,β = cone(convCα,β) ∪ {0}. (3.23)Proof. Since Kα is the epigraph of the function ‖ · ‖/α, which is continuous,convex, and positively homogeneous2, we deduce from [8, Proposition10.2] that Kα is a nonempty closed convex cone in H. Next, let us es-tablish (3.23). In view of Lemma 3.22(ii), it suffices to show that Kα =cone(convCα,β) ∪ {0}. Towards this aim, let us first observe that, due toFact 3.6 and Example 3.4,convCα,β = (conv S(0; β))× (conv{β/α}) = B(0; β)× {β/α}. (3.24)Now set K := cone(convCα,β) ∪ {0}, and take x = (x, ξ) ∈ Kα. If ξ =0, then (3.21) yields x = 0 and so x = 0 ∈ K. Otherwise, ξ > 0 andwe get from (3.21) that ‖β(αξ)−1x‖ = β(αξ)−1‖x‖ 6 β or, equivalently,β(αξ)−1x ∈ B(0; β); therefore, it follows from (3.24) that(x, ξ) =αξβ(βαξx,βα)∈ αξβ(B(0; β)× {β/α}) (3.25a)=αξβconvCα,β (3.25b)⊆ cone(convCα,β) (3.25c)⊆ K. (3.25d)Altogether, Kα ⊆ K. Conversely, take y ∈ cone(convCα,β). Then, byFact 3.19(i) and (3.24), there exist λ ∈ R++ and y ∈ B(0; β) such that2A function f : H → ]−∞,+∞] is positively homogeneous if (∀x ∈ H)(∀λ ∈R++) f (λx) = λ f (x).153.3. Convex conesy = λ(y, β/α) = (λy,λβ/α). In turn, since ‖λy‖ 6 λβ = α(λβ/α), weobtain y ∈ Kα. Hence cone(convCα,β) ⊆ Kα. This and the fact that 0 ∈ Kαyield K ⊆ Kα. Hence Kα = K, as claimed. Fact 3.24 Let K be a nonempty closed convex cone inH, and let x and p beinH. Thenp = PKx ⇔[p ∈ K, x− p ⊥ p, and x− p ∈ K	 ]. (3.26)and(∀ρ ∈ R+) PK(ρx) = ρPKx. (3.27)Proof. See, e.g., [8, Proposition 6.28 and Proposition 29.29]. Let us recall the celebrated Moreau decomposition for cones; see [32].Fact 3.25 (Moreau) Let K be a nonempty closed convex cone in H, and letx ∈ H. Then the following hold:(i) x = PKx + PK	x.(ii) PKx ⊥ PK	x.(iii) ‖x‖2 = d2K(x) + d2K	(x).Fact 3.26 Let K and S be nonempty closed convex cones in H. Then thefollowing hold:(i) K		 = K.(ii) (K ∩ S)	 = K	 + S	.(iii) (K + S)	 = K	 ∩ S	.Proof. See [8, Corollary 6.34, Proposition 6.35, and Proposition 6.27]. Fact 3.27 (Zarantonello) Let K1 and K2 be nonempty closed convex conesinH. ThenK2 ⊆ K1 ⇔ [ (∀x ∈ H) 〈PK2 x | x〉 6 〈PK1 x | x〉 ]. (3.28)Proof. See [39, Lemma 5.6]. Lemma 3.28 Let K and S be nonempty closed convex cones in H. Then thefollowing hold:163.3. Convex cones(i) (∀x ∈ H) ‖PKx‖2 = 〈x |PKx〉.(ii) (∀x ∈ H) 〈PK	x |PS	x〉+ ‖PKx‖2 + ‖PSx‖2 = ‖x‖2 + 〈PKx |PSx〉.Proof. Take x ∈ H. (i): We derive from Fact 3.25(i)&(ii) that ‖PKx‖2 =〈PKx |PKx〉 = 〈x− PK	x |PKx〉 = 〈x |PKx〉, as claimed. (ii): The Moreauconical decomposition and (i) give〈PK	x |PS	x〉 = 〈x− PKx | x− PSx〉 (3.29a)= ‖x‖2 − 〈x |PSx〉 − 〈x |PKx〉+ 〈PKx |PSx〉 (3.29b)= ‖x‖2 − ‖PSx‖2 − ‖PKx‖2 + 〈PKx |PSx〉, (3.29c)and the assertion follows. Lemma 3.29 Let K be a nonempty closed convex cone inH, and let x ∈ H. Thenthe following hold:(i) PKx 6= 0⇔ x ∈ Hr K	.(ii) Suppose that PKx 6= 0. Let ρ ∈ R++, and set p := (ρ/‖PKx‖)PKx. Then‖x− p‖ =√d2K(x) + (‖PKx‖ − ρ)2. (3.30)Proof. (i): We deduce from Fact 3.25 that x ∈ K	 ⇔ x−PK	x = 0⇔ PKx =0, and the claim follows.(ii): Set β := ρ/‖PKx‖. Then, because PKx ⊥ PKx by Fact 3.24, thePythagorean identity implies that‖x− p‖2 = ‖x− βPKx‖2 (3.31a)= ‖(PKx) + (1− β)PKx‖2 (3.31b)= ‖PKx‖2 + (1− β)2‖PKx‖2 (3.31c)= d2K(x) + (1− ρ/‖PKx‖)2‖PKx‖2 (3.31d)= d2K(x) + (‖PKx‖ − ρ)2, (3.31e)and thus (3.30) holds. Definition 3.30 Let C be a subset ofH. The recession cone of C isrec C := {x ∈ H | x + C ⊆ C}. (3.32)173.4. Convex functionsFact 3.31 Let C be a nonempty convex subset of H. Then the followinghold:(i) rec C is a convex cone and 0 ∈ rec C.(ii) Suppose that C is bounded. Then rec C = {0}.Proof. See [8, Proposition 6.49(i) and Corollary 6.52]. Fact 3.32 Let C be a nonempty closed convex subset of H, and let x ∈ H.Then the following are equivalent:(i) x ∈ rec C.(ii) There exist sequences (xn)n∈N in C and (αn)n∈N in ]0, 1] such thatαn → 0 and αnxn → x.Proof. See [8, Proposition 6.51]. 3.4 Convex functionsDefinition 3.33 Let f : H → [−∞,+∞]. The domain of f is dom f :={x ∈ H | f (x) < +∞} with closure dom f , and f is proper if dom f 6= ∅and −∞ /∈ f (H). Furthermore, the set of proper lower semicontinuousconvex functions fromH to ]−∞,+∞] is denoted by Γ0(H).Fact 3.34 Let C be a subset ofH. Then the following hold:(i) C is nonempty if and only if ιC is proper.(ii) C is closed if and only if ιC is lower semicontinuous.(iii) C is convex if and only if ιC is convex.Fact 3.35 Let f : H → ]−∞,+∞] be proper. Suppose that dom f isopen and convex, and that f is Gâteaux differentiable on dom f . Thenf is convex if and only if ∇ f is monotone, i.e., (∀x ∈ dom f )(∀y ∈dom f ) 〈x− y | ∇ f (x)−∇ f (y)〉 > 0.Proof. See [8, Proposition 17.7]. 183.4. Convex functionsFact 3.36 Let f : H → ]−∞,+∞] be convex, and let x ∈ dom f . Supposethat f is Gâteaux differentiable at x. Then f is lower semicontinuous at x.Proof. See [8, Proposition 17.48(i)]. Fact 3.37 Let C be a nonempty closed convex subset of H. Then thefollowing hold:(i) d2C is Fréchet differentiable ofH and ∇d2C = 2(Id−PC).(ii) Suppose that C is a cone and set q := (1/2)‖ · ‖2. Then q ◦ PK isFréchet differentiable onH and ∇(q ◦ PK) = PK.Proof. See [8, Corollary 12.31 and Proposition 12.32]. Definition 3.38 Let f : H → [−∞,+∞]. The conjugate of f isf ∗ : H → [−∞,+∞] : u 7→ supx∈H(〈x | u〉 − f (x)), (3.33)and the biconjugate of f is f ∗∗ := ( f ∗)∗.Example 3.39 Let C be a nonempty subset of H, and set f := ιC +(1/2)‖ · ‖2. Then f ∗ = (1/2)(‖ · ‖2 − d2C).Proof. See [8, Example 13.5]. Example 3.40 Let C be a nonempty closed convex subset ofH. Then( 12 d2C)∗= σC +12‖ · ‖2. (3.34)Proof. Let p = 2 in [8, Example 13.27(iii)]. Fact 3.41 (Self-conjugacy) Let f : H → [−∞,+∞]. Thenf = f ∗ ⇔ f = 12‖ · ‖2. (3.35)Proof. See [8, Proposition 13.19]. Fact 3.42 (Fenchel–Moreau) Let f : H → ]−∞,+∞] be proper. Then f ∈Γ0(H) if and only if f = f ∗∗. In this case, f ∗ belongs to Γ0(H) as well.193.4. Convex functionsFact 3.43 Let g : H → ]−∞,+∞] be proper, let h ∈ Γ0(H), and setf : H → [−∞,+∞] : x 7→{g(x)− h(x), if x ∈ dom g;+∞, otherwise.(3.36)Then(∀u ∈ H) f ∗(u) = supv∈dom h∗(g∗(u + v)− h∗(v)). (3.37)Proof. See [8, Proposition 14.19]. Definition 3.44 Let f ∈ Γ0(H), and let x ∈ H. Then Prox f x is the uniquepoint inH that satisfiesminy∈H(f (y) + 12‖x− y‖2)= f (Prox f x) + 12‖x− Prox f x‖2. (3.38)The operator Prox f : H → H is the proximity operator—or proximal map-ping—of f .Definition 3.45 Let f and g be functions from H to ]−∞,+∞]. The infimalconvolution of f and g isf  g : H → [−∞,+∞] : x 7→ infy∈H(f (y) + g(x− y)), (3.39)and it is exact at a point x ∈ H if(∃y ∈ H) ( f  g)(x) = f (y) + g(x− y) ∈ ]−∞,+∞]; (3.40)furthermore, f  g is exact if it is exact at every point of its domain, in whichcase we write f  g.Fact 3.46 Let f and g be functions fromH to ]−∞,+∞]. Then the followinghold:(i) Suppose that f 6 g. Then g∗ 6 f ∗.(ii) ( f  g)∗ = f ∗ + g∗.Proof. (i): See [8, Proposition 13.16(ii)]. (ii): See [8, Proposition 13.24(i)]. Fact 3.47 (Moreau) Let f ∈ Γ0(H) and set q := (1/2)‖ · ‖2. Then( f q) + ( f ∗q) = q and Prox f + Prox f ∗ = Id . (3.41)203.5. Subdifferential operators3.5 Subdifferential operatorsDefinition 3.48 Let f : H → ]−∞,+∞] be proper. The subdifferential of f is∂ f : H → 2H : x 7→ {u ∈ H | (∀y ∈ H) 〈y− x | u〉+ f (x) 6 f (y)}. (3.42)Fact 3.49 Let f ∈ Γ0(H). Then the following hold:(i) ∂ f ∗ = (∂ f )−1.(ii) dom ∂ f is a dense subset of dom f .Proof. See, e.g., [8, Corollary 16.30 and Corollary 16.39]. Fact 3.50 Let f : H → ]−∞,+∞] be proper and convex, and let x ∈ dom f .Suppose that f is Gâteaux differentiable at x. Then the following hold:(i) ∂ f (x) = {∇ f (x)}.(ii) f ∗(∇ f (x)) = 〈x | ∇ f (x)〉 − f (x).Proof. See [8, Proposition 17.31(i) and Proposition 17.35]. 3.6 Monotone operatorsDefinition 3.51 Let A : H → 2H. Then A is monotone if(∀(x, u) ∈ gra A)(∀(y, v) ∈ gra A) 〈x− y | u− v〉 > 0. (3.43)Furthermore, A is maximally monotone if it is monotone and there is nomonotone operator B : H → 2H such that gra A is a proper subset of gra B.Example 3.52 Let C be a nonempty subset ofH. Then PC is monotone.Proof. See [8, Example 20.12]. Fact 3.53 Let T : H → H be nonexpansive, i.e., Lipschitz continuous withconstant 1. Then Id−T is monotone.Proof. See [8, Example 20.7]. 213.6. Monotone operatorsFact 3.54 Let T : H → H be linear and continuous. Then L∗L is monotone,where L∗ : H → H is the adjoint of L.Proof. See [8, Example 20.16]. Fact 3.55 Let T : H → H be monotone and continuous. Then T is maxi-mally monotone.Proof. See [8, Corollary 20.28]. Example 3.56 Let C be a nonempty closed convex subset of H. Then PC ismaximally monotone.Proof. See [8, Example 20.32]. Definition 3.57 Let A : H → 2H be monotone. Then A is 3∗ monotone if(∀(x, u) ∈ dom A× ran A) inf(y,v)∈gra A〈x− y | u− v〉 > −∞. (3.44)Example 3.58 Let C be a nonempty closed convex subset of H. Then PC is3∗ monotone.Proof. Combine [8, Proposition 4.16 and Example 25.20(ii)]. Fact 3.59 Let A and B be 3∗ monotone operators fromH to 2H. Then A+ Bis 3∗ monotone.Proof. See [8, Proposition 25.22(i)]. Fact 3.60 (Brézis–Haraux) Let A and B be 3∗ monotone operators from Hto 2H such that A + B is maximally monotone. Thenran(A + B) = ran A + ran B. (3.45)Proof. See, e.g., [8, Theorem 25.24]. 22Chapter 4Projecting onto the intersectionof a cone and a sphere4.1 OverviewLet K and S be subsets of H. Only in rare cases is it possible to obtaina “closed form” for PK∩S in terms of PK and PS: e.g., when K and S areeither both half-spaces (Haugazeau; see [22] and also [8, Corollary 29.25])or both subspaces (Anderson–Duffin; see [1, Theorem 8] and also [8, Corol-lary 25.38]). Inspired by Example 5.5.2 in the recent and charming book[28], our aim in this chapter is to systematically study the case when K is a closedconvex cone and S is either the (convex) unit ball or (nonconvex) unit spherecentered at the origin. We obtain formulae describing the full (possibly set-valued) projector and also discuss nonpolyhedral cones such as the Lorentzcone or the cone of positive semidefinite matrices. We also revisit Lange’scopositivity example and tackle it with other algorithms that appear toperform quite well.We conclude this short introductory section with some comments onthe organization of this chapter. In Section 4.2, we provide various resultson cones and conical hulls. Cones that are finitely generated and corre-sponding projectors are investigated in Section 4.3. Our main results arepresented in Section 4.4 (cone intersected with ball) and Section 4.5 (coneintersected with sphere), respectively. Additional examples are providedin Section 4.6. In the final Section 4.7, we put the theory to good use andoffer new algorithmic approaches to determine copositivity.4.2 Cones and conical hulls revisitedIn general, for subsets C and D of H, C ∩ D 6= C ∩ D. However, thefollowing result provides an interesting instance where taking intersections234.2. Cones and conical hulls revisitedand closures commutes.Proposition 4.1 Let K be a nonempty cone in H, and let ρ ∈ R++. Then thefollowing hold:(i) K ∩ S(0; ρ) = K ∩ S(0; ρ).(ii) K ∩ B(0; ρ) = K ∩ B(0; ρ).Proof. We assume thatK 6= {0}, (4.1)since otherwise the assertions are clear.(i): Since we obviously have K ∩ S(0; ρ) ⊆ K∩ S(0; ρ), it suffices to verifythat K ∩ S(0; ρ) ⊆ K ∩ S(0; ρ). To do so, take x ∈ K ∩ S(0; ρ). Then, becausex ∈ K, there exists a sequence (xn)n∈N in K such thatxn → x. (4.2)In turn, by the continuity of ‖ · ‖ and the fact that x ∈ S(0; ρ),‖xn‖ → ‖x‖ = ρ ∈ R++, (4.3)and therefore, we can assume without loss of generality that(∀n ∈N) ‖xn‖ 6= 0. Hence, for every n ∈ N, since xn ∈ K and‖ρxn/‖xn‖‖ = ρ, the assumption that K is a cone implies that ρxn/‖xn‖lies in K ∩ S(0; ρ). Thus, (ρxn/‖xn‖)n∈N is a sequence in K ∩ S(0; ρ);moreover, (4.2) and (4.3) assert that ρxn/‖xn‖ → ρx/ρ = x. Consequently,x ∈ K ∩ S(0; ρ), as announced.(ii): First, it is clear that K ∩ B(0; ρ) ⊆ K ∩ B(0; ρ). Conversely, fix x ∈K ∩ B(0; ρ), and we shall consider two conceivable cases:(a) x = 0: By (4.1), there existsy ∈ Kr {0}. (4.4)In turn, set(∀n ∈N) yn := ρ(n + 1)‖y‖y. (4.5)Then, for every n ∈ N, since K is a cone, (4.4) and (4.5) assert that yn ∈ Kand thus, since ‖yn‖ = ρ/(n + 1) 6 ρ by (4.5), we deduce that yn ∈ K ∩B(0; ρ). Hence, because yn = ρy/[(n + 1)‖y‖] → 0 = x, we infer thatx ∈ K ∩ B(0; ρ).244.2. Cones and conical hulls revisited(b) x 6= 0: Since x ∈ K, there is a sequence (xn)n∈N in K such thatxn → x. (4.6)In turn, by the continuity of ‖ · ‖,‖xn‖ → ‖x‖ ∈ R++, (4.7)and we can therefore assume that (∀n ∈N) ‖xn‖ 6= 0. Now set(∀n ∈N) yn := ‖x‖‖xn‖ xn. (4.8)For every n ∈ N, because xn ∈ K and ‖x‖ 6 ρ, the assumption thatK is a cone and (4.8) yield yn ∈ K ∩ B(0; ρ). Consequently, since yn →‖x‖x/‖x‖ = x due to (4.6) and (4.7), we obtain x ∈ K ∩ B(0; ρ).To sum up, in both cases, we have x ∈ K ∩ B(0; ρ), and the conclusionfollows. Here is an improvement of [8, Corollary 6.53].Proposition 4.2 Let C be a nonempty closed convex set inH. Suppose that thereexists a nonempty closed subset D of C such that 0 /∈ D and that one of thefollowing holds:(a) (cone D) ∪ {0} = (cone C) ∪ {0}.(b) cone D = cone C.Then the following hold:(i) (cone C) ∪ (rec C) = cone C.(ii) Suppose that rec C = {0}. Then cone(C ∪ {0}) is closed.Proof. Let us first show that (a)⇒(b). To establish this, assume that (a)holds. Then, since 0 ∈ cone D and 0 ∈ cone C due to Remark 3.18, weinfer from Fact 3.19(ii) that cone D = cone D ∪ {0} = (cone D) ∪ {0} =(cone C) ∪ {0} = cone C ∪ {0} = cone C, which verifies the claim. Thus, itis enough to assume that (b) holds and to show that (i)&(ii) hold.(i): Clearly cone C ⊆ cone C. We now prove that rec C ⊆ cone C. Tothis end, take x ∈ rec C. Then Fact 3.32 ensures the existence of sequences254.2. Cones and conical hulls revisited(xn)n∈N in C and (αn)n∈N in ]0, 1] such that αnxn → x. Hence, because{αnxn}n∈N ⊆ cone C by Fact 3.19(i), we deduce from Fact 3.19(ii) that x ∈cone C = cone C. Thus (cone C) ∪ rec C ⊆ cone C. Conversely, fix y ∈cone C = cone D. It then follows from Fact 3.19(ii) that y ∈ cone D, andtherefore, in view of Fact 3.19(i), there exist sequences (βn)n∈N inR++ and(yn)n∈N in D such thatβnyn → y. (4.9)After passing to subsequences and relabeling if necessary, we assume thatβn → β ∈ [0,+∞]. (4.10)In turn, let us establish that β ∈ R+ by contradiction: assume that β = +∞.Then it follows from (4.9) that ‖yn‖ = (1/βn)‖βnyn‖ → 0 or, equivalently,yn → 0. Hence, since {yn}n∈N ⊆ D, the closedness of D asserts that 0 ∈ D,which violates our assumption. Therefore β ∈ R+, and this leads to twoconceivable cases:(a) β = 0: Then, by (4.10), we can assume without loss of generalitythat {βn}n∈N ⊆ ]0, 1]. In turn, since {yn}n∈N ⊆ D ⊆ C, we infer from(4.9)&(4.10) and Fact 3.32 that y ∈ rec C.(b) β > 0: Then, in view of (4.9)&(4.10), yn = (1/βn)(βnyn) → y/β.Therefore, because {yn}n∈N ⊆ C and C is closed, we obtain y/β ∈ C.Consequently, y ∈ βC ⊆ cone C.To sum up, (cone C) ∪ (rec C) = cone C, as announced.(ii): Since C = conv C by the convexity of C, we derive from (i) andLemma 3.22(ii) that cone C = (cone C) ∪ {0} = cone(C ∪ {0}), whichguarantees that cone(C ∪ {0}) is closed. Corollary 4.3 Let C be a nonempty subset of H, and set K := pos C. Supposethat 0 /∈ conv C and that conv C is weakly compact. Then K is the smallest closedconvex cone containing C ∪ {0}.Proof. According to Lemma 3.22(iii), it suffices to verify that K is closed.Since conv C is weakly compact, it is weakly closed and bounded. In turn,on the one hand, since conv C is convex and weakly closed, we derivefrom [8, Theorem 3.34] that conv C is closed. On the other hand, theboundedness of conv C guarantees that rec(conv C) = {0}. Altogether,because K = cone({0} ∪ conv C) due to Lemma 3.22(ii) and because0 /∈ conv C, applying Proposition 4.2(ii) to conv C (with the subset D—asin the setting of Proposition 4.2—being conv C) yields the closedness of K,as required. 264.2. Cones and conical hulls revisitedThe following two examples provide instances in which the assumptionof Proposition 4.2 holds.Example 4.4 Let C be a nonempty closed convex subset of H such thatCr {0} 6= ∅. Suppose that there exists ρ ∈ R++ satisfying(cone C) ∩ S(0; ρ) ⊆ C, (4.11)and set D := (cone C) ∩ S(0; ρ). Then the following hold:(i) D is a nonempty closed subset of C and 0 /∈ D.(ii) (cone D) ∪ {0} = (cone C) ∪ {0}.Proof. (i): The closedness of D is clear. Next, since 0 /∈ S(0; ρ), we have0 /∈ D. In turn, since C r {0} 6= ∅, we see that ∅ 6= cone C 6= {0},and since cone C is a cone, Remark 3.18 yields D 6= ∅. Finally, it followsfrom Fact 3.19(ii), Proposition 4.1(i) (applied to cone C), (4.11), and theclosedness of C that D = cone C ∩ S(0; ρ) = (cone C) ∩ S(0; ρ) ⊆ C = C, asclaimed.(ii): Because D ⊆ C, we get (cone D) ∪ {0} ⊆ (cone C) ∪ {0}. Con-versely, take x ∈ cone C. We then deduce from Fact 3.19(i) the existence ofλ ∈ R++ and y ∈ C such that x = λy. If y = 0, then x = 0 ∈ (cone D) ∪{0}. Otherwise, ‖y‖ 6= 0 and, since ρy/‖y‖ ∈ (cone C) ∩ S(0; ρ) ⊆ D, weobtain x = λy = (λ‖y‖/ρ)(ρy/‖y‖) ∈ cone D. Therefore (cone C)∪ {0} ⊆(cone D) ∪ {0}, and the conclusion follows. Before we present a new proof of the well-known fact that finitelygenerated cones are closed (see [34, Theorem 19.1, Corollary 2.6.2 and theremarks following Corollary 2.6.3]), we make a few comments.Remark 4.5 Let {xi}i∈I be a finite subset ofH, and set C := conv{xi}i∈I .(i) Since C = conv∪i∈I{xi}, [8, Proposition 3.39(i)] implies that C iscompact, and so it is closed and bounded. In turn, the boundednessof C and Fact 3.31(ii) give rec C = {0}.(ii) The geometric interpretation of the proof of Example 4.6 is as follows.If y lies in Cr {0}, then the ray R+y must intersect a “face” of C thatdoes not contain 0.(iii) Example 4.6 illustrates that the assumption of Proposition 4.2 is mildand covers the case of finitely generated cones.274.2. Cones and conical hulls revisitedExample 4.6 Let {xi}i∈I be a finite subset ofH and setK :=∑i∈IR+xi. (4.12)Then K is the smallest closed convex cone containing {xi}i∈I ∪ {0}.Proof. We derive from (3.15) and Lemma 3.22(iii) that K is the smallestconvex cone inH containing {xi}i∈I ∪{0}. Therefore, it suffices to establishthe closedness of K. Towards this goal, we first infer from Lemma 3.22(ii)(applied to {xi}i∈I) thatK = cone({0} ∪ conv{xi}i∈I). (4.13)Furthermore, we assume that{xi}i∈I r {0} 6= ∅, (4.14)because otherwise the claim is trivial. In turn, set C := conv{xi}i∈I ,I := {∅ 6= J ⊆ I ∣∣ 0 /∈ conv{xi}i∈J}, (4.15)andD :=⋃J∈Iconv{xi}i∈J ⊆ C. (4.16)Then, by (4.14), I is nonempty,3 and thus, 0 /∈ D 6= ∅. Moreover, D isclosed as a finite union of closed sets, namely (conv{xi}i∈J)J∈I . We nowclaim that(cone D) ∪ {0} = (cone C) ∪ {0}. (4.17)To do so, it suffices to verify that (cone C) ∪ {0} ⊆ (cone D) ∪ {0}. Takex ∈ (cone C)r {0}. Then Fact 3.19(i) ensures the existence of λ ∈ R++ andy ∈ Cr {0} (4.18)such that x = λy. Since y ∈ C = conv{xi}i∈I , there exist a nonempty subsetJ of I and{αi}i∈J ⊆ ]0, 1] (4.19)such that ∑i∈J αi = 1 and y = ∑i∈J αixi. If J ∈ I , then y ∈ conv{xi}i∈J ⊆ Dand hence x = λy ∈ cone D. Otherwise, 0 ∈ conv{xi}i∈J , and there thus3We just need to pick a nonzero element xj of {xi}i∈I and set J := {j}.284.3. Projectors onto cones generated by orthonormal setsexists {βi}i∈J ⊆ [0, 1] such that ∑i∈J βixi = 0 and J+ := {i ∈ J | βi > 0} 6=∅. In turn, setγ := mini∈J+αiβi(4.20)and (∀i ∈ J) δi := αi − γβi. By (4.19) and (4.20),(∀i ∈ J) δi > 0. (4.21)Now fix j ∈ J+ such that αj/β j = γ. Then we get δj = 0 as well as Jr {j} 6=∅ (since otherwise, J = {j} and y = αjxj = γβ jxj = 0, which is absurd),and hence,y = y− γ0 =∑i∈Jαixi − γ∑i∈Jβixi = ∑i∈Jr{j}δixi. (4.22)Therefore, in view of (4.21), (4.22), and (4.18), we must have ∑i∈Jr{j} δi >0. In turn, if J r {j} ∈ I , then set δ := ∑i∈Jr{j} δi and observe that y =δ∑i∈Jr{j}(δi/δ)xi ∈ cone D, which yields x = λy ∈ cone D. Otherwise,we reapply the procedure to y = ∑i∈Jr{j} δixi recursively until y can bewritten as y = ∑i∈J′ γixi, where J′ ∈ I and {γi}i∈J′ ⊆ R+ satisfying µ :=∑i∈J′ γi > 0. Consequently, y = µ∑i∈J′(γi/µ)xi ∈ cone D, from whichwe deduce that x = λy ∈ cone D. Thus (4.17) holds, and since rec C ={0} (see Remark 4.5(i)), it follows from Proposition 4.2(ii) (applied to C =conv{xi}i∈I) and (4.13) that K is closed, as desired. 4.3 Projectors onto cones generated by orthonormalsetsWe start with a conical version of [8, Example 3.10].Theorem 4.7 Let {ei}i∈I be a nonempty finite orthonormal subset ofH, setK :=∑i∈IR+ei, (4.23)and let x ∈ H. Then K is a nonempty closed convex cone inH,PKx =∑i∈Imax{〈x | ei〉, 0}ei, and dK(x) =√‖x‖2 −∑i∈I(max{〈x | ei〉, 0})2.(4.24)294.3. Projectors onto cones generated by orthonormal setsProof. We first infer from Example 4.6 that K is a nonempty closed convexcone. Thus, it is enough to verify (4.24). To this end, set(∀i ∈ I) αi := max{〈x | ei〉, 0} ∈ R+ (4.25)andp :=∑i∈Iαiei. (4.26)Then, by (4.25)&(4.26)&(4.23), we have p ∈ K, and by assumption, we get‖p‖2 =∥∥∥∥∥∑i∈I αiei∥∥∥∥∥2=∑i∈Iα2i . (4.27)Furthermore, (4.25) implies that(∀i ∈ I) [ αi = 〈x | ei〉 or αi = 0 ]⇔ αi(〈x | ei〉 − αi) = 0⇔ αi〈x | ei〉 = α2i ,(4.28)and therefore, we get from (4.26) that〈x | p〉 =〈x∣∣∣∣∣∑i∈I αiei〉=∑i∈Iαi〈x | ei〉 =∑i∈Iα2i . (4.29)In turn, on the one hand, (4.27) and (4.29) yield 〈x− p | p〉 = 〈x | p〉 −‖p‖2 = 0. On the other hand, invoking (4.26), (4.25), and our hypothesis,we deduce that(∀i ∈ I) 〈x− p | ei〉 = 〈x | ei〉 −〈∑j∈Iαjej∣∣∣∣∣ ei〉= 〈x | ei〉 − αi 6 0, (4.30)and hence, by (4.23), x− p ∈ K	. Altogether, we conclude that PKx = p =∑i∈I max{〈x | ei〉, 0}ei via Fact 3.24. Consequently, (4.27)&(4.29)&(4.25) gived2K(x) = ‖x− p‖2 (4.31a)= ‖x‖2 − 2〈x | p〉+ ‖p‖2 (4.31b)= ‖x‖2 −∑i∈Iα2i (4.31c)= ‖x‖2 −∑i∈I(max{〈x | ei〉, 0})2, (4.31d)which completes the proof. 304.3. Projectors onto cones generated by orthonormal setsRemark 4.8 Here are a few comments concerning Theorem 4.7.(i) In the setting of Theorem 4.7, suppose that {ei}i∈I is a singleton, saye. Then K = R+e is a ray and (4.24) becomesPKx = max{〈x | e〉, 0}e and dK(x) =√‖x‖2 − (max{〈x | e〉, 0})2,(4.32)which is precisely the formula for projectors onto rays (see, e.g., [8,Example 29.31]).(ii) Consider the setting of Theorem 4.7. Suppose that N is a strictlypositive integer, that I = {1, . . . , N}, that H = RN , and that (ei)i∈Iis the canonical orthonormal basis ofH. Then K = RN+ is the positiveorthant in H. Now take x = (ξi)i∈I ∈ H. In the light of (4.24), since(∀i ∈ I) 〈x | ei〉 = ξi, we retrieve the well-known formulaPKx = (max{ξi, 0})i∈I ; (4.33)see, for instance, [8, Example 6.29]. Moreover, upon setting I− :={i ∈ I | ξi < 0}, we derive from (4.24) thatdK(x) =√‖x‖2 −∑i∈I(max{ξi, 0})2 (4.34a)=√∑i∈Iξ2i − ∑i∈IrI−ξ2i (4.34b)=√∑i∈I−ξ2i (4.34c)with the convention that ∑i∈∅ ξ2i = 0.Corollary 4.9 Let {ei}i∈I be a nonempty finite orthonormal subset ofH. SetK := {y ∈ H | (∀i ∈ I) 〈y | ei〉 6 0}, (4.35)and let x ∈ H. Then K is a nonempty closed convex cone inH,PKx = x−∑i∈Imax{〈x | ei〉, 0}ei, and dK(x) =√∑i∈I(max{〈x | ei〉, 0})2.(4.36)Proof. SinceK =⋂i∈I{ei}	, (4.37)314.4. The projector onto the intersection of a cone and a ballwe see that K is a nonempty closed convex cone. Next, by (4.37),Fact 3.26(iii) implies that K =⋂i∈I (R+ei)	 = (∑i∈I R+ei)	, andsince ∑i∈I R+ei is a nonempty closed convex cone by Example 4.6,taking the polar cones and invoking Fact 3.26(ii) yield K	 =(∑i∈I R+ei)		 = ∑i∈I R+ei. Hence, according to Moreau’s theorem(Fact 3.25) and Theorem 4.7, we conclude that PKx = x − PK	x =x−∑i∈I max{〈x | ei〉, 0}ei and thatd2K(x) = ‖x‖2 − d2K	(x) (4.38a)= ‖x‖2 −(‖x‖2 −∑i∈I(max{〈x | ei〉, 0})2)(4.38b)=∑i∈I(max{〈x | ei〉, 0})2, (4.38c)as claimed in (4.36). 4.4 The projector onto the intersection of a cone and aballIt turns out that the projector onto the intersection of a cone and a ballhas a pleasing explicit form.Theorem 4.10 (cone intersected with ball) Let K be a nonempty closed convexcone inH, let ρ ∈ R++, and set C := K ∩ B(0; ρ). Then(∀x ∈ H)PCx =ρmax{‖PKx‖, ρ} PKx,dC(x) =√d2K(x) + (max{‖PKx‖ − ρ, 0})2.(4.39)Proof. Take x ∈ H, set β := ρ/ max{‖PKx‖, ρ} ∈ R++, and set p := βPKx.Then, since K is a cone and PKx ∈ K, we get p ∈ K, and thus, since ‖p‖ =β‖PKx‖ = ρ(‖PKx‖/ max{‖PKx‖, ρ}) 6 ρ, it follows that p ∈ K ∩ B(0; ρ) =C. Hence, because C is closed and convex, in the light of (3.8), it remains toverify that (∀y ∈ C) 〈x− p | y− p〉 6 0. To this end, take y ∈ C, and weconsider two alternatives:(a) ‖PKx‖ 6 ρ: Then β = ρ/ρ = 1. It follows that p = PKx, and so‖x− p‖ = ‖x− PKx‖ = dK(x). (4.40)324.4. The projector onto the intersection of a cone and a ballNext, because y ∈ K, (3.8) asserts that〈x− p | y− p〉 = 〈x− PKx | y− PKx〉 6 0. (4.41)(b) ‖PKx‖ > ρ: Then β = ρ/‖PKx‖ ∈ ]0, 1[, and so Lemma 3.29(ii)implies that‖x− p‖ =√d2K(x) + (‖PKx‖ − ρ)2. (4.42)In turn, on the one hand, since y belongs to the cone K, it follows that(1/β)y ∈ K, from which and (3.8) we deduce that〈x− PKx | y− βPKx〉 = β〈x− PKx | (1/β)y− PKx〉 6 0. (4.43)On the other hand, because y ∈ B(0; ρ) and β = ρ/‖PKx‖, theCauchy–Schwarz inequality yields〈PKx | y− βPKx〉 = 〈PKx | y〉− ρ‖PKx‖ 6 ‖PKx‖‖y‖− ρ‖PKx‖ 6 0. (4.44)Altogether, combining (4.43)&(4.44) and using the fact that β ∈ ]0, 1[, weobtain〈x− p | y− p〉 = 〈x− βPKx | y− βPKx〉 (4.45a)= 〈x− PKx | y− βPKx〉+ (1− β)〈PKx | y− βPKx〉 (4.45b)6 0. (4.45c)Hence, in both cases, we have 〈x− p | y− p〉 6 0. Thus p = PCx, and itfollows from (4.40)&(4.42) thatdC(x) = ‖x− PCx‖ = ‖x− p‖ =√d2K(x) + (max{‖PKx‖ − ρ, 0})2, (4.46)as stated in (4.39). Here are some easy consequences of Theorem 4.10.Example 4.11 In the setting of Theorem 4.10, suppose that K = H. ThenC = B(0; ρ), PK = Id, dK ≡ 0, and (4.39) becomes(∀x ∈ H) PCx = ρmax{‖x‖, ρ} x and dC(x) = max{‖x‖ − ρ, 0}.(4.47)We thus recover the formula for projectors onto balls. For a rigorous proofof (4.47) without invoking (3.8), see [10, Example 5].334.4. The projector onto the intersection of a cone and a ballCorollary 4.12 Let K be a nonempty closed convex cone in H, let ρ ∈ R++, andset C := K ∩ B(0; ρ). Then PC = PB(0;ρ) ◦ PK.Proof. Combine (4.39) and (4.47). Alternatively, set f := ιB(0;ρ) and κ := ιKin the equivalence “(iii)⇔(iv)” of [37, Theorem 4]. (Note that ιB(0;ρ) + ιK =ιC.) Remark 4.13 In the setting of Corollary 4.12, as we shall see in Exam-ple 4.14, PC 6= PK ◦ PB(0;ρ), i.e., PB(0;ρ) ◦ PK 6= PK ◦ PB(0;ρ), in general.Example 4.14 Suppose that H = R2. Set K := R2+ and x := (1,−1). Then(see also Figure 4.1)(PK ◦ PB(0;1))x = PK(PB(0;1)x) (4.47)= PK(1√2,− 1√2)(4.33)=(1√2, 0)(4.48)and(PB(0;1) ◦ PK)x = PB(0;1)(PKx) (4.33)= PB(0;1)(1, 0) (4.47)= (1, 0). (4.49)HencePB(0;1) ◦ PK 6= PK ◦ PB(0;1). (4.50)RR0x = (1,−1)PB(0;1)xPK(PB(0;1)x)K ∩ B(0; 1)PB(0;1)(PK x)Figure 4.1: Example 4.14 illustrates that the projectors onto a cone and ballmay fail to commute.344.5. The projector onto the intersection of a cone and a sphereAs will be seen in the next result, Example 4.14 is, however, not acoincidence.Corollary 4.15 Let K be a nonempty closed convex cone in H, and let ρ ∈ R++.Then(∀x ∈ H) (PK ◦ PB(0;ρ))x =ρmax{‖x‖, ρ} PKx. (4.51)Proof. It follows from (4.47) and (3.27) that(∀x ∈ H) (PK ◦ PB(0;ρ))x = PK(PB(0;ρ)x) (4.52a)= PK(ρmax{‖x‖, ρ} x)(4.52b)=ρmax{‖x‖, ρ} PKx, (4.52c)as desired. Remark 4.16 Consider the setting of Corollary 4.15. Using Corollary 4.15,Theorem 4.10, and Corollary 4.12, we deduce that(∀x ∈ H) (PK ◦ PB(0;ρ))x =max{‖PKx‖, ρ}max{‖x‖, ρ} (PB(0;ρ) ◦ PK)x. (4.53)4.5 The projector onto the intersection of a cone and asphereIn this section, which contains our second half of main results, wedevelop formulae for the projector onto the intersection of a cone and asphere.Lemma 4.17 Let C be a nonempty subset ofH, let β ∈ R++, and let u ∈ pos C4,say u = ∑i∈I αixi, where {αi}i∈I and {xi}i∈I are finite subsets of R+ and C,respectively. Suppose that ‖u‖ = β and that (∀y ∈ C) ‖y‖ = β. Then thefollowing hold:(i) ∑i∈I αi > 1.(ii) Let x ∈ H, and set κ := sup〈x |C〉. Suppose that κ ∈ ]−∞, 0] and thatκ 6 〈x | u〉. Then the following hold:4Here pos C was defined in (3.14).354.5. The projector onto the intersection of a cone and a sphere(a) PCx 6= ∅ and 〈x | u〉 = max〈x |C〉 = κ.(b) u ∈ S(0; β) ∩ cone(conv PCx).(c) Suppose that κ < 0. Then u ∈ PCx.Proof. (i): Since, by assumption, (∀i ∈ I) ‖xi‖ = β, it follows from thetriangle inequality thatβ = ‖u‖ =∥∥∥∥∥∑i∈I αixi∥∥∥∥∥ 6∑i∈I αi‖xi‖ = β∑i∈I αi. (4.54)Therefore, because β > 0, we obtain ∑i∈I αi > 1.(ii): Let us first establish that(∀i ∈ I) xi ∈ Cr PCx ⇒ αi = 0 (4.55)by contradiction: assume that there exists i0 ∈ I such thatxi0 ∈ Cr PCx (4.56)but thatαi0 > 0. (4.57)Then, because the vectors in C are of equal norm, we deduce fromLemma 3.9(i) and (4.56) that 〈x | xi0〉 < sup〈x |C〉 = κ, and so, by (4.57),αi0〈x | xi0〉 < αi0κ. Hence, sinceκ 6 0,κ 6 〈x | u〉,(∀i ∈ I) 0 6 αi and 〈x | xi〉 6 κ,(4.58)it follows from (i) thatκ 6 〈x | u〉 =∑i∈Iαi〈x | xi〉 (4.59a)= αi0〈x | xi0〉+ ∑i∈Ir{i0}αi〈x | xi〉 (4.59b)< αi0κ + ∑i∈Ir{i0}αiκ (4.59c)= κ∑i∈Iαi (4.59d)6 κ, (4.59e)364.5. The projector onto the intersection of a cone and a sphereand we thus arrive at a contradiction, namely κ < κ. Therefore, (4.55) holds.(ii)(a): If PCx were empty, then (4.55) would yield (∀i ∈ I) αi = 0and it would follow that u = 0 or, equivalently, β = ‖u‖ = 0, which isabsurd. Thus PCx 6= ∅, and so Lemma 3.9(i) implies that κ = max〈x |C〉.Furthermore, we infer from (4.58) and (i) thatκ 6 〈x | u〉 =∑i∈Iαi〈x | xi〉 6∑i∈Iαiκ = κ∑i∈Iαi 6 κ, (4.60)and the latter assertion follows.(ii)(b): In the remainder, since u 6= 0, appealing to (4.55), we assumewithout loss of generality that(∀i ∈ I) xi ∈ PCx (4.61)and that (∀i ∈ I)(∀j ∈ I) i 6= j ⇒ xi 6= xj. Hence, upon setting α :=∑i∈I αi > 1, we deduce from (4.61) thatu = α∑i∈Iαiαxi ∈ α conv PCx ⊆ cone(conv PCx). (4.62)Consequently, since ‖u‖ = β, the claim follows.(ii)(c): Invoking Lemma 3.9(i) and (4.61), we get (∀i ∈ I) 〈x | xi〉 =max〈x |C〉 = κ. Thus, by (ii)(a), κ = 〈x | u〉 = ∑i∈I αi〈x | xi〉 = κ∑i∈I αi,and since κ 6= 0, it follows that ∑i∈I αi = 1. To summarize, we haveu = ∑i∈I αixi,(∀i ∈ I) ‖xi‖ = ‖u‖ = β,{αi}i∈I ⊆ R+ satisfying ∑i∈I αi = 1,(∀i ∈ I)(∀j ∈ I) i 6= j⇒ xi 6= xj.(4.63)Lemma 2.3(iii) and (4.61) therefore imply that (∃i ∈ I) u = xi ∈ PCx, asdesired. The following example shows that the conclusion of Lemma 4.17(ii)(c)fails if the assumption that u ∈ pos C is omitted.Example 4.18 Suppose that H = R3 and that (e1, e2, e3) is the canonicalorthonormal basis of H. Set C := {e1, e2}, x := (−1,−1, 0), and u :=(1/2, 1/2,√2/2). Then u is not a conical combination of elements of C and,as in the assumption of Lemma 4.17, (β, κ) = (1,−1). Moreover, a simplecomputation gives ‖u‖ = 1, 〈x | u〉 = −1 = κ, and ‖x− e1‖ = ‖x− e2‖ =√5. Hence, PCx = C 6= ∅while u /∈ C.374.5. The projector onto the intersection of a cone and a sphereTheorem 4.19 Let K be a nonempty closed convex cone in H, let ρ ∈ R++, andset C := K ∩ S(0; ρ). Suppose that K 6= {0}. Then the following hold:(i) For every x ∈ K⊥, PCx = C and dC(x) =√‖x‖2 + ρ2.(ii) For every x ∈ H r K	, PCx = {(ρ/‖PKx‖)PKx} and dC(x) =√d2K(x) + (‖PKx‖ − ρ)2.Proof. We first observe that, by assumption and Remark 3.18, C 6= ∅.(i): Fix x ∈ K⊥. Then, for every y ∈ C = K ∩ S(0; ρ), since x ⊥ y and‖y‖ = ρ, we get ‖x − y‖2 = ‖x‖2 + ‖y‖2 = ‖x‖2 + ρ2. It follows thatdC(x) =√‖x‖2 + ρ2 and that PCx = C, as desired.(ii): First, by the very definition of C, we see thatC consists of vectors of equal norm. (4.64)Now take x ∈ Hr K	; set5 α := ρ/‖PKx‖ ∈ R++ andp := αPKx. (4.65)Then, because PKx belongs to the cone K, we obtain p ∈ K, and because‖p‖ =∥∥∥∥ ρ‖PKx‖ PKx∥∥∥∥ = ρ, (4.66)it follows thatp ∈ K ∩ S(0; ρ) = C. (4.67)Next, fix y ∈ C. Since y ∈ C ⊆ K and K is a cone, we have α−1y ∈ K.Therefore, since ‖y‖ = ρ, we derive from (4.65), (3.8), and (4.66) that〈x | p〉 − 〈x | y〉 = 〈x | p− y〉 (4.68a)= 〈x− PKx | p− y〉+ 〈PKx | p− y〉 (4.68b)= 〈x− PKx | αPKx− y〉+ 〈α−1 p | p− y〉 (4.68c)= α 〈x− PKx |PKx− α−1y〉︸ ︷︷ ︸>0 by (3.8)+α−1〈p | p− y〉 (4.68d)> (2α)−1(‖p‖2 + ‖p− y‖2 − ‖y‖2) (4.68e)= (2α)−1(ρ2 + ‖p− y‖2 − ρ2) (4.68f)5Due to Lemma 3.29(i), we have PKx 6= 0.384.5. The projector onto the intersection of a cone and a sphere= (2α)−1‖p− y‖2. (4.68g)To summarize, we have shown that (∀y ∈ C) y 6= p ⇒ 〈x | y〉 < 〈x | p〉.Combining this, (4.67), and (4.64), we infer from Lemma 3.9(i) that PCx ={p}. This and Lemma 3.29(ii) yield the latter assertion, and the proof iscomplete. Let us provide some examples.Corollary 4.20 (Projections onto circles) Let V be a nonzero closed linearsubspace ofH, let ρ ∈ R++, and set C := V ∩ S(0; ρ). Then(∀x ∈ H) PCx =C, if x ∈ V⊥;{ρ‖PV x‖ PV x}, otherwise.(4.69)Proof. Combine Theorem 4.19 and the fact that V	 = V⊥. Remark 4.21 Letting V = H in Corollary 4.20, we see that C = S(0; ρ), thatV⊥ = {0}, that PV = Id, and that (4.69) becomes(∀x ∈ H) PCx =C, if x = 0;{ρ‖x‖ x}, otherwise.(4.70)Hence, we recover the well-known formula for projectors onto spheres.Example 4.22 Let α ∈ R and β ∈ R++, and setSα,β := S(0; β)× {α}. (4.71)Then(∀x = (x, ξ) ∈H) PSα,βx =Sα,β, if x = 0;{(β‖x‖ x, α)}, otherwise.(4.72)Proof. Set V := H× {0}, which is a nonzero closed linear subspace of H.Let us first observe thatV = {x = (x, ξ) ∈H | 〈x | (0, 1)〉 = 0} = {(0, 1)}⊥, (4.73)394.5. The projector onto the intersection of a cone and a sphereand thus,(∀x = (x, ξ) ∈H) x ∈ V⊥ ⇔ x ∈ R(0, 1)⇔ x = 0. (4.74)Moreover, it is straightforward to verify thatS0,β = V ∩ S(0; β). (4.75)Now fix x = (x, ξ) ∈ H. Then, appealing to (3.12) and (4.73), we seethat PVx = (x, 0), Combining this, (4.75), and (4.74), we deduce fromCorollary 4.20 thatPS0,βx = PS0,β(x, ξ) =S0,β, if x = 0;{β‖PVx‖ PVx}, otherwise(4.76a)=S0,β, if x = 0;{(β‖x‖ x, 0)}, otherwise.(4.76b)Consequently, since6 Sα,β = (0, α) + S0,β, we derive from (4.76b) (appliedto the point (x, ξ − α)) and Proposition 3.8 thatPSα,βx = (0, α) + PS0,β(x− (0, α)) (4.77a)= (0, α) + PS0,β(x, ξ − α) (4.77b)=(0, α) + S0,β, if x = 0;(0, α) +{(β‖x‖ x, 0)}, otherwise(4.77c)=Sα,β, if x = 0;{(β‖x‖ x, α)}, otherwise,(4.77d)as announced in (4.72). Next, we turn to the more complicated case when the point to beprojected belongs to the polar cone.6As the reader can easily verify.404.5. The projector onto the intersection of a cone and a sphereTheorem 4.23 Let K be a convex cone in H such that Kr {0} 6= ∅, let ρ be inR++, and let x ∈ K	. Suppose that there exists a nonempty subset C of K suchthat(∀y ∈ C) ‖y‖ = ρ (4.78)and thatK = pos C. (4.79)SetD := K ∩ S(0; ρ) and κ := sup〈x |C〉. (4.80)Then the following hold:(i) Suppose that PCx = ∅. Then PDx = ∅.(ii) Suppose that PCx 6= ∅, and set E := S(0; ρ) ∩ cone(conv PCx). Then thefollowing hold:(a) PCx ⊆ PDx ⊆ E and max〈x |D〉 = max〈x |C〉.(b) Suppose that κ < 0. Then PDx = PCx.(c) Suppose that κ = 0. Then PDx = E.(iii) PCx 6= ∅⇔ PDx 6= ∅.Proof. We start with a few observations. First, since K 6= {0} by assump-tion, it follows from Remark 3.18 that D 6= ∅. Next, in view of (4.78) andthe assumption that C ⊆ K, we haveC ⊆ D. (4.81)In turn, because x ∈ K	, we get from (4.79) and Lemma 3.22(i) thatκ 6 0. (4.82)Finally, by the very definition of D, we see thatthe vectors in D are of equal norm. (4.83)(i): We prove the contrapositive and therefore assume that there existsu ∈ PDx. (4.84)Then, by (4.81), (4.83), (4.84), and Lemma 3.9(i), we obtainκ = sup〈x |C〉 6 sup〈x |D〉 = 〈x | u〉. (4.85)414.5. The projector onto the intersection of a cone and a sphereIn turn, combining (4.78), (4.82), (4.85), and the fact that u ∈ D = (pos C)∩S(0; ρ), we infer from Lemma 4.17(ii)(a) that PCx 6= ∅.(ii)(a): Let us first prove that PCx ⊆ PDx and that max〈x |D〉 =max〈x |C〉. To this end, take u ∈ PCx and y ∈ D. Then, becausey ∈ D ⊆ pos C, there exist finite sets {αi}i∈I ⊆ R+ and {xi}i∈I ⊆ C suchthat y = ∑i∈I αixi. In turn, on the one hand, since ‖y‖ = ρ, we infer from(4.78) and Lemma 4.17(i) that∑i∈I αi > 1. On the other hand, since u ∈ PCx,it follows from (4.78) and Lemma 3.9(i) that〈x | u〉 = max〈x |C〉 = κ. (4.86)So altogether, since (∀i ∈ I) xi ∈ C, using (4.82), we see that〈x | y〉 =∑i∈Iαi〈x | xi〉 6∑i∈Iαiκ = κ∑i∈Iαi 6 κ = 〈x | u〉. (4.87)Therefore, since u ∈ C ⊆ D by (4.81), we derive from (4.87) and (4.86) thatmax〈x |D〉 = 〈x | u〉 = max〈x |C〉. (4.88)Also, appealing to (4.88) and (4.83), we get from Lemma 3.9(i) that u ∈ PDx,as desired. It now remains to establish the inclusion PDx ⊆ E. To do so,fix v ∈ PDx. Then, in view of (4.83), Lemma 3.9(i) and (4.88)&(4.86)&(4.82)assert that〈x | v〉 = max〈x |D〉 = max〈x |C〉 6 0. (4.89)Thus, sincev ∈ D = (pos C) ∩ S(0; ρ), (4.90)it follows from (4.78) and Lemma 4.17(ii)(b) that v ∈ S(0; ρ) ∩cone(conv PCx) = E, as claimed.(ii)(b): Consider the element v ∈ PDx of the proof of (ii)(a). Combin-ing (4.78)&(4.89)&(4.90) and the assumption that κ < 0, we derive fromLemma 4.17(ii)(c) that v ∈ PCx, and hence, PDx ⊆ PCx. Consequently,since PCx ⊆ PDx by (ii)(a), the assertion follows.(ii)(c): According to (ii)(a), it suffices to show that E ⊆ PDx. Towardsthis end, take w ∈ E and y ∈ D. By the very definition of E, there existfinite sets {β j}j∈J ⊆ R++ and {xj}j∈J ⊆ PCx such that w = ∑j∈J β jxj.In turn, since {xj}j∈J ⊆ PCx, we get from (4.78) and Lemma 3.9(i) that(∀j ∈ J) 〈x | xj〉 = κ = 0, from which and (4.88) it follows that〈x |w〉 =∑j∈Jβ j〈x | xj〉 = 0 = κ = max〈x |D〉. (4.91)424.5. The projector onto the intersection of a cone and a sphereConsequently, since w ∈ E ⊆ D by the very definitions of E and D,invoking (4.83) and Lemma 3.9(i) once more, we conclude that w ∈ PDx, asrequired.(iii): Combine (i) and (ii)(a). We are now ready for the main result of this section which provides aformula for the projector of a finitely generated cone and a sphere.Corollary 4.24 (cone intersected with sphere) Let {xi}i∈I be a nonemptyfinite subset ofH, let ρ ∈ R++, and let x ∈ H. SetK := ∑i∈I R+xi,C := K ∩ S(0; ρ),κ := maxi∈I〈x | xi〉,I(x) := {i ∈ I | 〈x | xi〉 = κ}.(4.92)Suppose that (∀i ∈ I) ‖xi‖ = ρ. ThenPCx ={ρ‖PKx‖ PKx}, if κ > 0;S(0; ρ) ∩ cone(conv{xi}i∈I(x)), if κ = 0;{xi}i∈I(x), if κ < 0.(4.93)Proof. Set X := {xi}i∈I . First, it follows from Example 4.6 that K is anonempty closed convex cone. In addition, Lemma 3.22(i) (applied to{xi}i∈I) implies thatx ∈ K	 ⇔ κ = maxi∈I〈x | xi〉 6 0. (4.94)Next, due to our assumption, Lemma 3.9(i) yieldsPXx = {xi}i∈I(x) 6= ∅. (4.95)Let us now identify PCx in each of the following conceivable cases:(a) κ > 0: Then, by (4.94), we have x ∈ H r K	, and hence, Theo-rem 4.19(ii) asserts that PCx = {(ρ/‖PKx‖)PKx}.(b) κ = 0: Using Theorem 4.23(ii)(c) (with the set C being X = {xi}i∈I)and (4.95), we obtain PCx = S(0; ρ) ∩ cone(conv{xi}i∈I(x)).(c) κ < 0: Invoking Theorem 4.23(ii)(b) and (4.95), we immediately havePCx = {xi}i∈I(x). 434.5. The projector onto the intersection of a cone and a sphereRemark 4.25 Consider the setting of Corollary 4.24. Since {xi}i∈I(x) ⊆S(0; ρ) ∩ cone(conv{xi}i∈I(x)) by the assumption that ‖xi‖ ≡ ρ, we see thats : H → H : x 7→ρ‖PKx‖ PKx, if maxi∈I 〈x | xi〉 > 0;s(x) ∈ {xi}i∈I(x), otherwise(4.96)is a selection of PC.Example 4.26 Consider the setting of Theorem 4.7. SetC := K ∩ S(0; 1),κ := maxi∈I〈x | ei〉,I(x) := {i ∈ I | 〈x | ei〉 = κ},λ :=√∑i∈I(max{〈x | ei〉, 0})2.(4.97)ThenPCx ={λ−1∑i∈Imax{〈x | ei〉, 0}ei}, if κ > 0;{∑i∈I(x)αiei∣∣∣∣∣ {αi}i∈I(x) ⊆ R+, ∑i∈I(x)α2i = 1}, if κ = 0;{ei}i∈I(x), if κ < 0.(4.98)Proof. Since PKx = ∑i∈I max{〈x | ei〉, 0}ei by (4.24), we obtain‖PKx‖2 =∥∥∥∥∥∑i∈I max{〈x | ei〉, 0}ei∥∥∥∥∥2=∑i∈I(max{〈x | ei〉, 0})2 = λ2. (4.99)Next, let us show thatS(0; 1) ∩ cone(conv{ei}i∈I(x))={∑i∈I(x)αiei∣∣∣∣∣ {αi}i∈I(x) ⊆ R+, ∑i∈I(x)α2i = 1}. (4.100)To this end, denote the set on the right-hand side of (4.100) by D.Take y ∈ S(0; 1) ∩ cone(conv{ei}i∈I(x)). Then there exist λ ∈ R++and {αi}i∈I(x) ⊆ R+ such that y = λ∑i∈I(x) αiei = ∑i∈I(x)(λαi)ei.444.6. Further examplesFurthermore, since {ei}i∈I(x) is an orthonormal set, we get 1 =‖y‖2 = ‖∑i∈I(x)(λαi)ei‖2 = ∑i∈I(x)(λαi)2. Hence y ∈ D. Conversely,fix z ∈ D, say z = ∑i∈I(x) βiei, where {βi}i∈I(x) ⊆ R+ satisfying∑i∈I(x) β2i = 1, and set β := ∑i∈I(x) βi. It is clear that β > 0, andtherefore, z = β∑i∈I(x)(βi/β)ei ∈ cone(conv{ei}i∈I(x)). In turn, because‖z‖2 = ∑i∈I(x) β2i = 1, it follows that z ∈ S(0; 1) ∩ cone(conv{ei}i∈I(x)).Thus (4.100) holds. Consequently, using (4.24)&(4.99)&(4.100), we obtain(4.98) via Corollary 4.24. The following nice result was mentioned in [28, Example 5.5.2 andProblem 5.6.14].Example 4.27 (Lange) Suppose thatH = RN , that I = {1, . . . , N}, and that(ei)i∈I is the canonical orthonormal basis ofH. SetK := RN+ and C := K ∩ S(0; 1). (4.101)Now let x = (ξi)i∈I ∈ H; set κ := maxi∈I ξi, I(x) := {i ∈ I | ξi = κ}, andx+ := (max{ξi, 0})i∈I . ThenPCx ={1‖x+‖ x+}, if κ > 0;{∑i∈I(x)αiei∣∣∣∣∣ {αi}i∈I(x) ⊆ R+, ∑i∈I(x)α2i = 1}, if κ = 0;{ei}i∈I(x), if κ < 0.(4.102)Proof. Because (∀i ∈ I) 〈x | ei〉 = ξi and ‖x+‖2 = ∑i∈I(max{ξi, 0})2, (4.102)therefore follows from Example 4.26. 4.6 Further examplesIn this section, we provide further examples based on the Lorentz coneand on the cone of positive semidefinite matrices.Example 4.28 Let α and ρ be in R++, letKα = {(x, ξ) ∈ H⊕R | ‖x‖ 6 αξ} (4.103)454.6. Further examplesbe the Lorentz cone of parameter α of Example 3.23, set C := Kα ∩ S(0; ρ),and let x = (x, ξ) ∈H. ThenPCx ={ρ‖x‖ x}, if ‖x‖ 6 αξ and ξ > 0;{ρ√1+ α2(αx‖x‖ , 1)},if ‖x‖ > max{αξ,−ξ/α}or [ x 6= 0 and ‖x‖ 6 −ξ/α ];S(0; β)× {β/α}, if x = 0 and ξ < 0;C, if (x, ξ) = (0, 0).(4.104)Proof. Setβ :=ρα(1+ α2)1/2∈ R++, (4.105)Cα,β := S(0; β)× {β/α}, and κ := max〈x |Cα,β〉. Then it is readily verifiedthat(∀y ∈ Cα,β) ‖y‖ = ρ, (4.106)and due to Lemma 2.4,κ = β‖x‖+ ξβ/α. (4.107)Furthermore, by Example 3.23,Kα = posCα,β = cone(convCα,β) ∪ {0}, (4.108)and by Example 4.22 (applied to Cα,β), we have∅ 6= PCα,βx =Cα,β, if x = 0;{(β‖x‖ x,βα)}, otherwise.(4.109)Let us now identify PCx in the following conceivable cases:(a) ‖x‖ > −ξ/α: Then κ > 0 by (4.107), and so by (4.108) andLemma 3.22(i), x ∈ H r K	α . In turn, it follows from Theorem 4.19(ii)(applied to C = Kα ∩ S(0; ρ)) thatPCx ={ρ‖PKαx‖PKαx}. (4.110)To evaluate PCx further, we consider two subcases:464.6. Further examples(a.1) ‖x‖ 6 αξ: Then x ∈ Kα by (4.103), and so PKαx = x, whichyields PCx = {(ρ/‖x‖)x}.(a.2) ‖x‖ > αξ: Then, according to Example 3.13,PKαx = PKα(x, ξ) =α‖x‖+ ξ1+ α2(αx‖x‖ , 1), (4.111)and since α‖x‖+ ξ > 0, it follows that‖PKαx‖ =α‖x‖+ ξ1+ α2∥∥∥∥( αx‖x‖ , 1)∥∥∥∥ (4.112a)=α‖x‖+ ξ1+ α2√∥∥∥∥ αx‖x‖∥∥∥∥2 + 1 (4.112b)=α‖x‖+ ξ√1+ α2. (4.112c)Hence, combining (4.110)&(4.111)&(4.112), we getPCx ={ρ√1+ α2(αx‖x‖ , 1)}. (4.113)(b) ‖x‖ = −ξ/α: Then κ = 0 by (4.107), and invoking(4.106)&(4.108)&(4.109), Theorem 4.23(ii)(c) asserts thatPCx = S(0; ρ) ∩ cone(conv PCα,βx). (4.114)We consider two subcases:(b.1) x = 0: Then ξ = 0 and so x = (x, ξ) = 0. Moreover, due to(4.109), PCα,βx = Cα,β. Therefore, by (4.108) and (4.114),C = Kα ∩ S(0; ρ) (4.115a)= (cone(convCα,β) ∪ {0}) ∩ S(0; ρ) (4.115b)= cone(convCα,β) ∩ S(0; ρ) (4.115c)= cone(conv PCα,βx) ∩ S(0; ρ) (4.115d)= PCx. (4.115e)(b.2) x 6= 0: Then (4.109) yields PCα,βx = {(βx/‖x‖, β/α)}. In turn,since ‖(βx/‖x‖, β/α)‖ = ρ by (4.105) and a simple computation, we obtainfrom (4.114) and Fact 3.19(i) thatPCx = S(0; ρ) ∩ cone(conv PCα,βx) (4.116a)474.6. Further examples= S(0; ρ) ∩(R++(βx‖x‖ ,βα))(4.116b)={(βx‖x‖ ,βα)}(4.116c)={βα(αx‖x‖ , 1)}(4.116d)={ρ√1+ α2(αx‖x‖ , 1)}. (4.116e)(c) ‖x‖ < −ξ/α: Then κ < 0 by (4.107), and so, in view of(4.106)&(4.108)&(4.109), we deduce from Theorem 4.23(ii)(b) thatPCx = PCα,βx. Hence, by (4.109) and (4.105), we getPCx =Cα,β, if x = 0;{(β‖x‖ x,βα)}, if x 6= 0(4.117a)=Cα,β, if x = 0;{ρ√1+ α2(αx‖x‖ , 1)}, if x 6= 0.(4.117b)To sum up, we have shown thatPCx ={ρ‖x‖ x}, if − ξ/α < ‖x‖ 6 αξ;{ρ√1+ α2(αx‖x‖ , 1)},if ‖x‖ > max{αξ,−ξ/α}or [ x 6= 0 and ‖x‖ 6 −ξ/α ];Cα,β, if x = 0 and 0 < −ξ;C, if (x, ξ) = (0, 0)(4.118a)484.6. Further examples={ρ‖x‖ x}, if ‖x‖ 6 αξ and ξ > 0;{ρ√1+ α2(αx‖x‖ , 1)},if ‖x‖ > max{αξ,−ξ/α}or [ x 6= 0 and ‖x‖ 6 −ξ/α ];S(0; β)× {β/α}, if x = 0 and ξ < 0;C, if (x, ξ) = (0, 0),(4.118b)as announced in (4.104). In the remaining of this section, N is a strictly positive integer, andsuppose that H = SN is the Hilbert space of real symmetric matricesendowed with the scalar product 〈 · | · 〉 : (A, B) 7→ tra(AB), where trais the trace function; the associated norm is the Frobenius norm ‖ · ‖F.The closed convex cone of positive semidefinite symmetric matrix in His denoted by SN+ , and the set of orthogonal matrices of size N × N isUN := {U ∈ RN×N | UUᵀ = Id}, where Id is the identity matrix of RN×N .Next, for every x = (ξ1, . . . , ξN) ∈ RN , set x+ := (max{ξi, 0})16i6N anddefine Diag x to be the diagonal matrix whose, starting from the upperleft corner, diagonal entries are ξ1, . . . , ξN . Now, for every A ∈ H, theeigenvalues of A (not necessarily distinct) are denoted by (λi(A))16i6Nwith the convention that λ1(A) > · · · > λN(A). In turn, the mappingλ : H → RN : A 7→ (λ1(A), . . . ,λN(A)) is well defined. Finally, theEuclidean scalar product and norm of RN are respectively denoted by〈 · | · 〉 and ‖ · ‖.Remark 4.29 Let A ∈ H, U ∈ UN , and x ∈ RN . Then it is straightforwardto verify that‖UAUᵀ‖F = ‖A‖F = ‖λ(A)‖ (4.119)and that‖U(Diag x)Uᵀ‖F = ‖Diag x‖F = ‖x‖. (4.120)Lemma 4.30 Set K := SN+ . Let A ∈ H, and let U ∈ UN be such thatA = U(Diagλ(A))Uᵀ. Then PK A = U(Diag(λ(A))+)Uᵀ and ‖PK A‖F =‖(λ(A))+‖.Proof. It is well known that PK A = U(Diag(λ(A))+)Uᵀ (see, e.g., [29,Theorem A1] or [8, Example 29.32]). In turn, since U ∈ UN , it followsfrom Remark 4.29 that ‖PK A‖F = ‖(λ(A))+‖. 494.6. Further examplesFact 4.31 (Theobald) (See [35].) Let A and B be in H. Then the followinghold:(i) 〈A | B〉 6 〈λ(A) | λ(B)〉.(ii) 〈A | B〉 = 〈λ(A) | λ(B)〉 if and only if there exists U ∈ UN such thatA = U(Diagλ(A))Uᵀ and B = U(Diagλ(B))Uᵀ.Lemma 4.32 Let ρ ∈ R++, and setCρ :={A ∈ SN+∣∣∣ rank A = 1 and ‖A‖F = ρ}. (4.121)Then the following hold:(i) SN+ = posCρ.(ii) Cρ = {A ∈ H | (∃U ∈ UN) A = U(Diag(ρ, 0, . . . , 0))Uᵀ}.(iii) Let A ∈ H. Then max〈A |Cρ〉 = ρλ1(A) andPCρ A={U(Diag(ρ, 0, . . . , 0))Uᵀ∣∣∣ U ∈ UN , A = U(Diagλ(A))Uᵀ}(4.122a)6= ∅. (4.122b)Proof. (i): Set I := {1, . . . , N}, and let (ei)i∈I be the canonical orthonormalbasis of RN . First, since Cρ ∪ {0} ⊆ SN+ and SN+ is a convex cone, we inferfrom Lemma 3.22(iii) that posCρ ⊆ SN+ . Conversely, take A ∈ SN+ , and letU ∈ UN be such that A = U(Diagλ(A))Uᵀ; in addition, set (∀i ∈ I) Di :=Diag(ρei) ∈ SN+ . Then, for every i ∈ I, since rank Di = 1 and ‖UDiUᵀ‖F =‖Di‖F = ‖ρei‖ = ρ, we get from (4.121) that UDiUᵀ ∈ Cρ. In turn, because{λi(A)}i∈I ⊆ R+ andA = U(Diagλ(A))Uᵀ (4.123a)= U(∑i∈IDiag(λi(A)ei))Uᵀ (4.123b)= U(∑i∈Iλi(A)ρDi)Uᵀ (4.123c)=∑i∈Iλi(A)ρ(UDiUᵀ), (4.123d)504.6. Further exampleswe deduce that A ∈ posCρ. Hence, SN+ = posCρ.(ii): Recall that, if A is a matrix of rank r in SN+ , thenλ1(A) > · · · > λr(A) > λr+1(A) = · · · λN(A) = 0. (4.124)Now set D := {A ∈ H | (∃U ∈ UN) A = U(Diag(ρ, 0, . . . , 0))Uᵀ}. First,take A ∈ Cρ, and let U ∈ UN be such that A = U(Diagλ(A))Uᵀ.Then, since rank A = 1 and A ∈ SN+ , it follows from (4.124) that λ(A) =(λ1(A), 0, . . . , 0) and λ1(A) > 0; therefore, because ‖A‖F = ρ, we obtainρ = ‖A‖F = ‖λ(A)‖ = λ1(A). Hence, A = U(Diag(λ1(A), 0, . . . , 0))Uᵀ =U(Diag(ρ, 0, . . . , 0))Uᵀ, which yields A ∈ D. Conversely, take B ∈ D,say B = V(Diag(ρ, 0, . . . , 0))Vᵀ, where V ∈ UN . Then, since ρ > 0,we have B ∈ SN+ . Next, on the one hand, because V is nonsingularand ρ 6= 0, we have rank B = rank Diag(ρ, 0, . . . , 0) = 1. On the otherhand, since V ∈ UN , it follows that ‖B‖F = ‖V(Diag(ρ, 0, . . . , 0))Vᵀ‖F =‖(ρ, 0, . . . , 0)‖ = ρ. Altogether, B ∈ Cρ, which completes the proof.(iii): First, it follows from (ii) that(∀B ∈ H) B ∈ Cρ ⇔ λ(B) = (ρ, 0, . . . , 0). (4.125)Next, denote the right-hand set of (4.122) by D. Then, by (ii), ∅ 6= D ⊆ Cρ.Now, for every B ∈ Cρ, since λ(B) = (ρ, 0, . . . , 0), we infer from Fact 4.31(i)that 〈A | B〉 6 〈λ(A) | λ(B)〉 = ρλ1(A). Thus, sup〈A |Cρ〉 6 ρλ1(A).Furthermore, by (4.125), Fact 4.31(ii), and the very definition of D, we seethat, for every B ∈ Cρ,〈A | B〉 = ρλ1(A)⇔ 〈A | B〉 = 〈λ(A) | λ(B)〉 (4.126a)⇔ (∃U ∈ UN){A = U(Diagλ(A))Uᵀ,B = U(Diagλ(B))Uᵀ (4.126b)⇔ (∃U ∈ UN){A = U(Diagλ(A))Uᵀ,B = U(Diag(ρ, 0, . . . , 0))Uᵀ (4.126c)⇔ B ∈ D. (4.126d)Therefore, because D 6= ∅, we deduce that max〈A |Cρ〉 = ρλ1(A) and(∀B ∈ Cρ) 〈A | B〉 = max〈A |Cρ〉 ⇔ B ∈ D. Consequently, since thematrices in Cρ are of equal norm by (4.121), we derive from Lemma 3.9(i)that PCρ A = D, as desired. Example 4.33 Set K := SN+ , let ρ ∈ R++, and set C := K ∩ S(0; ρ). Inaddition, let A ∈ H, and let U ∈ UN be such that A = U(Diagλ(A))Uᵀ;514.6. Further examplessetD :={V(Diag(ρ, 0, . . . , 0))Vᵀ∣∣ V ∈ UN , A = V(Diagλ(A))Vᵀ} (4.127)andE := S(0; ρ) ∩ cone(convD). (4.128)ThenPCA ={ρ‖(λ(A))+‖U(Diag(λ(A))+)Uᵀ}, if λ1(A) > 0;E, if λ1(A) = 0;D, if λ1(A) < 0.(4.129)Proof. SetCρ :={B ∈ SN+∣∣∣ rank B = 1 and ‖B‖F = ρ}. (4.130)It then follows from Lemma 4.32(iii) thatmax〈A |Cρ〉 = ρλ1(A) and PCρ A = D. (4.131)Let us now consider all conceivable cases:(a) λ1(A) > 0: Then max〈A |Cρ〉 > 0, and thus, by Lemma 4.32(i)and Lemma 3.22(i), we obtain A ∈ H r K	. Therefore, since {0} 6= Kis a nonempty closed convex cone, we infer from Theorem 4.19(ii) andLemma 4.30 thatPCA ={ρ‖PK A‖F PK A}={ρ‖(λ(A))+‖U(Diag(λ(A))+)Uᵀ}. (4.132)(b) λ1(A) 6 0: Then max〈A |Cρ〉 6 0. Since (∀B ∈ Cρ) ‖B‖F = ρ and, byLemma 4.32(i), K = posCρ, it follows from Theorem 4.23(ii)(b)&(ii)(c) and(4.131) thatPCA ={PCρ A, if max〈A |Cρ〉 < 0;S(0; ρ) ∩ cone(conv PCρ A), if max〈A |Cρ〉 = 0(4.133a)={D, if λ1(A) < 0;E, if λ1(A) = 0,(4.133b)which completes the proof. 524.7. Copositive matrices: a numerical experimentRemark 4.34 Consider the setting of Example 4.33. SinceU(Diag(ρ, 0, . . . , 0))Uᵀ ∈ D ⊆ E, (4.134)the mappingA 7→ρ‖(λ(A))+‖U(Diag(λ(A))+)Uᵀ, if λ1(A) > 0;U(Diag(ρ, 0, . . . , 0))Uᵀ, otherwise(4.135)is a selection of PC.4.7 Copositive matrices: a numerical experimentIn this final section, N is a strictly positive integer and M is a symmetricmatrix in RN×N . Recall that M is copositive if (∀x ∈ RN+) 〈x |Mx〉 > 0; or,equivalently,µ(M) := minx∈RN+∩S(0;1)12 〈x |Mx〉 > 0. (4.136)For further information on copositive matrices, we refer the reader tothe surveys [18, 25] and references therein. In view of (4.136), testingcopositivity of M amounts tominimizex∈RN+∩S(0;1)12 〈x |Mx〉. (4.137)Now, set C := RN+ ∩ S(0; 1), set f : RN → R : x 7→ (1/2)〈x |Mx〉, and setg := ιC which is the indicator function of C. Note that neither f nor g isconvex; however, ∇ f is Lipschitz continuous with the operator norm ‖M‖(computed as the largest singular value of M) being a suitable Lipschitzconstant. The projection onto C is computed using (4.102). In turn, (4.137)can be written asminimizex∈RNf (x) + g(x). (4.138)To solve this problem, we compared the Fast Iterative Shrinkage-ThresholdingAlgorithm (FISTA) (see [13]), the Projected Gradient Method (PGM) (see [2,14]), the algorithm presented in [28, Example 5.5.2] by Lange, the Dou-glas–Rachford Algorithm (DRA) variant presented in [30] by Li and Pong,and the regular DRA for solving (4.138) when N ∈ {2, 3, 4}. For eachN ∈ {2, 3, 4}, using the copositivity criteria for matrices of order up to four534.7. Copositive matrices: a numerical experiment(see, e.g., [19, 33]), we randomly generate 100 copositive matrices (group A)together with 100 non-copositive (group B) ones with i.i.d. Gaussian entriesand run the mentioned algorithms on those matrices. For each algorithm, if(xn)n∈N is the sequence generated, then we terminate the algorithm when‖xn − xn−1‖max{‖xn−1‖, 1} < 10−8. (4.139)The maximum allowable number of iterations is 1000. For each matrixM in group A (respectively, group B), we declare success if µ(M) > 0(respectively, µ(M) < 0). We also record the average of the numberof iterations until success of each algorithm. The results, obtained usingMatlab, are reported in Table 4.1.Size Copositive FISTA PGM Lange Li–Pong DRsucc iter succ iter succ iter succ iter succ iter2× 2 Yes 100 5 100 5 100 89 100 94 96 23No 97 15 99 12 91 92 93 87 53 893× 3 Yes 100 27 100 24 100 91 100 232 95 63No 96 30 98 24 86 93 95 162 31 2144× 4 Yes 88 33 87 30 91 93 88 274 79 58No 97 45 94 41 91 95 98 236 33 137Table 4.1: Detecting whether a matrix is copositive using a variety ofalgorithms. Here “iter” means “the average of the numbers of iterations.”Finally, let us apply the algorithms to the well-known Horn matrixH :=1 −1 1 1 −1−1 1 −1 1 11 −1 1 −1 11 1 −1 1 −1−1 1 1 −1 1, (4.140)which is copositive with µ(H) = 0 (see [20, Equation (3.5)]). For eachalgorithm, we record the number of iterations and the value of f at thepoint that the algorithm is terminated. The results are recorded in Table 4.2.544.7. Copositive matrices: a numerical experimentFISTA PGM Lange Li–Pong DRfval iter fval iter fval iter fval iter fval iter3.5230e−17 11 2.8297e−20 10 2.9979e−07 95 1.4912e−14 170 0.0584 13Table 4.2: Detecting copositivity of the Horn matrix.We acknowledge that these algorithms might get stuck at points that arenot solutions and that the outcome might depend on the starting points;moreover, a detailed complexity analysis is absent. There are thus variousresearch opportunities to improve the current results. Nonetheless, ourpreliminary results indicate that FISTA and PGM are potentially significantcontenders for numerically testing copositivity.55Chapter 5On the sum of projectors ontoconvex sets5.1 OverviewWe assume that(Ci)i∈I is a finite family of nonempty closed convex subsets ofH (5.1)with corresponding projectors(PCi)i∈I . (5.2)In this chapter, we analyze carefully the question: When is the sum ofprojectors also a projector? (In view of Proposition 5.1(iii), an affirmativeanswer to this question requires the sum∑i∈I Ci to be closed. This happens,for instance, when each set is bounded.) It is known that, in the case oflinear subspaces, ∑i∈I PCi is a projector onto a closed linear subspace ifand only if the sets (Ci)i∈I are pairwise orthogonal; see [21, Theorem 2,p. 46]. This question is also of interest in Quantum Mechanics [27, p. 50].In 1971, Zarantonello [39] answered this question in the case of convexcones: ∑i∈I PCi is a projector if and only if the projectors (PCi)i∈I arepairwise orthogonal in the sense that, for every (i, j) ∈ I × I with i 6= j,we have (∀x ∈ H) 〈PCi x |PCj x〉 = 0. However, the question remainsopen in the general convex case. One goal of this chapter is to providenecessary and sufficient conditions for ∑i∈I PCi to be a projector withoutany further assumption on the sets (Ci)i∈I . This allows us to unify the twoaforementioned results and make a connection with the work [4] whereit was proved that, if the sum of a family of proximity operators is aproximity operator, then every partial sum remains a proximity operator.Interestingly, we shall see that this property is still valid in the class ofprojectors onto convex cones; in other words, if a finite sum of projectorsonto convex cones is a projector, then so are its partial sums. Nevertheless,565.2. Auxiliary resultsthis result fails outside the world of convex cones. Our main results aresummarized as follows:− We provide a characterization of projectors onto convex sets (The-orem 5.6). This result is a pillar of this chapter and a variant of[39, Theorem 4.1]. Furthermore, we also partially answer an openquestion by Zarantonello regarding [39, Theorem 4.1].− Theorem 5.12 provides a necessary and sufficient condition (withoutany additional assumptions on the underlying sets) under which∑i∈I PCi is a projector.− We present the partial sum property (see [4, Theorem 4.2]) for projectorsonto convex cones in Theorem 5.27, whose proof is based on Theo-rem 5.23 and [4, Theorem 4.2]. We also recover [39, Theorems 5.3 and5.5].This chapter is organized as follows. In Section 5.2, we collect miscella-neous results that will be used in the sequel. Our main results are presentedin Section 5.3: Theorem 5.6 provides a characterization of projectors, whichis a variant of [39, Theorem 4.1] and allows us to recover the classicalcharacterization of orthogonal projectors; see, e.g., [36, Theorem 4.29].In turn, we shall use Theorem 5.6 to establish a necessary and sufficientcondition for a finite sum of projectors to be a projector (Theorem 5.12).In Section 5.4, we show that this condition covers the result obtained byZarantonello ([39, Theorem 5.5]) and the case of linear subspaces. Fur-thermore, we provide Theorem 5.23 and Theorem 5.27 to illustrate theconnection between our work and [4, 39]. The one-dimensional case is thetopic of Section 5.5, where all the pairs (C, D) of nonempty closed convexsubsets of R satisfying PC + PD = PC+D are explicitly determined. Finally,we turn to a generalization of the classical result [21, Theorem 2, p. 46] inSection 5.6. Various examples are given to illustrate the necessity of ourassumptions.5.2 Auxiliary resultsHereinafter, it is convenient to setq := 12‖ · ‖2, (5.3)and note that ∇q = Id is the identity operator onH.575.2. Auxiliary resultsIn the finite-dimensional case, Proposition 5.1(ii) can be deduced from[11, Theorem 3.15]. Furthermore, let us point out that Proposition 5.1(iii)generalizes Zarantonello’s [39, Theorem 5.4].Proposition 5.1 Let m > 2 be an integer, set I := {1, . . . , m}, and let (Ci)i∈I bea family of nonempty closed convex subsets ofH. Then the following hold:(i) For every x ∈ H,12∥∥∥∥∥x−∑i∈I PCi x∥∥∥∥∥2=∑i∈I12 d2Ci(x)− (m− 1)q(x)+ ∑(i,j)∈I×Ii<j〈PCi x |PCj x〉. (5.4)(ii) ran∑i∈I PCi = ∑i∈I Ci.(iii) Suppose that there exists a closed convex set D such that ∑i∈I PCi = PD.Then ∑i∈I Ci is closed and D = ∑i∈I Ci.Proof. For brevity, set (∀i ∈ I) Pi := PCi and di := dCi .(i): Apply Lemma 2.3(ii) to (xi)i∈I = (Pix)i∈I and note that (∀i ∈ I) ‖x−Pix‖ = di(x).(ii): Let us verify the claim by induction on m. Assume first that m = 2.On the one hand, for every i ∈ {1, 2}, Example 3.58 asserts that Pi is3∗ monotone. On the other hand, since P1 and P2 are monotone andcontinuous, so is P1 + P2, and therefore P1 + P2 is maximally monotoneby Fact 3.55. Altogether, the Brézis–Haraux theorem (Fact 3.60) implies thatran(P1 +P2) = ran P1 + ran P2 = C1 + C2. Now assume that m > 3, that theconclusion holds for families containing m− 1 sets, and set T := ∑m−1i=1 Pi,which is clearly monotone and continuous. Then, since {Pi}i∈I are 3∗monotone by Example 3.58, we infer from Fact 3.59 that T = ∑m−1i=1 Pi is3∗ monotone. However, since T and Pm are monotone and continuous, sois their sum T + Pm, and thus T + Pm is maximally monotone by Fact 3.55.Therefore, because Pm is 3∗ monotone by Example 3.58, we derive fromthe Brézis–Haraux theorem (Fact 3.60) and Lemma 2.5 that ran∑i∈I Pi =ran(T + Pm) = ran T + ran Pm = ran T + ran Pm. Consequently, by theinduction hypothesis and Lemma 2.5,ran∑i∈IPi = ran T + ran Pm =m−1∑i=1Ci + Cm =m−1∑i=1Ci + Cm =∑i∈ICi, (5.5)585.3. Main resultswhich concludes the induction argument. Alternatively, apply [12,Lemma 3.1(ii)] with (Ai)i∈I = (Pi)i∈I .(iii): It follows from (ii) and our assumption that ∑i∈I Ci ⊆ ∑i∈I Ci =ran∑i∈I Pi = ran PD = D = ran PD = ran∑i∈I Pi ⊆ ∑i∈I Ci. Thus, weconclude that ∑i∈I Ci = D and that ∑i∈I Ci is closed. Recall from [31, pp. 89–90] that, if f : H → ]−∞,+∞], then the Fréchetsubdifferential of f is∂ˆ f : H → 2H : x 7→{u ∈ H∣∣∣∣∣ limx 6=y→x f (y)− f (x)− 〈u | y− x〉‖y− x‖ > 0}. (5.6)Lemma 5.2 Let f : H → R and z ∈ H. Suppose that f is Fréchet differentiableonH. Then(∀ε ∈ R++) ∂ˆ( f + εd{z})(z) = ∇ f (z) + εB(0; 1). (5.7)Proof. Fix ε ∈ R++. Since f is Fréchet differentiable and d{z} is convex, wederive from [31, Proposition 1.107 and Theorem 1.93] that ∂ˆ(g+ εd{z})(z) =∇ f (z) + ∂ˆ(εd{z})(z) = ∇ f (z) + ∂(εd{z})(z) = ∇ f (z) + ε∂d{z}(z). Hence, inview of [8, Example 16.62] (applied to C = {z}), (5.7) follows. 5.3 Main resultsProposition 5.3 Let T : H → H, and set f := q ◦ (Id− T). Suppose that f isFréchet differentiable onH with ∇ f = Id− T. Then Fix T 6= ∅.Proof. Let us proceed by contradiction and therefore assume that Fix T =∅. Then clearly (∀x ∈ H) f (x) > 0. Hence, because f : H → R++ isFréchet differentiable with ∇ f = Id − T and √ · : R++ → R is Fréchetdifferentiable, we deduce from [17, Theorem 5.1.11(b)] that g :=√ · ◦ (2 f )is Fréchet differentiable onH (thus continuous) and(∀x ∈ H) ∇g(x) = 2∇ f (x)2√2 f (x)=x− Tx‖x− Tx‖ . (5.8)Now let ε ∈ ]0, 1[. Since g is bounded below and continuous, Ekeland’svariational principle (see, e.g., [8, Theorem 1.46(iii)]) applied to g and(α, β) = (ε2, ε) yields the existence of z ∈ H such that (∀x ∈ H r595.3. Main results{z}) g(z) + εd{z}(z) = g(z) < g(x) + εd{z}(x). This guarantees that z is theunique minimizer of g + εd{z}. Thus, [31, Proposition 1.114], Lemma 5.2,and (5.8) imply that0 ∈ ∂ˆ(g + εd{z})(z) = ∇g(z) + εB(0; 1) =z− Tz‖z− Tz‖ + εB(0; 1), (5.9)which is absurd since ε ∈ ]0, 1[ and ‖(z− Tz)/(‖z− Tz‖)‖ = 1. Remark 5.4 Consider the setting and the assumption of Proposition 5.3.Zarantonello established in the proof of [39, Theorem 4.1] that, if (in ad-dition to our assumption) T is Lipschitz continuous, then Fix T 6= ∅.However, we do not need the Lipschitz continuity of T in our proof.Remark 5.5 Consider the setting and assumption of Proposition 5.3 andsuppose, in addition, that∇ f is continuous. Then we obtain an alternativeproof as follows. Suppose to the contrary that Fix T = ∅. Then g :=√ · ◦(2 f ) is continuously Fréchet differentiable onH (hence continuous) with(∀x ∈ H) ∇g(x) = x− Tx‖x− Tx‖ . (5.10)Fix ε ∈ ]0, 1[. Since g is bounded below and continuous, Ekeland’svariational principle implies that there exists z ∈ H such that (∀x ∈H r {z}) g(z) + εd{z}(z) = g(z) < g(x) + εd{z}(x). Thus, z is a mini-mizer of g + εd{z}(z). Therefore, because d{z} is convex, in view of [38,Theorem 3.2.4(iii)&(vi)&(ii)] and [8, Example 16.62], we see that0 ∈ ∇g(z) + ε∂d{z}(z) = ∇g(z) + εB(0; 1) =z− Tz‖z− Tz‖ + εB(0; 1), (5.11)which contradicts the fact that ε ∈ ]0, 1[.In [39], Zarantonello provided a necessary and sufficient condition interms of a differential equation for an operator on H to be a projector.The proof there, however, is not within the scope of Convex Analysis.He also conjectured (see the paragraph after [39, Corollary 2, p. 306]) thatthe Fréchet differentiability of the operator P in [39, Theorem 4.1] can bereplaced by the Gâteaux one. By assuming the monotonicity of P insteadof the Lipschitz continuity, we provide below an affirmative answer. Thenext result, which plays a crucial role in determining whether a sum ofprojectors is a projector (see Theorem 5.12 below), is a variant of [39,Theorem 4.1] with a proof rooted in Convex Analysis.605.3. Main resultsTheorem 5.6 (Characterization theorem) Let T : H → H, and set f := q ◦(Id− T). Then the following are equivalent:(i) There exists a nonempty closed convex subset C ofH such that T = PC.(ii) T is monotone, f is Gâteaux differentiable onH, and ∇ f = Id− T.If (i) or (ii) holds, then ran T is closed and convex, T = Pran T, and f =(1/2)d2ran T is Fréchet differentiable onH.Proof. “(i)⇒(ii)”: First, clearly ran T = ran PC = C is closed and convex.Next, it follows from Example 3.56 that T = PC is monotone. In turn,since f = q ◦ (Id−PC) = (1/2)d2C, we derive from Fact 3.37(i) that fis Fréchet differentiable (and therefore Gâteaux differentiable) on H with∇ f = Id−PC = Id− T, as desired.“(i)⇐(ii)”: Set g := q − f . Then, on the one hand, because q and fare Gâteaux differentiable, so is g. On the other hand, since ∇q = Id and∇ f = Id− T, we infer that ∇g = ∇(q− f ) = ∇q− ∇ f = T, which ismonotone by assumption. Altogether, Fact 3.35 yields the convexity of g.Therefore, since g is Gâteaux differentiable on H, it follows from Fact 3.36that g is lower semicontinuous onH. To sum up, we have shown thatg = q− f belongs to Γ0(H) and is Gâteaux differentiable onH with ∇g = T.(5.12)Now set h := g∗ − q and C := dom h. Let us show thatC = ran T is closed and convex. (5.13)Indeed, since h = g∗− q and dom q = H, we deduce that dom h = dom g∗.Thus, since g∗ ∈ Γ0(H) by (5.12) and Fact 3.42, it follows from Fact 3.49that C = dom h = dom g∗ = dom ∂g∗ = dom(∂g)−1 = ran ∂g. However,in the light of (5.12) and Fact 3.50(i), we see that ran ∂g = ran∇g = ran T,and hence C = dom g∗ = ran T. Therefore, because g∗ is convex, C =ran T = dom g∗ is closed and convex, as announced in (5.13). Next, weshall establish thath = ιC. (5.14)Towards this goal, fix u ∈ ran T, say u = Tx = ∇g(x), where x ∈ H. Then(5.12), Fact 3.50(ii), and the very definitions of g and f assert thath(u) = g∗(u)− q(u) = g∗(∇g(x))− q(Tx) (5.15a)615.3. Main results= 〈x | ∇g(x)〉 − g(x)− q(Tx) (5.15b)= 〈x | Tx〉 − q(x) + f (x)− q(Tx) (5.15c)= 〈x | Tx〉 − 12‖x‖2 + 12‖x− Tx‖2 − 12‖Tx‖2 (5.15d)= 0. (5.15e)Hence,h = 0 on ran T. (5.16)Now take u ∈ ran T, and let (un)n∈N be a sequence in ran T converging tou. Since f > 0, we see that g = q− f 6 q, and thus Fact 3.46(i) and Fact 3.41yield g∗ > q∗ = q, i.e., h > 0. On the one hand, the lower semicontinuityof g∗ and the continuity of q imply that h is lower semicontinuous. On theother hand, since {un}n∈N ⊆ ran T, (5.16) ensures that (∀n ∈N) h(un) = 0.Altogether, since un → u, we get 0 6 h(u) 6 lim h(un) = 0, which impliesthat h(u) = 0. This and (5.13) guarantee that h = 0 on ran T = dom h,showing that h = ιdom h = ιC, as claimed in (5.14). Hence, because g ∈Γ0(H), the Fenchel–Moreau theorem (Fact 3.42) and Example 3.39 give g =g∗∗ = (h + q)∗ = (ιC + q)∗ = q− (1/2)d2C. Consequently, invoking (5.12),(5.13), and Fact 3.37(i), we conclude that T = ∇g = ∇(q − (1/2)d2C) =Id− (Id−PC) = PC, as desired. Remark 5.7 Consider the implication “(ii)⇒(i)” of Theorem 5.6. If wemerely assume that T is defined on a proper open subset D of H, then,although there may exist a closed set C such that T is the restriction to Dof the projector onto C, the set C may fail to be convex. An example can beconstructed as follows. Suppose thatH 6= {0}, and setT : Hr {0} → H : x 7→ x‖x‖ , f := q ◦ (Id− T), and C := S(0; 1). (5.17)Then clearly C is a closed nonconvex set and T is the restriction toHr {0}of the set-valued projector PC. Thus, in the light of Example 3.52, T ismonotone. Next, since (∀x ∈ Hr {0}) f (x) = (1/2)‖(1− 1/‖x‖)x‖2 =(1/2)(‖x‖ − 1)2 = q(x) − ‖x‖ + 1/2, we infer that f is Fréchet differen-tiable onHr {0} and(∀x ∈ Hr {0}) ∇ f (x) = x− x‖x‖ = x− Tx. (5.18)Open Problem 5.8 We do not know whether the monotonicity of T canbe omitted in Theorem 5.6. Nevertheless, the following remark might beuseful in finding counterexamples if one thinks the answer is negative.625.3. Main resultsRemark 5.9 ([16]) Consider the setting of Theorem 5.6 and suppose thatH = R2. Set F := Id− T and (∀(x, y) ∈ H) F(x, y) := (F1(x, y), F2(x, y)).Now assume that f is Fréchet differentiable on H with ∇ f = Id− T = F;in addition, suppose that F1 and F2 are smooth. Then, since (F1, F2) = ∇ f ,it follows that ∂ f /∂x = F1 and that ∂ f /∂y = F2. Hence, due to Schwarz’stheorem,∂F1∂y=∂2 f∂y∂x=∂2 f∂x∂y=∂F2∂x. (5.19)However, because ∇ f = F, a direct computation givesF1(x, y) = F1(x, y)∂F1∂x(x, y) + F2(x, y)∂F2∂x(x, y)= F1(x, y)∂F1∂x(x, y) + F2(x, y)∂F1∂y(x, y),F2(x, y) = F1(x, y)∂F1∂y(x, y) + F2(x, y)∂F2∂y(x, y)= F1(x, y)∂F2∂x(x, y) + F2(x, y)∂F2∂y(x, y).(5.20)In the first equation of (5.20), one can try to solve for F1 in term of F2,and vise versa by using the second one. This approach recovers projectorsonto linear subspaces of R2 and might suggest a nonmonotone solutionof the equation ∇ f = Id − T. In addition, it is worth noticing that thefunction g : x 7→ ‖x− Tx‖ satisfies the eikonal equation (see, e.g., [3]), i.e.,(∀x ∈ HrFix T) ‖∇g(x)‖ = 1. This might give us some insights into OpenProblem 5.8.By specializing Theorem 5.6 to positively homogeneous operators onH,we obtain a characterization for projectors onto closed convex cones.Corollary 5.10 Let T : H → H and set f := q ◦ T. Then the following areequivalent:(i) There exists a nonempty closed convex cone K such that T = PK.(ii) T is monotone and positively homogeneous, f is Gâteaux differentiable onH, and ∇ f = T.If (i) or (ii) holds, then K = ran T.635.3. Main resultsProof. “(i)⇒(ii)”: Clearly ran T = ran PK = K. Now, it follows from Exam-ple 3.56 that T = PK is monotone. Next, because K is a nonempty closedconvex cone, (3.27) guarantees that T is positively homogeneous. In turn,since f = q ◦ T = q ◦ PK, Fact 3.37(ii) yield the Gâteaux differentiability off and, moreover, ∇ f = ∇(q ◦ PK) = PK = T, as desired.“(i)⇐(ii)”: First, since T is positively homogeneous,ran T is a cone inH. (5.21)Now set g : H → R : x 7→ (1/2)〈x | Tx〉 = (1/2)〈x | ∇ f (x)〉 and h :=q ◦ (Id− T). Since ∇ f = T is monotone and positively homogeneous byassumption, Lemma 2.6 ensures that g is Gâteaux differentiable on H and∇g = ∇ f = T. Thus, because h = q− 2g + f , it follows that h is Gâteauxdifferentiable on H with gradient ∇h = ∇q− 2∇g +∇ f = Id− 2T + T =Id− T. Consequently, since T is monotone, we conclude via Theorem 5.6(applied to h) and (5.21) that ran T is a closed convex cone in H and thatT = Pran T. In Corollary 5.10, if T is a bounded linear operator, then we recoverthe following characterization of orthogonal projectors. For an alternativeproof, which is based on the orthogonal decomposition H = V ⊕ V⊥,where V is a closed linear subspace ofH, see, e.g., [36, Theorem 4.29].Corollary 5.11 Let L : H → H. Then the following are equivalent:(i) There exists a closed linear subspace V ofH such that L = PV .(ii) L ∈ B(H) and L = L∗ = L2.(iii) L ∈ B(H) and L = L∗L.If one of (i)–(iii) holds, then V = ran L.Proof. “(i)⇒(ii)”: See, e.g., [8, Corollary 3.24(iii)&(vi)]. Moreover, it is clearthat ran L = ran PV = V.“(ii)⇒(iii)”: Clear.“(iii)⇒(i)”: On the one hand, because L ∈ B(H), we deduce fromFact 3.54 that L = L∗L is monotone. On the other hand, since L ∈ B(H), [8,Example 2.60] and our assumption imply that q ◦ L is Fréchet differentiableon H and ∇(q ◦ L) = L∗L = L. Altogether, because L is clearly positivelyhomogeneous, we obtain the conclusion via Corollary 5.10. 645.3. Main resultsWe now establish a necessary and sufficient condition under which afinite sum of projectors is a projector.Theorem 5.12 (Sum of projectors) Let m > 2 be an integer, set I :={1, . . . , m}, and let (Ci)i∈I be a family of nonempty closed convex subsets of H.Then there exists a closed convex set D such that ∑i∈I PCi = PD if and only if(∃γ ∈ R)(∀x ∈ H) ∑(i,j)∈I×Ii<j〈PCi x |PCj x〉 = γ; (5.22)in which case, ∑i∈I Ci is a closed convex set,∑i∈IPCi = P∑i∈I Ci , (5.23)andd2∑i∈I Ci =∑i∈Id2Ci − 2(m− 1)q+ 2γ. (5.24)Proof. For every i ∈ I, set Pi := PCi and di := dCi ; in addition, set T :=∑i∈I Pi, which is monotone due to Example 3.56, set f := q ◦ (Id− T), andset g : x 7→ ∑i<j〈Pix |Pjx〉. By Proposition 5.1(i),f =∑i∈I12 d2i − (m− 1)q+ g. (5.25)Suppose first that there exists a closed convex set D such that T = ∑i∈I Pi =PD. Then, in view of Proposition 5.1(iii), it follows that ∑i∈I Ci = D, andhence, we obtain the closedness of ∑i∈I Ci and (5.23). Now, on the onehand, since clearlyf = q ◦ (Id−PD) = 12 d2D = 12 d2∑i∈I Ci , (5.26)and by Theorem 5.6 (applied to T = PD), f Fréchet differentiable on Hand ∇ f = Id − T. On the other hand, for every i ∈ I, in the lightof Theorem 5.6 (applied to Pi), (1/2)d2i is Fréchet differentiable on Hand ∇(1/2)d2i = Id−Pi. Altogether, (5.25) implies that g is Fréchetdifferentiable and Id − T = ∇ f = ∑i∈I(Id−Pi) − (m − 1) Id+∇g =Id−∑i∈I Pi +∇g = Id− T +∇g. Hence,∇g = 0, and so [15, Theorem 3.5]guarantees the existence of γ ∈ R such that (∀x ∈ H) g(x) = γ.This, (5.25), and (5.26) yield (5.24), as required. Conversely, assume that(∃γ ∈ R)(∀x ∈ H) g(x) = γ. It then follows from (5.25) that f =∑i∈I(1/2)d2i − (m − 1)q + γ. Hence, f is Fréchet differentiable on H and∇ f = ∑i∈I(Id−Pi) − (m − 1) Id = Id−∑i∈I Pi = Id− T. Consequently,because T is monotone, the conclusion follows from Theorem 5.6. 655.3. Main resultsCorollary 5.13 Let C and D be nonempty closed convex subsets of H. Then thefollowing are equivalent:(i) There exists a closed convex set E such that PC + PD = PE.(ii) (∃γ ∈ R)(∀x ∈ H) 〈PCx |PDx〉 = γ.If (i) or (ii) holds, then C + D is a closed convex set,PC + PD = PC+D, (5.27)and d2C+D = d2C + d2D − 2q+ 2γ.The following simple example shows that the constant γ in Corol-lary 5.13 can take on any value.Example 5.14 Let u and v be in H, set C := {u}, and set D := {v}. Thenclearly PC + PD = P{u+v} = PC+D and (∀x ∈ H) 〈PCx |PDx〉 = 〈u | v〉.As a consequence of Corollary 5.13, a sum of projectors onto orthogonalsets is a projector; see also [9, Proposition 2.6].Corollary 5.15 Let C and D be nonempty closed convex subsets of H such thatC ⊥ D. Then the following hold:(i) C + D is a nonempty closed convex set.(ii) PC + PD = PC+D.(iii) d2C+D = d2C + d2D − 2q.Proof. Since (∀x ∈ H) 〈PCx |PDx〉 = 0, the conclusions readily follow fromCorollary 5.13. We now provide an instance where item (ii) of Corollary 5.13 holds, C *D⊥, and neither C nor D is a cone in general.Example 5.16 Let K be a nonempty closed convex cone in H, let ρ1 andρ2 be in R++, set C := K ∩ B(0; ρ1), and set D := K	 ∩ B(0; ρ2). It thenimmediately follows from Theorem 4.10 and Fact 3.25(ii) that, for everyx ∈ H,〈PCx |PDx〉 =〈ρ1max{‖PKx‖, ρ1} PKx∣∣∣∣ ρ2max{‖PK	x‖, ρ2} PK	x〉(5.28a)= 0. (5.28b)665.3. Main resultsFigure 5.1: A GeoGebra [26] snapshot illustrating the sets C (yellow) andD (green) in the setting of Example 5.16.We next establish a necessary and sufficient condition for u + PC to be aprojector.Example 5.17 Let C be a nonempty closed convex subset of H, and let u ∈H. Then, since (∀x ∈ H) u = P{u}x, we deduce from Corollary 5.13 thatu + PC = P{u} + PC is a projector onto a closed convex set (5.29a)⇔ (∃γ ∈ R)(∀x ∈ H) 〈u |PCx〉 = γ (5.29b)⇔ (∃γ ∈ R)(∀x ∈ C) 〈u | x〉 = γ (5.29c)⇔ (∀x ∈ C)(∀y ∈ C) 〈u | x〉 = 〈u | y〉 (5.29d)⇔ (∀x ∈ C)(∀y ∈ C) 〈u | x− y〉 = 0 (5.29e)⇔ u ∈ (C− C)⊥; (5.29f)675.3. Main resultsin which case, u + PC = Pu+C due to Corollary 5.13.Remark 5.18 Consider the setting of Example 5.17. Since u + PC is mono-tone, nonexpansive, and a sum of proximity operators, [4, Corollary 2.5]guarantees that u+ PC is a proximity operator. However, by Example 5.17,it is not a projector unless u ∈ (C− C)⊥.Here is a sufficient, but not necessary, condition for a sum of projectorsto be a projector.Corollary 5.19 Let m > 2 be an integer, set I := {1, . . . , m}, let (Ci)i∈I be afamily of nonempty closed convex subsets of H, and set C := ∑i∈I Ci. Supposethat, for every (i, j) ∈ I × I with i < j, there exists γi,j ∈ R such that (∀x ∈H) 〈PCi x |PCj x〉 = γi,j. Then C is a closed convex set and ∑i∈I PCi = PC.Proof. Set (∀k ∈ I) Dk := ∑ki=1 Ci, and let us establish that(∀k ∈ I r {1}) Dk is a closed convex set andk∑i=1PCi = PDk . (5.30)Due to Corollary 5.13, the claim holds if k = 2, and we therefore assumethat, for some k ∈ {2, . . . , m − 1}, Dk is a closed convex set and that∑ki=1 PCi = PDk . Then, by our assumption, (∀x ∈ H) 〈PDk x |PCk+1 x〉 =∑ki=1〈PCi x |PCk+1 x〉 = ∑ki=1 γi,k+1, from which and Corollary 5.13 (applied toDk and Ck+1) we infer that Dk+1 = Dk +Ck+1 is a closed convex set and, dueto the induction hypothesis, ∑k+1i=1 PCi = ∑ki=1 PCi + PCk+1 = PDk + PCk+1 =PDk+Ck+1 = PDk+1 . Hence, letting k = m in (5.30) yields the conclusion. We now illustrate that the assumption of Corollary 5.19 need not holdwhen merely ∑i∈I PCi = PC.Example 5.20 Let C be a nonempty closed convex subset of H such thatH r (C − C)⊥ 6= ∅, and suppose that u ∈ H r (C − C)⊥. Then P{u} +P{−u} + PC = PC is a projector. However, if x 7→ 〈P{u}x |PCx〉 = 〈u |PCx〉were a constant, then it would follow from Corollary 5.13 that u + PC =P{u} + PC is a projector, which violates Example 5.17 and the assumptionthat u /∈ (C− C)⊥.685.4. The partial sum property of projectors onto convex cones5.4 The partial sum property of projectors ontoconvex conesIn this section, we shall discuss the partial sum property and the con-nections between our work, Zarantonello’s [39, Theorems 5.5 and 5.3], andthe work [4]. We shall need the following two results. Let us providean instance where the star-difference of two sets (see [23]) can be explicitlydetermined. Lemma 5.21 was mentioned in [4, Footnote 5] and was alsostated implicitly in the proof of [39, Theorem 5.2].Lemma 5.21 (Star-difference of cones) Let K1 and K2 be nonempty closedconvex cones inH, and setK := {u ∈ H | u + K2 ⊆ K1}. (5.31)Then the following are equivalent:(i) K = K1.(ii) 0 ∈ K.(iii) K 6= ∅.(iv) K2 ⊆ K1.Proof. The chain of implications “(i)⇒(ii)⇒(iii)” is clear.“(iii)⇒(iv)”: Fix u ∈ K. Then, since K1 and K2 are cones, we infer that(∀ε ∈ R++) εu + K2 = ε(u + K2) ⊆ εK1 = K1. In turn, letting ε ↓ 0 andusing the closedness of K1, we obtain K2 ⊆ K1.“(iv)⇒(i)”: First, take u ∈ K1. Since K2 ⊆ K1 and K1 is a convex cone byassumption, it follows that u + K2 ⊆ K1 + K1 ⊆ K1, and therefore u ∈ K.Conversely, fix u ∈ K. Because u + K2 ⊆ K1 and 0 ∈ K2, we deduce thatu ∈ K1, which completes the proof. Proposition 5.22 Let C and D be nonempty closed convex subsets ofH, and setf := 12 d2C +12 d2D − q and h := f ∗ − q. (5.32)Then the following hold:(i) (∀u ∈ H) h(u) = supv∈D(σC(u + v) + 〈u | v〉).695.4. The partial sum property of projectors onto convex cones(ii) Suppose that C and D are cones and D ⊆ C	. Then h = ιC	∩D	 .Proof. (i): Since D is convex, closed, and nonempty, we see that ιD ∈ Γ0(H),and so7 (1/2)d2D = ιDq = ιDq. In turn, Moreau’s decompositionasserts that q− (1/2)d2D = q− ιDq = ι∗Dq. Thus, (5.32) yieldsf = 12 d2C − ι∗Dq. (5.33)Moreover, since ιD ∈ Γ0(H) and q∗ = q, Fact 3.46(ii) and theFenchel–Moreau theorem guarantee that (ι∗Dq)∗ = ι∗∗D + q∗ = ιD + q,which implies that dom(ι∗Dq)∗ = D. Consequently, becauseι∗Dq ∈ Γ0(H), Fact 3.43 and Example 3.40 imply that, for every u ∈ H,f ∗(u)− q(u) = ( 12 d2C − ι∗Dq)∗(u)− q(u) (5.34a)= supv∈dom(ι∗D q)∗(( 12 d2C)∗(u + v)− (ι∗Dq)∗(v))− q(u) (5.34b)= supv∈D(σC(u + v) + q(u + v)− q(v))− q(u) (5.34c)= supv∈D(σC(u + v) + 〈u | v〉), (5.34d)as announced.(ii): First, because D ⊆ C	, Lemma 5.21 (applied to the pair of closedconvex cones (C	, D)) yieldsC	 = {u ∈ H | u + D ⊆ C	}. (5.35)Next, we derive from (i) and Fact 3.21(iii) that(∀u ∈ H) h(u) = supv∈D(σC(u + v) + 〈u | v〉)(5.36a)= supv∈D(ιC	(u + v) + 〈u | v〉). (5.36b)Now fix u ∈ H, and let us consider two alternatives.(a) u ∈ Hr C	: In view of (5.35), there exists v ∈ D such that u + v ∈Hr C	, and therefore, by (5.36b), h(u) > ιC	(u + v) + 〈u | v〉 = +∞.7Here  and  denote the infimal convolution and the exact infimal convolution definedin Definition 3.45, respectively.705.4. The partial sum property of projectors onto convex cones(b) u ∈ C	: Then, by (5.35), u + D ⊆ C	. Hence, since D is a nonemptycone, it follows from (5.36b) and Fact 3.21(iii) that h(u) = supv∈D〈u | v〉 =σD(u) = ιD	(u) = ιC	∩D	(u).Altogether, we obtain the desired conclusion. Here is the first main result of this section. The proof of the implication“(v)⇒(i)” was inspired by [4, Lemma 5.3].Theorem 5.23 Let K1 and K2 be nonempty closed convex cones in H. Then thefollowing are equivalent:(i) K1 + K2 is closed and PK1 + PK2 = PK1+K2 .(ii) There exists a nonempty closed convex cone K such that PK1 + PK2 = PK.(iii) PK1 + PK2 is a proximity operator of a function in Γ0(H).(iv) PK1 + PK2 is nonexpansive.(v) Id−PK1 − PK2 is monotone.(vi) (∀x ∈ H) 〈PK1 x |PK2 x〉 = 0.Furthermore, if one of (i)–(vi) holds, thend2K1+K2 = d2K1 + d2K2 − 2q = d2K1 − d2K	2 = d2K2 − d2K	1 . (5.37)Proof. The chain of implications “(i)⇒(ii)⇒(iii)⇒(iv)” is clear, and theimplication “(iv)⇒(v)” follows from Fact 3.53. We now assume that (v)holds and establish (i). Towards this end, setf := 12 d2K1 +12 d2K2 − q. (5.38)and seth := f ∗ − q. (5.39)Let us first establish that h = ιK	1 ∩K	2 . To do so, we derive from themonotonicity of Id−PK1 − PK2 and Moreau’s conical decomposition that(∀x ∈ H) 〈x |PK	1 x− PK2 x〉 (5.40a)= 〈x− 0 | (Id−PK1 − PK2)x− (Id−PK1 − PK2)0〉 (5.40b)715.4. The partial sum property of projectors onto convex cones> 0. (5.40c)Thus, because K	1 and K2 are closed convex cones, Fact 3.27 guarantees thatK2 ⊆ K	1 , from which and Proposition 5.22(ii) we deduce thath = ιK	1 ∩K	2 , (5.41)as claimed. Next, by Theorem 5.6 (respectively applied to PK1 and PK2), f isFréchet differentiable onH (hence continuous) and∇ f = (Id−PK1) + (Id−PK2)− Id = Id−PK1 − PK2 , (5.42)which is monotone by assumption. Therefore, in view of Fact 3.35, f isconvex, and so f ∈ Γ0(H). In turn, because f ∗ = h + q = ιK	1 ∩K	2 + q by(5.39) and (5.41), the Fenchel–Moreau theorem and Example 3.39 yield f =f ∗∗ = (ιK	1 ∩K	2 + q)∗ = q− (1/2)d2K	1 ∩K	2 . Hence, by (5.42) and Fact 3.37(i),we obtain Id−PK1 − PK2 = ∇ f = Id− (Id−PK	1 ∩K	2 ) = PK	1 ∩K	2 . Thus, theMoreau conical decomposition and Fact 3.26(i)&(ii) guarantee that PK1 +PK2 = Id−PK	1 ∩K	2 = P(K	1 ∩K	2 )	 = PK		1 +K		2 = PK1+K2 . Consequently,Proposition 5.1(iii) asserts that K1 +K2 is closed, and therefore, PK1 +PK2 =PK1+K2 , as desired. To summarize, we have shown the equivalences of(i)–(v).“(i)⇔(vi)”: Follows from Corollary 5.13 and the fact that 〈PK10 |PK20〉 =0. Moreover, if (vi) holds, then (5.37) follows from Corollary 5.13 andFact 3.25(iii). Replacing one cone by a general convex set may make the implication“(v)⇒(i)” of Theorem 5.23 fail, as illustrated by the following example.Example 5.24 Let K be a nonempty closed convex cone inH, and let u ∈ H.Then, by Moreau’s conical decomposition, Id−PK−P{u} = PK	 −u, whichis clearly monotone. However, owing to Example 5.17, P{u} + PK = u + PKis not a projector provided that u /∈ (K− K)⊥.Here is an instance where the projector onto the intersection can beexpressed in term of the individual projectors.Corollary 5.25 Let K1 and K2 be nonempty closed convex cones in H. Then thefollowing are equivalent:(i) PK1∩K2 = PK1 + PK2 − Id .725.4. The partial sum property of projectors onto convex cones(ii) PK1 + PK2 − Id is a projector onto a closed convex set.(iii) PK1 + PK2 − Id is monotone.(iv) (∀x ∈ H) ‖PK1 x‖2 + ‖PK2 x‖2 = ‖x‖2 + 〈PK1 x |PK2 x〉.Proof. We first deduce from the Moreau conical decomposition andFact 3.26(ii) thatPK1∩K2 = PK1 + PK2 − Id⇔ Id−P(K1∩K2)	 = PK1 + PK2 − Id (5.43a)⇔ Id−PK	1 +K	2 = PK1 + PK2 − Id (5.43b)⇔ PK	1 +K	2 = (Id−PK1) + (Id−PK2) (5.43c)⇔ PK	1 +K	2 = PK	1 + PK	2 . (5.43d)“(i)⇔(ii)”: Denote by C the class of nonempty closed convex cones inH.Then, because the mapping C→ C : K 7→ K	 is bijective due to Fact 3.26(i),we derive from (5.43d), the equivalence “(i)⇔(ii)” of Theorem 5.23, and theMoreau conical decomposition that(i)⇔ PK	1 +K	2 = PK	1 + PK	2 (5.44a)⇔ K	1 + K	2 is closed and PK	1 +K	2 = PK	1 + PK	2 (5.44b)⇔ (∃K ∈ C) PK = PK	1 + PK	2 (5.44c)⇔ (∃K ∈ C) Id−PK	 = (Id−PK1) + (Id−PK2) (5.44d)⇔ (∃K ∈ C) PK	 = PK1 + PK2 − Id (5.44e)⇔ (∃K ∈ C) PK = PK1 + PK2 − Id (5.44f)⇔ (ii), (5.44g)where the last equivalence follows from the fact that PK1 + PK2 − Id ispositively homogeneous.“(i)⇔(iii)”: Since Id−(PK	1 +PK	2 ) = PK1 +PK2 − Id by Moreau’s decom-position, this equivalence is a consequence of (5.43d) and the equivalence“(ii)⇔(v)” of Theorem 5.23 (applied to (K	1 , K	2 )).“(i)⇔(iv)”: This readily follows from (5.43d), the equivalence“(ii)⇔(vi)” of Theorem 5.23 (applied to (K	1 , K	2 )), and Lemma 3.28(ii). By replacing (K1, K2) by (K1, K	2 ) in Corollary 5.25, we provide analternative proof for [39, Theorem 5.3]. The linear case of Corollary 5.26goes back at least to Halmos (see [21, Theorem 3, p. 48]).735.4. The partial sum property of projectors onto convex conesCorollary 5.26 (Zarantonello) Let K1 and K2 be nonempty closed convex conesin H. Then PK2 PK1 = PK2 if and only if PK1 − PK2 is a projector onto a closedconvex set; in which case, PK1 − PK2 = PK1∩K	2 .Proof. First, suppose that PK2 PK1 = PK2 . Then, by Fact 3.25(i)&(iii) andLemma 3.28(i),(∀x ∈ H) 〈PK1 x |PK	2 x〉 = 〈PK1 x | x〉 − 〈PK1 x |PK2 x〉 (5.45a)= 〈PK1 x | x〉 − 〈PK1 x |PK2 PK1 x〉 (5.45b)= ‖PK1 x‖2 − ‖PK2 PK1 x‖2 (5.45c)= ‖PK1 x‖2 − ‖PK2 x‖2 (5.45d)= ‖PK1 x‖2 + ‖PK	2 x‖2 − ‖x‖2. (5.45e)Hence, the equivalence “(i)⇔(iv)” of Corollary 5.25 (applied to (K1, K	2 ))yields PK1 − PK2 = PK1 + PK	2 − Id = PK1∩K	2 , as desired. Conversely,assume that PK1 − PK2 is a projector associated with a closed convex set.Since PK1 −PK2 = PK1 +PK	2 − Id, it follows from the equivalence “(i)⇔(ii)”of Corollary 5.25 (applied to (K1, K	2 )) thatPK1 − PK2 = PK1∩K	2 . (5.46)Now take x ∈ H. On the one hand, because PK1∩K	2 + PK2 = (PK1 − PK2) +PK2 = PK1 by (5.46), we infer from Theorem 5.23 that PK1∩K	2 x ⊥ PK2 x or,equivalently, by (5.46), (PK1 x − PK2 x) ⊥ PK2 x. On the other hand, (5.46)implies that PK1 x − PK2 x ∈ K	2 . Altogether, since clearly PK2 x ∈ K2, (3.26)asserts that PK2 PK1 x = PK2 x, and the proof is complete. The so-called partial sum property, i.e., if a finite sum of proximityoperators is a proximity operator, then so is every partial sum, was ob-tained in [4]. Somewhat surprisingly, as we shall see in the followingresult, this property is still valid in the class of projectors onto convexcones. The equivalence “(i)⇔(iii)” of the following result was obtained byZarantonello with a different proof (see [39, Theorem 5.5]).Theorem 5.27 (Partial sum property for cones) Let m > 2 be an integer, setI := {1, . . . , m}, and let (Ki)i∈I be a family of nonempty closed convex cones inH. Then the following are equivalent:(i) For every (i, j) ∈ I × I such that i 6= j, we have (∀x ∈ H) 〈PKi x |PKj x〉 =0.745.4. The partial sum property of projectors onto convex cones(ii) ∑i∈I Ki is closed and ∑i∈I PKi = P∑i∈I Ki .(iii) ∑i∈I PKi is a projection onto a closed convex cone inH.(iv) ∑i∈I PKi is a proximity operator of a function in Γ0(H).(v) For every nonempty subset J of I, ∑j∈J PKj is a proximity operator of afunction in Γ0(H).(vi) For every nonempty subset J of I, ∑j∈J Kj is closed and ∑j∈J PKj = P∑j∈J Kj .(vii) For every (i, j) ∈ I × I such that i 6= j, we have PKi + PKj is nonexpansive.(viii) For every (i, j) ∈ I× I such that i 6= j, we have Id−PKi −PKj is monotone.Proof. “(i)⇒(ii)”: A direct consequence of Corollary 5.19.“(ii)⇒(iii)” and “(iii)⇒(iv)”: Clear.“(iv)⇒(v)”: Let f ∈ Γ0(H) be such that ∑i∈I PKi = Prox f . Then,by Moreau’s decomposition, ∑i∈I PKi + Prox f ∗ = Prox f + Prox f ∗ = Id.Therefore, since {PKi}i∈I are proximity operators, the conclusion followsfrom [4, Theorem 4.2].“(v)⇒(vii)”: Clear.“(vii)⇒(viii)”: See Fact 3.53.“(viii)⇒(i)”: This is the implication “(v)⇒(vi)” of Theorem 5.23.To sum up, we have shown the equivalence of (i)–(viii) except for (vi).“(v)⇔(vi)”: Follows from the equivalence “(ii)⇔(iv).” As we now illustrate, the partial sum property may, however, fail out-side the class of projectors onto convex cones.Example 5.28 Suppose that H 6= {0}, let w ∈ H r {0}, set U := R+w,and set V := R+(−w) = R−w. Then, appealing to (4.32), we see that(∀x ∈ H) 〈PUx |PV x〉 = 0. Hence, by Theorem 5.23, PU + PV = PU+V =PRw. Now suppose that z ∈ H r (U −U)⊥ = H r (Rw)⊥. Then clearlyPU + PV + P{z} + P{−z} = PRw is the projector associated with the lineRw.However, due to Example 5.17, P{z} + PU = z + PU is not a projector.Theorem 5.27 gives us a different perspective of the projection ontocones generated by orthonormal families: It is just the sum of projectionsonto the generating rays.755.5. The one-dimensional caseExample 5.29 Let {ei}i∈I be a finite orthonormal subset of H, set (∀i ∈I) Ki := R+ei, and set K := ∑i∈I Ki. Then, for every (i, j) ∈ I × I such thati 6= j, since Ki ⊥ Kj, we see that (∀x ∈ H) 〈PKi x |PKj x〉 = 0. Hence, owingto Theorem 5.27, K = ∑i∈I Ki is closed and, by using (4.32),(∀x ∈ H) PKx =∑i∈IPKi x =∑i∈Imax{〈x | ei〉, 0}ei; (5.47)see also Theorem 4.7.5.5 The one-dimensional caseIn this section, we assume thatH = R (5.48)and thatC and D are nonempty closed intervals ofH. (5.49)The goal of this section is to describe all pairs (C, D) on the real line suchthat PC + PD = PC+D. We begin with a simple observation.Remark 5.30 If C = {0} or D = {0}, then clearly PC + PD = PC+D. Thus,we henceforth assume in this section thatC 6= {0} and D 6= {0}. (5.50)Here is a sufficient condition under which PC + PD = PC+D.Proposition 5.31 Suppose that C ∩ D = {0}. Then C + D is closed and PC +PC = PC+D.Proof. In the light of Proposition 3.15, we may and do assume that C ⊆ R−.Then Proposition 3.15(i) implies that max C = min D = 0, and thus (3.9)yields (∀ξ ∈ H) 〈PCξ |PDξ〉 = 0. Hence, according to Corollary 5.13, weconclude that C + D is closed and that PC + PD = PC+D. The next result classifies all pairs (C, D) such that PC +PD = PC+D. Item(ii) is a partial converse of Proposition 3.15.Theorem 5.32 (Dichotomy) Suppose that there exists a closed convex set E suchthat PC + PD = PE. Then exactly one of the following cases occurs:765.5. The one-dimensional case(i) C and D are singletons.(ii) Neither C nor D is a singleton and C ∩ D = {0}.Proof. Corollary 5.13 and our assumption guarantee the existence of γ ∈ Rsuch that(∀ξ ∈ H) (PCξ)(PDξ) = 〈PCξ |PDξ〉 = γ. (5.51)(i): Suppose that C = {pi}, where pi 6= 0 due to (5.50). Then, for everyξ ∈ D and every η ∈ D, since PCξ = PCη = pi, (5.51) implies that piξ =pi PDξ = pi PDη = piη, and because pi 6= 0, it follows that ξ = η. Therefore,D is a singleton, as required.(ii): Suppose that C is not a singleton. Let us first show that D isnot a singleton by proving the contrapositive. If D is a singleton, theninterchanging C and D in (i), we see that C is a singleton. Next, we shallestablish that C ∩ D 6= ∅ by contradiction. Assume that C ∩ D = ∅. Then,owing to the separation theorem (see, e.g., [8, Theorem 3.53]), we obtainµ ∈ Hr {0} and β ∈ R such that(∀ξ ∈ C)(∀η ∈ D) ξµ 6 β 6 ηµ. (5.52)Without loss of generality, we may and do assume thatµ > 0. (5.53)Then (5.52) asserts that C is bounded above and D is bounded below, andbecause they are closed, we infer that sup C = max C and inf D = min D.Let us consider the following conceivable cases.(a) max C = 0: Then min D 6= 0 (otherwise 0 ∈ C ∩ D, which isabsurd). Because C is not a singleton, we can find ξ1 ∈ C and ξ2 ∈ Csuch that ξ1 6= ξ2. In turn, due to (5.52) and (5.53), (∀i ∈ {1, 2}) ξi 6β/µ 6 min D, from which and (3.9) we deduce that PDξ1 = PDξ2 =min D. Consequently, since {ξ1, ξ2} ⊆ C, (5.51) implies that ξ1 min D =〈PCξ1 |PDξ1〉 = 〈PCξ2 |PDξ2〉 = ξ2 min D, and since min D 6= 0, it followsthat ξ1 = ξ2, which is impossible.(b) max C 6= 0: Since D is not a singleton, there are η1 ∈ D andη2 ∈ D such that η1 6= η2. In turn, we infer from (5.52)&(5.53) that(∀i ∈ {1, 2}) max C 6 β/µ 6 ηi, and therefore (3.9) yields PCη1 =PCη2 = max C. Thus, by (5.51) and the fact that {η1, η2} ⊆ D, , we see that(max C)η1 = 〈PCη1 |PDη1〉 = 〈PCη2 |PDη2〉 = (max C)η2. Consequently,since max C 6= 0, it follows that η1 = η2, which is absurd.775.6. On a result by HalmosTo summarize, we have shown that C ∩ D 6= ∅. Let us next verify thatC ∩ D is a singleton. To this end, take ξ ∈ C ∩ D and η ∈ C ∩ D, and letε ∈ ]0, 1[. On the one hand, by (5.51), we see that(∀ξ ∈ C ∩ D) ξ2 = γ. (5.54)On the other hand, since C ∩ D is convex and ε ∈ ]0, 1[, (1− ε)ξ + εη ∈C∩D. Altogether, ξ2 = [(1− ε)ξ+ εη]2 or, equivalently, ε(ξ− η)[(2− ε)ξ+εη] = ξ2 − [(1− ε)ξ + εη]2 = 0. Interchanging ξ and η yields ε(η − ξ)[(2−ε)η + εξ] = 0, and upon adding these equalities, we obtain ε(ξ − η)(2(1−ε)ξ − 2(1− ε)η) = 0, i.e., 2ε(1− ε)(ξ − η)2 = 0. Therefore, ξ = η and C ∩Dis thus a singleton, say C∩D = {pi}. It remains to show that pi = 0. Since Cis not a singleton, there exists ξ ∈ Cr {pi}. In turn, because C ∩ D = {pi},we derive from [8, Proposition 24.47] (applied to (Ω, φ) = (D, ιC)) and(5.51)&(5.54) that ξpi = 〈PCξ |PC∩Dξ〉 = 〈PCξ |PD(PCξ)〉 = 〈PCξ |PDξ〉 =γ = pi2. Thus, pi(ξ − pi) = 0, and since ξ 6= pi, it follows that pi = 0, whichcompletes the proof. 5.6 On a result by HalmosIn this section, we revisit and extend the classical result [21, Theorem 2,p. 46] to the nonlinear case.Proposition 5.33 Let C be a nonempty closed convex subset of H, and let K be anonempty closed convex cone inH. Suppose that there exits a closed convex set Dsuch that PC + PK = PD. Then C ⊆ K	.Proof. Our assumption and Corollary 5.13 guarantee the existence of γ ∈ Rsuch that (∀x ∈ H) 〈PCx |PKx〉 = γ. However, because PK0 = 0, we inferthat γ = 0. Therefore, for every x ∈ C, it follows from Lemma 3.28(i) that‖PKx‖2 = 〈x |PKx〉 = 〈PCx |PKx〉 = γ = 0; hence, PKx = 0, and Fact 3.25(i)thus implies that x = PK	x ∈ K	. Consequently, C ⊆ K	, as claimed. The following example shows that the conclusion of Proposition 5.33 ismerely a necessary condition for PC + PK = PC+K even when C is a cone.Example 5.34 Suppose that H = R2. Set u := (1, 0) and v := (−1, 1).Moreover, set C := R+v and K := R+u. Then, because 〈u | v〉 = −1 < 0,we see that C ⊆ K	. Furthermore, C + K is a closed cone by Example 4.6.Now set x := (1, 1) = v + 2u ∈ C + K. According to (4.32), PCx + PKx =(0, 0) + (1, 0) = (1, 0) 6= x = PC+Kx. Therefore, PC + PK 6= PC+K.785.6. On a result by HalmosWe now extend the classical [21, Theorem 2, p. 46] (in the case of twosubspaces) by replacing one subspace by a general convex set.Corollary 5.35 Let C be a nonempty closed convex subset of H, and let V be aclosed linear subspace ofH. Then the following are equivalent:(i) There exists a closed convex set D such that PC + PV = PD.(ii) C ⊥ V.Moreover, if (i) and (ii) hold, then D = C +V and PC + PV = PC+V .Proof. “(i)⇒(ii)”: It follows from Corollary 5.13 that D = C + V and thatPC + PV = PC+V . Now, by Proposition 5.33 and Fact 3.21(i), we obtainC ⊆ V	 = V⊥. “(ii)⇒(i)”: Immediate from Corollary 5.15. However, replacing the subspace V in Corollary 5.35 by cone might notwork. The following simple example shows that the implication “(i)⇒(ii)”of Corollary 5.35 may fail even when C and V are cones.Example 5.36 Consider the setting of Example 5.28. We have seen that PU +PV = PRw. Yet, U is not perpendicular to V. In fact, span U = span V =Rw.Combining Theorem 5.27, Theorem 5.23, and Corollary 5.35, we obtainthe following well-known result; see [21, Theorem 2, p. 46].Corollary 5.37 Let (Vi)i∈I be a finite family of closed linear subspaces ofH. Then∑i∈I PVi is a projector associated with a closed linear subspace if and only if, forevery (i, j) ∈ I × I with i 6= j, we have Vi ⊥ Vj.79Chapter 6Conclusion and future workWe have provided formulae for projection onto the intersection of a coneand a ball/sphere under mild assumptions. Our analysis allows us to covermany cases including nonpolyhedral cones, e.g., the ice cream cone andthe cone of positive semidefinite matrices; moreover, this analysis may behelpful in future research involving projection onto spheres. Also, we havefilled a gap in the literature of Convex Analysis by establishing a completeanswer to the question “When is the sum of projectors a projector?.” Theprovided analysis may give more insights into properties of projectionoperators associated with convex sets. To conclude this thesis, we list herequestions and directions for future research:P1 When is a linear combination (in particular, convex combination) ofprojectors a projector?P2 Provide a characterization for proximal mapping that is similar toTheorem 5.6.P3 Solve Open Problem 5.8.P4 Provide a proof rooted in Convex Analysis for Zarantonello’s [39, The-orem 4.1].80Bibliography[1] W. N. ANDERSON AND R. J. DUFFIN, Series and parallel additionof matrices, Journal of Mathematical Analysis and Applications, 26(1969), pp. 576–594. → pages 23[2] H. ATTOUCH, J. BOLTE, AND B. F. SVAITER, Convergence of de-scent methods for semi-algebraic and tame problems: proximal algorithms,forward–backward splitting, and regularized Gauss–Seidel methods, Math-ematical Programming, 137 (2013), pp. 91–129. → pages 53[3] M. BARDI AND I. C. DOLCETTA, Optimal Control and Viscosity Solutionsof Hamilton-Jacobi-Bellman Equations, Birkhäuser, Basel, 1997. → pages63[4] S. BARTZ, H. H. BAUSCHKE, AND X. WANG, The resolvent order: aunification of the orders by Zarantonello, by Loewner, and by Moreau, SIAMJournal on Optimization, 27 (2017), pp. 466–477. → pages 2, 56, 57, 68,69, 71, 74, 75[5] H. H. BAUSCHKE, Projection Algorithms and Monotone Operators, PhDthesis, Simon Fraser University, Burnaby, B.C., Canada, August 1996.→ pages 11[6] H. H. BAUSCHKE, M. N. BUI, AND X. WANG, On the sum of projectorsonto convex sets. https://arxiv.org/abs/1802.02287. → pages v, 2[7] , Projecting onto the intersection of a cone and a sphere, SIAM Journalon Optimization. in press (https://arxiv.org/abs/1708.00585). →pages v, 2[8] H. H. BAUSCHKE AND P. L. COMBETTES, Convex Analysis and Mono-tone Operator Theory in Hilbert Spaces, Springer, New York, second ed.,2017. → pages 3, 5, 8, 10, 11, 13, 15, 16, 18, 19, 20, 21, 22, 23, 25, 26, 27,29, 31, 49, 59, 60, 64, 77, 7881Chapter 6. Bibliography[9] H. H. BAUSCHKE, P. L. COMBETTES, AND D. R. LUKE, A stronglyconvergent reflection method for finding the projection onto the intersectionof two closed convex sets in a Hilbert space, Journal of ApproximationTheory, 141 (2006), pp. 63–69. → pages 66[10] H. H. BAUSCHKE AND M. N. DAO, On the finite convergence of theDouglas–Rachford algorithm for solving (not necessarily convex) feasibilityproblems in Euclidean spaces, SIAM Journal on Optimization, 27 (2017),pp. 507–537. → pages 33[11] H. H. BAUSCHKE, S. M. MOFFAT, AND X. WANG, Near equality,near convexity, sums of maximally monotone operators, and averages offirmly nonexpansive mappings, Mathematical Programming, 139 (2013),pp. 55–70. → pages 58[12] H. H. BAUSCHKE AND W. M. MOURSI, The magnitude of the minimaldisplacement vector for compositions and convex combinations of firmlynonexpansive mappings, Optimization Letters, (2018). https://doi.org/10.1007/s11590-018-1259-5. → pages 59[13] A. BECK AND M. TEBOULLE, A fast iterative shrinkage-thresholdingalgorithm for linear inverse problems, SIAM Journal on Imaging Sciences,2 (2009), pp. 183–202. → pages 53[14] J. BOLTE, S. SABACH, AND M. TEBOULLE, Proximal alternating lin-earized minimization for nonconvex and nonsmooth problems, Mathemati-cal Programming (Series A), 146 (2014), pp. 459–494. → pages 53[15] R. COLEMAN, Calculus on Normed Vector Spaces, Springer, New York,2012. → pages 65[16] C. COSNER, Personal communication, 2018. → pages 63[17] Z. DENKOWSKI, S. MIGÓRSKI, AND N. S. PAPAGEORGIOU, An In-troduction to Nonlinear Analysis: Theory, Kluwer, Dordrecht, 2003. →pages 59[18] M. DÜR, Copositive programming – a survey, in Recent Advances in Op-timization and its Applications in Engineering, M. Diehl, F. Glineur,E. Jarlebring, and W. Michiels, eds., Springer, 2010. → pages 53[19] K. HADELER, On copositive matrices, Linear Algebra and its Applica-tions, 49 (1983), pp. 79–89. → pages 5482Chapter 6. Bibliography[20] M. HALL AND M. NEWMAN, Copositive and completely positive quadraticforms, Mathematical Proceedings of the Cambridge PhilosophicalSociety, 59 (1963), pp. 329–339. → pages 54[21] P. R. HALMOS, Introduction to Hilbert Space and the Theory of SpectralMultiplicity, Chelsea Publishing Company, New York, NY, 1951. →pages 1, 56, 57, 73, 78, 79[22] Y. HAUGAZEAU, Sur les inéquations variationnelles et la minimisation defonctionnelles convexes, thèse de doctorat, Université de Paris, (1968).→ pages 23[23] J.-B. HIRIART-URRUTY AND C. LEMARÉCHAL, Convex Analysis andMinimization Algorithms I, Springer-Verlag, Berlin, 1993. → pages 8,69[24] , Convex Analysis and Minimization Algorithms II, Springer-Verlag,Berlin, 1993. → pages 8[25] J.-B. HIRIART-URRUTY AND A. SEEGER, A variational approach tocopositive matrices, SIAM Review, 52 (2010), pp. 593–629. → pages 53[26] INTERNATIONAL GEOGEBRA INSTITUTE, Geogebra software. https://www.geogebra.org/. → pages ix, 67[27] P. KAYE, R. LAFLAMME, AND M. MOSCA, An Introduction to QuantumComputing, Oxford University Press, New York, 2007. → pages 56[28] K. LANGE, MM Optimization Algorithms, SIAM, 2016. → pages 1, 23,45, 53[29] A. S. LEWIS AND J. MALICK, Alternating projections on manifolds,Mathematics of Operations Research, 33 (2008), pp. 216–234. → pages49[30] G. LI AND T. K. PONG, Douglas-Rachford splitting for nonconvex opti-mization with application to nonconvex feasibility problems, MathematicalProgramming, 159 (2016), pp. 371–401. → pages 53[31] B. S. MORDUKHOVICH, Variational Analysis and Generalized Differentia-tion I – Basic Theory, Springer-Verlag Berlin, 2006. → pages 59, 60[32] J.-J. MOREAU, Décomposition orthogonale d’un espace hilbertien selondeux cônes mutuellement polaires, Comptes Rendus Hebdomadaires des83Chapter 6. BibliographySéances de l’Académie des Sciences (Séries A), 225 (1962), pp. 238–240.→ pages 16[33] L. PING AND F. Y. YU, Criteria for copositive matrices of order four, LinearAlgebra and its Applications, 194 (1993), pp. 109–124. → pages 54[34] R. T. ROCKAFELLAR, Convex Analysis, Princeton University Press,1970. → pages 8, 9, 27[35] C. M. THEOBALD, An inequality for the trace of the product of twosymmetric matrices, Mathematical Proceedings of the Cambridge Philo-sophical Society, 77 (1975), pp. 265–267. → pages 50[36] J. WEIDMANN, Linear Operators in Hilbert Spaces, Springer, New York,1980. → pages 57, 64[37] Y.-L. YU, On decomposing the proximal map, in Advances in Neu-ral Information Processing Systems 26, C. J. C. Burges, L. Bottou,M. Welling, Z. Ghahramani, and K. Weinberger, eds., Curran Asso-ciates, Inc., 2013, pp. 91–99. → pages 34[38] C. ZA˘LINESCU, Convex Analysis in General Vector Spaces, World Scien-tific Publishing Co. Inc., River Edge, NJ, 2002. → pages 8, 60[39] E. H. ZARANTONELLO, Projections on convex sets in Hilbert spaceand spectral theory. I. Projections on convex sets, in Contributions toNonlinear Functional Analysis, E. H. Zarantonello, ed., AcademicPress, New York, 1971, pp. 237–341. → pages 1, 16, 56, 57, 58, 60,69, 73, 74, 80[40] , Projections on convex sets in Hilbert space and spectral theory. II.Spectral theory, in Contributions to Nonlinear Functional Analysis,E. H. Zarantonello, ed., Academic Press, New York, 1971, pp. 343–424.→ pages 784

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0369217/manifest

Comment

Related Items