## tutorial5

Previewing page
*1*
of
actual document.

**View the full content.**View Full Document

## tutorial5

0 0 35 views

- Pages:
- 4
- School:
- Washington University in St. Louis
- Course:
- Ese 415 - Optimization

**Unformatted text preview:**

ESE 415 U S Kamilov Tutorial session 2 23 2018 TA Hesam Mazidi Problem 1 Show that the Vandermonde matrix 4 x A x3 x2 x3 x2 x x2 x 1 1 is positive semidefinite PSD but not positive definite PD Solution 1 We note that A is PSD if and only if for any y y1 y2 y3 T we have y T Ay 0 Further A is PD if and only if for any y y1 y2 y3 T 6 0 0 0 T we have y T Ay 0 Notice that for any y y1 y2 y3 T y T Ay y1 x2 y2 x y3 2 2 Thus it immediately follows that A is PSD Now assume y y1 y2 y3 T 6 0 0 0 T In this case we can always find a vector y1 y2 y3 T such that y1 x2 y2 x y3 0 In particular 2 x x2 satisfies this condition concluding that A is not PD as desired Problem2 In each of the following problems fully justify your answer using optimality conditions i Show that f x y x2 4 2 y 2 has two global minima and one stationary point which is neither a local maximum nor a local minimum ii Find all local minima and all local maxima of f x y sin x sin y sin x y within the set 0 x 2 0 y 2 Page 1 of 4 ESE 415 U S Kamilov Tutorial session 2 23 2018 TA Hesam Mazidi Solution 2 i Note that f is a differentiable function with domain R2 This means that any stationary point x y T local maximum global maximum etc must satisfy f x y T 0 That is 2 x 2 4 2x 4 x 3 4x f 0 3 2y 2y The stationary points are easily obtained form eq 3 as x y T 0 0 T 2 0 T or 2 0 T Since f is twice differentiable we can invoke sufficient second order optimality conditions In particular denote H x y T as the Hessian of f obtained at x y T Then if H x y T is positive definite it follows that x y T is a local maximum if H x y T is negative definite x y T is a local minimum H x y T 4 3x 2 4 0 0 2 4 We therefore have the following characterizations 2 0 T is a local minimum since H 2 0 T is positive definite 2 0 T is a local minimum since H 2 0 T is positive definite Note that H 0 0 T is indefinite that is it is neither positive semidefinite nor negative semidefinite By invoking the necessary second order optimality conditions which state that if a stationary point x y T is a local minimum local maximum then H x y T is positive semidefinite negative semidefinite we conclude that 0 0 T is only a stationary point ii We approach this problem similar to i cos x cos x y f 0 cos y cos x y 5 Therefore the stationary points x y T are T 3 3 T and 5 3 5 3 T We proceed by checking the Hessian of f at stationary points sin x sin x y sin x y H x y T 6 sin x y sin y sin x y Clearly H 3 3 T is negative definite while H 5 3 5 3 T is positive definite That is 3 3 T is a local maximum and 5 3 5 3 T is a local minimum We note that H T 0 This means that we cannot determine whether T is a local maximum or local minimum from the necessary and sufficient second order optimality conditions One way to tackle this problem is to check the behavior of the function around the stationary point T by using the Taylor approximation f x y f sin x sin y sin x y 0 sin x sin y sin x y 2 use trigonometric identities sin x sin y sin x y 1 1 1 x 3 y 3 x y 3 3 3 3 o x 3 y 3 By examining f x y f along x y using above approximation we see that T cannot be a local maximum or a local minimum Thus T is only a stationary point Page 2 of 4 ESE 415 U S Kamilov Tutorial session 2 23 2018 TA Hesam Mazidi Problem 3 Show that the Newton method is affine invariant that is Given f and a non singular matrix A applying the Newton method for function g y f Ay would not affect the iterative progression toward the optimal point assuming it exists Solution 3 Define x Ay for all y Rn that is x is a affine transformation of y We first note that we have a one to one mapping from x to y since we can set x Ay and y A 1 x The Newton updates for g are given by y k 1 y k 2 g y k 1 g y k k T k 1 2 1 k y A f Ay A 7 T k A f Ay 8 k f Ay 9 y k 1 y k A 1 2 f xk 1 f xk 10 y A 2 k 1 f Ay Note that we can re write eq 10 as Therefore we have y k 1 y k A 1 2 f xk 1 f xk A y k 1 k 2 k y f x x k 1 1 k f x k x 11 12 13 This means that the progression iterates y k 1 y k k 0 have a one to one mapping with xk 1 xk k 0 In particular the rate of convergence is unaffected for any non singular affine transformation of variables is this true for the gradient descent method Problem 4 In this section we explore basics results concerning strong convexity A differentiable function f is said to be strongly convex with constant M 0 if f y f x f x T y x M kx yk2 2 Show that i g x f x M 2 2 kxk is convex ii f x f y T x y M kx yk2 x y Page 3 of 4 x y in domain of f 14 ESE 415 U S Kamilov Tutorial session 2 23 2018 TA Hesam Mazidi Solution 4 i Note that g is convex if and only if g y g x g x T y x x y Therefore we exploit the strong convexity of f to establish the convexity of g First we have g x f x M x g x T y x f x T y x M xT y M kxk2 15 using eq 14 we get the desired result ii To establish this inequality we need a property of convex functions Specifically h is a convex function then if and only if h x h y T …

View Full Document