31
$\begingroup$

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))$$

$\endgroup$
  • 1
    $\begingroup$ You can improve this post by asking a more specific question. $\endgroup$ – Pedro Tamaroff Jul 30 '16 at 3:22
  • $\begingroup$ Yes, maybe change the question to "Geometric intuition of conjugate function" or something similar. $\endgroup$ – Lorenzo Stella Aug 1 '16 at 9:02
  • 2
    $\begingroup$ This mini-paper by Bauschke and Lucet does a great job explaining the conjugate with examples and pictures. Link here: people.ok.ubc.ca/bauschke/Research/68.pdf $\endgroup$ – TSF Apr 18 '19 at 12:47
25
$\begingroup$

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).

enter image description here

Primal description: Values $f(x)$. Dual description: Crossing points $f^*(y)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great recommendation. $\endgroup$ – Michael Grant Aug 1 '16 at 14:12
  • $\begingroup$ @Lorenzo Stella I appreciate your answer but good lord, these notes are horrible! It was asked for a "geometric and intuitive explanation" of the convex conjugate, not a 340 pages long book filled with theorems and proofs. $\endgroup$ – rsp1984 Feb 1 '19 at 23:40
  • 2
    $\begingroup$ "Horrible" seems a bit exaggerated to me. There's no need to go through all 340 pages: reading page 7 is sufficient. $\endgroup$ – Lorenzo Stella Feb 3 '19 at 14:16
16
$\begingroup$

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 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 can be found graphically, looking for the tangent in the cost curve which is parallel to the vector $(1, y)$.

The analyst gets a ruler, plots his cost curve and goes around turning the ruler, finding optimal production points for every possible price. He gets a value of $x$ for every price, and can easily calculate the optimal profit at each price. He is happy it is not necessary to plot the cost curve multiple times (no computers back then). Without noticing, he has also discovered the conjugate function.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is actually a really useful explanation, +1 $\endgroup$ – Jeremias K Sep 18 '19 at 19:25
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\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.