Introduction
Constrained optimization studies how to minimize (maximize) an objective function while satisfying one or more constraints. Instead of searching freely over the entire space, the solution must lie in the feasible set defined by the constraints, such as an equality constraint $C(x)=0$ or an inequality constraint $G(x) \leq 0$. The Lagrange multiplier method provides a systematic way to find candidate optima by balancing the gradient of the objective against the gradients of the constraints. In this tutorial, we give a brief introduction to the Lagrange multiplier method. We will start with a simple equality-constrained problem and then move on to inequality constraints.
Equality constraint
Problem definition
Let's start from a very simple optimization problem:
\[ \min_x f(x) \qquad s.t. \quad C(x)=0. \]Minimizing $f(x)$ alone is not sufficient because the resulting minimum may lie outside the feasible set. Instead, we construct the Lagrangian:
\[ L(x,\lambda)=f(x)+\lambda C(x). \]where $\lambda$ is called a multiplier or dual variable.
At a regular local optimum, the solution must satisfy the following two first-order conditions:
\[ \frac{\partial L}{\partial \lambda}=C(x)=0, \tag{1} \]which means that the constraint must be satisfied exactly at the optimum.
And
\[ \frac{\partial L}{\partial x} = \frac{\partial f(x)}{\partial x} + \lambda \frac{\partial C(x)}{\partial x} = 0. \tag{2} \]which means that, at a regular constrained optimum, there is no downhill direction along the feasible set.
Equivalently, the gradient of the objective is balanced by the gradient of the constraint. Intuitively, the objective tends to move downhill along $-\nabla f$, while the constraint provides a reaction that prevents motion away from the feasible set.
Geometric intuition
This is better illustrated by the following figure.
Let's define the objective and constraint in 2D as $f(x,y)=x^2+y^2$ and $C(x,y)=1-x-y=0$, respectively. In the figure above, the black line represents the constraint. The green and purple lines are iso-lines of $f=0.5$ and $f=2.5$, respectively. This constrained optimization problem has a single global minimum at $(0.5,0.5)$, where $f(0.5,0.5)=0.5$.
Now suppose we do not know where the optimum is and choose an initial guess randomly, say point $A$. We can compute the negative gradient, $-\nabla f$ (the purple arrow), which points in the direction of steepest descent. It can be decomposed into two components: one normal to the constraint curve and one tangent to the constraint curve. The crucial part is the latter. As long as a gradient component exists along the constraint tangent, we can move along the curve to reach a lower function value until we arrive at the optimum, i.e., point $B$. At the optimum, $\nabla f$ and $\nabla C$ are parallel or antiparallel. They do not need to have the same magnitude. The multiplier $\lambda$ accounts for the relative magnitude and sign and enforces $\nabla f=-\lambda\nabla C$.
Feasible set
The feasible set of an equality constraint is a curve in 2D and a surface in 3D. Consider a 2D constraint:
\[ C(x,y)=0. \]Take a Taylor expansion about the current feasible point $(x,y)$:
\[ C(x+dx,y+dy)=C(x,y)+\nabla C \cdot d\mathbf{x}+O(\|d\mathbf{x}\|^2). \]where
\[ d\mathbf{x} = \begin{bmatrix} dx \\ dy \end{bmatrix}. \]represents a small step from $(x,y)$. To maintain feasibility, we require
\[ C(x+dx,y+dy)=0. \]Therefore,
\[ dC=C(x+dx,y+dy)-C(x,y) \approx \nabla C\cdot d\mathbf{x} =0. \]that is
\[ \nabla C\cdot d\mathbf{x}=0. \]Therefore, if $\nabla C\neq 0$, $\nabla C$ is perpendicular to $d\mathbf{x}$, which lies along the tangent direction of the constraint curve.
Inequality constraint
Solving an inequality-constrained optimization problem is very similar to solving an equality-constrained problem. However, there are two important differences.
First, an inequality constraint defines a feasible region rather than just a constraint surface. Second, an inequality constraint can be inactive, whereas an equality constraint is always active.
Consider the same objective function $f(x,y)$, but replace the equality constraint with the inequality constraint
\[ g(x,y)=1-x-y\leq 0. \]The optimization problem becomes
\[ \min_{x,y} f(x,y) \qquad \text{s.t.}\quad g(x,y)\leq 0. \]The Lagrangian is
\[ L(x,y,\mu)=f(x,y)+\mu g(x,y),\quad \mu\geq 0 \]It is a standard convention to write inequality constraints in the form
\[ g(x)\leq 0. \]Under this convention, the corresponding Lagrange multiplier must satisfy
\[ \mu\geq 0. \]The reason for this requirement will become clear later.
The shaded half-space, including its boundary, is the feasible set.
When the solution lies strictly inside the feasible region,
\[ g(x,y)<0, \]the constraint is inactive. In this case, the corresponding multiplier is zero:
\[ \mu=0. \]Therefore, the constraint has no influence on the optimum.
On the boundary,
\[ g(x,y)=0, \]the constraint becomes active and behaves locally like an equality constraint.
However, unlike an equality constraint, an inequality constraint is one-sided.
The constraint gradient $\nabla g$ points in the direction of increasing $g$, i.e., locally toward the infeasible side. Therefore, the corresponding mechanical constraint reaction is
\[ -\mu \nabla g. \]which points toward the feasible side.
Hence,
\[ \boxed{ \mu\geq 0 \quad\Rightarrow\quad -\mu\nabla g \text{ can only point toward the feasible side} } \]The inequality constraint can therefore prevent the solution from moving into the infeasible region, but it cannot pull the solution in the opposite direction. When the unconstrained descent direction points toward the infeasible region, an inequality constraint can only push, whereas an equality constraint can effectively push or pull because its multiplier is unrestricted in sign.
KKT condition
In a general optimization problem, equality and inequality constraints may coexist. Consider the following problem:
\[ p^*=\min_x f(x) \tag{3} \]$s.t.$
\[ g_{i}(x)\leq 0, \qquad i=1,\dots,m \]and
\[ h_{j}(x)= 0, \qquad j=1,\dots,p \]The Lagrangian is defined as:
\[ L(x,\nu,\mu) = f(x) + \sum_{j=1}^{p}\nu_j h_j(x) + \sum_{i=1}^{m}\mu_i g_i(x). \]where $\mu_i$ and $\nu_{j}$ are Lagrange multipliers. The vectorized form is:
\[ L(x,\nu,\mu) = f(x)+\nu^T h(x)+\mu^T g(x). \]At a local optimum $x^{*}$ satisfying an appropriate constraint qualification, the solution must satisfy the Karush–Kuhn–Tucker conditions, or KKT conditions for short. There are four conditions.
1) Primal feasibility
The solution itself must satisfy the original constraints, i.e.,
2) Dual feasibility
For an inequality constraint,
This prevents the inequality constraint from pulling the optimization into the infeasible set. For an equality constraint, there is no restriction on $\nu^*_{j}$.
3) Complementary slackness
This condition is specific to inequality constraints:
This condition encodes whether each inequality is active or inactive. If the constraint is inactive, $g_{i}(x^*)<0$, then complementary slackness requires $\mu^*_i=0$, so the constraint applies no reaction. If the constraint is active, $g_i(x^*)=0$, then $\mu_i^*$ may be positive or zero.
4) Stationarity This is the constrained analogue of $\nabla f=0$ in unconstrained optimization.
\[ \nabla_x L(x^*,\nu^*,\mu^*)=\nabla f(x^*) + J_h(x^*)^T\nu^* + J_g(x^*)^T\mu^* =0. \]In other words, the "objective force", "equality constraint reaction force", and "inequality constraint reaction force" balance at the optimum.
Solving the constrained problem defined above is nontrivial, especially with inequality constraints, because the reaction is unilateral and the active constraints are not known in advance. Several methods can be used to solve it, e.g., the active-set method, interior-point method, SQP, and augmented Lagrangian. An introduction to these methods is beyond the scope of this tutorial.
Reformulate the optimization as a saddle-point solution
The constrained optimization problem can also be reformulated compactly as:
\[ p^*=\min_x\sup_{\substack{\mu\geq0\\ \nu}}L(x,\nu,\mu) \tag{4} \]where "sup" stands for "supremum", the least upper bound.
\[ \sup_{\substack{\mu\geq0\\ \nu}}L(x,\nu,\mu) \]means taking the least upper bound of the Lagrangian while keeping $x$ fixed. The outer operator $\min$ then minimizes this upper bound. This is a min-max representation of the constrained problem.
If $x$ is feasible, then $h(x)=0$ and $g(x)\leq0$. Therefore,
\[ \sup_{\substack{\mu\geq0\\ \nu}}L(x,\nu,\mu)=f(x), \]because the equality term is zero and the supremum of $\mu^Tg(x)$ over $\mu\geq0$ is attained at $\mu=0$ and is equal to zero.
If $x$ is infeasible, then at least one equality constraint has $h_j(x)\neq0$ or one inequality constraint has $g_i(x)>0$. In the first case, $\nu_j$ can be taken to an arbitrarily large magnitude with the appropriate sign; in the second case, $\mu_i\to+\infty$. Therefore, the supremum becomes $+\infty$.
The outer minimization then becomes
\[ \min_x\sup_{\substack{\mu\geq0\\ \nu}}L(x,\nu,\mu) = \min_x \begin{cases} f(x), & h(x)=0,\ g(x)\leq0,\\ +\infty, & \text{otherwise}. \end{cases} \]In other words, the inner maximization acts like an indicator penalty for infeasibility: feasible points retain their original objective value $f(x)$, whereas infeasible points are assigned infinite cost. Consequently, the outer minimization automatically ignores all infeasible points.
This figure shows a saddle-like Lagrangian surface. Under suitable conditions, the primal-dual optimum forms a saddle point of the Lagrangian. Note that Eq.4 has a more general notation:
\[ p^*=\inf_x\sup_{\substack{\mu\geq0\\ \nu}}L(x,\nu,\mu) \tag{5} \]where "inf" stands for "infimum", the greatest lower bound. Eq.4 uses $\min$, which assumes that the minimum is attained, whereas $\inf$ does not require the greatest lower bound to be attained.
Primal problem and dual problem
The problem discussed so far is called the primal problem. The dual function is defined as
\[ q(\mu,\nu)=\inf_x L(x,\nu,\mu). \]By reversing the order of optimization in Eq.5, we obtain the dual problem:
\[ d^*=\sup_{\substack{\mu\geq0\\ \nu}}q(\mu,\nu) = \sup_{\substack{\mu\geq0\\ \nu}}\inf_xL(x,\nu,\mu). \tag{6} \]The dual problem provides a lower bound on the optimal value of the primal problem. For any primal-feasible $x$ and dual-feasible $\mu\geq0$,
\[ q(\mu,\nu) = \inf_xL(x,\nu,\mu) \leq L(x,\nu,\mu) \leq f(x). \]Taking the infimum over all primal-feasible $x$ and then the supremum over dual-feasible $(\mu,\nu)$ gives
\[ d^*\leq p^*, \]which is called weak duality. If $d^{*}=p^{*}$, the problem has strong duality.