# 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.
Mar 26, 2018 at 17:57
• To show that your problem is NP-hard, try encoding SAT as a non-convex optimization problem. 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 Mar 26, 2018 at 19:31
• However, the answer depends on your function. There are nonconvex functions easy to optimize. 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. Oct 5, 2019 at 14:30