MIT 6.7220/15.084 — Nonlinear Optimization Tue, Feb 6th 2024
Lecture 1
Introduction
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful for any
reports of typos.
1 Mathematical optimization, and this course
One cannot overstate how pervasive and far reaching mathematical optimization theory is. Opti-
mization is everywhere. This is true in two senses:
• Most of human endeavors and designs have an optimal aspiration in mind—–minimize risk,
maximize reward, reduce energy consumption, train a neural network to minimize model loss,
et cetera.
• Nature’s phenomena themselves seem to be guided by optimization—–the principle of least
action, Hamiltonian mechanics, the Rayleigh-Ritz variational principle (from which the
Schrödinger equation may be derived), et cetera.¹
¹See https://en.wikipedia.org/wiki/Variational_principle for a longer list.
But the benefits of an optimization mindset are also more subtle. For example, optimization in the
space of semidefinite matrices has led to important breakthroughs in classical combinatorial opti-
mization problems in graph theory, such as the Max-Cut problem [GW95]. Optimization theory
can also be used to show the funamental theorem of algebra, and amusingly Güler presents that on
page 34 (!) of his “Foundations of Optimization” book [Gül10], adapting some ideas by Terkelsen,
F. [Ter76] and Fefferman, C. [Fef67].
The literature on optimization dates back to (at least) the ancient Greeks, with their work on the
isoperimetric problem. The problem, which asks to construct the shape that maximizes the area
given a fixed perimeter, is at the center of the legend of how Carthage—one of the most powerful
empires of the classical world—was founded.² It was solved (to the standards of rigor of those times,
at least) by Zenodorus.³
²Dido was the legendary founder—and first queen—of Carthage, a Phoenician city-state that would then become
of the most powerful empires in the world, and will be destroyed by the Roman empire. As recounted by Blåsjö,
V. [Blå05], the legend says that “Dido, daughter of the king of Tyre, fled her home after her brother had killed
her husband”. She later “ended up on the north coast of Africa, where she bargained to buy as much land as she
could enclose with an oxhide. So she cut the hide into thin strips, and then she faced, and presumably solved, the
isoperimetric problem.”
³Approx 150BC, https://en.wikipedia.org/wiki/Zenodorus_(mathematician)
Fast forward to today, mathematical optimization is a vast field, subdivided into a myriad of sub-
fields depending on what types of optimization problems are being solved; here are just a few:
• Linear optimization refers to problems that seek to minimize or maximize linear objectives
subject to linear constraints imposed on continuous optimization variables.
• Integer linear optimization is akin linear optimization, but variables can be further restricted
to only taking integer values.
• Combinatorial optimization more generally studies optimization problems over finite sets.
• Convex optimization studies optimization of convex objectives on convex sets.
• Calculus of variations studies optimization problems in function spaces (that is, where the
optimal object that is sought is a function).
1.1 Focus and objectives of this course
This is a graduate-level course on nonlinear optimization. The main focus of this course is continu-
ous optimization in finite dimensional spaces. As such, nonlinear optimization encompasses a large
variety of topics and algorithms, with applications that range from semidefinite relaxations of com-
binatorial problems, to regression problems, to training of deep neural networks. I foresee that this
course attracts students from (at least) two very different categories:
• Some of you are interested in nonlinear optimization theory. Typically, you’re facing an opti-
mization problem that you hope to solve in closed form, so that you can plug in or reason
about the solution as part of a larger mathematical endeavor.
• Some of you are interested in nonlinear optimization algorithms. Typically, you are facing an
optimization problem for which you simply want a numerical solution.
In this course, the TAs and I have worked hard to cater to both of these categories of students.
1.2 Schedule and administrative details
Please see the syllabus available on Canvas for administrative details, contact information, home-
work and exam dates, and a tentative schedule of classes.
1.3 Prerequisites
This class is pretty light on prerequisites. Fundamentally, the only prerequisites are as follows:
• Linear algebra (18.06)
• Real analysis (18.100A/B/Q)
Beyond some basic mathematical concepts (continuity, vector spaces, some basic point-set topology),
we will try to keep this course as self-contained as possible. Always feel free to stop and ask me or
the TAs during class if there is something you are not familiar with!
A few homework problems will require some (simple!) coding. We recommend Python but you can
ask to switch to a different language of your choice—but please, ask the TAs before doing so. If you
have absolutely zero exposure to programming, that should not be a big issue, but please make sure
to talk to the TAs about it this week.
2 Optimization problems and some preliminary considerations
2.1 General form of a nonlinear optimization problem
In general, an optimization problem has the form
min
𝑥
s.t.
𝑓(𝑥)
𝑥 ∈ Ω
In terms of nomenclature:
• The function we are trying to minimize (or maximize), in this case 𝑓(𝑥), is called the objective
function.
• The entries of the vector 𝑥, are called optimization variables.
• The set Ω is called the feasible set or constraint set.
In particular, in this class we are interested in optimization problems that satisfy certain assump-
tions:
• First of all, we assume that Ω is a subset of some embedding finite Euclidean space 𝐸. Without
loss of generality, 𝐸 = ℝ𝑛.
• The objective function 𝑓(𝑥) is a continuous real-valued function. Very often, we also assume
it is differentiable.
• A category of problems we are paying attention to are those with functional constraints, that
is those in which the feasible set is defined as
Ω ≔ {𝑥 ∈ 𝐸 | 𝑔𝑖(𝑥) ≤ 0,
ℎ𝑗(𝑥) = 0,
𝑖 = 1, ..., 𝑟
𝑗 = 1, ..., 𝑚.}. (1)
When faced with an optimization problem, two questions are immediate:
• Does a solution exist?
• If yes, can we compute it?
We will look into some preliminary observations regarding these two questions in Sections 2.2 and 2.3,
respectively.
2.2 Existence of solutions: Weierstrass theorem
There are two reasons why an optimization problem might not attain a minimum:
• Ω is empty, that is, no feasible points exist at all; or
• for any candidate minimizer, there always exists another point that achieves a lower value, as
shown in the following two examples.
Example 2.1. Consider minimization of the the following two functions, both over their
domain:
𝑥
𝑦
−1 0 1
−12
−8
−4
4
8
12
𝑓(𝑥) = tan(𝑥)
Ω = (−𝜋
2 , 𝜋
2 )
𝑥
𝑦
−3 −2 −1 0 1 2 3
−8
−4
4
8
𝑓(𝑥) = −10 + 𝑒−𝑥
Ω = ℝ
In the plot on the left, the objective function is unbounded: values can be made arbitrarily
small. No minimizer exists.
In the plot on the right, the objective has a lower bound, but for any value of 𝑥, all the
values 𝑥′ > 𝑥 achieve a strictly smaller value than 𝑓(𝑥). Again, no minimizer exists.
So, assuming that the objective 𝑓 is continuous, when can we be certain that an optimizer exists?
If we inspect Example 2.1, we notice that both functions are continuous. In the first example, the
domain is open (the extrema ± 𝜋
2 are not in the domain) and bounded. In the second example, the
domain is unbounded and closed. This shows that, if there is any hope of establishing a general
result on existence of minimizers, such a result must require both closedness and boundedness. We
are in luck:
Theorem 2.1 (Weierstrass theorem). Let 𝑓 : Ω → ℝ be a continuous function defined on a non-
empty and compact (i.e., closed and bounded) set Ω. Then, there exists a minimizer 𝑥∗ ∈ Ω of
𝑓 on Ω, that is,
𝑓(𝑥∗) ≤ 𝑓 (𝑥) for all 𝑥 ∈ Ω.
A note on boundedness. Weierstrass theorem is a pretty universal tool that you can keep in your
toolbox for when you need to argue that an optimization problem has a solution. However, many
optimization problems do not start off with a bounded feasible set Ω. Consider the following example:
Example 2.2. Let 𝑦 ∈ ℝ𝑛 be a point, and 𝑆 ⊆ ℝ𝑛 be a closed but not necessarily bounded set.
Prove that there always exists a projection point
min
𝑥
s.t.
‖𝑥 − 𝑦‖
𝑥 ∈ 𝑆.
𝑆
𝑦
Solution . The idea is to show that we can safely restrict our attention to a compact subset of
the feasible set of the problem—in this case, 𝑆. By “safely”, we mean that the minimizer does
not change before and after making the modification.
In this case, this is simple: pick an arbitrary point 𝑧 ∈ 𝑆.
Then, we know that for sure, if a minimizer exists, it must
live in the intersection
Ω ≔ 𝑆 ∩ 𝔹‖𝑧−𝑦‖(𝑦)
between 𝑆 and the closed ball centered in 𝑦 of radius ‖𝑦 −
𝑧‖ (see the figure on the side). Now, Ω is nonempty (it
contains 𝑧), closed (since both 𝑆 and the ball are closed
and intersection preserves closedness) and bounded (since
the ball has finite radius). So, since the objective function
is continuous, we can invoke Weierstrass theorem and con-
clude the proof.
𝑆
𝑦
𝑧
Ω
□
More generally, we have the following:
Theorem 2.2 (Weierstrass theorem for compact sublevel sets). Let 𝑓 be a continuous function
defined on a set 𝑆. If 𝑓 has a nonempty and compact sublevel set, that is, there exists 𝛼 ∈ ℝ
such that
{𝑥 ∈ 𝑆 : 𝑓(𝑥) ≤ 𝛼}
is nonempty and bounded,4 then 𝑓 has a minimizing point in 𝑆.
4Closedness of the sublevel set is guaranteed by the continuity of 𝑓.
2.3 Nonlinear optimization is computationally hard
We now turn our attention to the second question: what is reasonable to expect in terms of compu-
tational efficiency in finding the solution?
Let me start with the good news: there are entire subclasses of nonlinear optimization problems that
are computationally tractable (most notably, convex optimization problems). As we will see, even
beyond these classes, usually it’s possible to at least guarantee some form of convergence to some
weaker, “local”, notion of optimality.
However, in general, finding minimizers of nonconvex problems is computationally intractable. This
means that we believe that there does not exist any algorithm that is able to solve all nonconvex
optimization problems. This is because we believe that linear integer programming is already in-
tractable, and nonconvex optimization captures known intractable problems such as Max-Cut,5
already under benign assumptions such as quadratic functional constraints and objective.
5NP-completeness of Max-Cut was shown by Garey, M. R., Johnson, D. S., & Stockmeyer, L. [GJS76].
Example 2.3 (Max-Cut as a nonlinear optimization problem). Max-Cut is one of the most
fundamental problems in theoretical computer science and discrete optimization. The definition
is very simple:
• Let 𝐺 = (𝑉 , 𝐸) be a graph, where 𝑉 ≔ {1, 2, ..., 𝑛} is the set of vertices.
• We want to partition 𝑉 into two sets 𝑆 and 𝑉 ∖ 𝑆, such that the number of edges going
between 𝑆 and 𝑉 ∖ 𝑆 is maximized.
Can you see how this optimization problem might be formulated as a nonlinear optimization
problem with integer variables? Can you remove the constraint that the variables are integer,
and convert it into a continuous problem?
Solution . As a general rule of thumb, the first we want to do when we go from a problem into
its mathematical programming formulation, is to pick variables. In this case, it is intuitive that
we need variables that encode whether each node belongs to 𝑆 or 𝑉 ∖ 𝑆. While several choices
make perfect sense, let’s go with the following. Let’s assign to each node 𝑣 ∈ 𝑉 a variable 𝑥𝑣 ∈
{−1, +1}, with the meaning that:
• if 𝑥𝑣 = +1, then 𝑣 ∈ 𝑆;
• if 𝑥𝑣 = −1, then 𝑣 ∈ 𝑉 ∖ 𝑆.
It is immediate to see that an edge (𝑢, 𝑣) ∈ 𝐸 is a cut edge (that is, connecting one node in 𝑆 to
one node in 𝑉 ∖ 𝑆) if and only if 𝑥𝑢 ⋅ 𝑥𝑣 = −1. Else, 𝑥𝑢 ⋅ 𝑥𝑣 = +1. Hence, we can count exactly
all edges in the cut by considering the objective function
ℎ(𝑥) = ∑
(𝑢,𝑣)∈𝐸
1 − 𝑥𝑢 ⋅ 𝑥𝑣
2 .
This leads to the discrete optimization problem
max
𝑥
s.t.
ℎ(𝑥)
𝑥𝑣 ∈ {−1, +1} ∀𝑣 ∈ 𝑉 .
This problem can be readily written as a continuous, nonlinear optimization problem by noting
that
𝑥𝑣 ∈ {−1, +1} ⟺ 𝑥2
𝑣 = 1.
This leads to the nonlinear optimization problem
max
𝑥
s.t.
∑
(𝑢,𝑣)∈𝐸
1 − 𝑥𝑢 ⋅ 𝑥𝑣
2
𝑥2
𝑣 = 1 ∀𝑣 ∈ 𝑉 ,
(2)
which is a quadratically-constrained quadratic optimization problem. □
Despite the overall generally negative message, I want to end with a message of encouragement.
Sure, we cannot hope to construct a machine that can solve all nonlinear optimization problems.
But nonlinear optimization theory is still incredibly powerful, both because many useful/powerful
optimization problems can be solved efficiently, and because even for the hard problems, nonlinear
optimization might have some tricks up its sleeve. As a case in point, it turns out that the optimiza-
tion problem in (2), which is hard, can be relaxed to a pretty non-obvious optimization problem that
can be efficiently solved.
For those interested, this is obtained by introducing the relaxation
max
𝑦
s.t.
∑
(𝑢,𝑣)∈𝐸
1 − 𝑦𝑢𝑣
2
𝑦𝑣𝑣 = 1 ∀𝑣 ∈ 𝑉
[𝑦𝑢𝑣] ≽ 0,
where [𝑦𝑢𝑣] denotes the matrix where the entry in row 𝑢 ∈ 𝑉 and column 𝑣 ∈ 𝑉 is 𝑦𝑢𝑣 and ≽ 0
means that the matrix just defined must be positive semidefinite. The important fact here is that
this relaxation can be efficiently solved (we will see how later on in this course). With some clever
rounding scheme, one can then recover a solution to the original Max-Cut instance that is guaran-
teed to be 0.878-approximate. This algorithm, due to Goemans, M. X., & Williamson, D. P. [GW95]
makes deep use of nonlinear optimization.
Bibliography
[GW95] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum
cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6,
pp. 1115–1145, Nov. 1995, doi: 10.1145/227683.227684.
[Gül10] O. Güler, Foundations of Optimization. New York, NY, USA: Springer, 2010. [Online].
Available: https://link.springer.com/book/10.1007/978-0-387-68407-9
[Ter76] F. Terkelsen, “The Fundamental Theorem of Algebra,” Am. Math. Mon., Oct. 1976, [On-
line]. Available: https://www.tandfonline.com/doi/abs/10.1080/00029890.1976.11994202
[Fef67] C. Fefferman, “An Easy Proof of the Fundamental Theorem of Algebra,” The American
Mathematical Monthly, vol. 74, no. 7, pp. 854–855, 1967, [Online]. Available: http://www.
jstor.org/stable/2315823
[Blå05] V. Blåsjö, “The Isoperimetric Problem,” Am. Math. Mon., Jun. 2005, [Online]. Available:
https://www.tandfonline.com/doi/pdf/10.1080/00029890.2005.11920227
[GJS76] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified NP-complete
graph problems,” Theoret. Comput. Sci., vol. 1, no. 3, pp. 237–267, Feb. 1976, doi:
10.1016/0304-3975(76)90059-1.
Lecture 1
Introduction
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful for any
reports of typos.
1 Mathematical optimization, and this course
One cannot overstate how pervasive and far reaching mathematical optimization theory is. Opti-
mization is everywhere. This is true in two senses:
• Most of human endeavors and designs have an optimal aspiration in mind—–minimize risk,
maximize reward, reduce energy consumption, train a neural network to minimize model loss,
et cetera.
• Nature’s phenomena themselves seem to be guided by optimization—–the principle of least
action, Hamiltonian mechanics, the Rayleigh-Ritz variational principle (from which the
Schrödinger equation may be derived), et cetera.¹
¹See https://en.wikipedia.org/wiki/Variational_principle for a longer list.
But the benefits of an optimization mindset are also more subtle. For example, optimization in the
space of semidefinite matrices has led to important breakthroughs in classical combinatorial opti-
mization problems in graph theory, such as the Max-Cut problem [GW95]. Optimization theory
can also be used to show the funamental theorem of algebra, and amusingly Güler presents that on
page 34 (!) of his “Foundations of Optimization” book [Gül10], adapting some ideas by Terkelsen,
F. [Ter76] and Fefferman, C. [Fef67].
The literature on optimization dates back to (at least) the ancient Greeks, with their work on the
isoperimetric problem. The problem, which asks to construct the shape that maximizes the area
given a fixed perimeter, is at the center of the legend of how Carthage—one of the most powerful
empires of the classical world—was founded.² It was solved (to the standards of rigor of those times,
at least) by Zenodorus.³
²Dido was the legendary founder—and first queen—of Carthage, a Phoenician city-state that would then become
of the most powerful empires in the world, and will be destroyed by the Roman empire. As recounted by Blåsjö,
V. [Blå05], the legend says that “Dido, daughter of the king of Tyre, fled her home after her brother had killed
her husband”. She later “ended up on the north coast of Africa, where she bargained to buy as much land as she
could enclose with an oxhide. So she cut the hide into thin strips, and then she faced, and presumably solved, the
isoperimetric problem.”
³Approx 150BC, https://en.wikipedia.org/wiki/Zenodorus_(mathematician)
Fast forward to today, mathematical optimization is a vast field, subdivided into a myriad of sub-
fields depending on what types of optimization problems are being solved; here are just a few:
• Linear optimization refers to problems that seek to minimize or maximize linear objectives
subject to linear constraints imposed on continuous optimization variables.
• Integer linear optimization is akin linear optimization, but variables can be further restricted
to only taking integer values.
• Combinatorial optimization more generally studies optimization problems over finite sets.
• Convex optimization studies optimization of convex objectives on convex sets.
• Calculus of variations studies optimization problems in function spaces (that is, where the
optimal object that is sought is a function).
1.1 Focus and objectives of this course
This is a graduate-level course on nonlinear optimization. The main focus of this course is continu-
ous optimization in finite dimensional spaces. As such, nonlinear optimization encompasses a large
variety of topics and algorithms, with applications that range from semidefinite relaxations of com-
binatorial problems, to regression problems, to training of deep neural networks. I foresee that this
course attracts students from (at least) two very different categories:
• Some of you are interested in nonlinear optimization theory. Typically, you’re facing an opti-
mization problem that you hope to solve in closed form, so that you can plug in or reason
about the solution as part of a larger mathematical endeavor.
• Some of you are interested in nonlinear optimization algorithms. Typically, you are facing an
optimization problem for which you simply want a numerical solution.
In this course, the TAs and I have worked hard to cater to both of these categories of students.
1.2 Schedule and administrative details
Please see the syllabus available on Canvas for administrative details, contact information, home-
work and exam dates, and a tentative schedule of classes.
1.3 Prerequisites
This class is pretty light on prerequisites. Fundamentally, the only prerequisites are as follows:
• Linear algebra (18.06)
• Real analysis (18.100A/B/Q)
Beyond some basic mathematical concepts (continuity, vector spaces, some basic point-set topology),
we will try to keep this course as self-contained as possible. Always feel free to stop and ask me or
the TAs during class if there is something you are not familiar with!
A few homework problems will require some (simple!) coding. We recommend Python but you can
ask to switch to a different language of your choice—but please, ask the TAs before doing so. If you
have absolutely zero exposure to programming, that should not be a big issue, but please make sure
to talk to the TAs about it this week.
2 Optimization problems and some preliminary considerations
2.1 General form of a nonlinear optimization problem
In general, an optimization problem has the form
min
𝑥
s.t.
𝑓(𝑥)
𝑥 ∈ Ω
In terms of nomenclature:
• The function we are trying to minimize (or maximize), in this case 𝑓(𝑥), is called the objective
function.
• The entries of the vector 𝑥, are called optimization variables.
• The set Ω is called the feasible set or constraint set.
In particular, in this class we are interested in optimization problems that satisfy certain assump-
tions:
• First of all, we assume that Ω is a subset of some embedding finite Euclidean space 𝐸. Without
loss of generality, 𝐸 = ℝ𝑛.
• The objective function 𝑓(𝑥) is a continuous real-valued function. Very often, we also assume
it is differentiable.
• A category of problems we are paying attention to are those with functional constraints, that
is those in which the feasible set is defined as
Ω ≔ {𝑥 ∈ 𝐸 | 𝑔𝑖(𝑥) ≤ 0,
ℎ𝑗(𝑥) = 0,
𝑖 = 1, ..., 𝑟
𝑗 = 1, ..., 𝑚.}. (1)
When faced with an optimization problem, two questions are immediate:
• Does a solution exist?
• If yes, can we compute it?
We will look into some preliminary observations regarding these two questions in Sections 2.2 and 2.3,
respectively.
2.2 Existence of solutions: Weierstrass theorem
There are two reasons why an optimization problem might not attain a minimum:
• Ω is empty, that is, no feasible points exist at all; or
• for any candidate minimizer, there always exists another point that achieves a lower value, as
shown in the following two examples.
Example 2.1. Consider minimization of the the following two functions, both over their
domain:
𝑥
𝑦
−1 0 1
−12
−8
−4
4
8
12
𝑓(𝑥) = tan(𝑥)
Ω = (−𝜋
2 , 𝜋
2 )
𝑥
𝑦
−3 −2 −1 0 1 2 3
−8
−4
4
8
𝑓(𝑥) = −10 + 𝑒−𝑥
Ω = ℝ
In the plot on the left, the objective function is unbounded: values can be made arbitrarily
small. No minimizer exists.
In the plot on the right, the objective has a lower bound, but for any value of 𝑥, all the
values 𝑥′ > 𝑥 achieve a strictly smaller value than 𝑓(𝑥). Again, no minimizer exists.
So, assuming that the objective 𝑓 is continuous, when can we be certain that an optimizer exists?
If we inspect Example 2.1, we notice that both functions are continuous. In the first example, the
domain is open (the extrema ± 𝜋
2 are not in the domain) and bounded. In the second example, the
domain is unbounded and closed. This shows that, if there is any hope of establishing a general
result on existence of minimizers, such a result must require both closedness and boundedness. We
are in luck:
Theorem 2.1 (Weierstrass theorem). Let 𝑓 : Ω → ℝ be a continuous function defined on a non-
empty and compact (i.e., closed and bounded) set Ω. Then, there exists a minimizer 𝑥∗ ∈ Ω of
𝑓 on Ω, that is,
𝑓(𝑥∗) ≤ 𝑓 (𝑥) for all 𝑥 ∈ Ω.
A note on boundedness. Weierstrass theorem is a pretty universal tool that you can keep in your
toolbox for when you need to argue that an optimization problem has a solution. However, many
optimization problems do not start off with a bounded feasible set Ω. Consider the following example:
Example 2.2. Let 𝑦 ∈ ℝ𝑛 be a point, and 𝑆 ⊆ ℝ𝑛 be a closed but not necessarily bounded set.
Prove that there always exists a projection point
min
𝑥
s.t.
‖𝑥 − 𝑦‖
𝑥 ∈ 𝑆.
𝑆
𝑦
Solution . The idea is to show that we can safely restrict our attention to a compact subset of
the feasible set of the problem—in this case, 𝑆. By “safely”, we mean that the minimizer does
not change before and after making the modification.
In this case, this is simple: pick an arbitrary point 𝑧 ∈ 𝑆.
Then, we know that for sure, if a minimizer exists, it must
live in the intersection
Ω ≔ 𝑆 ∩ 𝔹‖𝑧−𝑦‖(𝑦)
between 𝑆 and the closed ball centered in 𝑦 of radius ‖𝑦 −
𝑧‖ (see the figure on the side). Now, Ω is nonempty (it
contains 𝑧), closed (since both 𝑆 and the ball are closed
and intersection preserves closedness) and bounded (since
the ball has finite radius). So, since the objective function
is continuous, we can invoke Weierstrass theorem and con-
clude the proof.
𝑆
𝑦
𝑧
Ω
□
More generally, we have the following:
Theorem 2.2 (Weierstrass theorem for compact sublevel sets). Let 𝑓 be a continuous function
defined on a set 𝑆. If 𝑓 has a nonempty and compact sublevel set, that is, there exists 𝛼 ∈ ℝ
such that
{𝑥 ∈ 𝑆 : 𝑓(𝑥) ≤ 𝛼}
is nonempty and bounded,4 then 𝑓 has a minimizing point in 𝑆.
4Closedness of the sublevel set is guaranteed by the continuity of 𝑓.
2.3 Nonlinear optimization is computationally hard
We now turn our attention to the second question: what is reasonable to expect in terms of compu-
tational efficiency in finding the solution?
Let me start with the good news: there are entire subclasses of nonlinear optimization problems that
are computationally tractable (most notably, convex optimization problems). As we will see, even
beyond these classes, usually it’s possible to at least guarantee some form of convergence to some
weaker, “local”, notion of optimality.
However, in general, finding minimizers of nonconvex problems is computationally intractable. This
means that we believe that there does not exist any algorithm that is able to solve all nonconvex
optimization problems. This is because we believe that linear integer programming is already in-
tractable, and nonconvex optimization captures known intractable problems such as Max-Cut,5
already under benign assumptions such as quadratic functional constraints and objective.
5NP-completeness of Max-Cut was shown by Garey, M. R., Johnson, D. S., & Stockmeyer, L. [GJS76].
Example 2.3 (Max-Cut as a nonlinear optimization problem). Max-Cut is one of the most
fundamental problems in theoretical computer science and discrete optimization. The definition
is very simple:
• Let 𝐺 = (𝑉 , 𝐸) be a graph, where 𝑉 ≔ {1, 2, ..., 𝑛} is the set of vertices.
• We want to partition 𝑉 into two sets 𝑆 and 𝑉 ∖ 𝑆, such that the number of edges going
between 𝑆 and 𝑉 ∖ 𝑆 is maximized.
Can you see how this optimization problem might be formulated as a nonlinear optimization
problem with integer variables? Can you remove the constraint that the variables are integer,
and convert it into a continuous problem?
Solution . As a general rule of thumb, the first we want to do when we go from a problem into
its mathematical programming formulation, is to pick variables. In this case, it is intuitive that
we need variables that encode whether each node belongs to 𝑆 or 𝑉 ∖ 𝑆. While several choices
make perfect sense, let’s go with the following. Let’s assign to each node 𝑣 ∈ 𝑉 a variable 𝑥𝑣 ∈
{−1, +1}, with the meaning that:
• if 𝑥𝑣 = +1, then 𝑣 ∈ 𝑆;
• if 𝑥𝑣 = −1, then 𝑣 ∈ 𝑉 ∖ 𝑆.
It is immediate to see that an edge (𝑢, 𝑣) ∈ 𝐸 is a cut edge (that is, connecting one node in 𝑆 to
one node in 𝑉 ∖ 𝑆) if and only if 𝑥𝑢 ⋅ 𝑥𝑣 = −1. Else, 𝑥𝑢 ⋅ 𝑥𝑣 = +1. Hence, we can count exactly
all edges in the cut by considering the objective function
ℎ(𝑥) = ∑
(𝑢,𝑣)∈𝐸
1 − 𝑥𝑢 ⋅ 𝑥𝑣
2 .
This leads to the discrete optimization problem
max
𝑥
s.t.
ℎ(𝑥)
𝑥𝑣 ∈ {−1, +1} ∀𝑣 ∈ 𝑉 .
This problem can be readily written as a continuous, nonlinear optimization problem by noting
that
𝑥𝑣 ∈ {−1, +1} ⟺ 𝑥2
𝑣 = 1.
This leads to the nonlinear optimization problem
max
𝑥
s.t.
∑
(𝑢,𝑣)∈𝐸
1 − 𝑥𝑢 ⋅ 𝑥𝑣
2
𝑥2
𝑣 = 1 ∀𝑣 ∈ 𝑉 ,
(2)
which is a quadratically-constrained quadratic optimization problem. □
Despite the overall generally negative message, I want to end with a message of encouragement.
Sure, we cannot hope to construct a machine that can solve all nonlinear optimization problems.
But nonlinear optimization theory is still incredibly powerful, both because many useful/powerful
optimization problems can be solved efficiently, and because even for the hard problems, nonlinear
optimization might have some tricks up its sleeve. As a case in point, it turns out that the optimiza-
tion problem in (2), which is hard, can be relaxed to a pretty non-obvious optimization problem that
can be efficiently solved.
For those interested, this is obtained by introducing the relaxation
max
𝑦
s.t.
∑
(𝑢,𝑣)∈𝐸
1 − 𝑦𝑢𝑣
2
𝑦𝑣𝑣 = 1 ∀𝑣 ∈ 𝑉
[𝑦𝑢𝑣] ≽ 0,
where [𝑦𝑢𝑣] denotes the matrix where the entry in row 𝑢 ∈ 𝑉 and column 𝑣 ∈ 𝑉 is 𝑦𝑢𝑣 and ≽ 0
means that the matrix just defined must be positive semidefinite. The important fact here is that
this relaxation can be efficiently solved (we will see how later on in this course). With some clever
rounding scheme, one can then recover a solution to the original Max-Cut instance that is guaran-
teed to be 0.878-approximate. This algorithm, due to Goemans, M. X., & Williamson, D. P. [GW95]
makes deep use of nonlinear optimization.
Bibliography
[GW95] M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum
cut and satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6,
pp. 1115–1145, Nov. 1995, doi: 10.1145/227683.227684.
[Gül10] O. Güler, Foundations of Optimization. New York, NY, USA: Springer, 2010. [Online].
Available: https://link.springer.com/book/10.1007/978-0-387-68407-9
[Ter76] F. Terkelsen, “The Fundamental Theorem of Algebra,” Am. Math. Mon., Oct. 1976, [On-
line]. Available: https://www.tandfonline.com/doi/abs/10.1080/00029890.1976.11994202
[Fef67] C. Fefferman, “An Easy Proof of the Fundamental Theorem of Algebra,” The American
Mathematical Monthly, vol. 74, no. 7, pp. 854–855, 1967, [Online]. Available: http://www.
jstor.org/stable/2315823
[Blå05] V. Blåsjö, “The Isoperimetric Problem,” Am. Math. Mon., Jun. 2005, [Online]. Available:
https://www.tandfonline.com/doi/pdf/10.1080/00029890.2005.11920227
[GJS76] M. R. Garey, D. S. Johnson, and L. Stockmeyer, “Some simplified NP-complete
graph problems,” Theoret. Comput. Sci., vol. 1, no. 3, pp. 237–267, Feb. 1976, doi:
10.1016/0304-3975(76)90059-1.