# Nemirovski Proposition 2.3.7 (exponential cone)

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?

• The link to the source material is broken, perhaps removed by its author. Commented Aug 8, 2022 at 23:34
• Commented Aug 10, 2022 at 15:19
• Have you tried expanding $\exp(y-4y^{2})$ in a power series? Commented Aug 10, 2022 at 15:32
• No, i did not. All i want is to understand where is it coming from. Commented Aug 11, 2022 at 16:00
• @DmitryAnokhin Brian just told you. Commented Aug 12, 2022 at 13:45

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.