Geometric intuition of conjugate function I am looking for a geometric and intuitive explanation of the conjugate function and how it maps to the below analytical formula.
$$ f^*(y)= \sup_{x \in \operatorname{dom} f } (y^Tx-f(x))$$
 A: You can think of conjugate function as an extended infimum function. For $y=0$,$\ f^*(y)$ is simply the infimum of $f$. Here I try to explain what it means geometrically.
Assume:
$x \in \mathbb{R}^n$
, $x_{n+1}= f(x) \in \mathbb{R}$
I denote the axis that measures the output of $f$ as $x_{n+1}$.
Note that we always measure the infimum of a function according to the line $x_{n+1}=0$. Think of finding the infimum of $f$ as finding the supremum of a set $S$:
$ inf(f) = sup(S = \{ 0 - f(x) | x \in dom f\})$
But what if we wanted to measure the infimum of $f$ according to an inclined line that passes through the origin, say, $y^Tx=0$? This is where we can use conjugate function. It takes the slope of the line as its input, and outputs $f$'s infimum according to the line $y^Tx=0$. So its formula should make sense now. It looks like the case above:
$f^*(y) = sup(S = \{y^Tx - f(x)|x\in dom f\})$
As an example of its usage, we sometimes need to measure this extended infimum function in Lagrange dual function for finding a lower bound on the optimal value of an optimization problem.
A: To me the best interpretation is economic. Interpret $f(x)$ as the cost to produce the quantity $x$ of some product and interpret $y$ as the market price per unit. It is easy to see that $f^*(y)$ represents the optimal profit at given prices $y$. The quantity $xy$ represents revenue from sales and $f(x)$ represents production costs.
Now for the geometrical interpretation. If you sketch the graph of the costs of production $f(x)$ and assume it convex, continuous, and differentiable, you will see that the point of optimal production, given prices $y$, is given by $y - f'(x)=0$, and this can be found graphically with a ruler, looking for the tangent in the cost curve with the same slope $y$. If you place the ruler in that tangent point, it can be seen that the ruler intersection with the vertical axis will give $-(xy - f(x))$.
This is a very useful calculating device. Provided only with the graph of $f(x)$ and a ruler, the analyst is able to turn the ruler and find what is the optimal profit for each possible price. This can be plotted into another piece of paper. Then given any price $y$ he is able to find what was the optimal profit. Without noticing, he has discovered the conjugate function.
A: I found Bertsekas' explanations quite simple and useful to understand many different things in convex analysis and optimization. You may want to check out his book "Convex Optimization Theory", or his notes for the MIT course, which also cover conjugacy.
The short explanation on page 7 of the notes is as follows:

Dual description of convex functions
  
  
*
  
*Define a closed convex function by its epigraph.
  
*Describe the epigraph by hyperplanes.
  
*Associate hyperplanes with crossing points (the conjugate function).
  
  
  
Primal description: Values $f(x)$. Dual description: Crossing points $f^*(y)$.

A: I'm going to attempt a very basic and intuitively understandable explanation. Of course this will be grossly oversimplifying things but I understand it's what was asked for.
The point of the convex conjugate is to represent a function $f$ as a set of tangent hyperplanes. The parameters of all the tangent hyperplanes are encoded in the convex conjugate function $f^*$.
Let's make things easier to understand by covering the 1D case. In that case our $f^*$ is called the Legendre transformation and our hyperplanes become simple lines. The generalization to multidimensional functionals is then relatively straightforward.
Here's the Legendre transformation:
$f^*(y)=\sup(yx - f(x))$
The domain of $f^*$ is slope values, the co-domain is y-offsets (as in a simple line equation $ax + b$). Hence $f^*$ encodes a set of lines. First we're going to evaluate $f^*$ at a single point $y$.
$f^*$ at a point $y$ is the largest difference value between $f$ and a line through the origin with slope $y$.
Note that this value might be still negative. In plain English, it's the degree to which $yx$ "surpasses" $f(x)$ in value. If your function $f$ goes "above" $yx$ (for example $f(x) = x^2+1$ and $y=0.5$) then the value $f^*(y)$ will be negative. If your function goes "below" $yx$ your value will be positive.
The "surpass value" is important because in the convex case it is one parameter of a tangent line to $f$: the y-offset.
To imagine $f^*(y)$ not just for a single value $y$ but for the entire domain, picture $f(x)$ and a line through the origin that's rotating around the origin, like a propeller. For each incremental rotation we plot the largest difference value between $f$ and the line into a new coordinate system (where $y$ may go along the x-axis and $f^*(y)$ may go along the y-axis). The resulting graph then shows the whole Legendre transformation of $f$.
The Wikipedia Article on Legendre transformations also has some more good information, such as:
If the convex function $f$ is defined on the whole line and is everywhere differentiable, then $f^*(y)$ can be interpreted as the negative of the y-intercept of the tangent line to the graph of f that has slope $y$.
So $f^*$ can be seen as a map where the input is a slope and the output is a y-offset in the coordinate system of $f$. Thus $f^*$ holds the information how much I need to offset a line with a particular slope such that it becomes a tangent to $f$. The set of all the lines offset in y by their respective amounts covers the area at and below $f$.
It's not too hard to imagine why that particular trick only works for convex functions.
PS: If $f$ is convex there is a much easier definition of the Legendre transformation which avoids the whole supremum thing:
$f^*(f'(x))=x*f'(x)-f(x)$
In plain English: For $x$ We compute $f'(x)$ and define $f^*$ at $f'(x)$ as the negative y intercept of the tangent line.
A: Some intuition might come from thinking in terms of support functions. Given a set $A\subseteq \mathbb{R}^n$, its support function is given by
$$h_A(x)\equiv \sup\{x\cdot a: \,\,a\in A\}.$$
The idea is simple: the support function attempts to describe a set by the set of its support hyperplanes. For each direction $x\in\mathbb{R}^n$, we project the set $A$ onto $x$, and look for the largest value of the projection. This will correspond to an hyperplane that has normal vector $x$, and is tangent to $A$. More precisely, $h_A(x)$ tells you that said tangent hyperplane is
$$\{y\in\mathbb{R}^n : \,\, x\cdot y=h_A(x)\}.$$
If $A$ is convex, then it is completely characterised by the set of its support hyperplanes, and thus there is a bijection between $A$ and $h_A$.
Consider now a function $f:\mathbb{R}^n\to \tilde{\mathbb{R}}$, and its epigraph:
$$\operatorname{epi}(f)\equiv \{(x,\alpha)\in\mathbb{R}^{n+1}: \,\, f(x)\le \alpha\}\subseteq \mathbb{R}^{n+1}.$$
Geometrically, this is the set of point that sit above (or on) the graph of $f$. A function $f$ is convex (as a function) iff its epigraph is (as a set).
Because we now have a convex set to deal with, the epigraph of $f$, a natural question is how can we characterise it via its support hyperplanes, i.e., what's its support function. We have
$$h_{\operatorname{epi}(f)}(\mathbf x^*,y^*) =
\sup_{\mathbf x\in\mathbb{R}^n, \,\, \alpha\ge f(\mathbf x)} \left(\mathbf x^*\cdot\mathbf x+y^* \alpha\right).$$
Note that I'm strictly following the definition of $h_A(x)$ I gave above.
But we can now observe something else: for the characterisation in terms of hyperplanes, we don't need to look at $h_A(\mathbf x^*)$ for all $\mathbf x^*\in\mathbb{R}^n$. Rather, it's enough to look at all directions. This can mean all $\mathbf x^*$ such that $\|\mathbf x^*\|=1$. But it can also mean, if we have a subset of $\mathbb{R}^{n+1}$ like we do here, that it's enough to only look at "direction vectors" of the form $(\mathbf x,\pm1)$ for all $\mathbf x\in\mathbb{R}^n$.
But also, $h_{\operatorname{epi}(f)}(\mathbf x^*,1)$ is bound to always be infinite for convex $f$ (think of what the tangent hyperplanes of such functions look like).
It is therefore sufficient to look at $h_{\operatorname{epi}(f)}(\mathbf x^*,-1)$. If we use the definition above, this is
$$h_{\operatorname{epi}(f)}(\mathbf x^*,-1)
\equiv \sup_{\mathbf x\in\mathbb{R}^n} \left(\mathbf x^*\cdot\mathbf x-f(\mathbf x)\right).$$
Note that we could remove the $\alpha\ge f(\mathbf x)$ part of the sup because maximising with respect to such $\alpha$ is trivial: we need the $\alpha$ that maximises $-\alpha$ and is such that $\alpha\ge f(\mathbf x)$, and this is clearly just $-f(\mathbf x)$.
We just found precisely the convex conjugate of $f$.
We conclude that the convex conjugate of $f$ can be given the precise geometric interpretation of the function characterising the set of tangent hyperplanes to the (epi)graph of $f$.
See also Please explain the intuition behind the dual problem in optimization., and Physical interpretation and notions about conjugate function?.
