Please typeset or write your solutions neatly! If we cannot read it, we cannot grade it.
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 ∇f(x) = 0) that is neither a local minimum nor a local maximum. List all stationary points of the following functions, where x , and for each stationary point indicate whether it is a local minimum/maximum, a global minimum/maximum, or a saddle point.
; [5pts]
; [5pts]
. [5pts]
Q 3. Let A be a real symmetric n × n matrix with eigenvalues λ1 ≤ λ2 ≤ ··· ≤ λn. Prove that, ∀x ∈ Rn :
; [5pts]
. [5pts]
Q 4. Let f : Rn → R ∪ {−∞,+∞} be an extended real valued convex function. Assume that f is such that for all x,y ∈ Rn, 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 +∞ everywhere. [5pts]
(ii) If, ∀x ∈ Rn, f(x) ≤ M, for some constant M < ∞, then f must be a constant function (i.e., taking the same value for all x ∈ Rn). [5pts]
Q 5 (Jensen’s Inequality). Let f : Rn → R be a convex function. Prove that for any sequence of numbers x1,x2,...,xk ∈ Rn and any sequence of non-negative scalars α1,α2,...,αk ≥ 0 such that we have:
. [8pts]
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 ∀x,y ∈ Rn :
f(y) ≥ f(x) + h∇f(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
,
that is, the Hessian of f is positive semidefinite. [10pts]
1
Q 8. Let f(x) := xTAx − bTx, 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 −1
0
A = 0
...
−1 −1
2
−1
0
...
0 0
−1
2 −1
...
0 0 0
−1
2
...
0 ...
...
...
... ... ... 0
0
0
0
...
−1 −1
0
0 0 .
...
2
Is f convex? Justify your answer. [15pts]
Q 9. Let f : Rn → R be a continuously differentiable function that satisfies the following:
,
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: {x ∈ Rn : kxk2 ≤ 1})? Explain. [15pts]
2
