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

学霸联盟