26.6 Projections 297
Proposition26.13. Letf :Rd →R ̄ be a convex function andA ⊂Rda
nonempty convex set. Then for anyx∗∈dom(∇f)it holds that:
x∗∈argminx∈Af(a)⇔∀x∈A∩dom(f) :〈∇f(x∗),x−x∗〉≥ 0. (26.3)
26.6 Projections
IfA⊂Rdandx∈Rd, then the Euclidean projection ofxonAis ΠA(x) =
argminy∈A‖x−y‖^22. One can also project with respect to a Bregman divergence
induced by convex functionf. Let ΠA,fbe defined by
ΠA,f(x) = argminy∈ADf(y,x).
An important property of the projection is that minimizing a Legendre function
fon a convex setAis (usually) equivalent to finding the unconstrained minimum
on the domain offand then projecting that point ontoA.
Theorem26.14. Letf:Rd→R ̄be Legendre,A⊂Rda non-empty, closed
convex set and assume thaty ̃=argminz∈Rdf(z)exists. Then the fol lowing hold:
(a)y= argminz∈Af(z)exists and is unique;
(b)y= argminz∈ADf(z,y ̃).
The assumption thaty ̃exists is necessary. For examplef(x) =−
√
xforx≥ 0
andf(x) =∞forx <0 is Legendre with domaindom(f) = [0,∞), butfdoes
not have a minimum on its domain.
26.7 Notes
1 The ‘infinity arithmetic’ on the extended real line is as follows:
α+∞=∞ forα∈(−∞,∞]
α−∞=−∞ forα∈[−∞,∞)
α·∞=∞andα·(−∞) =−∞ forα > 0
α·∞=−∞andα·(−∞) =∞ forα < 0
0 ·∞= 0·(−∞) = 0.
Likeα/0 the value of∞−∞is not defined. We also haveα≤∞for allαand
α≥−∞for allα.
2 There are many ways to define the topological notions used in this chapter.
The most elegant is also the most abstract, but there is no space for that here.
Instead we give the classical definitions that are specific toRdand subsets.
LetAbe a subset ofRd. A pointx∈Ais aninterior pointif there exists
anε >0 such thatBε(x) ={y:‖x−y‖ 2 ≤ε} ⊂A. TheinteriorofAis
int(A) ={x∈A:xis an interior point}. The setAisopenifint(A) =A
