0
$\begingroup$

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!

$\endgroup$
  • $\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. Mar 26 '18 at 17:57
  • 1
    $\begingroup$ To show that your problem is NP-hard, try encoding SAT as a non-convex optimization problem. $\endgroup$ – Yuval Filmus Mar 26 '18 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 Mar 26 '18 at 19:31
  • $\begingroup$ However, the answer depends on your function. There are nonconvex functions easy to optimize. $\endgroup$ – Eugene Mar 26 '18 at 19:32
3
$\begingroup$

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.

$\endgroup$
  • $\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 Nov 18 '18 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$ – Daniel Porumbel Oct 5 at 14:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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