APM 462 Nonlinear Optimization Summer 2025
Assignment 1
Due date: May 24, 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) and DS abbreviates Durea and Stru-
gariu (An Introduction to Nonlinear Optimization Theory 2014).
TUT 1 (LY 7.9 3.) Let f(x, y, z) = 2x2 + xy + y2 + yx + z2 − 6x − 7y − 8z + 9 and Ω = R3
and consider the problem
min f(x, y, z)
s.t. (x, y, z) ∈ Ω
(a) Use the FONC to find all candidates for minimizers.
(b) Use the SONC to find all candidates for minimizers.
(c) Use the SOSC to find all local minimizers.
(d) Show that the local minimizer you found is a global minimizer.
TUT 2 (LY 7.9 7.) Let fi : Ω → R be a family of convex functions defined on a convex set
Ω ⊂ Rn for i ∈ I (where I is some index set). Show that the function
f : Ω→ R ∪ {+∞} defined by
f(x) := sup
i∈I
f(x)
is convex in the region where it is finite.
TUT 3 (LY 7.9 8.) Let g : R→ R be a non-decreasing function that is convex and let f : Ω ⊂
Rn → R be a convex function on a convex set Ω. Show that the function
h : Ω→ R given through
h(x) = g(f(x))
is convex on Ω.
TUT 4 (DS 7 7.7) Let a, b ∈ R with a < b and f ∈ C1(R) such that f ′(a)·f ′(b) < 0. Consider
f¯ : [a, b]→ R given through f¯(x) = f(x). Show that f¯ admits a minimum
on (a, b).
TUT 5 (DS 7 7.9) Show that f : (1,∞)→ R given through f(x) = − ln ( ln(x)) is convex.
1
TUT 6 (DS 7 7.9) Show that a convex bounded function is constant.
TUT 7 (H 3.8 23) Consider the problem
min f(x1, x2)
s.t. (x1, x2) ∈ Ω
with f(x1, x2) = x1x2 and
Ω =
{
(x1, x2) ∈ R2 : 2x1 + x2 ≥ 6, x1 ≥ 1, x2 ≥ 1
}
.
(a) Prove that this problem admits a global minimizer.
(b) Graph Ω and the level sets of f and find the minimizer(s) of f on Ω
graphically.
2
HW 1 (LY 7.9 1.) To approximate a given function g : [0, 1]→ R by a polynomial
p(x) = anx
n + an−1xn−1 + · · ·+ a1x+ a0
of degree n or less with real coefficients, we need to find coefficents a0, a1, . . . , an−1, an
such that the function
f(a0, a1, . . . , an) =
1
2
∫ 1
0
(
g(x)− p(x))2dx
is minimal.
(a) Write this problem as (unconstrained) optimization problem in the
form
min f(x)
s.t. x ∈ Ω
(b) Compute the FONC for the minimizer for the problem found in (a)
(no need to compute this minimizer explictly).
(c) Compute (and simplify) the Hessian for the function f found in (a).
(d) In the case that n = 1, is ∇2f positive definite?
HW 2 (LY 7.9 16.) Let f : Rn → R be convex and continuous. Define a new function φ :
Rn+1 → R by
φ(x1, x2, . . . , xn, xn+1) := xn+1f
( x1
xn+1
,
x2
xn+1
, . . . ,
xn
xn+1
)
.
We define φ(x1, . . . , xn, 0) := 0.
(a) Prove that for λ ∈ R and x ∈ Rn+1 we get
φ(λx) = λφ(x).
(b) Prove that φ is a convex and continuous function.
(c) Compute ∇φ and ∇2φ in terms ∇f and ∇2f .
HW 3 (LY 7.9 17.) Let A ∈ Rm×n, 0 ̸= b ∈ Rm and µ > 0. Consider the regression problem
with regularization term
min f(x)
s.t. x ∈ Ω
where Ω = Rn and
f(x) = |Ax− b|2 + µ|x|2.
(a) Prove that f is convex.
3
(b) Write down and simplify the FONC.
(c) Write down the SONC and the SOSC. Are those conditions fulfilled?
HW 4 Consider the problem
min f(x)
s.t. x ∈ Ω
where Ω = Rn and where f : Rn → R is given through
f(x) =
1
2
xTQx+ bTx+ c
where Q ∈ Rn×n is positive definite, b ∈ Rn and c ∈ R. Find a minimizer
for this problem and prove that it is the global minimizer for f over Ω.
HW 5 (H 3.8 22) Consider the problem
min f(x1, x2)
s.t. (x1, x2) ∈ Ω
where
f(x1, x2) = 2x
2
1 + x
2
2 − 2x1x2 − 6x1 + 1
and
Ω =
{
(x1, x2) ∈ R2 : 3 ≤ x1 ≤ 6, 0 ≤ x2 ≤ 6
}
.
(a) Show that f is convex.
(b) Using the FONC, find the candidate minimizer(s) of f on Ω.
(c) Prove that the candidate you found in (b) is a global minimizer of f
on Ω.
HW 6 Consider the problem
min f(x1, x2)
s.t. (x1, x2) ∈ Ω
where
f(x1, x2) = x
2
1 − x2
and
Ω =
{
(x1, x2) ∈ R2 : x2 ≥ 1− x1
}
.
(a) Is f convex?
(b) Using the FONC, find the candidate minimizer(s) of f on Ω.
(c) Prove that the candidate you found in (b) is a global minimizer of f
on Ω.
4

学霸联盟