Nemirovski Proposition 2.3.7 (exponential cone)

Question

I came across Proposition 2.3.7 from Nemirovski (https://www2.isye.gatech.edu/~nemirovs/LMCOLN2022Fall.pdf) which states the following:

Does anybody know why they start the proof from:

$$\exp\{y-4y^{2} \}\leq 1+y \leq \exp\{y\}$$

Where does it come from?

Answer 1

The basic idea behind the result is that $\exp(x) = 1 + x + O(x^2)$, whereby $\exp(x) = \exp(2^{-k} x)^{2^k} = \lim_{k \rightarrow \infty} (1 + 2^{-k} x)^{2^k}$ holds for all $x \in \mathbb{R}$ and provides an approximation for any finite $k$.

To verify the strength of the approximation the authors wished to establish a sandwich of the form $$ (1 - \epsilon)\exp(x) \leq (1+ 2^{-k} x)^{2^k} \leq \exp(x).$$

The upper bound of this sandwich is implied by the valid inequality, $(1 + y) \leq \exp(y)$, as seen by setting $y = 2^{-k} x$.

To lower bound of the sandwich is less obvious and we need to find a multiplier such that $f(x) \exp(x) \leq (1+ 2^{-k} x)^{2^k}$ on the range $|x| \leq R$. Letting $f(x) = g(x)^{2^k}$, this simplifies to $g(y) \exp(y) \leq (1+ y)$ on the range $|y| \leq 2^{-k} R$. Obviously, $g(y) \leq 1$ for this to be valid and for a tight sandwich we also impose $g(0) = 1$. Thus $g(y) = 1 + O(y^2)$ and this yields two obvious candidates:

• $g(y) = 1 - y^2\quad$ (the simplest polynomial).
• $g(y) = \exp(-y^2)\quad$ (the simplest Gaussian function / bell curve).

Although both of these multipliers establish the sandwich inequality for finite values of $k$, the latter stays closer to $1$ in the neighborhood of $0$, thus reaching the max deviation of $1 - \epsilon$ for smaller values of $k$, thus resulting in a smaller second-order cone approximation.

Why the authors added a constant factor and used $g(y) = \exp(-4y^2)$ is beyond me. Probably they had a smarter way of producing the multiplier that didn't involve guessing.