Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
1
Solutions To Problems of Chapter 8
1. Prove the Cauchy - Schwartz’s inequality in a general Hilbert space.
Solution: We have to show that ∀x,y∈H,
|hx,yi| ≤ kxkkyk,
kyk2.
Thus
0≤ kxk2−|hx,yi|2
kyk2,
2. Show a) that the set of points in a Hilbert space H,
C={x:kxk ≤ 1}
is a convex set, and b) the set of points
2
is a nonconvex one.
Solution: From the definition of a Hilbert space (see Appendix of this
chapter) the norm is the induced by the inner product norm, i.e.,
kxk= (hx,xi)
1
2.
a) Let us now consider two points, x1,x2∈H, such that
kx1k ≤ 1,kx2k ≤ 1,
and let
3. Show the first order convexity condition.
Solution: Assume that fis convex. Then
fλy+ (1 −λ)x≤λf(y) + (1 −λ)f(x)
or
fx+λ(y−x)−f(x)≤λf(y)−f(x).
Taking λ−→ 0, we can employ the Taylor expansion and get
4. Show that a function fis convex, iff the one-dimensional function,
g(t) := f(x+ty),
is convex, ∀x,yin the domain of definition of f.
Solution: Observe that,
g(λt1+ (1 −λ)t2) = f(x+λt1y+ (1 −λ)t2y)
5. Show the second order convexity condition.
Hint: Show the claim first for the one-dimensional case and then use the
result of the previous problem, for the generalization.
Solution: We start with the one-dimensional case. Let a function f(x)
be convex. Then we know from the first order convexity condition that
6. Show that a function
f:Rl7−→ R
is convex iff its epigraph is convex.
Solution: a) Assume fto be convex. We have to show that its epigraph
f(x1)≤r1, f(x2)≤r2.(14)
Combining (11) and (14) we get
f(x)≤λf(x1) + (1 −λ)f(x2)≤λr1+ (1 −λ)r2=r,
7. Show that if a function is convex, then its lower level set is convex for any ξ.
Solution: Let the function fbe convex and two points, x,y, which lie in
8. Show that in a Hilbert space, H, the parallelogram rule,
kx+yk2+kx−yk2= 2 kxk2+kyk2,∀x,y∈H.
holds true.
Solution: The proof is straightforward from the respective definitions and
the properties of the inner product relation.
9. Show that if x,y∈H, where His a Hilbert space, then the induced by
the inner product norm satisfies the triangle inequality, as required by any
norm, i.e.,
kx+yk ≤ kxk+kyk
Solution: By the respective definitions we have
kx+yk2:= hx+y,x+yi=kxk2+hx,yi+hy,xi+kyk2,
10. Show that if a point x∗is a local minimizer of a convex function, it is nec-
essarily a global one. Moreover, it is the unique minimizer if the function
is strictly convex.
Solution: Let x∗be a local minimizer. Then, there exists ǫ > 0 and
y∗/∈B[0, ǫ] such that
f(x∗)≤f(x∗+ ∆),∀∆∈B[0, ǫ],
11. Let Cbe a closed convex set in a Hilbert space, H. Then show that
∀x∈H, there exists a point, denoted as PC(x)∈C, such that
kx−PC(x)k= min
y∈Ckx−yk.
Solution: Let x6∈ C, otherwise it is trivial. Let ρbe the largest lower
bound of kx−yk,y∈C, i.e.,
ρ:= inf
From the parallelogram law, we can write
8
However, since Cis convex, the point 1
2(xn+xm)∈Cand we deduce
That is, xnis a Cauchy sequence and since His Hilbert the sequence
converges to a point x∗. Moreover it converges in C, since Cis closed,
i.e., x∈C. Hence we have
kx−x∗k=kx−xn+xn−x∗k
12. Show that the projection of a point x∈Honto a non-empty closed convex
set, C⊂H, lies on the boundary of C.
Solution: Assume that PC(x) is an interior point of C. By the defini-
tion of interior points, ∃δ > 0 such that
13. Derive the formula for the projection onto a hyperplane in a (real) Hilbert
space, H.
Solution: Let us first show that a hyperplane, H, is a closed convex set.
Convexity is shown trivially. To show closeness, let yn∈H−→ y∗. We
will show that y∗∈H. Let
hθ,zi+θ0=0hx−z,x−zi.
Using Lagrange multipliers, we obtain the Lagrangian
L(z, λ) = hx−z,x−zi − λhθ,zi+θ0.
For those not familiar with infinite dimensional spaces, it suffices to say
that similar rules of differentiation apply, although the respective defini-
14. Derive the formula for the projection onto a closed ball, B[0, ρ].
Solution: The closed ball is defined as
B[0, ρ] = {y:kyk ≤ ρ}.
We have already seen (Problem 2) that it is convex. Let us show the
closeness. Let
kzk2=ρ2,
since the projection is on the boundary. Taking the gradient of the La-
grangian we get
2(z−x) + 2λz= 0,
or
z=1
z=−ρ
kxkx.
11
From the two possible vectors, we have to keep the one that has the smaller
distance from x. However,
15. Find an example of a point whose projection on the ℓ1ball is not unique.
Solution: The ℓ1ball of radius ρ= 1 in Rlis defined as
S1[0, ρ] = {y:X
i=1
|yi| ≤ ρ}.
16. Show that if C⊂H, is a closed convex set in a Hilbert space, then ∀x∈H
and ∀y∈C, the projection PC(x) satisfies the following properties:
12
•Real{hx−PC(x),y−PC(x)i} ≤ 0.
• kPC(x)−PC(y)k2≤Real{hx−y, PC(x)−PC(y)i}.
Solution: We know that PC(x)∈C. Hence, due to the convexity of C,
∀λ∈[0,1]
λy+ (1 −λ)PC(x)∈C.
Hence
17. Prove that if Sis a closed subspace S⊂Hin a Hilbert space H, then
∀x,y∈H,
hx, PS(y)i=hPS(x),yi=hPS(x), PS(y)i.
and
PS(ax+by) = aPS(x) + bPS(y).
Hint: Use the result of Problem 18.
18. Let Sbe a closed convex subspace in a Hilbert space H,S⊂H. Let S⊥be
the set of all elements x∈Hwhich are orthogonal to S. Then show that,
a) S⊥is also a closed, subspace, b) S∩S⊥={0}, c) H=S⊕S⊥; that
is, ∀x∈H,∃x1∈Sand x2∈S⊥:x=x1+x2, where x1,x2are unique.
Solution:
a) We will first prove that S⊥is a subspace. Indeed if x1∈S⊥and
x2∈S⊥then
hx1,yi=hx2,yi= 0,∀y∈S.
14
where the Cauchy-Schwartz inequality has been used. The last inequality
b) Let x∈S∩S⊥. By definition, since it belongs to both subspaces,
c) Let x∈H. We have that
We apply the same for jy. Then we have that
hx−PS(x), jyi=−jhx−PS(x),yi.
x=x3+x4,x3∈S, x4∈S⊥.
15
Then
x1+x2=x3+x4
or
S→x1−x3=x4−x2∈S⊥,
since x−PS(x)∈S⊥. Note that we used the fact that if y∈Sthen
since
19. Show that the relaxed projection operator is a non-expansive mapping.
Solution: By the respective definitions we have,
kTC(x)−TC(y)k=kx+µ(PC(x)−x)−y−µ(PC(y)−y)k
=k(1 −µ)(x−y) + µ(PC(x)−PC(y))k.
20. Show that the relaxed projection operator is a strongly attractive map-
ping.
Solution: By the respective definition we have,
kTC(x)−yk2=kx+µ(PC(x)−x)−yk2
=kx−yk2+µ2kPC(x)−xk2+ 2µReal{hx−y, PC(x)−xi}
21. Give an example of a sequence in a Hilbert space H, which converges
weakly but not strongly.
Solution: Define the sequence of points xn∈l2,
xn={0,0,...,1,0,0, . . .}:= {δni}, i = 0,1,2, . . .
22. Prove that if C1. . . CKare closed convex sets in a Hilbert space H, then
the operator
T=TCK· · · TC1,
is a regular one; that is,
kTn−1(x)−Tn(x)k −→ 0, n −→ ∞,
Fact 2:
Fix(T) =
K
\
k=1
Ck:= C.
Indeed, if x∈Cthen
TKTK−1· · · T1(x) = TKTK−1· · · T2(x) = . . .
previous two facts are valid for general Hilbert spaces.
Fact3: If Cis a closed subspace, then Tk, k = 1, . . . , K, and T=
TKTK−1· · · T1are linear operators. The proof is trivial from the respec-
tive linearity of the projection operators, Pk, k = 1, . . . , K. This is also
true for general Hilbert spaces.
kx−T1(x)k=µ2
1kx−P1(x)k2≤µ1
2−µ1kx−yk2− kT1(x)−yk2.
Let now
kx−T2T1(x)k2=kx−T1(x) + T1(x)−T2T1(x)k2
