How can I derive the following lower bound for $\arccos(x)$ for $x\in [-1, +1]$ $$\frac{\text{arccos}(x)}{\pi} ≥ \frac{0.8785(1-x)}{2}$$
I can see it from the plot that it holds, but how would one derive it?
This appeared in some lecture notes discussing randomized algorithms to get the solution of a quadratic binary optimization problem from a SDP relaxation.
You know that the lower bound function $f(x)$ is of the form $f(x)=m(x-1)$, because you want it to be $0$ at $x=1$. You also want $f$ to coincide with $\arccos(x)/\pi$ at the same point where the derivatives match (they are tangent). This gives you a set of 2 equations with 2 unknowns: the slope of the bound and $x_0$, where the two functions are tangent. This system can be solved numerically. For example, with Python, you could use the code provided here.
Another way to think about this would be to consider the 1st order Taylor expansion of the $\arccos(x)/\pi$ as a function of the coordinate around which it is expanded, $x_0$, and express it in the form $ax+b$. Then, one has to find the value of $x_0$ at which $b=-a$.
One can actually prove that this is the tightest linear lower bound to the original function in some sense. The argument is as follows. Of all the linear lower bounds, the tightest one naturally corresponds to the smallest value of $$I[\ell(x)=ax+b]=\int_{-1}^{1}\mathrm{d}x\left(\frac{\arccos(x)}{\pi} - \ell(x)\right) = 1 - 2b,$$ which, noticeably, only depends on $b$. Then, we have to find the highest value of $b$ (smaller than $1/2$) for which there exists at least one possible value of $a$ such that the function $\ell(x)=ax+b$ is actually a lower bound. For a sufficiently small $b$, the possible values of $a$ will belong to an interval (consider for reference the case $b=0.2$, for example, that you can see below, where $a\in[-0.73,-0.2]$). The conditions that determine the minimum and maximum values of $a$ are then to touch the original function, but never cross: $\ell(x)$ tangent to the original function and $\ell(1)=0$, respectively. It's easy to check that the possible interval for $a$ becomes smaller as $b$ becomes larger. Eventually, only a single value of $a$ is allowed, and this happens at the maximum possible value of $b$ that yields a linear lower bound. To get it, we must apply both conditions, as done above.