The most naive approach is to use the Fenchel-Young inequality. Recall the definition of the convex conjugate $$f_{\ast }(y)=\underset{x\in {ℝ}^n}{sup}⟨x,y⟩-f(x)$$ From this definition we can immediately see that $$\forall x,y\in {ℝ}^n,f_{\ast }(y)\ge ⟨x,y⟩-f(x).$$

This is not exactly the same form as the duality principle from (1), but this is also true for $x^{\ast }$ the global minimum of $f$ , so $$\forall y\in {ℝ}^n,f(x^{\ast })\ge ⟨x^{\ast },y⟩-f_{\ast }(y),$$ and clearly $f(x)\ge f(x^{\ast })$ , yielding $$\forall x,y\in {ℝ}^n,f(x)\ge ⟨x^{\ast },y⟩-f_{\ast }(y).$$

We now have a function $g$ in the correct form. Unfortunately

$$g(y)=⟨x^{\ast },y⟩-f_{\ast }(y)$$ so the expression for $g$ involves $x^{\ast }$ and is uncomputable in general. But this attempt was a step in the right direction, we now need to investigate how to control the inner product part.

In our previous attempt we were left with a hanging $⟨x^{\ast },y⟩$ term. In order to avoid it, let's apply Fenchel-Young to a slightly perturbed function $\phi :{ℝ}^n\times {ℝ}^n\to \overline{ℝ}$ , $$\phi (x,u)=f(x)+⟨x,u⟩.$$ The hope is that adding this inner product term might give us something to cancel $⟨x^{\ast },y⟩$ .

Fenchel-Young for $\phi$ reads $$\phi (x,u)\ge ⟨x,v⟩+⟨u,y⟩-{\phi }_{\ast }(v,y).$$ It is worth pointing out that $\phi (x,0)=f(x)$ , so maybe a strategic evaluation of $\phi$ and ${\phi }_{\ast }$ can yield a useful form of duality. Setting $u=0$ and $v=0$ gives the promising $$\phi (x,0)\ge -{\phi }_{\ast }(0,y),$$ since the inner product part is $⟨x,0⟩+⟨0,y⟩$ .

This is exactly the form we want, with $g(y)=-{\phi }_{\ast }(0,y)$ . We hope that ${\phi }_{\ast }$ might be easier to compute. Looking back at the development in this section, we have never used the exact definition of $\phi$ . In the next section we will see that maybe choosing $\phi$ in a smarter way can be better.

In this section, we consider general function $\phi :{ℝ}^n\times {ℝ}^n\to \overline{ℝ}$ with the property that $$\phi (x,0)=f(x)$$ We will call such a function $\phi$ a perturbation function. The same Fenchel-Young argument gives $$\phi (x,u)\ge ⟨x,v⟩+⟨u,y⟩-{\phi }_{\ast }(v,y),$$ and after the same clever evaluation $$\phi (x,0)\ge -{\phi }_{\ast }(0,y).$$

This again has the form of a duality theory, where

$$\underset{x\in {ℝ}^n}{inf}\phi (x,0)\ge \underset{y\in {ℝ}^n}{sup}-{\phi }_{\ast }(0,y).$$ For a general convex optimization problem we can advance no further. The next step is to assume some special structure of the problem and to construct a perturbation function such that ${\phi }_{\ast }(0,y)$ is actually computable.

The particular structured problem we will consider in this section is $$\underset{x\in {ℝ}^n}{inf}{f}_1(x)+f_2(x),$$ with $f_1$ and $f_2$ convex. With experience, I can see that $$\phi (x,u)=f_1(x)+f_2(x-u)$$ is a promising candidate for a perturbation function.

Let's investigate

Substituting in (3) gives

$$\underset{x\in {ℝ}^n}{inf}{f}_1(x)+f_2(x)\ge \underset{y\in {ℝ}^n}{sup}-f_1^{}{}_{\ast }{}^{}(y)-f_2^{}{}_{\ast }{}^{}(-y).$$ This inequality is called Fenchel's duality formula. In the last section we will see a Theorem that allows use to compute $\mathrm{gap}(f_1+f_2,-f_1^{}{}_{\ast }{}^{}-f_2^{}{}_{\ast }{}^{}(-\cdot ))$ .

Another well understood case is that of constrained optimization. Here we consider the problem

$$\underset{x\in \{z|G(z)=0\}}{inf}f(x)$$ for some $f:{ℝ}^n\to \overline{ℝ}$ and $G:{ℝ}^n\to {ℝ}^m$ .

The perturbation function we will consider is Let's compute $${\phi }_{\ast }(0,y)=\underset{x\in {ℝ}^n,u\in {ℝ}^m}{sup}⟨u,y⟩-\phi (x,u).$$ Since if $G(x)\ne u$ we would have $-\phi (x,u)=-\mathrm{\infty }$ , we can conclude that $G(x)=u$ and that

$${\phi }_{\ast }(0,y)=\underset{x\in {ℝ}^n}{sup}⟨G(x),y⟩-f(x).$$

The argument the supremum in (6) appears often enough in optimization that it received a name: the lagrangian. More concretly: the function $\mathrm{\ell }:{ℝ}^n\times {ℝ}^m\to \overline{ℝ}$ defined by $$\mathrm{\ell }(x,y)=f(x)-⟨y,G(x)⟩$$ is called the lagrangian of (5). This object plays a vital role in the first-order theory of constrained optimization.

Armed with the lagrangian we can compute $${\phi }_{\ast }(0,y)=\underset{x\in {ℝ}^n}{sup}-\mathrm{\ell }(x,y)=-\underset{x\in {ℝ}^n}{inf}\mathrm{\ell }(x,y),$$ and with this we obtain the duality formula $$\underset{x\in \{z|G(z)=0\}}{inf}f(x)\ge \underset{y\in {ℝ}^m}{sup}\underset{x\in {ℝ}^n}{inf}\mathrm{\ell }(x,y).$$

Let's investigate one more thing. Observe that Therefore $$\underset{x\in \{z|G(z)=0\}}{inf}f(x)=\underset{x\in {ℝ}^n}{inf}\underset{y\in {ℝ}^m}{sup}\mathrm{\ell }(x,y),$$ and the final formulation of the lagrangian duality is $$\underset{x\in {ℝ}^n}{inf}\underset{y\in {ℝ}^m}{sup}\mathrm{\ell }(x,y)\ge \underset{y\in {ℝ}^m}{sup}\underset{x\in {ℝ}^n}{inf}\mathrm{\ell }(x,y).$$ In other words, duality comes from commuting $inf$ and $sup$ for the lagrangian function and strong duality holds exactly for those problems whit lagrangians for which $inf$ and $sup$ commute.

In this section we will see some sufficient conditions on the perturbation function for strong duality to hold. This section is marked with * because this result is rather technical, so feel free to skip it if this is your first foray in duality theory for optimization.