3
$\begingroup$

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

enter image description here

Does anybody know why they start the proof from:

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

Where does it come from?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.