APM462: Homework 5 Comprehensive assignment for first term 1 Due: Sat Feb 27 (before 9pm) on Crowdmark. (1) Recall that in lecture I proved that at a regular point p, TpM ⊆ Tp and then said that equality follows from the Implicit Function Theorem. In this problem you are asked to prove Tp ⊆ TpM in a special case. Let f : Rn → R be a C1 function. Recall from HW4 that the graph of f is the surface M := {(x, f(x)) ∈ Rn × R | x ∈ Rn} in Rn × R. (a) Let p := (x0, f(x0)) ∈M . Find the space Tp. (b) Show that Tp ⊆ TpM . That is show that any vector in the space Tp is a tangent vector to M at p. Note: unlike the case on HW4 Q7, here you are not allowed to assume that Tp = TpM . (2) Let f : R3 → R, and g : R2 → R1 be C1 functions. Use Lagrange multipliers (1st order conditions) to show that first constrained op- timization problem and the second unconstrained problem have the same candidates for minimizers: min f(x, y, z) subject to h(x, y, z) = z − g(x, y) = 0 (x, y, z) ∈ R3, and min f(x, y, g(x, y)) (x, y) ∈ R2. Note: the first problem involves the variables x, y, z while the sec- ond one only x, y. (3) This question explores a surprising relationship called “linear programming duality” be- tween two related linear problems. If you took APM236 you would have seen duality there. Here we will prove duality using the Kuhn-Tucker conditions. Let A be an m × n matrix, b ∈ Rm, and c ∈ Rn. Consider the following two optimization problems, the “primal problem”: 1Copyright c©2021 J. Korman. Sharing this material publically is not allowed without permission of author. 1 2max cTx subject to Ax ≤ b x ≥ 0, and the “dual problem”: min bT p subject to AT p ≥ c p ≥ 0. Let x∗ be an primal optimal solution and p∗ be an optimal dual solution. (a) Write the Kuhn-Tucker (1st order neccessary) conditions for x∗. Hint: use Lagrange multipliers p∗ (for the Ax ≤ b constraints) and µ (for the x ≥ 0 constraints). (b) Show that the Lagrange mutipliers p∗ for the optimal primal x∗ satisfy the constraints of the dual problem. (c) Use the comlementary slackness conditions for the primal prob- lem to show that (p∗)TAx∗ = pT∗ b. (d) Write the Kuhn-Tucker (1st order neccessary) conditions for p∗. Hint: use Lagrange multipliers x∗ (for the AT p ≥ c constraints) and ν (for the p ≥ 0 constraints). (e) Show that the Lagrange mutipliers x∗ for the optimal dual p∗ satisfy the constraints of the primal problem. (f) Use the comlementary slackness conditions for the dual problem to show that cTx∗ = (p∗)TAx∗. (4) Let Q be a 2× 2 positive definite symmetric matrix. Let f ∈ C2 be an increasing, non-negative, and convex function on R1. Let F (s) denote the area of the sublevel sets {xTQx ≤ f(s)2}: F (s) = area {x ∈ R2 | xTQx ≤ f(s)2}. Prove that F is convex. (5) Let R > 0 and assume the following problem has a solution: min f(x, y, z) subject to x2 + y2 − z2 ≤ R2. 3Note that the Kuhn-Tucker conditions (*) are: ∇f(x, y, z) + µ 2x2y −2z = 00 0 µ(x2 + y2 − z2 −R2) = 0, µ ≥ 0. (a) Write the Kuhn-Tucker conditions for the following problem using Lagrange multipliers µ1 and µ2: min f(r √ R2 + z2 cos θ, r √ R2 + z2 sin θ, z) subject to r − 1 ≤ 0 −r ≤ 0 z, θ ∈ R1 (b) Show that the conditions you found in part (a) imply the Kuhn- Tucker conditions (*). Start by expressing µ in terms of µ1 and µ2. There should be three cases to consider: when r = 0, 0 < r < 1, and r = 1. (6) Consider the following optimization problem where f, h are C1 func- tions on Rn: min f(x) x ∈ Rn subject to h(x) = 0. Suppose p is a regular point of the constraint h. Prove that TpM = Tp. Hint: HW4 Q.7 and the implicit function theorem.
欢迎咨询51作业君