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?


  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Mar 26, 2018 at 17:57
  • 1
    $\begingroup$ To show that your problem is NP-hard, try encoding SAT as a non-convex optimization problem. $\endgroup$ Commented Mar 26, 2018 at 18:07
  • $\begingroup$ Even a QP problem with one negative eigenvalue is $\mathcal{NP}$-hard, see link.springer.com/article/10.1007/BF00120662 $\endgroup$
    – Eugene
    Commented Mar 26, 2018 at 19:31
  • $\begingroup$ However, the answer depends on your function. There are nonconvex functions easy to optimize. $\endgroup$
    – Eugene
    Commented Mar 26, 2018 at 19:32

2 Answers 2


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*} $$

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

  • $\begingroup$ If one want's to convert this into an unconstrained problem, just add a small enough bump function at 0 to the objective. $\endgroup$
    – Miheer
    Commented Nov 18, 2018 at 16:38
  • $\begingroup$ 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. $\endgroup$ Commented Oct 5, 2019 at 14:30
  • $\begingroup$ 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. $\endgroup$ Commented Mar 20 at 8:52

Quadratic programming is an example of a non-convex optimization problem that is NP-hard. See Transforming SAT to Quadratic Programming in polynomial time for a proof.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.