APM 462 Nonlinear Optimization Summer 2025
Assignment 3
Due date: June 21, 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 and H abbreviates Hendrix (Introduction to
Nonlinear and Global Optimization 2010).
TUT 1 (H 3.8 23) This is TUT 7 from Assignment 1. Solve it using Lagrange multipliers.
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
Use the FONC to find all candidates for minimizers.
TUT 2 (H 3.8 22) This is HW 5 from Assignment 1. Solve it using Lagrange multipliers.
Consider the problem
min f(x1, x2) = 2x
2
1 + x
2
2 − 2x1x2 − 6x1 + 1
s.t. g1(x1, x2) = x1 − 3 ≥ 0
g2(x1, x2) = 6− x1 ≥ 0
g3(x1, x2) = x2 ≥ 0
g4(x1, x2) = 6− x2 ≥ 0
Recall that f is convex. Using the FONC, find the global minimizer of f
subject to the constraints.
TUT 3 This is HW 6 from Assignment 1. Solve it using Lagrange multipliers.
Consider the problem
min f(x1, x2) = x
2
1 − x2
s.t. g(x1, x2) = 1− x1 − x2 ≥ 0
Use the FONC, SONC and SOSC to find the minimizer of f subject to
the constraint.
1
TUT 4 (LY 8.10 17.) This is TUT 3 from Assignment 2. Solve it using Lagrange multipliers.
Consider the problem
min f(x, y) = x2 + y2 + xy − 3x
s.t. g1(x, y) = x ≥ 0
g2(x, y) = y ≥ 0
Using the FONC, SONC and SOSC find all minimizers of f subject to the
constraints.
TUT 5 (LY 11.10 1.) In R2, consider the problem
min f(x, y)
s.t. g1(x, y) = x ≥ 0
g2(x, y) = y ≥ 0
g3(x, y) = (x− 1)2 − y ≥ 0
Show that the point (x, y) = (1, 0) is a feasible point but that it is not a
regular point.
TUT 6 (LY 11.10 13.) In R2, consider the problem
max f(x, y) = 14x− x2 + 6y − y2 + 7
s.t. g1(x, y) = 2− x− y ≥ 0
g2(x, y) = 3− x− 2y ≥ 0
(a) Which feasible points are regular?
(b) Using the FONC, find candidate maximizers for this problem.
(c) Using the SONC and the SOSC, find all maximizers for this problem.
TUT 7 (LY 11.10 20.) Consider the 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) Which feasible points are regular?
(b) Using the FONC, find candidate minimizers for this problem.
(c) Using the SONC and the SOSC, find the minimizers for this problem.
2
HW 1 (LY 11.10 2.) Consider the following problem: Find the rectangle with a given perimeter,
that has the greatest area.
(a) Write this problem as constrained optimization problem.
(b) Which feasible points are regular?
(c) Solve the FONC to find all candidate maximizers.
(d) Which one of the points you found in (a) satisfy the SONC?
(e) Use the SOSC to solve the problem.
HW 2 (LY 11.10 10.) A young egoistic person has inherited a fortune of amount F . Now they
are planning how they should spend their money during the rest of their
life so that it maximizes their total enjoyment during their lifetime. They
assume that they still have N years to live (starting at year 0).
They consider the function
x :
{
{0, 1, 2, . . . , N + 1} → R≥0
t 7→ x(t)
where x(t) denotes the wealth of the young person at the beginning of
year t and the function
u :
{
{0, 1, 2, . . . , N} → R≥0
t 7→ u(t)
where u(t) denotes the total amount of money the person spents in year
t. Hence, x(0) = F holds and because the person wants to spent all of the
inheritance during their lifetime, x(N + 1) = 0 holds.
If at the beginning of year t (for t = 0, 1, 2, . . . , N) their capital is x(t),
then at the beginning of year t+ 1, their capital is given through
x(t+ 1) = αx(t)− u(t)
where α ≥ 1 is fixed.
The enjoyment of the person is given through a smooth function ψ :
R≥0 → R≥0 where ψ(u(t)) denotes the total enjoyment the person gets in
year t by spending u(t).
The total enjoyment of the person over their lifetime is given through
N∑
t=0
ψ(u(t))βt
where 0 < β < 1.
(a) Write the problem described as an optimization problem. Hint: De-
fine the vectors x = (x0, . . . , xN+1) := (x(0), . . . , x(N + 1)) ∈ RN+2
and u = (u0, . . . , uN ) := (u(0), . . . , u(N)) ∈ RN+1.
3
(b) Compute the FONC for this problem.
(c) For the special case ψ(u) =
√
u, find the optimal x and the optimal
u for the problem, using the FONC from (b).
HW 3 (LY 11.10 12.) Consider the problem
min f(x) =
1
2
xTQx− bTx
s.t. h(x) = Ax− c = 0
where x ∈ Rn, A ∈ Rm×n, c ∈ Rm (for m ≤ n), b ∈ Rn and Q ∈ Rn×n.
Here, we do not assume that Q is symmetric or that it is positive (semi-)
definite.
(a) What do we need to assume for A so that all feasible points are
regular?
(b) Compute the FONC (assuming that all points are regular).
(c) Compute the SONC and the SOSC (assuming all points are regular).
(d) Solve the problem, assuming m = n and that A is invertible.
HW 4 (LY 11.10 16.) Consider the problem in R2
min f(x, y) = (x− 1)2 + y2
s.t. g(x, y) = −x+ κy2 ≥ 0
where κ > 0 is a parameter.
(a) Which feasible points are regular?
(b) For which values of κ is (x, y) = (0, 0) a solution to the FONC con-
ditions?
(c) For which values of κ is (x, y) = (0, 0) a solution to the SONC con-
ditions?
(d) For which values of κ is (x, y) = (0, 0) a solution to the SOSC condi-
tions?
HW 5 (H 3.8 1.) Consider the problem in R2
min f(x, y) = (x− 3)2 + (y − 2)2
s.t. g1(x, y) = 3 + y − x2 ≥ 0
g2(x, y) = 1− y ≥ 0
g3(x, y) = x ≥ 0
Find all local minimizers of this problem using Lagrange multipliers. Which
local minimizers are also global minimizers?
4
HW 6 (H 3.8 14.) Consider the problem in R2
min f(x, y) = (x− 3)2 + (y − 2)2
s.t. g1(x, y) = 5− y2 − x2 ≥ 0
g2(x, y) = 4− x− 2y ≥ 0
g3(x, y) = x ≥ 0
g4(x, y) = y ≥ 0
(a) Find the minimizer to the above problem graphically.
(b) Show that the minimizer you found in (a) fulfills the KKT conditions
(FONC).
(c) What happens if we consider the problem
min f(x, y) = (x− 3)2 + (y − 2)2
s.t. g1(x, y) = 5− y2 − x2 ≥ 0
g2(x, y) = 10− x− 2y ≥ 0
g3(x, y) = x ≥ 0
g4(x, y) = y ≥ 0
instead?
5

学霸联盟