Physical interpretation and notions about conjugate function?
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) = 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.
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}^ \mathsf{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:
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.]
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.).
There is an alternative way to obtain the (Lagrange) dual function of the primal problem by using conjugate function.
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}^\mathsf{T}\mathbf{x}$ and the function $f$ over its domain can be obtained as,$$\nabla_{\textbf{x}}[\mathbf{y}^\mathsf{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)^\mathsf{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}^\mathsf{T}\mathbf{y}-f^*(\mathbf{y})]\\ &=& \sup_{\mathbf{x}_{0} \in \text{dom} f} [\mathbf{\mathbf{x}}^\mathsf{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})^\mathsf{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})^\mathsf{T}(\mathbf{y}-\mathbf{x}) \quad \text{for all } \mathbf{x}, \mathbf{y} \in \text{dom}f.$$
Let $g_{f}$ be the convex envelope of $f$. If $f$ is a lower semi-continuous function and its domain is compact (i.e., closed and bounded), then $f^{**} = g_{f}$ [4].
References for more info.:
- Convex Optimization for Signal Processing and Communications, by Chong-Yung Chi.
- Convex Optimization by Stephen Boyd.
- Convex analysis and optimization, by D. P. Bertsekas.
- Lagrange multipliers and nonconvex programs, by J. Falk.