Constraints make a stationary point of the objective alone an unreliable guide. A constraint can prevent movement in a direction that would otherwise decrease the objective. Lagrange multipliers encode this obstruction, while duality turns suitable multipliers into a lower bound on every feasible objective value. When the bound meets a feasible value, optimality is proved.
The Lagrangian and weak duality
Consider minimizing over subject to for and for .
Definition 2.1.1
(Lagrangian, dual function and dual problem)
The Lagrangian is
The dual function is ; it can be . The dual problem maximizes over and unrestricted , with optimal value ; the primal infimum is .
Theorem 2.1.2
(Weak duality)
For any primal feasible and any with arbitrary , . Consequently , with extended-real values interpreted whenever the bounds are defined.
Proof
(Feasibility makes every added term nonpositive)
For feasible , the equality terms vanish and because and . Consequently . Taking the infimum over feasible and the supremum over dual-feasible multipliers gives .
If a feasible and dual-feasible have equal values, each is optimal even without convexity. The statement compares bounds; it does not assert that either optimum is attained. Strong duality means equality of optimal values, not automatically equality of particular trial values. A numerical dual iterate can be feasible but still give a poor bound. Conversely, a very good objective value at an infeasible point is not a primal upper bound at all. When both a feasible primal value and a dual value are available, their difference is a nonnegative duality gap. A small gap bounds how far each value is from the common optimum whenever a finite optimum lies between them.
The sign convention matters. For a maximization problem, or when inequalities are written , the corresponding multiplier signs must be changed consistently. Multipliers are not arbitrary penalties: choosing a negative in the present convention can reverse the lower-bound argument.
KKT conditions
Definition 2.1.3
(Karush–Kuhn–Tucker conditions)
For differentiable functions on an open domain, the KKT conditions at with multipliers are:
- Primal feasibility: and .
- Dual feasibility: .
- Complementary slackness: for each .
- Stationarity: .
Complementary slackness says a strictly inactive inequality has zero multiplier; an active inequality can also have zero multiplier. It does not say every active constraint has a positive multiplier. KKT conditions are not automatically necessary at every constrained optimum: a constraint qualification is needed.
Theorem 2.1.4
(KKT sufficiency for a convex problem)
On an open convex domain, let and all be differentiable and convex, and all affine. Any feasible point and multipliers satisfying stationarity, multiplier nonnegativity and complementary slackness are primal and dual optimal.
Proof
(A chain of one inequality, one minimization and one equality)
Because , each is convex and each is affine, the function is convex and differentiable on the open domain. Stationarity says its gradient vanishes at , so by the first-order characterization of convexity minimizes it, and . Complementary slackness and feasibility give . Hence every feasible obeys
so is primal optimal. For any dual-feasible , weak duality gives , so the multipliers are dual optimal.
Proof X-ray
What each link of the chain uses
The displayed chain makes the certificate transparent. The first inequality uses only feasibility of and the sign ; it is weak duality at a single point. The middle inequality is where convexity and differentiability are used: they promote the stationarity equation to global minimization of the Lagrangian, which for a nonconvex problem could identify a maximum or a saddle instead. The final equality uses complementary slackness together with ; without it the chain would only give , a weaker bound. No constraint qualification appears anywhere: qualifications concern the existence of multipliers, while this proof starts from multipliers already in hand.
Notice that this theorem does not require Slater's condition. Slater is one useful route to the existence of multipliers at a minimizer; once a KKT certificate has been found, the sufficiency proof needs only the listed convexity and differentiability assumptions. Separating the two directions avoids the mistaken conclusion that a failure of strict feasibility invalidates an already verified certificate.
The converse direction needs a hypothesis, and a concrete sufficient form of Slater's condition is the following.
Theorem 2.1.5
(Slater's condition gives KKT multipliers)
Let be open and convex, and every be differentiable and convex on , and the be affine. Suppose there is a point in satisfying all equalities and strictly satisfying every inequality, and that the primal minimum is finite and attained in . Then strong duality holds, optimal multipliers exist, and every primal minimizer has KKT multipliers.
Its separation proof is given in the unit on separation, subgradients and strong duality. Strict feasibility is a hypothesis to check, not a conclusion from the existence of an optimum. More refined versions weaken strictness for affine inequalities and use relative interiors; this section uses the stronger condition just stated.
Worked example: a dual certificate
Worked example 2.1.6
(A KKT point and its dual function)
Minimize subject to . The Lagrangian is . Stationarity gives and . At an active constraint, , so and . This point is feasible, , and complementarity holds. Convexity makes these KKT conditions sufficient.
The same conclusion can be read directly from the dual. Substituting the minimizer of gives
The maximum is , equal to the primal value. A feasible point such as is strictly feasible, so Slater's condition also holds.
The multiplier is the slope of the optimal value with respect to a small relaxation of this right-hand side, with sign reversed under this convention, when the value function is differentiable; it is not generally the derivative without that extra qualification.
Why qualification matters
The Slater hypothesis cannot simply be dropped, even for a convex problem.
Counterexample mode
A convex problem whose minimizer has no multipliers
Claim: every minimizer of a differentiable convex problem has KKT multipliers. Minimize subject to ; both functions are convex. The only feasible point is , hence it is optimal. Yet stationarity would require at , that is , which is impossible for every multiplier. The feasible set has no strictly feasible point, and the constraint gradient vanishes at the optimum. The repaired statement is the Slater theorem above, whose strict-feasibility hypothesis fails here. This example does not disprove KKT sufficiency; it shows why necessity needs assumptions.
Equality constraints and their multipliers
An equality is different from an inequality: its multiplier has no sign restriction. The reason is visible in the weak-duality proof. At every feasible point , so vanishes for either sign of . Replacing an equality by two opposite inequalities is possible algebraically, but can introduce redundant multipliers and makes their interpretation less direct.
Worked example 2.1.7
(Equality-constrained projection)
Minimize subject to . Write . Stationarity gives and , so . Feasibility then gives and . The negative multiplier is allowed because the constraint is an equality. The objective is convex and the equality affine, so KKT certifies the global minimum . Alternatively, on the feasible line. The two proofs arrive at the same lower bound by different routes.
Worked example 2.1.8
(An active constraint with zero multiplier)
Minimize subject to . The unique optimum is , where the constraint is active. Stationarity gives , hence . All KKT conditions hold. Activity alone therefore does not imply a positive multiplier. The feasible set prevents motion to the right, but the unconstrained optimizer already lies at the boundary, so there is no first-order improvement to be gained by relaxing this particular constraint.
Worked example 2.1.9
(A dual function can be unbounded below)
Minimize subject to . For , the Lagrangian is . Its infimum over is unless ; at it is . Thus the dual maximum is , achieved at . The primal point has value , giving a matching certificate. The calculation shows why minimizing over its whole domain, rather than substituting only feasible , is essential to the dual function.
Sensitivity and a sign check
Concept lensAnalytic
A multiplier as a derivative of the optimal value
Suppose a scalar right-hand side appears in a constraint , written as . Keeping an optimal multiplier fixed while changing changes the Lagrangian by . Under conditions that make the optimal-value function differentiable and justify the envelope formula, . The multiplier is thus also a rate: the marginal decrease of the optimal value per unit relaxation of the constraint. The negative sign is natural: increasing enlarges the feasible set, so the minimum cannot increase. This monotonicity remains true without differentiability, although a particular derivative formula may fail.
For the quadratic example above, replacing by gives the active solution when . Its optimal value is , and the multiplier is . Differentiating the value gives . For , the unconstrained minimizer is feasible, the value is zero, and the multiplier is zero. The calculation makes clear both the local interpretation of the multiplier and the change in the active set.
Choosing and checking candidates
For a small problem, list plausible active sets, solve stationarity together with their active equalities, and then check every inequality and multiplier sign. An algebraic solution that violates either condition is not a KKT point. Inactive constraints require zero multipliers, but the converse need not hold. Finally, use convexity for sufficiency or another argument for a nonconvex problem. KKT stationarity can identify a maximum or saddle in a nonconvex problem, so an answer cannot end merely with a solved multiplier equation.
Constructing a dual without guessing the answer
The order of operations matters. First state the primal domain and put inequalities in the chosen sign convention. Next form using nonnegative inequality multipliers and unrestricted equality multipliers. For fixed multipliers, minimize over the entire domain, retaining the possibility that the infimum is . Only then maximize the resulting function subject to multiplier feasibility. If the minimizer of does not exist, the infimum still defines ; replacing it with an unjustified stationary solution can give a false dual value.
To see the role of curvature, consider subject to . For , . Completing the square gives , so . The maximizing multiplier is and . The primal feasible point has value , providing a global certificate. The stationary point is the global minimizer of because its quadratic coefficient is positive, not simply because the derivative vanishes.
A dual function is concave even when the primal problem is nonconvex. For two multiplier pairs and , the Lagrangian is affine in the multipliers, so
The inequality follows because each term inside the infimum is bounded below by its corresponding infimum. Thus maximizing the dual is a concave maximization problem over the convex multiplier domain. Concavity does not by itself promise a finite optimum or zero gap; those are separate questions.
Yes: without convexity the dual optimum can lie strictly below the primal optimum, even in a one-variable problem.
A natural next question
Can the best dual bound fall strictly short of the optimum?
Yes: without convexity the dual optimum can lie strictly below the primal optimum, even in a one-variable problem.
Minimize over the nonconvex domain subject to . The only feasible point is , so . For ,
whose maximum is . The gap is positive, so no multiplier certifies the optimum. Convexity together with Slater's condition is one sufficient way to rule such gaps out.
Common mistakes
A multiplier and a feasible candidate must be checked together. Weak duality always supplies a bound, but equality of primal and dual optimal values is an additional claim, and KKT conditions alone do not certify a nonconvex stationary point as globally optimal.
Common mistake
(Expecting every active constraint to have a positive multiplier)
An active constraint does not force a positive multiplier: in the problem subject to the constraint is active and . A negative multiplier, on the other hand, is invalid for a constraint written as in this minimization convention.
Common mistake
(Minimizing the Lagrangian only over feasible points)
A dual function is an infimum over the full domain, not over the primal feasible set. For subject to , restricting to feasible at would give the value instead of the correct .
Common mistake
(Mixing sign conventions)
The choice of a sign convention does not change the underlying problem, but it changes the formulas in its certificate. Writing as gives a nonnegative multiplier multiplying . If instead the same inequality is written as , retaining the same multiplier sign in the same Lagrangian would produce an upper-bound term at feasible points. Check the weak-duality inequality before interpreting any multiplier.
Summary
The Lagrangian turns constraints into candidate lower bounds. A primal feasible point and a dual feasible multiplier with matching values certify global optimality. In a differentiable convex problem, the KKT conditions produce such a certificate; strict feasibility under the stated hypotheses guarantees that the certificate exists at an attained optimum. These are sufficient tools for the examples here, not a complete account of duality or all possible constraint qualifications.
Exercises
Quick check
(Minimize subject to and give a KKT certificate.)
The unconstrained minimizer is infeasible, so try the active constraint.
Solution · Answer
The minimizer is . Stationarity at gives ; feasibility, nonnegativity and complementarity hold. Convexity certifies the answer.
Quick check
(Minimize subject to . Is its constraint active, and what is its multiplier?)
Compare the unconstrained minimizer with the bound.
Solution · Answer
The minimizer is , the inequality is strict there, so the constraint is inactive, and complementarity gives .
Quick check
(For the problem of minimizing subject to , calculate for and verify equality of primal and dual values.)
Minimize over all real .
Solution · Answer
Minimize over to get and . Its maximum on is at , equal to the primal value .