Consider the functions $f(x) = \sin x$ and $g(x) = (x+1)^2 (x-1)^2$. We know that $f$ has an infinite number of local minimizers and is nonconvex on a non-compact subset of $R$. We know that $g$ has two local minimizers and is nonconvex only on a compact subset of $R$. So, in a sense, $g$ is "closer" to being a convex function than $f$ is.
Is there some test or measure that one might use to represent this fact? I realize that one can look at the hessian and see where it is positive semidefinite, but that can get difficult to interpret, particularly if the function in question is defined on a high-dimensional space or has a complicated hessian.
Along the lines of my previous comment: Let $n$ be a positive integer and let $\mathcal{X} \subseteq \mathbb{R}^n$ be a convex set. Motivated by the standard definition of $\mu$-strong convexity, we can define a (possibly nonconvex) function $f:\mathcal{X}\rightarrow\mathbb{R}$ to have “convexity parameter $\mu$” if $\mu$ is the largest real number such that $$ f(x) - \frac{\mu}{2} ||x||^2$$ is a convex function over $x \in \mathcal{X}$. Here, $||x||= \sqrt{\sum_{i=1}^nx_i^2}$ is the standard Euclidean norm.
Intuitively, the value $\mu$ is the weight associated with the largest parabola that can be subtracted from $f$ while ensuring the resulting function is convex. It can be shown that the function $f$ is convex if and only if $\mu \geq 0$. If $\mu>0$ the function is said to be strongly convex. Larger values of $\mu$ correspond to "stronger" forms of convexity.
In the special case when $\mathcal{X}=\mathbb{R}$ and the function $f$ is twice differentiable, the value $\mu$ is equal to: $$ \mu = -\inf_{x \in \mathbb{R}} f’’(x) $$ and hence represents the degree of curvature of the function.
Examples:
1) $f(x) = \sin(x)$. Then: \begin{align} h(x) &= \sin(x) - \frac{\mu}{2}x^2\\ h'(x) &= \cos(x) - \mu x \\ h''(x) &= -\sin(x) - \mu \end{align} The largest value of $\mu$ for which $h''(x) \geq 0$ for all $x$ is $\mu=-1$.
2) $g(x) = (x+1)^2(x-1)^2$. Then: $$ g''(x) = 12x^2-4 \geq -4$$ The largest value of $\mu$ for which $g(x) - \frac{\mu}{2}x^2$ is convex is $\mu=-4$. Thus, by this measure, this function $g$ is "more nonconvex" than the previous function $f$.
Some useful properties of this definition:
1) If $f$ has convexity parameter $\mu \in \mathbb{R}$, then for any constants $a \in \mathbb{R}^n$ and $b \in \mathbb{R}$, the function $f(x) + a^Tx+b$ also has convexity parameter $\mu$.
2) If $f$ and $g$ are two functions that have convexity parameters $\mu$ and $\lambda$, respectively, then $f+g$ has convexity parameter greater than or equal to $\mu+\lambda$.
3) If $f$ has convexity parameter $\mu \in \mathbb{R}$, then $f(x) - \frac{r}{2}||x-c||^2$ is a convex function for every constant $c \in \mathbb{R}^n$ and $r \leq \mu$.
4) Suppose $f$ is a convex function. Fix $c \in \mathbb{R}^n$ and $\mu \in \mathbb{R}$. Then $f(x) + \frac{\mu}{2}||x-c||^2$ has convexity parameter greater than or equal to $\mu$.