44.02.03 · optimization-control / 02-convex-duality-kkt

Fenchel Duality and the Conjugate as a Modeling Tool

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §31, §16, §12; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5; Bauschke & Combettes 2017 Convex Analysis and Monotone Operator Theory in Hilbert Spaces 2nd ed. (Springer) Ch. 15, §13.3

Intuition Beginner

Many practical problems are really two cost pieces glued together. You want a model that fits your data, and you also want that model to stay simple. Fitting is one cost; complexity is another. The total job is to make the sum small. Curve-fitting with a smoothness penalty, signal recovery with a sparsity penalty, portfolio choice with a risk penalty — all share this shape: minimize one piece plus a second piece.

Fenchel duality is a way to take such a glued-together problem apart cleanly. Each piece has a mirror-image description called its conjugate, which records the same information in the language of slopes rather than positions. When you rewrite each piece through its conjugate and recombine, the original minimization turns into a different maximization — its dual. The two problems share one answer, so you may solve whichever is easier.

Why is this so useful for building models? Because the conjugate dictionary is small and reusable. A handful of conjugate pairs — a squared term, an absolute-value term, a "stay inside this set" rule, a "biggest stretch in a direction" measure — combine by a few fixed rules. Once you know the pieces and the rules, you can assemble a convex model the way you snap together blocks, and read off its dual for free.

Here is the everyday picture. Two factories each make part of a product, and you want the cheapest combined output. Instead of negotiating the whole bundle at once, you post a price per unit of the shared resource. Each factory responds to that price on its own, and you tune the price until the two responses agree. The conjugate is exactly "the best each piece can do at a given price," and the dual problem is the search for the price that makes the pieces fit together.

Visual Beginner

Figure: on the left, two cost curves $f$ and $g$ are stacked and their sum is minimized at a single bottom point; on the right, the same data viewed through conjugates, where the dual reads off the best price. A linear "price line" of slope $y$ slides up until it just touches both pieces from below at a common slope; the height where it meets the axis is the dual value, and at the matching price the two pieces share a tangent.

   primal: minimize f(x) + g(x)         dual: choose a price y

   cost                                   each piece answers the price:
    |   f \        / g                    f gives  -f*(y)
    |     \      /                         g gives  -g*(-y)
    |      \    /                          add them: dual value at price y
    |  sum  \  /  <- min of the sum
    |        \/                            slide the price line up until
  --+---------+----------- x               it supports both pieces:
    |        x*                            best price y*  ->  dual optimum
    |
   primal optimum p* = dual optimum d*   (they agree: Fenchel duality)

Worked example Beginner

Fit a single number $x$ to a measurement, but keep $x$ small. Minimize the sum of a fit cost and a size cost:

minimize f (x) + g (x), f (x) = \frac{1}{2} (x - 3)^{2}, g (x) = \frac{1}{2} x^{2} .

The honest answer is plain: add the two pieces, $\frac{1}{2} (x - 3)^{2} + \frac{1}{2} x^{2} = x^{2} - 3 x + \frac{9}{2}$ , whose smallest value sits where the slope $2 x - 3$ is zero, at $x = 1.5$ , giving total cost $\frac{9}{4} = 2.25$ . We now recover $2.25$ from the price (dual) side.

Step 1. Write each conjugate. The mirror of $f (x) = \frac{1}{2} (x - 3)^{2}$ is $f^{*} (y) = \frac{1}{2} y^{2} + 3 y$ , and the mirror of $g (x) = \frac{1}{2} x^{2}$ is $g^{*} (y) = \frac{1}{2} y^{2}$ . (Each is found by tilting the piece by a line of slope $y$ and reading the top; the squared term keeps a squared mirror.)

Step 2. Form the dual value at a price. The dual posts one price $y$ to the first piece and the opposite price $- y$ to the second, then sums the best responses:

d (y) = - f^{*} (y) - g^{*} (- y) = - (\frac{1}{2} y^{2} + 3 y) - \frac{1}{2} y^{2} = - y^{2} - 3 y .

Step 3. Pick the best price. Maximize $d (y) = - y^{2} - 3 y$ . Its slope is $- 2 y - 3$ , zero at $y = - 1.5$ , where $d (- 1.5) = - 2.25 + 4.5 = 2.25$ .

What this tells us. The best dual value is $2.25$ , exactly the primal minimum, and the matching price is $y^{⋆} = - 1.5$ — which is the shared slope of the two pieces at $x = 1.5$ (since $f^{'} (1.5) = - 1.5$ and $g^{'} (1.5) = 1.5 = - y^{⋆}$ ). The price that closes the problem is the common tangent slope.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f : R^{n} \to (- \infty, + \infty]$ and $g : R^{m} \to (- \infty, + \infty]$ are proper closed convex functions, $A \in R^{m \times n}$ is linear, and the conjugate $f^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - f (x))$ is the Legendre-Fenchel transform of 37.07.03. The pairing $⟨ \cdot, \cdot ⟩$ is the standard inner product and $A^{⊤}$ the adjoint.

Definition (Fenchel primal and dual problems). The Fenchel primal problem is the composite minimization

p^{⋆} = x \in R^{n} in f [f (x) + g (A x)],

and the Fenchel dual problem is

d^{⋆} = y \in R^{m} sup [- f^{*} (A^{⊤} y) - g^{*} (- y)] .

The dual is itself a convex program: $f^{*}, g^{*}$ are closed convex (conjugates always are, by 37.07.03), so the objective is concave in $y$ .

Definition (support function). For a nonempty set $C \subseteq R^{n}$ , the support function is $σ_{C} (λ) = sup_{x \in C} ⟨ λ, x ⟩$ . The indicator $ι_{C}$ takes the value $0$ on $C$ and $+ \infty$ off $C$ . Conjugation pairs them: $ι_{C}^{*} = σ_{C}$ , and for closed convex $C$ , $σ_{C}^{*} = ι_{C}$ ^{[Rockafellar §13]}.

Definition (dual norm). For a norm $∥ \cdot ∥$ on $R^{n}$ , the dual norm is $∥ λ ∥_{*} = sup_{∥ x ∥ \leq 1} ⟨ λ, x ⟩$ . The conjugate of a norm is the indicator of the dual unit ball, $(∥ \cdot ∥)^{*} (λ) = ι_{{∥ \cdot ∥_{*} \leq 1}} (λ)$ — zero when $∥ λ ∥_{*} \leq 1$ , $+ \infty$ otherwise.

Definition (infimal convolution). The infimal convolution of $f_{1}, f_{2}$ is

(f_{1} □ f_{2}) (x) = x_{1} + x_{2} = x in f [f_{1} (x_{1}) + f_{2} (x_{2})] = z in f [f_{1} (z) + f_{2} (x - z)] .

It is the largest convex function whose epigraph is the (Minkowski) sum $epi f_{1} + epi f_{2}$ . The exact-at-the-end identity is conjugate duality of the two binary operations, sum and infimal convolution: $(f_{1} □ f_{2})^{*} = f_{1}^{*} + f_{2}^{*}$ , and dually $(f_{1} + f_{2})^{*} = f_{1}^{*} □ f_{2}^{*}$ under a qualification, established in the Key theorem.

Counterexamples to common slips

Fenchel duality without a constraint qualification can have a positive gap. Take $n = m = 1$ , $A = 1$ , with $f, g$ closed convex whose domains meet only at a single boundary point (for instance $f = ι_{(- \infty, 0]}$ and $g (x) = ι_{[0, \infty)} (x) - x$ extended suitably). Then $relint (dom f) \cap relint (A^{- 1} dom g) = \emptyset$ and the values $p^{⋆}, d^{⋆}$ can split. Weak duality $d^{⋆} \leq p^{⋆}$ survives unconditionally; only equality needs the qualification.
The conjugate-of-a-sum identity needs domain overlap. $(f_{1} + f_{2})^{*} = f_{1}^{*} □ f_{2}^{*}$ holds with attainment only when $relint (dom f_{1}) \cap relint (dom f_{2}) \neq = \emptyset$ . Without it the infimal convolution may fail to be attained or fail to be closed, and one must pass to its lsc closure.
A norm is not its own conjugate. Unlike $\frac{1}{2} ∥ \cdot ∥_{2}^{2}$ , which is self-conjugate, the conjugate of $∥ \cdot ∥$ is not a norm but the indicator of the dual unit ball. The squared norm scales the conjugate; the bare norm produces a hard constraint. Confusing the two collapses the dual of a LASSO-type problem.

Key theorem with proof Intermediate+

The hinge is Fenchel's duality theorem: it equates the composite primal with the conjugate-pair dual under a relative-interior qualification, and the engine is the Legendre-Fenchel machinery of 37.07.03 together with the separation theorem standing behind it.

Theorem (Fenchel duality). Let $f : R^{n} \to (- \infty, + \infty]$ and $g : R^{m} \to (- \infty, + \infty]$ be proper closed convex, and $A \in R^{m \times n}$ .

(i) (Weak duality.) For every $y \in R^{m}$ and $x \in R^{n}$ , $- f^{*} (A^{⊤} y) - g^{*} (- y) \leq f (x) + g (A x)$ ; hence $d^{⋆} \leq p^{⋆}$ .

(ii) (Strong duality.) If the qualification

\exists \overset{x}{^} \in relint (dom f) with A \overset{x}{^} \in relint (dom g)

holds and $p^{⋆}$ is finite, then $d^{⋆} = p^{⋆}$ and the dual supremum is attained at some $y^{⋆}$ .

Proof of (i). Fix $x, y$ . The Fenchel-Young inequality of 37.07.03 applied to $f$ at the pair $(x, A^{⊤} y)$ gives $f (x) + f^{*} (A^{⊤} y) \geq ⟨ A^{⊤} y, x ⟩ = ⟨ y, A x ⟩$ . Applied to $g$ at $(A x, - y)$ it gives $g (A x) + g^{*} (- y) \geq ⟨ - y, A x ⟩ = - ⟨ y, A x ⟩$ . Adding the two,

f (x) + g (A x) + f^{*} (A^{⊤} y) + g^{*} (- y) \geq ⟨ y, A x ⟩ - ⟨ y, A x ⟩ = 0,

which rearranges to $- f^{*} (A^{⊤} y) - g^{*} (- y) \leq f (x) + g (A x)$ . Taking the supremum over $y$ on the left and the infimum over $x$ on the right yields $d^{⋆} \leq p^{⋆}$ . $□$

Proof of (ii). Embed the problem in the perturbation framework. Define the value function

p (u) = x in f [f (x) + g (A x + u)], u \in R^{m},

so $p^{⋆} = p (0)$ . Under the convexity of $f, g$ and linearity of $A$ , the function $(x, u) \mapsto f (x) + g (A x + u)$ is jointly convex, and $p$ is its partial infimum over $x$ , hence convex (a partial infimum of a jointly convex function is convex, by the projection-of-a-convex-set calculus of 44.01.01). The qualification places $0$ in $relint (dom p)$ : indeed $dom p = dom g - A (dom f)$ , and the relative-interior point $A \overset{x}{^} \in relint (dom g)$ gives $0 \in relint (dom g - A dom f)$ . A finite convex function with $0$ in the relative interior of its domain is subdifferentiable there: $\partial p (0) \neq = \emptyset$ (Rockafellar's subdifferentiability theorem, the relative-interior case of 44.02.05). Pick $- y^{⋆} \in \partial p (0)$ . By the Fenchel-Young equality of 37.07.03, $- y^{⋆} \in \partial p (0)$ means $p (0) + p^{*} (- y^{⋆}) = ⟨ - y^{⋆}, 0 ⟩ = 0$ , i.e. $p^{⋆} = - p^{*} (- y^{⋆})$ .

It remains to identify $- p^{*} (- y^{⋆})$ with the dual objective. Compute the conjugate of $p$ directly:

p^{*} (- y) = u sup (⟨ - y, u ⟩ - p (u)) = u sup x sup (⟨ - y, u ⟩ - f (x) - g (A x + u)) .

Substitute $w = A x + u$ , so $u = w - A x$ and $⟨ - y, u ⟩ = ⟨ - y, w ⟩ + ⟨ y, A x ⟩ = ⟨ - y, w ⟩ + ⟨ A^{⊤} y, x ⟩$ :

p^{*} (- y) = x sup (⟨ A^{⊤} y, x ⟩ - f (x)) + w sup (⟨ - y, w ⟩ - g (w)) = f^{*} (A^{⊤} y) + g^{*} (- y) .

Therefore $p^{⋆} = - p^{*} (- y^{⋆}) = - f^{*} (A^{⊤} y^{⋆}) - g^{*} (- y^{⋆}) \leq d^{⋆}$ . Combined with weak duality $d^{⋆} \leq p^{⋆}$ from (i), all are equal and $y^{⋆}$ attains the dual. $□$

Bridge. This theorem builds toward the proximal and splitting algorithms of chapter 06 and appears again in every regularized estimator whose penalty is handled on the dual side. This is exactly the Lagrangian strong duality of 44.02.01 re-expressed through the conjugate: introduce a splitting variable $z = A x$ , attach a multiplier $y$ to the equality $z = A x$ , and the Lagrangian dual function becomes $- f^{*} (A^{⊤} y) - g^{*} (- y)$ , so Fenchel duality is dual to Lagrangian duality term-by-term and generalises the price picture of 44.02.01 to the conjugate-pairing form. The foundational reason the gap closes is that the value function $p$ is subdifferentiable at $0$ precisely when $0 \in relint (dom p)$ , the relative-interior qualification, which is the conjugate-duality reading of Slater's condition. Putting these together, the multiplier $y^{⋆} \in - \partial p (0)$ is simultaneously the optimal dual price, the shared subgradient linking the two pieces through the conjugacy inversion of 44.02.05, and the marginal sensitivity of $p^{⋆}$ to perturbing the coupling.

Exercises Intermediate+

Exercise 1 (easy, symbolic).

Show that the conjugate of the indicator $ι_{C}$ of a nonempty set $C$ is the support function $σ_{C}$ , and deduce that the conjugate of a norm $∥ \cdot ∥$ is the indicator of the dual unit ball.

Hint

Write out $ι_{C}^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - ι_{C} (x))$ . For the norm, use $∥ x ∥ = sup_{∥ λ ∥_{*} \leq 1} ⟨ λ, x ⟩$ .

Answer

$ι_{C}^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - ι_{C} (x)) = sup_{x \in C} ⟨ λ, x ⟩ = σ_{C} (λ)$ , since subtracting $ι_{C}$ restricts the supremum to $C$ . For the norm, $(∥ \cdot ∥)^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - ∥ x ∥)$ . If $∥ λ ∥_{*} \leq 1$ then $⟨ λ, x ⟩ \leq ∥ λ ∥_{*} ∥ x ∥ \leq ∥ x ∥$ , so the supremand is $\leq 0$ with equality at $x = 0$ , giving value $0$ . If $∥ λ ∥_{*} > 1$ , pick $x_{0}$ with $∥ x_{0} ∥ = 1$ , $⟨ λ, x_{0} ⟩ = ∥ λ ∥_{*} > 1$ , and scale $x = t x_{0}$ : $t (∥ λ ∥_{*} - 1) \to + \infty$ . Hence $(∥ \cdot ∥)^{*} = ι_{{∥ λ ∥_{*} \leq 1}}$ , the indicator of the dual unit ball.

Exercise 3 (medium, symbolic).

Derive the Fenchel dual of the LASSO problem $min_{x} \frac{1}{2} ∥ A x - b ∥_{2}^{2} + τ ∥ x ∥_{1}$ and identify the dual feasible set.

Hint

Set $f (x) = τ ∥ x ∥_{1}$ , $g (z) = \frac{1}{2} ∥ z - b ∥_{2}^{2}$ . Use $(τ ∥ \cdot ∥_{1})^{*} = ι_{{∥ \cdot ∥_{\infty} \leq τ}}$ .

Answer

With $f = τ ∥ \cdot ∥_{1}$ and $g = \frac{1}{2} ∥ \cdot - b ∥_{2}^{2}$ : $f^{*} (A^{⊤} y) = ι_{{∥ A^{⊤} y ∥_{\infty} \leq τ}} (A^{⊤} y)$ (the dual norm of $ℓ_{1}$ is $ℓ_{\infty}$ , scaled by $τ$ ), and $g^{*} (- y) = \frac{1}{2} ∥ y ∥_{2}^{2} - ⟨ y, b ⟩$ . The Fenchel dual is

y sup [⟨ y, b ⟩ - \frac{1}{2} ∥ y ∥_{2}^{2}] subject to ∥ A^{⊤} y ∥_{\infty} \leq τ,

equivalently $max_{y} - \frac{1}{2} ∥ y - b ∥_{2}^{2} + \frac{1}{2} ∥ b ∥_{2}^{2}$ over the box-image constraint $∥ A^{⊤} y ∥_{\infty} \leq τ$ — a projection of $b$ onto ${y : ∥ A^{⊤} y ∥_{\infty} \leq τ}$ . The $ℓ_{1}$ penalty became a hard $ℓ_{\infty}$ constraint on the dual variable, the signature conjugate-modeling move.

Exercise 5 (medium, symbolic).

Show that Tikhonov regularization $min_{x} \frac{1}{2} ∥ A x - b ∥_{2}^{2} + \frac{γ}{2} ∥ x ∥_{2}^{2}$ has Fenchel dual $max_{y} [⟨ y, b ⟩ - \frac{1}{2} ∥ y ∥_{2}^{2} - \frac{1}{2 γ} ∥ A^{⊤} y ∥_{2}^{2}]$ , and relate the primal-dual recovery $x^{⋆} = - \frac{1}{γ} A^{⊤} y^{⋆}$ .

Hint

Take $f (x) = \frac{γ}{2} ∥ x ∥_{2}^{2}$ , $g (z) = \frac{1}{2} ∥ z - b ∥_{2}^{2}$ . Use $f^{*} (λ) = \frac{1}{2 γ} ∥ λ ∥_{2}^{2}$ and the Fenchel-Young equality for primal recovery.

Answer

$f^{*} (A^{⊤} y) = \frac{1}{2 γ} ∥ A^{⊤} y ∥_{2}^{2}$ and $g^{*} (- y) = \frac{1}{2} ∥ y ∥_{2}^{2} - ⟨ y, b ⟩$ as in Exercise 2. The dual is $sup_{y} [- \frac{1}{2 γ} ∥ A^{⊤} y ∥_{2}^{2} - \frac{1}{2} ∥ y ∥_{2}^{2} + ⟨ y, b ⟩]$ , the stated expression. Primal recovery: at the optimum the Fenchel-Young equality $f (x^{⋆}) + f^{*} (A^{⊤} y^{⋆}) = ⟨ A^{⊤} y^{⋆}, x^{⋆} ⟩$ holds, i.e. $A^{⊤} y^{⋆} \in \partial f (x^{⋆}) = γ x^{⋆}$ , so $x^{⋆} = \frac{1}{γ} A^{⊤} y^{⋆}$ . (Sign convention: with the dual price attached as $- y$ to $g$ , the stationarity gives $x^{⋆} = - \frac{1}{γ} A^{⊤} y^{⋆}$ once the residual $y^{⋆} = b - A x^{⋆}$ is substituted.) The dual is again a strongly concave QP, uniquely solvable.

Exercise 6 (hard, symbolic).

Compute the conjugate of the log-sum-exp function $f (x) = lo g \sum_{i = 1}^{n} e^{x_{i}}$ and identify it as a negative entropy on the simplex.

Hint

Maximize $⟨ λ, x ⟩ - lo g \sum_{i} e^{x_{i}}$ ; stationarity forces $λ$ into the probability simplex, and $f$ is invariant under adding a constant to all $x_{i}$ .

Answer

Set the gradient of $⟨ λ, x ⟩ - lo g \sum_{j} e^{x_{j}}$ to zero: $λ_{i} = e^{x_{i}} / \sum_{j} e^{x_{j}}$ , so $λ$ lies in the open simplex ${λ ≻ 0, \sum_{i} λ_{i} = 1}$ and $x_{i} = lo g λ_{i} + c$ for the free constant $c$ . Substituting (the $c$ cancels because $\sum_{i} λ_{i} = 1$ and $lo g \sum_{j} e^{x_{j}} = c + lo g \sum_{j} λ_{j} = c$ ):

f^{*} (λ) = i \sum λ_{i} lo g λ_{i} if λ ⪰ 0, \sum_{i} λ_{i} = 1,

and $f^{*} (λ) = + \infty$ otherwise (the supremum diverges off the simplex: if some $λ_{i} < 0$ send $x_{i} \to - \infty$ ; if $\sum λ_{i} \neq = 1$ shift all $x_{i}$ by $t$ and let $t \to \pm \infty$ ). So the conjugate of log-sum-exp is the negative Shannon entropy restricted to the probability simplex — the canonical exponential-family / entropy duality.

Exercise 7 (hard, symbolic).

Using the perturbation function $p (u) = in f_{x} [f (x) + g (A x + u)]$ , prove that the optimal Fenchel dual variable $y^{⋆}$ equals $- \nabla p (0)$ when $p$ is differentiable at $0$ , and interpret it as a sensitivity.

Hint

From the Key theorem, $- y^{⋆} \in \partial p (0)$ . When $p$ is differentiable the subdifferential is the singleton ${\nabla p (0)}$ .

Answer

The Key theorem produced $- y^{⋆} \in \partial p (0)$ with $p (0) = - p^{*} (- y^{⋆}) = - f^{*} (A^{⊤} y^{⋆}) - g^{*} (- y^{⋆}) = d^{⋆}$ . The subgradient inequality reads $p (u) \geq p (0) + ⟨ - y^{⋆}, u ⟩ = p^{⋆} - ⟨ y^{⋆}, u ⟩$ for all $u$ , a global affine lower bound tangent at $u = 0$ . If $p$ is differentiable at $0$ , then $\partial p (0) = {\nabla p (0)}$ (44.02.05), forcing $- y^{⋆} = \nabla p (0)$ , i.e. $y^{⋆} = - \nabla p (0)$ . Interpretation: $y^{⋆}$ is the marginal change in the optimal value per unit perturbation of the linear coupling $z = A x$ ; the dual price measures how much the optimum moves when the constraint linking the two pieces is relaxed, exactly the multiplier-as-sensitivity reading of 44.02.01.

Exercise 8 (hard, symbolic).

Recover Lagrangian duality of a convex inequality-constrained program $min_{x} f_{0} (x)$ s.t. $f_{i} (x) \leq 0$ from Fenchel duality by an appropriate choice of $f, g, A$ .

Hint

Stack the constraints into $F (x) = (f_{1} (x), \dots, f_{m} (x))$ , and take $g$ to be the indicator of the nonpositive orthant composed so that the conjugate produces the nonnegative multipliers.

Answer

Let $h (x) = (f_{0} (x), f_{1} (x), \dots, f_{m} (x))$ and take the outer function $G (t_{0}, t_{1}, \dots, t_{m}) = t_{0} + ι_{{t_{i} \leq 0}} (t_{1}, \dots, t_{m})$ , so the primal $in f_{x} G (h (x))$ is the constrained program. Conjugating $G$ : $G^{*} (s_{0}, s) = + \infty$ unless $s_{0} = 1$ , and for $s_{0} = 1$ , $G^{*} (1, s) = sup_{t_{i} \leq 0} ⟨ s, t ⟩ = 0$ if $s ⪰ 0$ else $+ \infty$ , so $G^{*} (1, s) = ι_{{s ⪰ 0}}$ . The Fenchel dual variable splits as $(1, λ)$ with $λ ⪰ 0$ , and the dual objective becomes $in f_{x} [f_{0} (x) + \sum_{i} λ_{i} f_{i} (x)] = g (λ)$ , the Lagrange dual function. Maximizing over $λ ⪰ 0$ is the Lagrangian dual of 44.02.01; the nonnegativity of $λ$ is exactly the support condition $G^{*} (1, λ) < \infty$ . Fenchel duality thus contains Lagrangian duality as the special case where $g$ encodes the constraint cone.

Advanced results Master

Conjugate calculus as a modeling algebra

The operational power of Fenchel duality rests on a closed set of rules that compute conjugates of composite functions, turning model assembly into symbolic manipulation ^{[Boyd & Vandenberghe §3.3]}. Separability conjugates coordinatewise: $(\sum_{i} f_{i} (x_{i}))^{*} = \sum_{i} f_{i}^{*} (λ_{i})$ . Scaling and affine precomposition obey $(α f)^{*} (λ) = α f^{*} (λ / α)$ for $α > 0$ and $(f (A x + b))^{*} (λ) = f^{*} ((A^{⊤})^{- 1} λ) - ⟨(A^{⊤})^{- 1} λ, b ⟩$ when $A$ is invertible, with a partial-inverse statement otherwise. The two binary operations sum and infimal convolution are exchanged by conjugation, $(f □ g)^{*} = f^{*} + g^{*}$ unconditionally and $(f + g)^{*} = f^{*} □ g^{*}$ under $relint (dom f) \cap relint (dom g) \neq = \emptyset$ ^{[Rockafellar §16]}. The Moreau envelope $e_{γ} f = f □ \frac{1}{2 γ} ∥ \cdot ∥_{2}^{2}$ is the canonical smoothing: its conjugate is $f^{*} + \frac{γ}{2} ∥ \cdot ∥_{2}^{2}$ , a strongly convex regularization on the dual side, and its gradient is $\frac{1}{γ} (Id - prox_{γ f})$ , the bridge to proximal algorithms. These rules, applied recursively, let one read off the dual of any tree of convex pieces glued by sums and linear maps.

The Rockafellar conjugate-duality framework

Rockafellar's Convex Analysis §31 subsumes Lagrangian, Fenchel, and conic duality into a single perturbational scheme ^{[Rockafellar §31]}. One starts from a bivariate convex function $F (x, u)$ — the objective embedded in a family of perturbations indexed by $u$ — and forms the value function $p (u) = in f_{x} F (x, u)$ and the Lagrangian-type function $K (x, y) = in f_{u} (F (x, u) + ⟨ y, u ⟩)$ , the partial conjugate in $u$ . The primal value is $p (0) = in f_{x} sup_{y} K (x, y)$ and the dual value is $sup_{y} in f_{x} K (x, y) = sup_{y} (- F^{*} (0, y))$ , where $F^{*}$ conjugates in both arguments. Weak duality is the generic max-min inequality; strong duality with dual attainment is $p$ being closed and subdifferentiable at $0$ , equivalently $p (0) = p^{**} (0)$ and $\partial p (0) \neq = \emptyset$ . Specializing $F (x, u) = f (x) + g (A x + u)$ gives Fenchel duality; $F (x, u) = f_{0} (x) + ι_{{f_{i} (x) \leq u_{i}}}$ gives Lagrangian duality; the cone-perturbation $F (x, u) = ⟨ c, x ⟩ + ι_{{A x - b \in K - u}}$ gives conic duality. The duality gap is in every case the discrepancy $p (0) - p^{**} (0)$ between the value function and its closed convex hull at the origin, and the constraint qualification is uniformly $0 \in relint (dom p)$ .

Fenchel-Rockafellar duality and the role of attainment

The sharp statement separates no gap from dual attainment. If $f, g$ are proper closed convex and $A (dom f) \cap relint (dom g) \neq = \emptyset$ (or the symmetric relative-interior condition), then $p^{⋆} = d^{⋆}$ with the dual supremum attained ^{[Bauschke & Combettes Ch. 15]}. The qualification controls attainment, not merely the absence of a gap: there exist closed convex $f, g$ with $p^{⋆} = d^{⋆}$ finite but the dual sup unattained, the analogue of a recession-direction failure. In the polyhedral special case — $f, g$ polyhedral convex — strong duality and attainment hold with no relative-interior hypothesis, the conjugate-duality face of the unconditional polyhedral strong duality that Farkas-type theorems of the alternative supply, because polyhedral epigraphs are closed under linear images.

Self-duality of the squared norm and the Moreau decomposition

The quadratic $q = \frac{1}{2} ∥ \cdot ∥_{2}^{2}$ is the unique self-conjugate function, $q^{*} = q$ , and this fixed-point status makes it the canonical regularizer. Its consequence is the Moreau identity: for any proper closed convex $f$ and any $x$ , $prox_{γ f} (x) + γ prox_{f^{*} / γ} (x / γ) = x$ , decomposing every point into a primal-proximal and a dual-proximal part. The identity is the proximal shadow of the conjugacy inversion $\partial f^{*} = (\partial f)^{- 1}$ of 44.02.05: the proximal map is the resolvent $(Id + γ \partial f)^{- 1}$ , and inverting the subdifferential through conjugation inverts the resolvent through Moreau. This is why dual and primal-dual splitting methods can apply a proximal step to a function only through its conjugate, and the conjugate calculus above is precisely what makes those conjugate proximal steps computable.

Synthesis. The conjugate is exactly the change of coordinates from positions to prices, and the central insight of this unit is that Fenchel duality $in f_{x} [f (x) + g (A x)] = sup_{y} [- f^{*} (A^{⊤} y) - g^{*} (- y)]$ is one perturbational scheme of which Lagrangian duality is a sibling specialization, not a separate theorem. This is exactly the strong duality of 44.02.01 read through the conjugate: the splitting multiplier $y^{⋆}$ on $z = A x$ produces the conjugate-pair dual, so Fenchel duality is dual to Lagrangian duality term-by-term and both generalise to the Rockafellar bivariate framework where the gap is the value function's failure of closure at $0$ . The foundational reason the gap vanishes is subdifferentiability of $p$ at the origin, the relative-interior qualification that generalises Slater. Putting these together, the conjugate calculus — separability, the sum/infimal-convolution exchange, the support function and dual norm, the self-dual quadratic — is a modeling algebra: each convex penalty contributes a conjugate, each linear coupling an adjoint, and the dual assembles mechanically; the bridge is the perturbation function $p$ , the single convex object through which Fenchel, Lagrangian, and conic duality, the conjugacy inversion of 44.02.05, and the proximal machinery of chapter 06 become one theory, and it appears again in the large-deviations conjugacy of 37.07.03 where the same algebra combines rate functions.

Full proof set Master

Proposition 1 (conjugate of a sum / infimal-convolution exchange). Let $f_{1}, f_{2} : R^{n} \to (- \infty, + \infty]$ be proper closed convex with $relint (dom f_{1}) \cap relint (dom f_{2}) \neq = \emptyset$ . Then $(f_{1} + f_{2})^{*} = f_{1}^{*} □ f_{2}^{*}$ , and the infimal convolution on the right is exact (attained) and closed.

Proof. The direction $(f_{1} □ f_{2})^{*} = f_{1}^{*} + f_{2}^{*}$ for any proper functions is Exercise 4. Apply it to the pair $f_{1}^{*}, f_{2}^{*}$ : since $f_{1}, f_{2}$ are closed convex, $f_{i}^{**} = f_{i}$ by Fenchel-Moreau 37.07.03, so $(f_{1}^{*} □ f_{2}^{*})^{*} = f_{1}^{**} + f_{2}^{**} = f_{1} + f_{2}$ . Conjugating both sides and using that $f_{1}^{*} □ f_{2}^{*}$ has a closed convex hull whose conjugate is $f_{1} + f_{2}$ gives $(f_{1} + f_{2})^{*} = cl (f_{1}^{*} □ f_{2}^{*})$ . The relative-interior qualification upgrades closure to exactness: by the subdifferential sum rule of 44.02.05, which holds under exactly this qualification, for each $λ$ the infimum defining $(f_{1}^{*} □ f_{2}^{*}) (λ) = in f_{μ} (f_{1}^{*} (μ) + f_{2}^{*} (λ - μ))$ is attained at a $μ$ with $λ - μ$ and $μ$ realizing a common subgradient, so no closure operation is needed and $(f_{1} + f_{2})^{*} = f_{1}^{*} □ f_{2}^{*}$ pointwise with attainment. $□$

Proposition 2 (Fenchel duality, gap and attainment). For proper closed convex $f, g$ and linear $A$ , weak duality $d^{⋆} \leq p^{⋆}$ is unconditional; if $\exists \overset{x}{^} \in relint (dom f)$ with $A \overset{x}{^} \in relint (dom g)$ and $p^{⋆}$ finite, then $p^{⋆} = d^{⋆}$ with dual attainment.

Proof. Weak duality is part (i) of the Key theorem, a direct sum of two Fenchel-Young inequalities. For strong duality, the perturbation function $p (u) = in f_{x} [f (x) + g (A x + u)]$ is convex with $dom p = dom g - A dom f$ ; the qualification places $0 \in relint (dom p)$ . A proper convex function finite on a neighborhood-in-its-affine-hull of $0$ is subdifferentiable there (44.02.05), so $\partial p (0) \neq = \emptyset$ ; pick $- y^{⋆} \in \partial p (0)$ . Fenchel-Young equality 37.07.03 gives $p (0) + p^{*} (- y^{⋆}) = 0$ . The computation in the Key theorem identifies $p^{*} (- y) = f^{*} (A^{⊤} y) + g^{*} (- y)$ , whence $p^{⋆} = p (0) = - f^{*} (A^{⊤} y^{⋆}) - g^{*} (- y^{⋆}) \leq d^{⋆} \leq p^{⋆}$ , equality throughout with $y^{⋆}$ attaining the dual. $□$

Proposition 3 (support function and dual-norm conjugacy). For nonempty closed convex $C$ , $ι_{C}^{*} = σ_{C}$ and $σ_{C}^{*} = ι_{C}$ ; for a norm $∥ \cdot ∥$ with dual norm $∥ \cdot ∥_{*}$ , $(∥ \cdot ∥)^{*} = ι_{B_{*}}$ where $B_{*} = {λ : ∥ λ ∥_{*} \leq 1}$ , and $(ι_{B_{*}})^{*} = ∥ \cdot ∥$ .

Proof. $ι_{C}^{*} (λ) = sup_{x} (⟨ λ, x ⟩ - ι_{C} (x)) = sup_{x \in C} ⟨ λ, x ⟩ = σ_{C} (λ)$ by definition of the indicator. Since $σ_{C}$ is closed convex (a supremum of linear functions) and $C$ is closed convex, biconjugation 37.07.03 gives $σ_{C}^{*} = ι_{C}^{**} = ι_{C}$ . For the norm, Exercise 1 computes $(∥ \cdot ∥)^{*} = ι_{B_{*}}$ ; conjugating again and using biconjugation, $(ι_{B_{*}})^{*} = (∥ \cdot ∥)^{**} = ∥ \cdot ∥$ because a norm is closed convex. The pair $(∥ \cdot ∥, ι_{B_{*}})$ is thus a conjugate pair, the mechanism by which an $ℓ_{1}$ penalty in a primal becomes an $ℓ_{\infty}$ constraint in the dual. $□$

Proposition 4 (log-sum-exp / negative-entropy conjugacy). Let $f (x) = lo g \sum_{i = 1}^{n} e^{x_{i}}$ . Then $f^{*} (λ) = \sum_{i} λ_{i} lo g λ_{i}$ on the simplex $Δ = {λ ⪰ 0, \sum_{i} λ_{i} = 1}$ and $+ \infty$ off it; the pair is mutually conjugate, $f^{**} = f$ .

Proof. $f$ is convex (its Hessian is the covariance matrix of the softmax distribution, positive semidefinite) and finite everywhere, hence closed. Exercise 6 computes $f^{*}$ : stationarity of $⟨ λ, x ⟩ - f (x)$ forces $λ$ into the relative interior of $Δ$ with $x_{i} = lo g λ_{i} + c$ , the additive constant canceling, giving $f^{*} (λ) = \sum_{i} λ_{i} lo g λ_{i}$ ; off $Δ$ the supremum diverges via a coordinate sent to $- \infty$ (for $λ_{i} < 0$ ) or a uniform shift (for $\sum_{i} λ_{i} \neq = 1$ ), so $f^{*} = + \infty$ there. Since $f$ is closed convex, Fenchel-Moreau 37.07.03 gives $f^{**} = f$ ; conjugating the negative entropy on the simplex returns log-sum-exp. This pair is the convex-duality core of the exponential family and of the entropy-regularized linear programs that underlie softmax models. $□$

Connections Master

Lagrangian duality and Slater's condition 44.02.01 is the sibling specialization: introducing a splitting variable $z = A x$ and a multiplier on $z = A x$ turns the Lagrangian dual function into $- f^{*} (A^{⊤} y) - g^{*} (- y)$ , so Fenchel duality is Lagrangian duality re-expressed through conjugates, and Slater's interior-point condition becomes the relative-interior qualification $0 \in relint (dom p)$ on the perturbation function. Exercise 8 recovers the constrained Lagrangian dual from a Fenchel dual by encoding the constraint cone in $g$ .
The Legendre-Fenchel transform 37.07.03 is the immediate analytic engine: the conjugate, the Fenchel-Young inequality, and the Fenchel-Moreau biconjugation theorem proved there are what make the dual objective well-defined and what close the gap, and the conjugate calculus of this unit (dual norms, support functions, infimal convolution) is the same algebra that combines large-deviations rate functions in the probabilistic setting.
Subdifferential calculus 44.02.05 supplies the optimality and recovery layer: the conjugacy inversion $\partial f^{*} = (\partial f)^{- 1}$ links the optimal primal and dual variables through a shared subgradient, the Moreau-Rockafellar sum rule under the relative-interior qualification is exactly the condition making the conjugate-of-a-sum identity exact, and subdifferentiability of the value function at $0$ is what produces the attained dual multiplier $y^{⋆} \in - \partial p (0)$ .
The convex-operation calculus and supporting-hyperplane structure of 44.01.01 underlies the perturbation function's convexity: $p (u) = in f_{x} [f (x) + g (A x + u)]$ is convex because it is a partial infimum of a jointly convex function, and the relative-interior and recession-cone facts that govern when the infimum is attained and the gap closes are the convex-set apparatus assembled there.

Historical & philosophical context Master

The conjugate of a convex function originates with Werner Fenchel, whose 1949 paper On conjugate convex functions (Canadian Journal of Mathematics 1, 73-77) introduced the supremum-defined transform; the duality theorem for $in f_{x} [f (x) + g (x)]$ that now bears his name appeared in his 1951 Princeton lecture notes Convex Cones, Sets, and Functions ^{[Fenchel 1953]}, where he paired the conjugates of two convex functions and proved their values meet under a separation hypothesis. Fenchel's formulation was geometric, framed through the supporting hyperplanes of the two epigraphs, and he isolated the qualification — that the functions' domains overlap in a relative-interior sense — needed to exclude a gap.

The synthesis of Fenchel's duality with Lagrange's multiplier method is due to R. Tyrrell Rockafellar, whose Convex Analysis ^{[Rockafellar §31]} (Princeton, 1970) introduced the bivariate perturbation function $F (x, u)$ and showed that Fenchel duality, Lagrangian duality, and conic duality are specializations of a single conjugate-duality scheme in which the gap is the value function's failure of lower-semicontinuity at the origin. Jean-Jacques Moreau, working in parallel in the early 1960s, contributed the infimal convolution, the Moreau envelope, and the proximal decomposition that connect conjugacy to the algorithms; Bauschke and Combettes later codified the Hilbert-space form and the attainment-versus-gap distinction. Boyd and Vandenberghe brought the conjugate calculus into engineering practice, where the conjugate dictionary became the standard device for deriving the duals of regularized estimation problems.

Bibliography Master

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@article{fenchel1949conjugate,
  author  = {Fenchel, Werner},
  title   = {On conjugate convex functions},
  journal = {Canadian Journal of Mathematics},
  volume  = {1},
  pages   = {73--77},
  year    = {1949}
}

@misc{fenchel1953convex,
  author       = {Fenchel, Werner},
  title        = {Convex Cones, Sets, and Functions},
  note         = {Lecture notes, Department of Mathematics, Princeton University},
  year         = {1953}
}

@book{bauschke2017convex,
  author    = {Bauschke, Heinz H. and Combettes, Patrick L.},
  title     = {Convex Analysis and Monotone Operator Theory in Hilbert Spaces},
  edition   = {2nd},
  series    = {CMS Books in Mathematics},
  publisher = {Springer},
  year      = {2017}
}

@article{moreau1965proximite,
  author  = {Moreau, Jean-Jacques},
  title   = {Proximit\'e et dualit\'e dans un espace hilbertien},
  journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
  volume  = {93},
  pages   = {273--299},
  year    = {1965}
}

Prerequisites

44.02.01
37.07.03

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.3 — the conjugate as the gap between a function and a linear underestimator
intermediate: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.3, §5; Rockafellar 1970 Convex Analysis (Princeton) §31
master: Rockafellar 1970 Convex Analysis (Princeton) §31, §16, §12; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5; Bauschke & Combettes 2017 Convex Analysis and Monotone Operator Theory in Hilbert Spaces 2nd ed. (Springer) Ch. 15, §13.3

References

Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §3.3 the conjugate function and conjugate calculus; §3.3.1 examples (log-sum-exp, norms, indicators); §5.1.6 the conjugate form of the dual; §5 LASSO/Tikhonov and regularized problems
Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §12 conjugate convex functions; §16 the conjugate of a sum / infimal convolution duality; §31 Fenchel's duality theorem and the conjugate-duality framework
Bauschke, H. H. & Combettes, P. L. — Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd ed. (Springer, 2017) · Ch. 13 conjugation and infimal convolution; §13.3 the conjugate of an infimal convolution is a sum; Ch. 15 Fenchel-Rockafellar duality
Fenchel, W. — Convex Cones, Sets, and Functions · Lecture notes, Princeton University (1953); the duality theorem for inf [f(x)+g(x)]

Estimated time

beginner: 18m
intermediate: 45m
master: 80m