5
$\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!

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 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
    Mar 26, 2018 at 19:31
  • $\begingroup$ However, the answer depends on your function. There are nonconvex functions easy to optimize. $\endgroup$
    – Eugene
    Mar 26, 2018 at 19:32

2 Answers 2

Reset to default
6
$\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.

Improve this answer
$\endgroup$
2
  • $\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, 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$
    – Daniel Porumbel
    Oct 5, 2019 at 14:30
3
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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