Motivation
A lower bound proves an optimization result only if we know why it is valid and whether it can reach the true minimum. Convex geometry supplies that reason. A hyperplane can separate a point from a convex set, while a subgradient is a supporting slope of a convex function. Applied to the set of attainable constraint violations and objective values, a supporting hyperplane becomes a Lagrange multiplier. We will derive this connection under explicit finite-dimensional assumptions and examine what changes when those assumptions fail.
The geometry is useful even for nonsmooth objectives. The absolute value has no ordinary derivative at zero, yet it has supporting slopes there and a clear minimizer. A subgradient records all such slopes. In contrast, a multiplier's interpretation as a derivative of an optimal value requires differentiability of that value function; without it, the correct conclusion is an inequality.
Definitions
Definition 5.1.1
(Convex set, subgradient and subdifferential)
A nonempty set is convex if it contains each segment between its points. For a finite convex function on an open convex set , a vector is a subgradient at if
The set of all such vectors is . Thus exactly when minimizes over . If is differentiable at , : the derivative supplies a subgradient, and testing a candidate along forces equality in every direction. For , the subdifferential at zero is .
Definition 5.1.2
(Euclidean projection)
For a point and closed nonempty convex , its Euclidean projection is the unique minimizer of over . Existence follows by restricting a minimizing sequence to a bounded ball and taking a convergent subsequence; uniqueness follows from strict convexity of squared distance. The projection inequality is for every , obtained by differentiating squared distance along the segment from to .
Theorem/Proposition
Theorem 5.1.3
(Strict separation from a closed convex set)
If is nonempty, closed and convex and , there is a nonzero vector and a scalar with for all .
Two auxiliary facts about open convex sets are used in the duality proof.
Lemma 5.1.4
(Open convex sets and their closures)
A nonempty open convex set satisfies .
Proposition 5.1.5
(Weak separation from an open convex set)
If a nonempty open convex set does not contain , there is a nonzero with for all .
With these tools the main duality theorem can be stated.
Theorem 5.1.6
(Slater strong duality with attained multipliers)
Let be open and convex; let be differentiable and convex on , and let be affine. Suppose there is with and for every . If the finite primal minimum is attained at , there exist and such that satisfy KKT, and the dual maximum equals .
The strict inequalities are a deliberately strong, easy-to-check form of Slater's condition. More general relative-interior formulations allow some affine inequalities without strictness. The conclusion says both that there is no gap and that dual multipliers attain the maximum. It does not follow merely from convexity or from the existence of a primal minimizer.
Proof sketch or proof idea
Separation from projection
Proof
(Projection gives the separator)
Take and . Since , . The projection inequality yields for every , whereas . Set . The supporting hyperplane is perpendicular to the shortest segment from to ; the strict gap is the squared distance. Closedness matters: if and , no linear functional can put a strict gap between and every point of .
Concept lensAnalytic
The separator as a subgradient of the distance function
Let , a convex function vanishing exactly on . For with , the vector is a subgradient of at : with , the projection inequality gives , so . For the left side is zero, which rearranges to . Strict separation is thus the subgradient inequality of read on the zero set.
Proof
(Approximating a simplex from inside)
First, an elementary lemma states that a nonempty open convex set equals . The inclusion is immediate. Conversely, if lies in the interior of the closure, choose a small simplex around contained in that interior. Approximate each vertex by a point of closely enough that remains in the interior of the new simplex. Convexity puts that simplex inside , so . This proof does not use separation.
Proof
(Weak separation by limits)
We also use the standard open-set separation consequence: if a nonempty open convex set excludes , a nonzero satisfies for all . For completeness, if , the projection argument applies to . If , take points tending to (boundary points admit such a sequence), separate each from , normalize the separating normals, and take a convergent subsequence on the unit sphere. Passing to the limit gives the weak separation. The lemma gives when , so these two cases cover all possibilities.
A supporting plane for perturbations
Proof
(Separating the strict upper set)
Restrict attention first to . Define the strict upper set
It is nonempty and open: the same witness works for a sufficiently small change of . It is convex because convex combinations of witnesses stay in , and convexity of each function preserves the strict upper inequalities. The point is outside : a witness would be primal feasible and have value below the minimum.
Separate this point from . Since is upward closed in each coordinate, a separating normal can be chosen as with , , and
For any , approach from above to obtain . If , the strictly feasible point gives for any nonzero , a contradiction. Thus ; divide by it and reuse the symbol . We have proved
At , feasibility gives the reverse inequality, so equality holds and for each . The function is convex and differentiable and is minimized by on the affine slice . Since is open, small motions along every vector in remain in . Hence is orthogonal to , so it lies in . Choose with .
The full Lagrangian is convex on and stationary at , so its infimum over is its value there, . Thus the constructed multipliers attain the dual value . Weak duality supplies the matching upper bound on every dual value. This completes the proof, including dual attainment, without assuming it at the start.
Why the signs in the perturbation proof are forced
Proof X-ray
What the strict upper set does
Three features of carry the argument. First, is upward closed, and this forces the signs: if the normal had a negative coefficient in some coordinate, moving that coordinate to inside would drive to , contradicting its lower bound. So , , and separation guarantees . Second, strict feasibility is used at exactly one step, to rule out : with , any nonzero gives . Once , normalizing it to one turns the remaining coordinates into multipliers; with only boundary feasible points an abnormal normal with can occur, as in the nonattained dual below. Third, the strict inequalities make open and convex without any closedness claim about the epigraph of the value function, which can fail: an infimum over a noncompact domain need not be attained, and a projection of a closed convex set need not be closed. Approaching from above converts the weak separation into the inequality on . The equality multipliers enter only afterwards, from the affine-slice gradient condition, so dual attainment is a consequence rather than an assumption.
Value functions and sensitivity
For inequality right-hand sides , define , taking when infeasible, and for define .
Proposition 5.1.7
(Multipliers are subgradients of the value function)
Suppose is finite and a pair with satisfies , as under the Slater hypotheses above. Then
so is a subgradient of the extended-valued convex function at zero. If is differentiable at zero, then .
Proof
(Weak duality for the perturbed problem)
If is infeasible, and there is nothing to prove. Otherwise let satisfy and . Since ,
Taking the infimum over such gives the inequality. If is differentiable at zero, dividing by small and by small gives for every .
The inequality remains meaningful for infeasible perturbations, and without differentiability distinct supporting slopes can exist. The convexity of follows by combining near-optimal feasible points for two perturbations and then letting their objective errors tend to zero.
Supporting slopes at a kink
The value function can be nondifferentiable even when its definition is simple. Consider . At zero, every satisfies for all , so . No ordinary derivative exists there: the one-sided slopes are zero and one. A single subgradient still gives a valid global lower bound, but it describes one support line, not a unique marginal effect. At a point of differentiability every supporting slope agrees with the gradient.
Subgradients can be combined directly. If and for convex functions on the same domain, adding their two defining inequalities gives . Conversely, a full sum rule identifying every subgradient of a sum requires its own regularity assumptions; the simple inclusion is all we need here. For instance, is : adding two shifts every supporting slope of by two, and subtracting the affine term proves the reverse inclusion.
Worked examples
Worked example 5.1.8
(Projection produces the separating line)
Let and . Its projection is and . Every point satisfies , whereas . The line supports and strictly separates .
Worked example 5.1.9
(A nonsmooth subdifferential)
For , the condition for every holds exactly for : testing positive and negative gives both bounds, and those bounds are sufficient. Therefore , certifying its minimum despite the missing ordinary derivative. At the subdifferential is , while at it is .
Worked example 5.1.10
(A concrete value-function corner)
Consider minimizing subject to and . Its value is . At both constraints are active. Writing them as and , stationarity requires with nonnegative multipliers. Every pair summing to one is optimal. The supporting slope for perturbations of the second constraint is , exactly the subdifferential of at zero. This explicit example shows that nonunique multipliers and a nondifferentiable value can occur even in a linear convex problem; neither indicates a duality gap.
The support inequality is valid for every perturbation, even if the chosen multiplier is not unique. It is often weaker away from the base point than the true value function. For the corner example, choosing slope zero gives the valid lower bound , while choosing slope one gives . Taking the maximum of the available affine lower bounds recovers exactly in this particular example; this equality is not automatic for a general optimization problem.
Common mistakes
The following errors are easy to make with separation and multipliers.
Common mistake
(Expecting strict separation from an open set)
If lies in the closure of an open convex set but not in , only weak separation is available. For the open unit disc and , the normal gives on the disc, but no with for all exists, because points of the disc approach .
Common mistake
(One multiplier does not make the value differentiable)
At a corner the subdifferential can contain many slopes. In the corner example above every is an optimal multiplier, while has no derivative at zero. Choosing one multiplier proves a supporting inequality, not a unique marginal effect.
Common mistake
(Slater is sufficient, not necessary)
A problem can have zero gap and an attained dual without a strictly feasible point. Minimizing subject to and has only the feasible point , so Slater fails; but equals when and otherwise, and attains the primal value .
Zero gap and dual attainment are two different conclusions, and the theorem asserts both.
Counterexample mode
Equal values do not guarantee a dual maximizer
It is tempting to conclude from that some multiplier attains the supremum. Minimize subject to . The only feasible point is zero, so . For , : the derivative at zero is one, so a slightly negative improves the Lagrangian. Yet as : using gives for , while . Strong duality holds in value, but no finite multiplier attains it. The missing hypothesis is strict feasibility: no point has . With a strictly feasible point, the separation argument produces an attaining multiplier.
Summary
Projection gives strict separation from a closed convex set. Open separation applied to the convex perturbation set gives multipliers, and strict feasibility forces a nonzero objective coefficient. An affine-slice argument adds equality multipliers and proves dual attainment. Subgradients express supporting inequalities, while derivatives require further smoothness.
Exercises
Quick check
(Find the projection of onto and give a strict separating inequality.)
Project vertically onto the line .
Solution · Answer
The projection is ; gives on the half-space.
Quick check
(Find at and use it to minimize over , or explain if no minimum exists.)
Look at negative before using subgradients.
Solution · Answer
. For , , which tends to as ; there is no minimum. The subdifferential of the sum at zero is , excluding zero.
Quick check
(Minimize subject to . Find an optimal multiplier and the value function for the perturbed constraint near zero.)
Solve the perturbed constraint for .
Solution · Answer
Write . The minimum is at and stationarity gives . For , the feasible set is , so and . The formula changes when .
Quick check
(For the nonattained-dual example above, prove for each finite and find an explicit lower bound tending to one.)
Use .
Solution
At zero the derivative of is one; moving slightly left makes its value less than one. For , gives . Since , its supremum is one but is not attained.