代做Math 164: Optimization Assignment 1 Spring 2024

Math 164: Optimization

Assignment 1

Spring 2024

1.  Suppose A ∈ Rn ×n is an invertible matrix.  Show that AT A is positive definite.

2. Consider f : R2 → R given by f(x1 , x2 ) = 2x1 x2 − x1(2) − x2(2).  Compute the Hessian ∇2 f(x) and conclude if f is a convex function.

3.  Show that a function f : Ω ⊆ Rn  → R ∈ C1  is convex iff

f(z) ≥ f(x) + ∇f(x)T (z − x)   ∀x,z ∈ Ω .

4. Consider the function f(x) = xTAx where A ∈ Rn ×n. Find ∇f(x). What is ∇f(x), if A is symmetric? Note.  Do  not  use  a pre-derived formula  and show  all your work.

5.  Consider the Euclidean ball B = {x : x1(2)  + x2(2) ≤ 1}.  Find all feasible directions d  at x = (0, 0) and y = (1, 0). Justify your work.

Suggested problems (not for submission)

1.  Show that the intersection of two convex sets is convex.

2. Let C ⊂ R2  be the triangle with vertices (0, 0), (a,0), and (0, a), where a > 0.  Prove C is convex.

3.  Consider the following problem:

minimize ∥Ax − b∥2(2)

s.t.       x1 + ··· + xn  = 1

x1 , ··· , xn  ≥ 0

Here A ∈ Rm ×n  (m > n) and b ∈ Rm . Is the problem a convex optimization problem? If yes, provide a proof. If no, explain why not, giving complete explanations.

    4.  Show that a function f : Ω ⊆ Rn  → R  ∈ C2  is convex iff ∇2 f(x) is positive semidefinite for all x ∈ Ω .

5.  Let f  :  Rn   → R  be  a  convex function defined on a convex set Ω  ⊆ Rn.   Show a point is a global minimizer of f over Ω iff it is a local minimizer of f.

6. Let f : Rn  → R be a strictly convex function.  Show that f has at most one global minimizer.

7.  Let f  : Rn   → R  be a convex function defined on a convex set Ω ⊆ Rn.  Then, the set of all global minimizers of f over Ω is a convex set.