These notes are a brief introduction to Lagrange multipliers and convex duality, with as little technical detail as possible since the epsilon-delta proofs can be found in many places. Consider the problem of minimizing a smooth function \(f:\mathbb{R}^d \to \mathbb{R}\). In the absence of constraints, the first-order condition is of course
\[ \nabla f(x_\star)=0. \]
Indeed, if the gradient is non-zero, one can move a little in the direction \(-\nabla f\) and decrease the function. In some sense, a lot of these notes are about generalizing this simple remark to the case of equality and inequality constraints. Constraints only change one thing: some directions are no longer available, which indeed means that the condition \(\nabla f(x_\star)=0\) will need to be relaxed in different ways. As we will see, the notion of Lagrange multipliers and Lagrange duality are the natural generalizations of this simple idea.
Equality constraints
Suppose first that the feasible set is described by \(r \geq 1\) smooth equality constraints. Near a regular point \(x\), this is a smooth surface of dimension \(d-r\). Along any vector \(v\) in the tangent space and a local minimum \(x_\star\), the function \(f\) cannot decrease to first order, which readily gives that \(\nabla f(x_\star)\) must be orthogonal to the tangent space. Since the tangent space is orthogonal to each of the constraint gradients \(\nabla h_a(x_\star)\), the gradient of \(f\) must be a linear combination of the \(\nabla h_a(x_\star)\), i.e. there exist multipliers \(\nu_a \in \mathbb{R}\) such that \(\nabla f(x_\star) = \sum_{a=1}^r \nu_a \, \nabla h_a(x_\star)\). This is because for any linear subspace \(V\) of \(\mathbb{R}^d\), we have that \((V^\perp)^\perp = V\). Equivalently, after changing the signs of the coefficients, we have that
\[ \textcolor{green}{ \nabla f(x_\star) + \sum_{a=1}^r \nu_a \, \nabla h_a(x_\star) =0} \tag{1}\]
for some \( \textcolor{green}{\nu_a \in \mathbb{R}}\). This is the whole derivation of Lagrange multipliers for equality constraints: at an optimum, the objective gradient has no tangent component.
Inequality constraints
Now, we can do more or less the same thing for inequality constraints, except that the geometry is a little more complicated. Consider \(m \geq 1\) smooth inequality constraints \(g_i(x)\leq 0\). The feasible set is now a manifold whose boundary is described by the active constraints, i.e. those for which \(g_i(x_\star)=0\). The tangent space is now replaced by the tangent cone, which locally looks like a half-space. Consider a local minimum \(x_\star\) and the set of active constraints \(\mathcal{A}(x_\star) = \{i: g_i(x_\star)=0\}\). Exactly the same argument as for equality constraints shows that \(\nabla f(x_\star)\) must be a linear combination of the active constraint gradients \(\nabla g_i(x_\star)\). Nevertheless, the coefficients are not arbitrary since the feasible set is a cone, not a linear space. Since the inequality constraints are given by \(g_i(x)\leq 0\), this means that if one follows the direction \(-\nabla g_i(x_\star)\), one is moving into the feasible region and consequently, to first order, the objective function should be increasing since we assumed that \(x_\star\) is a local minimum. This means that \(\nabla f(x_\star)\) must be a linear combination of the active constraint gradients \(\nabla g_i(x_\star)\) with non-positive coefficients. The non-active constraints do not contribute since the span of the active constraint gradients is already describing all the available directions. Assuming that there are also \(r\) equality constraints, we have that the first-order condition at a local minimum \(x_\star\) is \(\nabla f(x_\star) + \sum_{a=1}^r \nu_a \, \nabla h_a(x_\star) + \sum_{i \in \mathcal{A}(x_\star)} \lambda_i \, \nabla g_i(x_\star) =0\) with coefficients \(\nu_a \in \mathbb{R}\) and \( \textcolor{green}{\lambda_i \geq 0}\). It is more convenient to write the sum over all constraints instead of only the active ones, with the understanding that \(\lambda_i=0\) for inactive constraints. This are the so-called complementary slackness condition and means that, at a local minimum \(x_\star\) we have:
\[ \textcolor{green}{ \nabla f(x_\star) + \sum_{a=1}^r \nu_a \, \nabla h_a(x_\star) + \sum_{i=1}^m \lambda_i \, \nabla g_i(x_\star) = 0} \tag{2}\]
where \(\nu_a \in \mathbb{R}\) and \( \textcolor{green}{\lambda_i \geq 0}\) and:
\[ \textcolor{green}{\lambda_i \, g_i(x_\star) = 0.} \tag{3}\]
In words, this means that either the constraint \(g_i\) has some slack, in which case its multiplier \(\lambda_i\) vanishes, or the multiplier is non-zero, in which case the constraint is active.
The Lagrangian
It can quickly becoming tiresome to keep writing Equation 2 so it is convenient to introduce the Lagrangian function
\[ \mathcal{L}(x,\lambda,\nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{a=1}^r \nu_a h_a(x). \]
The discussion proves that at a local minimum we have:
\[ \nabla_x \mathcal{L}(x_\star,\lambda,\nu)=0. \]
Together with the satisfaction of the constraints and complementary slackness conditions. These are ususally called the Karush–Kuhn–Tucker (KKT) conditions and reads:
\[ \textcolor{green}{ \begin{aligned} g_i(x_\star)&\leq 0, & h_a(x_\star)&=0,\\ \lambda_i&\geq 0, & \lambda_i g_i(x_\star)&=0, \end{aligned} } \tag{4}\]
Naturally, as in the unconstrained case and as the reasoning above clearly shows it, these are only necessary conditions for a local minimum and absolutely no guarantee that a point satisfying them is indeed a local minimum, and even less a global minimum. Naturally and as expected, a lot changes if the problem has some convexity structure, which is the topic of the next section.
A small pathology
We have quietly assumed that the gradients of the constraints describe the local geometry of the feasible set. Above, we simply said that the tangent space is orthogonal to the constraint gradients, but this is not always true and it’s worth giving a small example of what can go wrong. Consider the problem of minimizing \(f(x)=x\) subject to the constraint \(g(x)=x^2\leq 0\). In that case, the feasible set is simply \(\{0\}\), the global minimum is certainly \(x_\star=0\), and the gradient of the constraint vanishes at the optimum so that the KKT conditions \(\nabla f(0) = 1 + \lambda \cdot 0 = 0\) cannot be satisfied. What went wrong is that the constraint \(g(x)=x^2\leq 0\) is degenerate and the gradient of the constraint does not faithfully describe the local geometry of the feasible set. This shows that one has to be a bit careful when using the KKT conditions and a few “regularity” conditions are certainly needed to guarantee that the KKT conditions are indeed necessary for a local minimum. These are called constraint qualifications and intuitively ensure that the gradients of the constraints faithfully describe the local geometry of the feasible set. The simplest and most common constraint qualification is the linear independence constraint qualification (LICQ), which simply requires that the gradients of the active constraints are linearly independent. This is a very mild condition and is satisfied in most practical problems. Quite nicely, in the case where all constraints are affine then constraint qualifications are automatically satisfied.
The convex case
It is standard that, in the unconstrained case, a stationary point of a convex function is a global minimum. As we will see, this is also true in the constrained case. Consider the convex program: \[ \begin{aligned} \textrm{minimize} \qquad & f(x),\\ \textrm{subject to} \qquad & g_i(x)\leq 0,\\ & Ax=b, \end{aligned} \tag{5}\]
where \(f\) and the functions \(g_i\) are convex. Indeed, in that case the feasible set is convex (note that we need the equality constraints to be affine for this to be true, not just convex). The Lagrangian is then also convex in \(x\) for any choice of multipliers \(\lambda \geq 0\) and \(\nu\):
\[ \mathcal{L}(x,\lambda,\nu) = f(x)+\sum_i \lambda_i g_i(x)+\nu^\top(Ax-b). \]
Now, assume that a feasible point \(x_\star\) and multipliers \((\lambda_\star,\nu_\star)\) satisfy the KKT conditions Equation 4. Since the Lagrangian is convex in \(x\), stationarity \(\nabla_x \mathcal{L}(x_\star,\lambda_\star,\nu_\star) = 0\) implies that the function \(x \mapsto \mathcal{L}(x,\lambda_\star,\nu_\star)\) has a global minimum at \(x_\star\):
\[ \mathcal{L}(x_\star,\lambda_\star,\nu_\star) \leq \mathcal{L}(x,\lambda_\star,\nu_\star) \]
for every \(x\). Furthermore, \(f(x_\star) = \mathcal{L}(x_\star,\lambda_\star,\nu_\star)\) by complementary slackness and feasibility. Even better, for any feasible \(x\), we have that \(\mathcal{L}(x,\lambda_\star,\nu_\star) \leq f(x)\) since \(\lambda_\star \geq 0\) and \(g_i(x)\leq 0\). Combining these two inequalities gives:
\[ \textcolor{green}{f(x_\star) = \mathcal{L}(x_\star,\lambda_\star,\nu_\star) \leq \mathcal{L}(x,\lambda_\star,\nu_\star) \leq f(x)} \]
for every feasible \(x\). Thus, in a convex problem, the KKT conditions are sufficient for global optimality:
\[ \textcolor{green}{\textrm{KKT} \quad \Longrightarrow \quad \textrm{global optimum}.} \tag{6}\]
No constraint qualification is needed for this direction. Convexity alone turns the local balance of gradients into a global certificate of optimality.
The converse direction is more delicate. We would like to say that, under some conditions, a global optimum necessarily admits KKT multipliers. Naturally, the discussions of the constraint \(x^2\leq 0\) above shows that this is not true in general and we need some constraint qualification conditions as described above. For a convex problem, the standard convenient condition is Slater’s condition: there exists a feasible point \(\bar x\) that lies strictly inside the feasible set, i.e. such that
\[ \textcolor{blue}{ \textrm{Slater:} \qquad \qquad A\bar x=b \quad \text{and} \quad g_i(\bar x)<0 \; \text{for all } \; 1 \leq i \leq m. } \]
Note that Morton Slater is not the same person as John Slater for the famous Slater determinant in quantum mechanics, but I have not been able to find much information about Morton Slater. Under Slater’s condition, an optimal point necessarily admits KKT multipliers. Combining this with Equation 6 gives the useful equivalence
\[ \textcolor{green}{ \textrm{global optimum} \quad \Longleftrightarrow \quad \textrm{KKT}.} \tag{7}\]
The two ingredients have different jobs. Convexity makes KKT sufficient; good constraint geometry makes KKT necessary.
The dual problem
The discussion above hints at a more general principle. For multipliers \(\lambda \geq 0\) and arbitrary \(\nu\), the dual function is defined as the infimum of the Lagrangian over \(x\):
\[ q(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu). \]
Furthermore, for any feasible \(x\) and \(\lambda_i\geq 0\), we have \(\mathcal{L}(x,\lambda,\nu) \leq f(x)\) Consequently, the dual function is always a lower bound on the optimal value of the original problem:
\[ q(\lambda,\nu) \leq f(x) \]
for every feasible \(x\). And no convexity is needed for this inequality to hold. Taking the infimum over all feasible \(x\) gives that, for any choice of dual-feasible multipliers \(\lambda \geq 0\) and \(\nu\), the dual function is a lower bound on the optimal value of the original problem:
\[ \textcolor{green}{q(\lambda,\nu) \leq p_\star} \]
where \(p_\star\) is the optimal value of the original problem. Naturally, one can try to find the best lower bound by maximizing the dual function in order to get as close as possible to the optimal value of the original problem. This gives the dual problem:
\[ d_\star = \sup_{\lambda\geq 0,\,\nu} q(\lambda,\nu) \]
and, as described above, the optimal value of the dual problem is always a lower bound on the optimal value of the original problem \(d_\star\leq p_\star\). This is called weak duality, and it does not require convexity. Naturally, convexity gives a stronger result, as we will see in moment. For example, one can show that in the convex case and under Slater’s condition,
\[ \textcolor{green}{d_\star=p_\star.} \tag{8}\]
The best lower bound produced by the dual problem touches the primal optimum exactly. This is strong duality and the proof is a relatively simple argument that boils down to exhibiting a supporting hyperplane to a convex set.
Proof:
There is a simple geometric picture behind this result. Consider the set \(\mathcal{C}\) of all \((u,v,t)\) such that there exists some \(x\) with
\[ g_i(x)\leq u_i, \quad Ax-b=v, \quad f(x)\leq t. \]
Under convexity of \(f\) and the \(g_i\), this set is convex. Furthermore, the intersection of \(\mathcal{C}\) with the plane \(P=\{(u,v,t): u=0, v=0\}\) is the set of all \((0,0,t)\) such that there exists a feasible \(x\) with \(f(x)\leq t\). This means that the optimal value \(p_\star\) is the infimum of \(t\) such that \((0,0,t)\in \mathcal{C}\). This means that the point \((0,0,p_\star)\) lies on the boundary of \(\mathcal{C}\). This means that there exists a supporting hyperplane \(H\) to \(\mathcal{C}\) at this point, i.e.
\[ H: \{ (u,v,t): \sum_i \lambda_i u_i + \sum_j \nu_j v_j + \mu t = \mu p_\star\} \]
such that \(\mathcal{C}\) lies entirely on one side of \(H\). This means that for every \((u,v,t)\in \mathcal{C}\), we have \(\sum_i \lambda_i u_i + \sum_j \nu_j v_j + \mu t \geq \mu p_\star\). Now, one can easily see that necessarily \(\mu \geq 0\) and \(\lambda_i \geq 0\) for all \(1 \leq i \leq m\) by definition of \(\mathcal{C}\). The interesting question is whether \(\mu\) can be zero. If \(\mu > 0\) then we can normalize and assume \(\mu=1\) and the inequality reads \(\sum_i \lambda_i u_i + \sum_j \nu_j v_j + t \geq p_\star\) for all \((u,v,t)\in \mathcal{C}\). This means that for every \(x\) we have \(f(x) + \sum_i \lambda_i g_i(x) + \sum_j \nu_j (Ax-b) \geq p_\star\) and in particular, taking the infimum over \(x\) gives \(q(\lambda,\nu) \geq p_\star\). Since we already know that \(q(\lambda,\nu) \leq p_\star\), this gives \(d_\star = q(\lambda,\nu) = p_\star\) and strong duality holds. Now, let us show that the Slater condition ensures that \(\mu\) cannot be zero. To see this, note that if \(\mu=0\) then \(\sum_i \lambda_i u_i + \sum_j \nu_j v_j \geq 0\) holds for all \((u,v,t)\in \mathcal{C}\). But the Slater condition ensures that there exists a strictly feasible point \((\bar u, \bar v, \bar t)\in \mathcal{C}\) with \(\bar u_i < 0\) and \(\bar v_j = 0\) for all \(1 \leq j \leq p\) and \(1 \leq i \leq m\). This means that \(\sum_i \lambda_i \bar u_i + \sum_j \nu_j \bar v_j = \sum_i \lambda_i \bar u_i \leq 0\). Furthermore, one can easily see that the coefficients \(\lambda_i\) cannot be all zero so that in fact \(\sum_i \lambda_i \bar u_i < 0\), which is a contradiction. In conclusion, Slater’s condition ensures that \(\mu > 0\) and after normalization, the corresponding hyperplane gives a dual lower bound equal to \(p_\star\).In conclusion, the whole story may be summarized as follows. Equality constraints contribute a linear space of normals; active inequalities contribute a cone of outward normals. The Lagrangian records the balance of these normals with the objective gradient. Constraint qualifications ensure that the normals describe the true feasible geometry. Convexity then turns this local balance into a global certificate, while duality turns the same multipliers into an exact lower bound on the optimum.