MIT 6.7220/15.084 — Nonlinear Optimization (Spring ‘25) Thu, Feb 27th 2025
Lecture 7
Lagrange multipliers and KKT conditions
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
With separation in our toolbox, in Lecture 5 we have been able to prove the characterization
of the normal cone to the intersection of linear constraints. As a reminder, this was the
result that we were able to prove.¹
Theorem L7.1. Let Ω ⊆ ℝ𝑛 be defined as the intersection of 𝑚 linear inequalities
Ω ≔ {𝑥 ∈ ℝ𝑛 : 𝑎⊤
𝑖 𝑥 = 𝑏𝑖 ∀𝑖 = 1, ..., 𝑟
𝑐⊤
𝑗 𝑥 ≤ 𝑑𝑗 ∀𝑗 = 1, ..., 𝑠}
Given a point 𝑥 ∈ Ω, define the index set of the “active” inequality constraints
𝐼(𝑥) ≔ {𝑗 ∈ {1, ..., 𝑠} : 𝑐⊤
𝑗 𝑥 = 𝑑𝑗}.
Then, the normal cone at any 𝑥 ∈ Ω is given by
𝒩Ω(𝑥) =
{{{
{{
∑
𝑟
𝑖=1
𝜇𝑖𝑎𝑖 + ∑
𝑗∈𝐼(𝑥)
𝜆𝑗𝑐𝑗 : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0
}}}
}}
= {∑
𝑟
𝑖=1
𝜇𝑖𝑎𝑖 + ∑
𝑠
𝑗=1
𝜆𝑗𝑐𝑗 : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0, 𝜆𝑗(𝑑𝑗 − 𝑐⊤
𝑗 𝑥) = 0 ∀𝑗 = 1, ..., 𝑠},
where the second equality simply rewrites the condition 𝑗 ∈ 𝐼(𝑥) via complementary
slackness (see Lecture 3).
L7.1 Karush-Kuhn-Tucker (KKT) conditions
The result of Theorem L7.1 gives a complete characterization of the normal cone for sets
defined as intersections of linear constraints. We now turn our attention to more general
constraint sets, defined as the intersection of differentiable functional constraints
min
𝑥
s.t.
𝑓(𝑥)
ℎ𝑖(𝑥) = 0 𝑖 ∈ {1, ..., 𝑟}
𝑔𝑗(𝑥) ≤ 0 𝑗 ∈ {1, ..., 𝑠}.
(1)
L7.1.1 The general idea
Consider any point 𝑥⋆ on the boundary
of the feasible set Ω depicted on the
side, which is the intersection of three
inequality constraints 𝑔𝑖(𝑥) ≤ 0 for 𝑖 ∈
{1, 2, 3} (in particular, in the figure the
𝑔𝑖(𝑥) are quadratic constraints).
The set of directions that form an ob
tuse angle with all directions that from
𝑥⋆ remain inside of the set coincides
with the normal cone at the lineariza=
tion of the constraints that are binding
(holding with equality) at 𝑥⋆.
0.5 1 1.5 2 2.5 3 3.5 4 4.5
−2
−1.5
−1
−0.5
0.5
1
1.5
0
Ω
𝑔1(𝑥) = 0
𝑔2(𝑥) = 0
𝑔3(𝑥) = 0
𝑥1
𝑥2
𝒩Ω(𝑥1)
𝒩Ω(𝑥2)
The above observation suggests that for a nonlinear optimization problem with functional
constraints, −∇𝑓(𝑥) should belong to the normal cone to the linearization of the binding
constraints at 𝑥. This condition goes under the name of KarushKuhnTucker (KKT)
optimality condition.²
Since the binding linearized constraints are of the form
ℎ𝑖(𝑥⋆) + ⟨∇ℎ𝑖(𝑥⋆), 𝑥 − 𝑥⋆⟩ = 0 ⟹ ⟨∇ℎ𝑖(𝑥⋆), 𝑥⟩ = ⟨∇ℎ𝑖(𝑥⋆), 𝑥⋆⟩ − ℎ𝑖(𝑥⋆)
𝑔𝑖(𝑥⋆) + ⟨∇𝑔𝑖(𝑥⋆), 𝑥 − 𝑥⋆⟩ ≤ 0 ⟹ ⟨∇𝑔𝑖(𝑥⋆), 𝑥⟩ ≤ ⟨∇𝑔𝑖(𝑥⋆), 𝑥⋆⟩ − 𝑔𝑖(𝑥⋆),
from Theorem L7.1 we know that the normal cone of the linearization ̃ Ω of Ω around 𝑥⋆ is
𝒩̃Ω(𝑥⋆) =
{{{
{{
∑
𝑟
𝑖=1
𝜇𝑖∇ℎ𝑖(𝑥⋆) + ∑
𝑗∈𝐼(𝑥⋆)
𝜆𝑗∇𝑔𝑗(𝑥⋆) : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0
}}}
}}
,
where the set of binding inequality constraints 𝐼(𝑥⋆) is
𝐼(𝑥⋆) ≔ {𝑗 ∈ {1, ..., 𝑠} : 𝑔𝑗(𝑥⋆) = 0}.
(All equality constraints are always binding, and so we can directly sum over all 𝑖 = 1, ..., 𝑟.)
By using the complementary slackness reformulation of 𝐼(𝑥), the first=order optimality
conditions induced by the linearization of the feasible set are typically rewritten as follows.
Definition L7.1 (KKT conditions). Consider a nonlinear optimization problem with
differentiable objective function and functional constraints, in the form given in (1),
and let 𝑥 be a point in the feasible set (“Primal Feasibility”). The KKT conditions at
𝑥 are given by
−∇𝑓(𝑥) = ∑
𝑟
𝑖=1
𝜇𝑖∇ℎ𝑖(𝑥) + ∑
𝑠
𝑗=1
𝜆𝑗∇𝑔𝑗(𝑥) (“Stationarity”)
𝜇𝑖 ∈ ℝ, 𝜆𝑗 ≥ 0 ∀𝑖 = 1, ..., 𝑟, 𝑗 = 1, ..., 𝑠 (“Dual feasibility”)
𝜆𝑗 ⋅ 𝑔𝑗(𝑥) = 0 ∀𝑗 = 1, ..., 𝑠. (“Complementary slackness”)
In the definition above, we have noted in quotes the typical names for each of the different
conditions. However, please do not get distracted by these names:
• What the KKT conditions are really saying is that −∇𝑓(𝑥) must be in the normal
cone to the linearization of the constraint set.
• The complementary slackness condition is just a fancier way of writing “if 𝑗 ∉ 𝐼(𝑥),
then 𝜆𝑗 = 0”.
The KKT conditions are often necessary conditions for optimality (for example, in the
picture above), but not always.
L7.1.2 Failure of the KKT conditions
It is important to keep in mind that in some cases KKT conditions might fail to hold at
optimality. This typically happens when the linearization of the constraints collapses. To
fix ideas, consider the following simple example.
Example L7.1 (Failure of KKT). Consider the problem
0.2 0.4 0.6 0.8 1 x
0.25
0.5
0.75
1
y
0
Ω
min
(𝑥,𝑦)
s.t.
−𝑥
𝑦 − (1 − 𝑥)3 ≤ 0
𝑥 ≥ 0
𝑦 ≥ 0.
Let’s denote the objective and functional con=
straints as
• 𝑓(𝑥, 𝑦) ≔ −𝑥,
• 𝑔1(𝑥, 𝑦) ≔ 𝑦 − (1 − 𝑥)3 ≤ 0,
• 𝑔2(𝑥, 𝑦) ≔ −𝑥 ≤ 0,
• 𝑔3(𝑥, 𝑦) ≔ −𝑦 ≤ 0.
The feasible set Ω for this problem is shown on the right. At the optimal point (𝑥⋆, 𝑦⋆) ≔
(1, 0), the gradients of the objective and the binding constraints (𝑔1 and 𝑔3) are
∇𝑓(𝑥⋆, 𝑦⋆) = (−1
0 ); ∇𝑔1(𝑥⋆, 𝑦⋆) = (0
1); ∇𝑔3(𝑥⋆, 𝑦⋆) = ( 0
−1).
It is then clear that there exist no Lagrange multipliers 𝜆1, 𝜆3 such that
−∇𝑓(𝑥⋆, 𝑦⋆) = 𝜆1∇𝑔1(𝑥⋆, 𝑦⋆) + 𝜆3∇𝑔3(𝑥⋆, 𝑦⋆).
The KKT conditions fail in this case.
The reason why the KKT conditions failed at the optimal point (𝑥⋆, 𝑦⋆) = (1, 0) in Example
L7.1 is due to the fact that the linearization of constraint 𝑔1(𝑥, 𝑦) ≤ 0 around the optimal
point (𝑥⋆, 𝑦⋆) = (1, 0) is 𝑦 ≤ 0. This is parallel to the existing constraint 𝑦 ≥ 0, and fails to
capture the fact that 𝑥 ≤ 1 on the feasible set Ω.
L7.1.3 Constraint qualification
Conditions that prevent the degenerate behavior illustrated in Example L7.1 above go under
the name of constraint qualification. Several constraint qualification conditions are known
in the literature.
■ Concave and affine constraints. We already know that when the feasible set Ω is defined
via linear constraints (that is, all ℎ𝑖 and 𝑔𝑗 in (1) are affine functions), then no further
constraint qualifications hold, and the necessity of the KKT conditions is implied directly
by Theorem L7.1.
With only very little work, we can show that the same remains true if the 𝑔𝑗 are allowed
to be concave functions (that is, the −𝑔𝑗 are convex functions).
Theorem L7.2 (Concave and linear constraints). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of
(1). If
• the binding inequality constraints {𝑔𝑗}𝑗∈𝐼(𝑥) are concave differentiable functions
in a convex neighborhood of 𝑥; and
• the equality constraints {ℎ𝑖}𝑟
𝑖=1 are affine functions on ℝ𝑛,
then the KKT conditions hold at 𝑥.
(In fact, this might very well be in Pset 3...)
■ Linear independence of gradients. In Example L7.1, the linearization of two constraints
coincided, causing problems. When all linearized constraints are linearly independent, the
issue is avoided.
Theorem L7.3 (Linear independence of gradients). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of
(1). If all functions ℎ𝑖, 𝑔𝑗 are continuously differentiable and the multiset of gradients
at 𝑥 of all active constraints
{∇ℎ𝑖(𝑥) : 𝑖 = 1, ..., 𝑟} ∪ {∇𝑔𝑗(𝑥) : 𝑗 ∈ 𝐼(𝑥)}
is linearly independent,³ then the KKT conditions hold at 𝑥.
In fact, the condition above is a special case of a much more general condition called
MangasarianFromowitz constraint qualification [MF67].
Example L7.2. One might wonder why the condition requires continuous differentiability
rather than just differentiability (after all the KKT conditions only use the gradients).
To appreciate the need, consider the following example, due to Fernández, L. A. [Fer97]:
min
𝑥,𝑦
s.t.
𝑥
ℎ(𝑥, 𝑦) = 0
𝑥, 𝑦 ∈ ℝ,
where ℎ(𝑥, 𝑦) ≔
{
{
{
{
{𝑦 if 𝑥 ≥ 0
𝑦 − 𝑥2 if 𝑥 < 0 and 𝑦 ≤ 0
𝑦 + 𝑥2 if 𝑥 < 0 and 𝑦 > 0.
It is clear that for 𝑥 < 0, ℎ(𝑥, 𝑦) ≠ 0, and for 𝑥 ≥ 0, ℎ(𝑥, 𝑦) = 0 is equivalent to 𝑦 =
0. Hence, the constraint ℎ(𝑥, 𝑦) = 0 is equivalent to the constraint 𝑦 = 0, 𝑥 ≥ 0. It is
evident that the unique minimizer is the point (0, 0).
As it turns out, the function ℎ is differentiable at (0, 0), with
∇ℎ(0, 0) = (0
1).
However, the function is not continuously differentiable (it is not differentiable on the
ray (𝑥, 0) for 𝑥 < 0). The KKT conditions in this case would require that there exists
𝜇 ∈ ℝ such that
−(1
0) = 𝜇(0
1),
which is clearly impossible. Hence, the minimizer does not satisfy the KKT conditions.
■ Slater’s condition. Finally, we consider a popular constraint qualification condition for
problems with convex inequality constraints and affine equality constraints.
Theorem L7.4 (Slater’s condition [Sla59]). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of (1). If
• the binding inequality constraints {𝑔𝑗}𝑗∈𝐼(𝑥) are convex differentiable functions;
and
• the equality constraints {ℎ𝑖}𝑟
𝑖=1 are affine functions; and
• there exists a feasible point 𝑥0 that is strictly feasible for the binding inequality
constraints, that is,
𝑔𝑗(𝑥0) < 0 ∀𝑗 ∈ 𝐼(𝑥)
then the KKT conditions hold at 𝑥.
The strict feasibility requirement is key and cannot be relaxed, even if the 𝑔𝑗 are convex
and thus rather well=behaved. For example, consider what would happen in the problem
min 𝑥 subject to 𝑥2 ≤ 0...
Similarly, the convexity requirement cannot be relaxed even under strict feasibility, as
Example L7.1 shows.
A nice feature of Slater’s condition is that it is sufficient for optimality, and not just
necessary, when the objective function 𝑓 is convex.
Theorem L7.5. If 𝑓 is convex and the constraints satisfy Slater’s condition, then the
KKT conditions are both necessary and sufficient for optimality.
Proof. Necessity is guaranteed from Theorem L7.4. So, we focus on sufficiency. Let the
problem satisfying Slater’s conditions be
min
𝑥
s.t.
𝑓(𝑥)
𝑔𝑖(𝑥) ≤ 0 𝑖 = 1, ..., 𝑟
𝐴𝑥 = 𝑏,
and 𝑥⋆ be a feasible point satisfying the KKT conditions. In particular, we know that
there exist multipliers 𝜆⋆
𝑖 ≥ 0 and 𝜇⋆ such that
∇𝑓(𝑥⋆) + ∑
𝑟
𝑖=1
𝜆⋆
𝑖 ∇𝑔𝑖(𝑥⋆) + 𝐴⊤𝜇⋆ = 0, (2)
and that the complementary slackness condition
𝜆⋆
𝑖 𝑔𝑖(𝑥⋆) = 0 ∀𝑖 = 1, ..., 𝑟.
holds. Since 𝑓 and all the 𝑔𝑖’s are convex, Equation (2) implies that 𝑥⋆ is a minimizer of
the function
𝐿(𝑥) ≔ 𝑓(𝑥) + ∑
𝑟
𝑖=1
𝜆⋆
𝑖 𝑔𝑖(𝑥) + ⟨𝜇⋆, 𝐴𝑥 − 𝑏⟩,
as first=order optimality conditions are sufficient for convex functions. Furthermore, note
that 𝐿(𝑥) ≤ 𝑓(𝑥) for all feasible 𝑥, since 𝜆⋆
𝑖 ≥ 0 and all feasible 𝑥 satisfy 𝑔𝑖(𝑥) ≤ 0 and
𝐴𝑥 = 𝑏. Hence, for any feasible 𝑥 we can write
𝑓(𝑥) ≥ 𝐿(𝑥) ≥ 𝐿(𝑥⋆) = 𝑓(𝑥⋆),
where the last equality follows from the complementary slackness conditions. □
L7.2 Further readings
The following books all contain an excellent and approachable treatment of the KKT
condititions:
[Gül10] Güler, O. (2010). Foundations of Optimization. Springer. https://link.springer.
com/book/10.1007/978-0-387-68407-9
[Jah07] Jahn, J. (2007). Introduction to the Theory of Nonlinear Optimization. Springer.
https://link.springer.com/book/10.1007/978-3-540-49379-2
[Ber16] Bertsekas, D. P. (2016). Nonlinear Programming (3rd edition). Athena Scientific.
For a more advanced treatment with connections to metric regularity and nonsmooth
analysis, I recommend the following book by Borwein and Lewis.
[BL06] Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization.
Springer. https://link.springer.com/book/10.1007/978-0-387-31256-9
Bibliography for this lecture
[KT51] Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear Programming. In Proceedings of
the Second Berkeley Symposium on Mathematical Statistics and Probability (Vol.
2, pp. 481–493). University of California Press.
[Kar39] Karush, W. (1939). Minima of functions of several variables with inequalities as
side conditions.
[Kje00] Kjeldsen, T. H. (2000). A Contextualized Historical Analysis of the Kuhn–Tucker
Theorem in Nonlinear Programming: The Impact of World War II. Historia Math.,
27(4), 331–361. https://doi.org/10.1006/hmat.2000.2289
[MF67] Mangasarian, O. L., & Fromovitz, S. (1967). The Fritz John necessary optimality
conditions in the presence of equality and inequality constraints. J. Math. Anal.
Appl., 17(1), 37–47. https://doi.org/10.1016/0022-247X(67)90163-1
[Fer97] Fernández, L. A. (1997). Classroom note: On the limits of the Lagrange multiplier
rule. SIAM Review, 39(2), 292–297.
[Gül10] Güler, O. (2010). Foundations of Optimization. Springer. https://link.springer.
com/book/10.1007/978-0-387-68407-9
[Jah07] Jahn, J. (2007). Introduction to the Theory of Nonlinear Optimization. Springer.
https://link.springer.com/book/10.1007/978-3-540-49379-2
[Ber16] Bertsekas, D. P. (2016). Nonlinear Programming (3rd edition). Athena Scientific.
[BL06] Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization.
Springer. https://link.springer.com/book/10.1007/978-0-387-31256-9
Changelog
• Feb 27, 2025: Added Theorem L7.5.
• Feb 28, 2025: Fixed two typos (thanks Nicolas Gorlo!)
• Mar 1, 2025: Added footnote 3 (https://piazza.com/class/m6lg9aspoutda/post/56)
• Mar 2, 2025: Added equation number to (2)
• Mar 15, 2025: Fixed indexing in Theorem L7.1 (thanks Khizer Shahid!)
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹For reasons of convenience, Theorem L7.1 makes a distinction between equality and inequality
constraints. Of course, equality constraints can be rewritten as two inequality constraints (see also section
L3.2.1 “A remark on equality constraints” from Lecture 3), but the notation will be more convenient this
way for what is about to come in the rest of the lecture.
²The KKT conditions used to be called “Kuhn=Tucker conditions” and were first published by Kuhn, H.
W., & Tucker, A. W. [KT51]. It was later discovered that the same conditions had appeared more than 10
years earlier in the unpublished master’s thesis of Karush, W. [Kar39]. An analysis of the history of the
KKT conditions is given by Kjeldsen, T. H. [Kje00].
³Remark: the union above is meant with repetition. Indeed, consider what would happen if in Example
L7.1 we had made the third constraint 𝑦 = 0 instead of 𝑦 ≥ 0.
Lecture 7
Lagrange multipliers and KKT conditions
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
With separation in our toolbox, in Lecture 5 we have been able to prove the characterization
of the normal cone to the intersection of linear constraints. As a reminder, this was the
result that we were able to prove.¹
Theorem L7.1. Let Ω ⊆ ℝ𝑛 be defined as the intersection of 𝑚 linear inequalities
Ω ≔ {𝑥 ∈ ℝ𝑛 : 𝑎⊤
𝑖 𝑥 = 𝑏𝑖 ∀𝑖 = 1, ..., 𝑟
𝑐⊤
𝑗 𝑥 ≤ 𝑑𝑗 ∀𝑗 = 1, ..., 𝑠}
Given a point 𝑥 ∈ Ω, define the index set of the “active” inequality constraints
𝐼(𝑥) ≔ {𝑗 ∈ {1, ..., 𝑠} : 𝑐⊤
𝑗 𝑥 = 𝑑𝑗}.
Then, the normal cone at any 𝑥 ∈ Ω is given by
𝒩Ω(𝑥) =
{{{
{{
∑
𝑟
𝑖=1
𝜇𝑖𝑎𝑖 + ∑
𝑗∈𝐼(𝑥)
𝜆𝑗𝑐𝑗 : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0
}}}
}}
= {∑
𝑟
𝑖=1
𝜇𝑖𝑎𝑖 + ∑
𝑠
𝑗=1
𝜆𝑗𝑐𝑗 : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0, 𝜆𝑗(𝑑𝑗 − 𝑐⊤
𝑗 𝑥) = 0 ∀𝑗 = 1, ..., 𝑠},
where the second equality simply rewrites the condition 𝑗 ∈ 𝐼(𝑥) via complementary
slackness (see Lecture 3).
L7.1 Karush-Kuhn-Tucker (KKT) conditions
The result of Theorem L7.1 gives a complete characterization of the normal cone for sets
defined as intersections of linear constraints. We now turn our attention to more general
constraint sets, defined as the intersection of differentiable functional constraints
min
𝑥
s.t.
𝑓(𝑥)
ℎ𝑖(𝑥) = 0 𝑖 ∈ {1, ..., 𝑟}
𝑔𝑗(𝑥) ≤ 0 𝑗 ∈ {1, ..., 𝑠}.
(1)
L7.1.1 The general idea
Consider any point 𝑥⋆ on the boundary
of the feasible set Ω depicted on the
side, which is the intersection of three
inequality constraints 𝑔𝑖(𝑥) ≤ 0 for 𝑖 ∈
{1, 2, 3} (in particular, in the figure the
𝑔𝑖(𝑥) are quadratic constraints).
The set of directions that form an ob
tuse angle with all directions that from
𝑥⋆ remain inside of the set coincides
with the normal cone at the lineariza=
tion of the constraints that are binding
(holding with equality) at 𝑥⋆.
0.5 1 1.5 2 2.5 3 3.5 4 4.5
−2
−1.5
−1
−0.5
0.5
1
1.5
0
Ω
𝑔1(𝑥) = 0
𝑔2(𝑥) = 0
𝑔3(𝑥) = 0
𝑥1
𝑥2
𝒩Ω(𝑥1)
𝒩Ω(𝑥2)
The above observation suggests that for a nonlinear optimization problem with functional
constraints, −∇𝑓(𝑥) should belong to the normal cone to the linearization of the binding
constraints at 𝑥. This condition goes under the name of KarushKuhnTucker (KKT)
optimality condition.²
Since the binding linearized constraints are of the form
ℎ𝑖(𝑥⋆) + ⟨∇ℎ𝑖(𝑥⋆), 𝑥 − 𝑥⋆⟩ = 0 ⟹ ⟨∇ℎ𝑖(𝑥⋆), 𝑥⟩ = ⟨∇ℎ𝑖(𝑥⋆), 𝑥⋆⟩ − ℎ𝑖(𝑥⋆)
𝑔𝑖(𝑥⋆) + ⟨∇𝑔𝑖(𝑥⋆), 𝑥 − 𝑥⋆⟩ ≤ 0 ⟹ ⟨∇𝑔𝑖(𝑥⋆), 𝑥⟩ ≤ ⟨∇𝑔𝑖(𝑥⋆), 𝑥⋆⟩ − 𝑔𝑖(𝑥⋆),
from Theorem L7.1 we know that the normal cone of the linearization ̃ Ω of Ω around 𝑥⋆ is
𝒩̃Ω(𝑥⋆) =
{{{
{{
∑
𝑟
𝑖=1
𝜇𝑖∇ℎ𝑖(𝑥⋆) + ∑
𝑗∈𝐼(𝑥⋆)
𝜆𝑗∇𝑔𝑗(𝑥⋆) : 𝜇𝑖 ∈ ℝ, 𝜆𝑗 ∈ ℝ≥0
}}}
}}
,
where the set of binding inequality constraints 𝐼(𝑥⋆) is
𝐼(𝑥⋆) ≔ {𝑗 ∈ {1, ..., 𝑠} : 𝑔𝑗(𝑥⋆) = 0}.
(All equality constraints are always binding, and so we can directly sum over all 𝑖 = 1, ..., 𝑟.)
By using the complementary slackness reformulation of 𝐼(𝑥), the first=order optimality
conditions induced by the linearization of the feasible set are typically rewritten as follows.
Definition L7.1 (KKT conditions). Consider a nonlinear optimization problem with
differentiable objective function and functional constraints, in the form given in (1),
and let 𝑥 be a point in the feasible set (“Primal Feasibility”). The KKT conditions at
𝑥 are given by
−∇𝑓(𝑥) = ∑
𝑟
𝑖=1
𝜇𝑖∇ℎ𝑖(𝑥) + ∑
𝑠
𝑗=1
𝜆𝑗∇𝑔𝑗(𝑥) (“Stationarity”)
𝜇𝑖 ∈ ℝ, 𝜆𝑗 ≥ 0 ∀𝑖 = 1, ..., 𝑟, 𝑗 = 1, ..., 𝑠 (“Dual feasibility”)
𝜆𝑗 ⋅ 𝑔𝑗(𝑥) = 0 ∀𝑗 = 1, ..., 𝑠. (“Complementary slackness”)
In the definition above, we have noted in quotes the typical names for each of the different
conditions. However, please do not get distracted by these names:
• What the KKT conditions are really saying is that −∇𝑓(𝑥) must be in the normal
cone to the linearization of the constraint set.
• The complementary slackness condition is just a fancier way of writing “if 𝑗 ∉ 𝐼(𝑥),
then 𝜆𝑗 = 0”.
The KKT conditions are often necessary conditions for optimality (for example, in the
picture above), but not always.
L7.1.2 Failure of the KKT conditions
It is important to keep in mind that in some cases KKT conditions might fail to hold at
optimality. This typically happens when the linearization of the constraints collapses. To
fix ideas, consider the following simple example.
Example L7.1 (Failure of KKT). Consider the problem
0.2 0.4 0.6 0.8 1 x
0.25
0.5
0.75
1
y
0
Ω
min
(𝑥,𝑦)
s.t.
−𝑥
𝑦 − (1 − 𝑥)3 ≤ 0
𝑥 ≥ 0
𝑦 ≥ 0.
Let’s denote the objective and functional con=
straints as
• 𝑓(𝑥, 𝑦) ≔ −𝑥,
• 𝑔1(𝑥, 𝑦) ≔ 𝑦 − (1 − 𝑥)3 ≤ 0,
• 𝑔2(𝑥, 𝑦) ≔ −𝑥 ≤ 0,
• 𝑔3(𝑥, 𝑦) ≔ −𝑦 ≤ 0.
The feasible set Ω for this problem is shown on the right. At the optimal point (𝑥⋆, 𝑦⋆) ≔
(1, 0), the gradients of the objective and the binding constraints (𝑔1 and 𝑔3) are
∇𝑓(𝑥⋆, 𝑦⋆) = (−1
0 ); ∇𝑔1(𝑥⋆, 𝑦⋆) = (0
1); ∇𝑔3(𝑥⋆, 𝑦⋆) = ( 0
−1).
It is then clear that there exist no Lagrange multipliers 𝜆1, 𝜆3 such that
−∇𝑓(𝑥⋆, 𝑦⋆) = 𝜆1∇𝑔1(𝑥⋆, 𝑦⋆) + 𝜆3∇𝑔3(𝑥⋆, 𝑦⋆).
The KKT conditions fail in this case.
The reason why the KKT conditions failed at the optimal point (𝑥⋆, 𝑦⋆) = (1, 0) in Example
L7.1 is due to the fact that the linearization of constraint 𝑔1(𝑥, 𝑦) ≤ 0 around the optimal
point (𝑥⋆, 𝑦⋆) = (1, 0) is 𝑦 ≤ 0. This is parallel to the existing constraint 𝑦 ≥ 0, and fails to
capture the fact that 𝑥 ≤ 1 on the feasible set Ω.
L7.1.3 Constraint qualification
Conditions that prevent the degenerate behavior illustrated in Example L7.1 above go under
the name of constraint qualification. Several constraint qualification conditions are known
in the literature.
■ Concave and affine constraints. We already know that when the feasible set Ω is defined
via linear constraints (that is, all ℎ𝑖 and 𝑔𝑗 in (1) are affine functions), then no further
constraint qualifications hold, and the necessity of the KKT conditions is implied directly
by Theorem L7.1.
With only very little work, we can show that the same remains true if the 𝑔𝑗 are allowed
to be concave functions (that is, the −𝑔𝑗 are convex functions).
Theorem L7.2 (Concave and linear constraints). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of
(1). If
• the binding inequality constraints {𝑔𝑗}𝑗∈𝐼(𝑥) are concave differentiable functions
in a convex neighborhood of 𝑥; and
• the equality constraints {ℎ𝑖}𝑟
𝑖=1 are affine functions on ℝ𝑛,
then the KKT conditions hold at 𝑥.
(In fact, this might very well be in Pset 3...)
■ Linear independence of gradients. In Example L7.1, the linearization of two constraints
coincided, causing problems. When all linearized constraints are linearly independent, the
issue is avoided.
Theorem L7.3 (Linear independence of gradients). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of
(1). If all functions ℎ𝑖, 𝑔𝑗 are continuously differentiable and the multiset of gradients
at 𝑥 of all active constraints
{∇ℎ𝑖(𝑥) : 𝑖 = 1, ..., 𝑟} ∪ {∇𝑔𝑗(𝑥) : 𝑗 ∈ 𝐼(𝑥)}
is linearly independent,³ then the KKT conditions hold at 𝑥.
In fact, the condition above is a special case of a much more general condition called
MangasarianFromowitz constraint qualification [MF67].
Example L7.2. One might wonder why the condition requires continuous differentiability
rather than just differentiability (after all the KKT conditions only use the gradients).
To appreciate the need, consider the following example, due to Fernández, L. A. [Fer97]:
min
𝑥,𝑦
s.t.
𝑥
ℎ(𝑥, 𝑦) = 0
𝑥, 𝑦 ∈ ℝ,
where ℎ(𝑥, 𝑦) ≔
{
{
{
{
{𝑦 if 𝑥 ≥ 0
𝑦 − 𝑥2 if 𝑥 < 0 and 𝑦 ≤ 0
𝑦 + 𝑥2 if 𝑥 < 0 and 𝑦 > 0.
It is clear that for 𝑥 < 0, ℎ(𝑥, 𝑦) ≠ 0, and for 𝑥 ≥ 0, ℎ(𝑥, 𝑦) = 0 is equivalent to 𝑦 =
0. Hence, the constraint ℎ(𝑥, 𝑦) = 0 is equivalent to the constraint 𝑦 = 0, 𝑥 ≥ 0. It is
evident that the unique minimizer is the point (0, 0).
As it turns out, the function ℎ is differentiable at (0, 0), with
∇ℎ(0, 0) = (0
1).
However, the function is not continuously differentiable (it is not differentiable on the
ray (𝑥, 0) for 𝑥 < 0). The KKT conditions in this case would require that there exists
𝜇 ∈ ℝ such that
−(1
0) = 𝜇(0
1),
which is clearly impossible. Hence, the minimizer does not satisfy the KKT conditions.
■ Slater’s condition. Finally, we consider a popular constraint qualification condition for
problems with convex inequality constraints and affine equality constraints.
Theorem L7.4 (Slater’s condition [Sla59]). Let 𝑥 ∈ Ω ⊆ ℝ𝑛 be a minimizer of (1). If
• the binding inequality constraints {𝑔𝑗}𝑗∈𝐼(𝑥) are convex differentiable functions;
and
• the equality constraints {ℎ𝑖}𝑟
𝑖=1 are affine functions; and
• there exists a feasible point 𝑥0 that is strictly feasible for the binding inequality
constraints, that is,
𝑔𝑗(𝑥0) < 0 ∀𝑗 ∈ 𝐼(𝑥)
then the KKT conditions hold at 𝑥.
The strict feasibility requirement is key and cannot be relaxed, even if the 𝑔𝑗 are convex
and thus rather well=behaved. For example, consider what would happen in the problem
min 𝑥 subject to 𝑥2 ≤ 0...
Similarly, the convexity requirement cannot be relaxed even under strict feasibility, as
Example L7.1 shows.
A nice feature of Slater’s condition is that it is sufficient for optimality, and not just
necessary, when the objective function 𝑓 is convex.
Theorem L7.5. If 𝑓 is convex and the constraints satisfy Slater’s condition, then the
KKT conditions are both necessary and sufficient for optimality.
Proof. Necessity is guaranteed from Theorem L7.4. So, we focus on sufficiency. Let the
problem satisfying Slater’s conditions be
min
𝑥
s.t.
𝑓(𝑥)
𝑔𝑖(𝑥) ≤ 0 𝑖 = 1, ..., 𝑟
𝐴𝑥 = 𝑏,
and 𝑥⋆ be a feasible point satisfying the KKT conditions. In particular, we know that
there exist multipliers 𝜆⋆
𝑖 ≥ 0 and 𝜇⋆ such that
∇𝑓(𝑥⋆) + ∑
𝑟
𝑖=1
𝜆⋆
𝑖 ∇𝑔𝑖(𝑥⋆) + 𝐴⊤𝜇⋆ = 0, (2)
and that the complementary slackness condition
𝜆⋆
𝑖 𝑔𝑖(𝑥⋆) = 0 ∀𝑖 = 1, ..., 𝑟.
holds. Since 𝑓 and all the 𝑔𝑖’s are convex, Equation (2) implies that 𝑥⋆ is a minimizer of
the function
𝐿(𝑥) ≔ 𝑓(𝑥) + ∑
𝑟
𝑖=1
𝜆⋆
𝑖 𝑔𝑖(𝑥) + ⟨𝜇⋆, 𝐴𝑥 − 𝑏⟩,
as first=order optimality conditions are sufficient for convex functions. Furthermore, note
that 𝐿(𝑥) ≤ 𝑓(𝑥) for all feasible 𝑥, since 𝜆⋆
𝑖 ≥ 0 and all feasible 𝑥 satisfy 𝑔𝑖(𝑥) ≤ 0 and
𝐴𝑥 = 𝑏. Hence, for any feasible 𝑥 we can write
𝑓(𝑥) ≥ 𝐿(𝑥) ≥ 𝐿(𝑥⋆) = 𝑓(𝑥⋆),
where the last equality follows from the complementary slackness conditions. □
L7.2 Further readings
The following books all contain an excellent and approachable treatment of the KKT
condititions:
[Gül10] Güler, O. (2010). Foundations of Optimization. Springer. https://link.springer.
com/book/10.1007/978-0-387-68407-9
[Jah07] Jahn, J. (2007). Introduction to the Theory of Nonlinear Optimization. Springer.
https://link.springer.com/book/10.1007/978-3-540-49379-2
[Ber16] Bertsekas, D. P. (2016). Nonlinear Programming (3rd edition). Athena Scientific.
For a more advanced treatment with connections to metric regularity and nonsmooth
analysis, I recommend the following book by Borwein and Lewis.
[BL06] Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization.
Springer. https://link.springer.com/book/10.1007/978-0-387-31256-9
Bibliography for this lecture
[KT51] Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear Programming. In Proceedings of
the Second Berkeley Symposium on Mathematical Statistics and Probability (Vol.
2, pp. 481–493). University of California Press.
[Kar39] Karush, W. (1939). Minima of functions of several variables with inequalities as
side conditions.
[Kje00] Kjeldsen, T. H. (2000). A Contextualized Historical Analysis of the Kuhn–Tucker
Theorem in Nonlinear Programming: The Impact of World War II. Historia Math.,
27(4), 331–361. https://doi.org/10.1006/hmat.2000.2289
[MF67] Mangasarian, O. L., & Fromovitz, S. (1967). The Fritz John necessary optimality
conditions in the presence of equality and inequality constraints. J. Math. Anal.
Appl., 17(1), 37–47. https://doi.org/10.1016/0022-247X(67)90163-1
[Fer97] Fernández, L. A. (1997). Classroom note: On the limits of the Lagrange multiplier
rule. SIAM Review, 39(2), 292–297.
[Gül10] Güler, O. (2010). Foundations of Optimization. Springer. https://link.springer.
com/book/10.1007/978-0-387-68407-9
[Jah07] Jahn, J. (2007). Introduction to the Theory of Nonlinear Optimization. Springer.
https://link.springer.com/book/10.1007/978-3-540-49379-2
[Ber16] Bertsekas, D. P. (2016). Nonlinear Programming (3rd edition). Athena Scientific.
[BL06] Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization.
Springer. https://link.springer.com/book/10.1007/978-0-387-31256-9
Changelog
• Feb 27, 2025: Added Theorem L7.5.
• Feb 28, 2025: Fixed two typos (thanks Nicolas Gorlo!)
• Mar 1, 2025: Added footnote 3 (https://piazza.com/class/m6lg9aspoutda/post/56)
• Mar 2, 2025: Added equation number to (2)
• Mar 15, 2025: Fixed indexing in Theorem L7.1 (thanks Khizer Shahid!)
★These notes are class material that has not undergone formal peer review. The TAs and I are grateful
for any reports of typos.
¹For reasons of convenience, Theorem L7.1 makes a distinction between equality and inequality
constraints. Of course, equality constraints can be rewritten as two inequality constraints (see also section
L3.2.1 “A remark on equality constraints” from Lecture 3), but the notation will be more convenient this
way for what is about to come in the rest of the lecture.
²The KKT conditions used to be called “Kuhn=Tucker conditions” and were first published by Kuhn, H.
W., & Tucker, A. W. [KT51]. It was later discovered that the same conditions had appeared more than 10
years earlier in the unpublished master’s thesis of Karush, W. [Kar39]. An analysis of the history of the
KKT conditions is given by Kjeldsen, T. H. [Kje00].
³Remark: the union above is meant with repetition. Indeed, consider what would happen if in Example
L7.1 we had made the third constraint 𝑦 = 0 instead of 𝑦 ≥ 0.