Math 164
Midterm Practice
1. Consider the problem
minimize f (x)
subject to x ∈ Ω
• The function f ∈ C2 is defined from R2 → R;
• The constraint set is Ω = {x = [x1 , x2]T : x1 ≥ 1, x2 ≥ 2}.
Consider the point x* = [1, 2]T :
• The gradient of f at x* is ▽f (x* ) = [1, 0]T ;
• The Hessian of f at x* is F .
Given all the information above, is x* definitely a local minimizer, definitely not a local minimizer, or possibly a local minimizer? Justify your work.
2. Consider the problem of minimizing f (x) = 1 0 0 -1 on R. Note that 0 is the global minimizer of f.
(a) Write down the algorithm for Newton’s method applied to this problem.
(b) Show that as long as the starting point is not 0, the algorithm in part a does not converge to 0.
3. Given a fixed set of known points {x(1) , · · · , x(k)} where each point x(i) ∈ Rn , consider the function f : Rn → R defined as:
f(x) = 1 k k X i=1 ∥x − x (i) ∥ 2
Recall useful property ⅡuⅡ2 := uTu for u ∈ Rn.
(a) Show that f is quadratic in the form. f(x) = 1 2x T Qx − bTx + c. Identify Q ∈ Rn ×n , b ∈ Rn , and c ∈ R in that form.
(b) Compute the gradient ▽f (x) and the Hessian F (x) of f.
(c) Find the point(s) that statisfy the FONC.
(d) Use the SOSC to find a strict local minimizer of f.
(e) Is the point from part (d) a strict global minimizer?
4. Given f : Rn → R, consider the general iterative algorithm
x(k+1) = x(k) + αk d(k);
where d(1) , d(2) , · · · are given vectors in Rn and αk is chosen to minimize f (x(k) + αk d(k)). Show that for each k, the vector x(k+1) − x(k) is orthogonal to ▽f (x(k+1)) (assuming that the gradient exists).