I am trying to understand how to reason about example 3.21 on page 91 of Boyd & Vandenberghe's Convex Optimization, for the exponential case:
The conjugate of $f(x) = e^x$ is defined as
$$f^*(y) = \sup_{x \in \textbf{dom} f} \left( y^T x - f(x) \right)$$ $xy−e^x$ is unbounded if $y < 0$. For $y > 0$, $xy−e^x$ reaches its maximum at $x=\log(y)$, so we have $f^*(y)=y \log(y)−y$. For $y=0$, $f^*(y) = \sup_x −e^x = 0$.
In summary, $\textbf{dom} f^* = \mathbb{R}_{+}$ and $f^∗(y) = y \log(y) − y$ (with the interpretation $0 \log(0) = 0$).
My questions:
First of all, I don't understand how would someone strategically reason for which values of $y$, $y^Tx - f(x)$ is unbounded. In this case, it is unbounded for $y<0$, for a different problem with $f(x)= - \log(x)$, the expression inside the supremum, $xy + log(x)$ is unbounded for $y \geq 0$. So, how can I consistently reason about such scenarios (which direction y is unbounded and bounded)?
Also, for this particular problem, how did they come up with the domain of $f^*$ at the end. Could you please walk me through it?
Any explanation/intuition or thought process to tackle these type of problems would be highly appreciated. Thanks a lot.
Question 1: The goal is to simplify $$g(y) = \sup_x \left\{ xy - e^x \right\}.$$ To maximize an unconstrained differentiable concave function you normally solve: $$\frac{d}{dx}\left\{ xy - e^x \right\} = y-e^x = 0,$$ but this only has a solution when $y > 0$. For your other example $f(x) = -\log (x)$, you get $d/dx \left\{ xy+\log(x)\right\} =y+1/x=0$ which only has a solution for $y < 0$.
Now you just need to study the cases for which the derivative is never $0$. This is more ad-hoc, but it is still not complete magic. For $xy-e^x$, the derivative is upper bounded by $y$, so if $y<0$, you can get to $\infty$ by letting $x \to -\infty$. For $y=0$ the function value turns out to be bounded. For $xy+\log(x)$ the derivative is always at least $y$, so when $y>0$ you can get to $\infty$ by letting $x \to \infty$. For $y=0$ the function value turns out to be unbounded.
Question 2: $\text{dom} f^*$ is the effective domain of $f^*$, i.e., the part of the domain where $f^*$ is finite. This follows directly from the result of Question 1.