# Is global non-convex optimization NP-complete?

Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision problem

Is there a set of points such that f < C?

Where C is some constant. However, I am not sure if these problems are in the class of NP-Complete, and if so, what would you say the size of the input is? Complexity of the function?

Thanks!

• It's not straightforward to figure out how to formalize this in terms where NP-completeness is applicable. What are the inputs, and what are the desired outputs? Is $f$ fixed, or part of the input? If $f$ is fixed, please specify the function $f$ in the question. If it's part of the input, how is the function $f$ specified? What's the type signature of $f$? Is it continuous ($f:\mathbb{R} \to \mathbb{R}$) or discrete? If it is discrete and specified as a truth table, that takes exponential space, which is problematic. If it id continuous, it can't be specified as a truth table.
– D.W.
Commented Mar 26, 2018 at 17:57
• To show that your problem is NP-hard, try encoding SAT as a non-convex optimization problem. Commented Mar 26, 2018 at 18:07
• Even a QP problem with one negative eigenvalue is $\mathcal{NP}$-hard, see link.springer.com/article/10.1007/BF00120662 Commented Mar 26, 2018 at 19:31
• However, the answer depends on your function. There are nonconvex functions easy to optimize. Commented Mar 26, 2018 at 19:32

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&(a\cdot x)^2 + \sum_{i=1}^n x_i^2(1 - x_i)^2\\ \text{subject to}\quad& \sum_{i=1}^n x_i \ge 1. \end{align*}
• A different way to obtain an unconstrained problem, replace $(a\cdot x)^2$ with $\left(a\cdot x-\frac{a_1+a_2+\dots + a_n}2\right)^2$ and you obtain a reduction from the (bi-)partition problem. Commented Oct 5, 2019 at 14:30
• Leaving note for my own reference: The second term in the expression to minimize is $0$ when $x_i =1$ or $x_i=0$. At all other $x_i$ values, it is $>0$ due to the square. Similarly the minimum attainable value for $(a\cdot x)^2$ is also $0$. Hence the entire expression can be $0$ if some subset of $a_i$'s has zero sum. As finding the minima will have at least as much complexity as the problem of checking if $0$ is a minima, the problem of finding the minima is also NP. Commented Mar 20 at 8:52