Fenchel–Rockafellar duality

Let f on $\mathbb R^n$ and g on $\mathbb R^m$ be proper closed convex functions, and let A be linear from the first space to the second. The primal value is the infimum of f(x)+g(Ax). Applying Fenchel–Young to f with slope −Aᵀy and to g with slope y cancels the two inner products. The resulting bound is $-f^*(-A^\top y)-g^*(y)$. Maximizing it defines the dual. A dual point is useful only when both conjugate terms are finite; otherwise its bound may simply be negative infinity.

The signs can also be derived by introducing z=Ax and a multiplier term $\langle y,Ax-z\rangle$. Infimizing over x produces −f*(−Aᵀy), and infimizing over z produces −g*(y). Writing this split carefully is safer than memorizing a sign pattern. The dual objective is concave because it is the negative sum of convex conjugates composed with linear maps. Weak duality holds without the later qualification, so every finite dual value remains a valid certificate even when the best attainable certificate leaves a gap.

Use the following finite-dimensional sufficient condition: there exists x₀ in the relative interior of dom f such that Ax₀ lies in the relative interior of dom g. The relative interior is taken in each domain’s own affine hull. Assume also that the primal infimum is a finite real number. Under these hypotheses, Fenchel–Rockafellar duality gives p*=d* and the dual supremum is attained. This is a theorem statement, not a derivation from weak duality. Its proof uses separation and regularity of the convex perturbation value function.

The conclusion does not assert that the primal infimum is attained. For f(x)=exp(x), g identically zero and A the identity, the domains are all of R and the qualification holds. The primal value zero is approached as x tends to negative infinity but has no minimizing point. The dual is attained at y=0 and has value zero. A separate compactness or coercivity argument is needed for a primal minimizer. Nor is the sufficient relative-interior condition necessary: its failure means this particular theorem cannot be invoked, not that a positive duality gap has been proved.

For finite primal and dual values at x and y, their difference is the sum of two nonnegative Fenchel gaps. It vanishes exactly when −Aᵀy belongs to ∂f(x) and y belongs to ∂g(Ax). These conditions certify both sides optimal directly, even if one did not first establish a global qualification. They also reveal the meaning of the dual variable: y is a supporting slope of the measurement-space cost, and its pullback balances a supporting slope of the original-space cost. Constraints fit naturally because indicator subgradients are normal cones.

An approximate computational certificate should report feasible finite x and y and the numerical value of their gap. A small gradient residual alone is different: it can be tiny at a point with substantial objective error, especially without strong convexity or an error bound. Checking domains is essential when g is an indicator or a conjugate imposes a norm constraint. An infeasible dual vector does not provide the claimed finite lower bound merely because substituting it into a simplified polynomial happens to return an appealing number.