Is global non-convex optimization NP-complete?
Yes, non-convex optimization is NP-hard. For a simple proof, consider the following reduction from Subset-Sum. The Subset-Sum problem asks whether there is a subset of the input integers $a_1, \dots, a_n$ which sums to zero. To reduce to non-convex programming, let $x_1, \dots, x_n$ be variables encoding the subset and consider the following non-convex program:

$$
\begin{align*}
\text{minimize }\quad&amp;(a\cdot x)^2 + \sum_{i=1}^n x_i^2(1 - x_i)^2\\
\text{subject to}\quad&amp; \sum_{i=1}^n x_i \ge 1.
\end{align*}
$$

Note that the optimum of this program is zero iff the Subset-Sum instance has a subset which sums to zero.