13
$\begingroup$

If given a convex function $f: \mathbb{R} \to \mathbb{R}$, then the conjugate function $f^*$ is defined as $$f^*(s) = \sup_{t \in \mathbb{R}} (st-f(t))$$

Now i want to understand what is the physical interpretation of this conjugate function? What is its exposition? Please help me.

$\endgroup$
11
$\begingroup$

The basic idea behind duality in convex analysis is to view a (closed) convex set $C$ as an intersection of half spaces. Applying this idea to the epigraph of a convex function $f$ suggests that we should view $f$ as a supremum of affine functions.

An affine minorant of $f$ is a function $x \mapsto \langle m, x \rangle - b$ such that $$ \tag{$\spadesuit$} f(x) \geq \langle m, x \rangle - b \quad \text{for all } x. $$ The vector $m$ is called the "slope" of the affine minorant. Typically $f$ has many affine minorants with a given slope $m$, corresponding to different values of the scalar $b$. We only care about the best affine minorant with slope $m$ --- in other words, we only care about the best scalar $b$. So: For a given $m$, which value of $b$ is the "best"? Which value of $b$ makes the inequality in $(\spadesuit)$ as tight as possible?

Notice that \begin{align} & f(x) \geq \langle m, x \rangle - b \quad \text{for all } x \\ \iff & b \geq \langle m, x \rangle - f(x) \quad \text{for all } x\\ \iff & b \geq \sup_x \, \langle m, x \rangle - f(x) \\ \iff & b \geq f^*(m). \end{align} This shows that the best choice of $b$ is $f^*(m)$. We have just discovered the convex conjugate $f^*$. The whole point of $f^*$ is that it tells us how to view $f$ as a supremum of affine functions. You give $f^*$ a slope $m$, and it gives you the best choice of $b$.

It now becomes very intuitive that $f$ can be recovered from $f^*$, because: \begin{align} f(x) &= \sup_m \, \langle m, x \rangle - f^*(m) \quad \text{(because $f$ is a supremum of affine functions)} \\ &= f^{**}(x). \end{align} While it is obvious that $f$ can be recovered from $f^*$, the fact that the "inversion formula" $f = f^{**}$ is so simple is a surprising and beautiful fact.

I wrote a similar explanation with some more details here: Please explain the intuition behind the dual problem in optimization.

$\endgroup$
  • $\begingroup$ Wow, this just explained this topic so well. Thank you! $\endgroup$ – 今天春天 Jul 6 '18 at 20:03
7
$\begingroup$

Suppose $f: \mathbb{R}^n \to \mathbb{R}$, then the conjugate function is: $$f^*(\mathbf{y}) \triangleq \sup_{x\in \text{dom} f} [\mathbf{y}^T\mathbf{x}-f(\mathbf{x})],$$ where: $\text{dom}f^* = \{\textbf{y}|f^*(\mathbf{y})<+\infty\}$. Then, it is clear from the definition that it is a function bounded above.

Some notions and descriptions about the conjugate function:

  1. Even if $f(x)$ is a non-convex function, then the conjugate function $f^*(\mathbf{y})$ is guaranteed to be a convex function in $\mathbf{y}$. [Notice: The conjugate function is the pointwise supremum of a set of affine functions in $\mathbf{y}$ (here, convexity aspect of affine function matters) , so, it is convex.]

  2. As an interpretation, it somehow represents (encodes) the convex hull of the epigraph of $f$ in terms of its supporting hyperplanes (The concept behind this is depicted in figure below.).enter image description here

  3. There is an alternative way to obtain the (Lagrange) dual function of the primal problem by using conjugate function.

  4. If the function $f$ is closed and convex, then $f^{**} = f$ (conjugate of conjugate is function itself);

    Proof:
    Suppose $f$ is differentiable, then the conjugate function, which is the max $\mathbf{y}^T\mathbf{x}$ and the function $f$ over its domain can be obtained as,

    $$\nabla_{\textbf{x}}[\mathbf{y}^T\mathbf{x}-f(\mathbf{x})] = \mathbf{0}_n \implies \mathbf{y} = \nabla_{\mathbf{x}} f(\mathbf{x}^{\star}).$$ Also, by assuming the $f$ as convex function, the second order condition is satisfied and we have

    $$f^*(\mathbf{y}) = \nabla_{\mathbf{x}}f(\mathbf{x}^\star)^T \mathbf{x}-f(\mathbf{x}^\star).$$ Then by using thses results we have,

    \begin{eqnarray} f^{**}(\mathbf{x}) &=& \sup_{\mathbf{y} \in \text{dom} f^*} [\mathbf{x}^T\mathbf{y}-f^*(\mathbf{y})]\\ &=& \sup_{\mathbf{x}_{0} \in \text{dom} f} [\mathbf{\mathbf{x}}^T\nabla f(\mathbf{x}_{0}) -\nabla f(\mathbf{x}_{0})^T\mathbf{x}_{0} +f(\mathbf{\mathbf{x}_{0}})]\\ &=& \sup_{\mathbf{x}_{0} \in \text{dom} f} [f(\mathbf{\mathbf{x}_{0}})+\nabla f(\mathbf{x}_{0})^T(\mathbf{x}-\mathbf{x}_{0})] \\ &=& f(x), \end{eqnarray}

    where the last equality refers to the first order condition for a convex function as:

    $$f(\mathbf{y}) \geq f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}) \quad \text{for all } \mathbf{x}, \mathbf{y} \in \text{dom}f.$$

  5. If the $f$ is a lower semi-continuous function and its domain is compact (i.e., closed and bounded), and suppose $g_{f}$ is the convex envelope of $f$, then $f^{**} = g_{f}$ [4].


References for more info.:

  1. Convex Optimization for Signal Processing and Communications, by Chong-Yung Chi.
  2. Convex Optimization by Stephen Boyd.
  3. Convex analysis and optimization, by D. P. Bertsekas.
  4. Lagrange multipliers and nonconvex programs, by J. Falk.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.