Q 1. Prove that all isolated minima are strict.
Hint: One way to prove this is by contrapositive. [7pts]
Q 2. A saddle point is a stationary point (a point x with rf(x) = 0) that is neither a local minimum nor a local maximum. List all stationary points of the following functions, where x = [xx12], and for each stationary point indicate whether it is a local minimum/maximum, a global minimum/maximum, or a saddle point.
(i)
f(x) =
x14
10x12 + 10x22;
[5pts]
20
) ;
(ii)
f(x) = x 2
+ x 2
+
1
sin( x1
2
2
[5pts]
11
2
2
) + cos( x2
(iii)
f(x) =
x1
+ x1 cos(x2).
[5pts]
2
Q 3. Let A be a real symmetric n n matrix with eigenvalues 1 2n: Prove that, 8x 2 Rn :
(i)
xT Ax 1kxk22;
[5pts]
(ii)
xT Ax nkxk22.
[5pts]
Q 4. Letnf : Rn ! R [ f
; +1g be an extended real valued convex function. Assume that f is such that for all
x; y 2 R ; f(y)
lim
#0 f( x + (1
)y): Prove that:
(i)
If there exists a point x such that f(x) =
; then f is not real-valued anywhere – it equals either
or +1
everywhere.
[5pts]
(ii)
If, 8x 2 Rn; f(x)
n M; for some constant M < 1; then f must be a constant function (i.e., taking the same
value for all x 2 R
).
[5pts]
Q 5 (Jensen’s Inequality). Let f : Rn ! R be a convex function. Prove that for any sequence of numbers
x1; x2; : : : ; xk 2 Rn and any sequence of non-negative scalars 1; 2; : : : ; k 0 such that Pk i = 1 we
i=1
have:
k k
X
Xi
[8pts]
f
ixiif(xi):
i=1
=1
Q 6. Let f : Rn ! R be a convex continuously differentiable function. Using the definition of convexity from the class and properties of directional derivatives, prove that it must be 8x; y 2 Rn :
f(y) f(x) + hrf(x); y xi : [10pts]
Q 7. Let f : Rn ! R be a twice continuously differentiable function. Prove that if f is convex, then it must be
r2f(x) 0; 8x 2 Rn;
that is, the Hessian of f is positive semidefinite. [10pts]
1
Q 8. Let f(x) := xT Ax bT x; where b is the vector of all 1’s and A is an n n matrix defined by: Aii = 2 for
1 i n; Ai;i+1 = 1; for 1 i n
1 and An;1 = A1;n =
1: That is, A is defined as:
2 21
21010
: : :
0
013
6
0
::: 0
7
A =
0
0
1 2
: : :
0
0
:
6
7
6
0
1
2
1
: : :
0
0
7
.
.
.
. .
. .
.
.
6
..
..
..
..
..
..
7
6
7
6
1
0
0
0
: : :
1 2
7
6
7
Is f convex? Justify your answer.
4
5
[15pts]
Q 9. Let f : Rn ! R be a continuously differentiable function that satisfies the following:
m
(8x; y 2 Rn) : f(y) f(x) + hrf(x); y xi +
ky xk22;
2
where m 0 is some constant.
Prove that f cannot be Lipschitz continuous on the entire Rn: Would it be possible for f to be Lipschitz continuous
if we take the domain to be the unit Euclidean ball (i.e., the set: fx 2 Rn : kxk2 1g)? Explain. [15pts]
2
