A lower bound built from a slope
A tangent line to a differentiable convex function stays below its graph. What if the function is not differentiable, or we want the best affine lower bound with a prescribed slope? For a function , its conjugate is
The extended value lets us incorporate constraints: for a nonempty set , its indicator is zero on and outside. We call proper when it is finite at some point and never takes . Unless otherwise stated, assume properness. A conjugate may still be infinite at a particular ; this means that no finite intercept gives an affine lower bound of the specified slope. Being a supremum of affine functions of , is convex even if is not.
By rearranging the definition, for every with and every ,
This Fenchel inequality is useful because its two sides depend on different variables. Equality has a precise geometric meaning. Recall that means for every ; this definition is meaningful for proper functions, whether or not differentiable.
Theorem 5.4.1
(Equality in Fenchel's inequality)
Let be proper and . Then if and only if . In particular equality forces to be finite.
Proof
(The supremum and the supporting plane are the same statement)
Equality says that is the supremum of over . This is equivalent to
which rearranges to the subgradient inequality . Conversely, that inequality bounds the supremum above by , while the choice bounds it below by the same number. Since is finite, so is . No differentiability, convexity, or attainment theorem is needed for this equivalence.
Three conjugates to compute by hand
Worked example 5.4.2
(Conjugate of a quadratic)
For on , completing the square gives . Thus , attained at . Equality in (1) holds exactly when , as the theorem predicts for a differentiable function.
Worked example 5.4.3
(Conjugate of the absolute value)
For , if then , with equality at zero. If , send to infinity with the sign of : then is unbounded. Therefore . Equality in (1) at reads , which gives the familiar subgradient ; for it forces with , so .
Worked example 5.4.4
(Conjugate of an indicator: the support function)
For nonempty , , because points outside contribute . This is called the support function of . When it is for and for . The supremum is over the actual feasible set, not automatically over all of . For the unbounded set the same computation gives for and for : the conjugate takes the value on a whole half-line.
The next computation obtains one conjugate from two different functions, which raises the question of what a conjugate remembers.
Counterexample mode
A conjugate does not remember arbitrary nonconvex detail
Let and elsewhere. Then . The same conjugate comes from the indicator of . For example at the original value is , whereas the interval indicator is zero. Thus one cannot reconstruct an arbitrary function simply by taking its conjugate twice; closed convex hypotheses matter for such a reconstruction theorem.
A dual bound for a constrained problem
Let be an real matrix and consider
Each multiplier produces a lower bound.
Proposition 5.4.5
(Weak duality for an equality constraint)
For every and every feasible ,
Hence , even if neither optimum is attained.
Proof
(Fenchel’s inequality with the slope )
If there is nothing to prove. Otherwise apply (1) with : , and feasibility turns the right side into . When , the bound holds trivially. Taking the infimum over feasible and then the supremum over gives the last claim.
The sign of the transpose follows from choosing the Lagrangian ; choosing the opposite Lagrangian sign is equally valid if used consistently.
Theorem 5.4.6
(A primal-dual pair certifies a global minimum)
Suppose is feasible, , and . Then minimizes subject to , maximizes , and .
Proof
(Matching the two bounds)
By the equality theorem and feasibility, . Therefore . Weak duality places every dual value below every feasible objective, so for all and all feasible , and both are optimal.
This is a sufficient certificate; its existence is not asserted without additional hypotheses.
Common mistake
(Reading the certificate theorem backwards)
The theorem does not say that every constrained problem has a multiplier with . Without further hypotheses the dual bound can be strictly below the primal value. For on and the constraint , the primal value is , while gives and .
Worked example 5.4.7
(Minimum norm with a linear equality)
Minimize subject to . Here and , obtained by completing squares coordinatewise. Thus . Its maximum is at . The feasible point has objective , and . The matched values are a proof of global optimality, not just a numerical coincidence.
Concept lensGeometric
A certificate has two jobs
Feasibility provides an upper bound on the infimum, while any multiplier provides a lower bound. Equality of the two bounds closes the gap. A stationary equation alone is insufficient if the candidate violates the constraint; a feasible point alone does not prove optimality.
Exercises with solutions
Quick check
(Find the conjugate of and the point at which the supremum is attained.)
Shift the variable before completing the square.
Solution · Answer
Put . Then , so , attained at , or .
Quick check
(Find the conjugate of and the subdifferential .)
Maximize a linear function over an interval.
Solution · Answer
Maximizing on gives for and for . At , the inequality for all holds exactly when . Thus . Values outside the interval impose no additional restriction because the left side is .
Quick check
(Minimize subject to . Find a dual maximizer using .)
The dual is finite only for .
Solution · Answer
Feasibility forces , with value . The dual is for and otherwise, so its maximum is at . Equivalently . The primal and dual values agree.
Quick check
(For with no constraints, determine and explain why this sharp bound does not produce a minimizer.)
Ask whether equality in (1) can hold.
Solution · Answer
. Hence (1) gives , the exact infimum. But at every finite , so equality never holds and the infimum is not attained. A sharp bound need not be achieved.