APM 462 Nonlinear Optimization Summer 2025 Assignment 4 Due date: July 12, 2025; 11.59 pm Problems named TUT are for discussion during the tutorials. Problems named HW are to be handed in on Crowdmark until the due date. Only selected HW problems will be graded. LY abbreviates Luenberger and Ye, H abbreviates Hendrix (Introduction to Nonlinear and Global Optimization 2010), vB abbreviates van Brunt, BV ab- breviates Boyd and Vandenberghe (Convex Optimization 2009). TUT 1 (H 3.8 23) This is TUT 1 from Assignment 2. Consider the problem min f(x1, x2) = x1x2 s.t. g1(x1, x2) = 2x1 + x2 − 6 ≥ 0 g2(x1, x2) = x1 − 6 ≥ 0 g3(x1, x2) = x2 − 1 ≥ 0 (a) Find the dual function of this problem and compute it explictly. (b) Solve the dual problem. (c) Does strong duality hold? TUT 2 (LY 11.10 21) Consider the problem min f(x) s.t. h(x) = 0 g(x) ≥ 0 where x ∈ Rn, f : Rn → R is convex, h ∈ C1(Rn,Rm), g ∈ C1(Rn,Rp) and where gj : Rn → R is concave for j = 1, . . . , p. Show that the dual problem of the dual problem is in some sense the original problem. TUT 3 (BV 5.21) Consider the problem min f(x) (1) s.t. h(x) = 0 g(x) ≥ 0 x ∈ Ω 1 where Ω ⊆ Rn is a convex set. We define the dual function to (1) as ϕ : { Rm × Rp≥0 → R (λ, µ) 7→ infx∈Ω { f(x)− λTh(x)− µT g(x)} (note that this is the same definition as given in the lectures, just that we restrict x to Ω). Consider the problem min f(x, y) = e−x s.t. g(x, y) = −x 2 y ≥ 0 (x, y) ∈ Ω = {(x, y) ∈ R2 : y > 0} Note that f is convex and g is concave (proved in HW 2 on Assignment 1). (a) Show that a global minimum of this problem is given through (x0, y0) = (0, 1) with f0 = 1. (b) Find and compute the dual function for this problem. (c) Find the solution to the dual problem and show that strong duality does not hold. (d) What assumption of the strong duality theorem does not hold (this question is not related to Ω)? TUT 4 (LY 8.10 17.) This is TUT 3 from Assignment 2. Consider the problem min f(x, y) = x2 + y2 + xy − 3x s.t. g1(x, y) = x ≥ 0 g2(x, y) = y ≥ 0 (a) Find the dual function to this problem. (b) Solve the dual problem. (c) Does strong duality hold? Why? TUT 5 (vB 2.2 4.) Consider the problem (for X = C2([0, 1])) min J(y) = ∫ 1 0 (y′)2 + y2 + 4yex dx s.t. y ∈ S = {y ∈ X : y(0) = 0, y(1) = 1}. (a) Find all extremals for J that are in X. (b) Which extremal is a solution (i.e. global minimum) to the above problem? 2 TUT 6 (vB 3.2. 1.) For X = C2([t0, t1],R2), consider the functional J(q) = ∫ t1 t0 L(t, q, q˙) dt where L(t, q, q˙) = 1 2 (q˙21 + q˙ 2 2)− gq2 with g constant. (a) Find the extremals for J . (b) Verify that if y is an extremal for J then the quantity H = 2∑ k=1 q˙k ∂L ∂q˙k − L is constant. 3 HW 1 (LY 11.10 20.) This is TUT 7 from Assignment 3. Consider the (linear programming) problem min f(x) = cTx s.t. h(x) = Ax− b = 0 g(x) = x ≥ 0 where x ∈ Rn, c ∈ Rn, A ∈ Rm×n and b ∈ Rm for m ≤ n. (a) Find the dual function for the above problem and compute it explic- itly. (b) Solve the dual problem. HW 2 (LY 14.8 1.) Consider the following problem min f(x, y) = xy s.t. g(x, y) = x+ y − 4 ≥ 0 (x, y) ∈ Ω = {(x, y) ∈ R2 : 1 ≤ x ≤ 5, 1 ≤ y ≤ 5} (see TUT 3 for the definition of dual function for problems with Ω). (a) Show that f is not convex. (b) Compute the dual function explicitly. (c) Show that the dual function is concave. (d) Solve the dual problem. (e) Does strong duality hold? Why or why not? HW 3 (vB 2.2 2.) Let X be a function space on [x0, x1], S ⊆ X, x0 < x1 and define the functionals Ji : { X → R y 7→ Ji(y) = ∫ x1 x0 fi(x, y, y ′) dx where fi ∈ C2([x0, x1]× R× R) for i = 1, 2. (a) Show that for all A,B ∈ R and for all y ∈ S and η ∈ H we have δ(AJ1 +BJ2)(η, y) = AδJ1(η, y) +BδJ2(η, y). (b) Show that for all y ∈ S and η ∈ H we have δ(J1J2)(η, y) = J1(η, y)δJ2(η, y) + δJ1(η, y)J2(η, y). (c) Assume that g : R × R → R is a differentiable function. Show that for all y ∈ S, η ∈ H we have δg(J1, J2)(η, y) = ∂1g(J1, J2)(η, y)δJ1(η, y) + ∂2g(J1, J2)(η, y)δJ2(η, y). 4 HW 4 (vB 2.2. 5.) Consider the problem (with X = C2([−1, 1])) min J(y) = ∫ 1 −1 x4(y′)2 dx s.t. y ∈ S = {y ∈ X : y(−1) = −1, y(1) = 1} (a) Show that no extremals in X exist that are in S. (b) Without resorting to the Euler-Lagrange equation, prove that the above problem can not admit a local minimum in S. HW 5 (vB 2.3 1.) Consider the functional J(y) = ∫ x1 x0 f(x) √ 1 + (y′)2 dx where 0 < x0 < x1 and f(x) is a function that is sufficiently smooth. (a) Find the general solution for the Euler-Lagrange equation of J . (b) Find the general solution for the Euler-Lagrange equation of J if f(x) = √ x. (c) Find the general solution for the Euler-Lagrange equation of J if f(x) = x. HW 6 (vB 3.1. 5.) Define the functionals J(y) = ∫ x1 x0 f(x, y, y′, y′′) dx and K(y) = ∫ x1 x0 F (x, y, y′, y′′) dx where F (x, y, y′, y′′) = f(x, y, y′, y′′) + d dx G(x, y, y′) for G sufficiently smooth. Prove that any extremal for J must also be an extremal for K. 5 51作业君版权所有