DCT Lexicon · Governing Dynamics
Fenchel–Rockafellar Duality and Dual Bounds
Duality gives every optimisation problem a shadow: a lower bound computed from prices. Where the bound meets the primal value, the gap is zero and the solution is certified optimal.
DCT Governing Dynamics
In depth
Formal statement
For with proper, convex and lower semicontinuous, the Fenchel–Rockafellar dual is:
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Fenchel–Rockafellar strong duality
If (a Slater-type condition), then and the dual supremum is attained. The duality gap of any primal–dual pair bounds its suboptimality.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
In DCT
A dual bound is an audit: it proves that no programme can do better than a stated value, without enumerating programmes. The duality gap is the optimisation certificate's residual, and the dual variables are the prices that reappear in Lagrangian coordination.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Limits
Strong duality fails without a constraint qualification, and nonconvex problems have a positive gap in general. Integer structure (lumpy rounds) makes the gap a true measure of what convexification cannot see.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Go next
- Lagrangian Dual Coordination: Dual multipliers coordinate resource allocation (Pathway 6).
- Occupation Measures: Stochastic control becomes a linear program over occupation measures, whose dual is the value function.
- Full Certificates: A zero duality gap is part of a full certificate.
- Nonsmooth Optimality and Generalized KKT: A primal–dual optimal pair satisfies the generalised KKT system.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
References
- Rockafellar (1970), Convex Analysis
- Bauschke & Combettes (2017), Convex Analysis and Monotone Operator Theory in Hilbert Spaces
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
In the book: Vol. II, Ch. 3: Convex Enterprise Optimization
Related: Lagrangian Dual Coordination · Occupation Measures · Full Certificates · Nonsmooth Optimality and Generalized KKT
GD.08


