APM462

APM462 Midterm Project1 APM462 Midterm Project1 Due: Sat Mar 11 (before 9pm) on Crowdmark (1) Conside the convex set C := {(x,y) ∈ R2 | x2+y2 ≤ 1 and x,y ≥ 0}, the unit disc intersect the first quadrant, and let δC (x, y) be its indi- cator function. Find ∂δC(x0,y0) where (x0,y0) is a boundary point of C. Hint: Draw a picture. There should be 6 cases to consider. NotethatC=C1∩C2∩C3 whereC1 ={(x,y)∈R2 |x2+y2 ≤1}, C2 ={(x,y)∈R2 |−x≤0},andC3 ={(x,y)∈R2 |−y≤0}. (2) LetF(x,y)=f(x)+g(y)wheref,g:R1 →R. (a) Prove that ∂F(x0,y0) = ∂f(x0)×∂g(y0). Recall that the prod- uct of two sets A × B = {(a, b) | a ∈ A, b ∈ B}. (b) Use the formula in part (a) to compute ∂F(x0,y0) for the func- tion F (x, y) = |x| + y2. (3) Consider the following optimization problem: minimize: f (x, y) = 21 (x − 2)2 + 21 (y − 3)2 subjectto: g1(x,y)=x≤1 g2(x,y) = y ≤ 1 (a) Draw a diagram in R2 of the feasible set and the level sets of f. Then solve the problem graphically. (b) Use the 1st order necessary Kuhn-Tucker conditions to find the candidate(s) for minimizer(s). (c) Check whether the candidates you found in part (b) satisfy the 2nd order necessary condition for minimizer. (d) Check whether the candidates you found in part (b) satisfy the 2nd order sufficient condition for minimizer. (4) Consider the following optimization problem: minimize: f (x, y) = 12 (x − 2)2 + 21 (y − 3)2 subject to: g(x, y) = max{|x|, |y|} ≤ 1 (a) Draw a diagram in R2 of the feasible set g ≤ 1 and the level sets of f. Then solve the problem graphically. (b) Find ∂f(x,y) and ∂g(x,y). Note: for ∂g(x,y) there are nine cases to consider. (c) Solve the minimization problem using subdifferentials. Hint: does you solution to part (c) agree with your graphical solution in part (a)? 1Copyright ⃝c 2023 J. Korman. Sharing or selling this material without permission of author is a copyright violation. 1 2 (5) Solve the following convex minimization problem using subdifferen- tials where f(x,y) = max{|x|,y + 12} and b > 0: minimize: f(x,y) subject to: g1(x, y) = x2 + y2 − 1 ≤ 0, g2(x, y) = |x| + y − b ≤ 0. Hint: the answer should depend on the parameter b. (6) Consider the following convex minimization problem where g(x, y) = |x| + y − 1: minimize: f(x,y)=(x−3)2 +(y−1)2 subject to: (x,y) ∈ C := {g(x,y) ≤ 0} (a) Solve this problem using subdifferentials. (b) Convert this problem into an equivalent problem of inequality constraints and use the Kuhn-Tucker conditions to find candi- dates for minimizer(s). Hint: get rid of of the abslute value in the inequality g(x, y) ≤ 0 by replacing the inequality with two inequalities. (7) Let a ∈ R be a number and consider the optimization problem: min f (x, y) = x + ay subjectto: g(x,y)=y−|x|≥0 Note that {g = 0} is a cone with vertex at the origin. Also note that g is not diffferentiable at the origin. (a) Solve this problem using subdifferentials. Hint: after you draw a picture the solution should be pretty clear. Once you know what the solution should be, you will know what to aim for. Note that there are two cases to consider depending on the value of a. (b) Find all the regular points of the set {g ≥ 0}. (c) Use the 1st order Kuhn-Tucker neccessary conditions for a local min to find the candidate(s) for minimizer(s) and then solve the optimization problem. Hint: as in question (6) you should first replace the constraint g ≥ 0 with two other constraints so as to get rid of the absolute value.