Perturbed Optimization and Duality

The Dual Problem

(Ekeland and Temam 1999) describe the concept of perturbed optimization and how it relates to duality theory. It is interesting to derive standard Lagrange and Fenchel duality from this perspective. Consider a function $f:E\to \overline{\mathbb{R}}$ from $E={\mathbb{R}}^n$ to the extended real numbers $\overline{\mathbb{R}}=\mathbb{R}\cup \{-\mathrm{\infty },+\mathrm{\infty }\}$. We are interested minimizing $f$. We introduce a perturbation function $\mathrm{\Phi }:E\times F\to \overline{\mathbb{R}}$ where $F={\mathbb{R}}^m$ and such that

$$f(x)=\mathrm{\Phi }(x,0)\text{for all }x\in E.$$

Our purpose is to compute $v(0)$ where the value function $v:F\to \overline{\mathbb{R}}$ is defined as

$$v(y)=\underset{x\in E}{inf}\mathrm{\Phi }(x,y)\text{for all }y\in F.$$

The convex conjugate function ${\mathrm{\Phi }}^{\ast }:E^{\ast }\times F^{\ast }\to \overline{\mathbb{R}}$ is defined as

$${\mathrm{\Phi }}^{\ast }(p,q)=\underset{x\in E,y\in F}{sup}⟨p,x⟩+⟨q,y⟩-\mathrm{\Phi }(x,y)$$

so that $\mathrm{\Phi }(x,y)+{\mathrm{\Phi }}^{\ast }(p,q)\ge ⟨p,x⟩+⟨q,y⟩$ for all $(x,y,p,q)$. In particular, we have

$$\mathrm{\Phi }(x,0)+{\mathrm{\Phi }}^{\ast }(0,q)\ge 0$$

for all $x\in E$ and $q\in F^{\ast }$. Since algebra directly shows that ${\mathrm{\Phi }}^{\ast }(0,q)=v^{\ast }(q)$, we have the fundamental inequality:

$$\begin{array}{}\text{(1)}& v(0)=\underset{x\in E}{inf}f(x)\ge \underset{q\in F^{\ast }}{sup}-v^{\ast }(q)=v^{\ast \ast }(0).\end{array}$$

This is the so-called dual problem. Note that it does indeed depend on the perturbation function $\mathrm{\Phi }$ and not only on the function $f$. If one can analyze the conjugate function $v^{\ast }$, then one can obtain lower bounds on the infimum of $f$. As first sight, Equation 1 may seem like a trivial result since for any function $F$ we have that $F(0)+F^{\ast }(0)\ge 0$ and getting hold of the conjugate function $v^{\ast }$ does not seem to be an easy task; we will see that this is not the case. One says that strong duality holds if

$$\begin{array}{}\text{(2)}& v(0)=v^{\ast \ast }(0).\end{array}$$

Convexity and Strong Duality

If one assumes that the objective function $f(x)$ is convex and the perturbation function $\mathrm{\Phi }(x,y)$ is jointly convex in $(x,y)$, then the value function $v$ is also convex. Indeed, the function $y\mapsto \underset{x}{inf}C(x,y)$ is convex as soon as the function $C(x,y)$ is convex in $(x,y)$. Since a function $g$ equals its biconjugate $g^{\ast \ast }(x)$ at a point $x$ as soon its subdifferential $\partial g(x)$ is nonempty, this shows that strong duality @#eq-strong-duality holds as soon as $\partial v(0)\ne \mathrm{\varnothing }$. Furthermore, in a finite dimensional space, a convex function is continuous and admits a subdifferential at any point within the interior of its domain. This shows that if $0$ belongs to the interior of the domain of $v$, then strong duality holds. Since a convex function is continuous at $x$ if it is bounded in a neighborhood of $x$, strong duality holds as soon as $v$ is bounded in a neighborhood of $0$. By definition of the value function we have that $v(y)\le \mathrm{\Phi }(x,y)$. This shows that strong duality holds as soon $v(0)$ is finite and there exists $x_0\in E$ such that the function ${\mathrm{\Phi }}_{x_0}:y\mapsto \mathrm{\Phi }(x_0,y)$ is continuous at $0$.

Fenchel Duality

Consider the case of a function to minimize of the type:

$$\underset{x}{inf}f(x)=G(x)+H(Ax)$$

for a linear operator $A:E\to F$ and two convex functions $G:E\to \overline{\mathbb{R}}$ and $H:F\to \overline{\mathbb{R}}$. One can consider the perturbation function

$$\mathrm{\Phi }(x,y)=G(x)+H(Ax-y).$$

Algebra gives that ${\mathrm{\Phi }}^{\ast }(0,q)=G^{\ast }(A^{\mathrm{\top }}q)+H^{\ast }(-q)$ so that the dual problem reads

$$\underset{q\in F^{\ast }}{sup}-G^{\ast }(A^{\mathrm{\top }}q)-H^{\ast }(-q).$$

By the previous discussion, strong duality holds, for example, as soon as the primal problem is finite and there exists $x_0$ such that $G(x_0)<\mathrm{\infty }$ and the function $H$ is continuous at $A{x}_0$.

References

Ekeland, Ivar, and Roger Temam. 1999. Convex Analysis and Variational Problems. SIAM.