1
$\begingroup$

I am currently working on a project that involves a mixed-integer non-linear optimization problem, and wondering if I can state that this problem NP-hard in a research paper. I'm not looking for a formal proof as much as a reasonable argument and/or a citation.

The MINLP has the following general form:

$\begin{align} \min_{x} & \quad f(x) + C ~\|x\|_0 \\ \text{s.t.} & \qquad x \in \mathbb{Z}^d \cap [10,10]^d \end{align}$

where:

  • $\|x\|_0 = \sum_{i=1}^d 1[x_i \neq 0]$ is the $l_0$-norm

  • $C > 0$ is fixed constant that represents the $l_0$ regularization parameter

  • $f: \mathbb{R}^d \rightarrow \mathbb{R}^+$ is a strictly convex non-linear function. In practice, $f$ is a loss function and is part of the input. As an example, consider $f(x) = \log(1+\exp(-x^T z_k))$ where $z_1,\ldots,z_K \in \mathbb{R}^d$ are fixed parameters derived from a dataset.

In practice, I represent and implement this MINLP using the following formulation:

$\begin{align} \min_{x} & \quad \sum_{k=1}^K v_k + C ~\sum_{i=0}^d y_i & \\ \text{s.t.} & \qquad f_k = \log(1+\exp(-x^T z_k)) & \text{for } k = 1,\ldots,K\\ & \qquad |x_i| \leq 10 y_i & \text{for } i = 1,\ldots,d\\ & \qquad x_i \in \{-10,\ldots,10\} & \text{for } i = 1,\ldots,d\\ & \qquad y_i \in \{0,1\} & \text{for } i = 1,\ldots,d\\ \end{align}$

This formulation requires $K + 2d$ total variables ($f_k, x_i, y_i$) of which $K$ are real and $2d$ are discrete. In addition, it uses $K + 2d$ constraints (this accounts for the fact that we have to express the $|x_i| \leq 10 y_i$ constraints using two constraints, but does not account for the lower and upper bound constraints on $x_i$ and $y_i$).


Some thoughts: I am pretty sure that the problem is NP-hard, since it has the elements of other problems that are NP-hard such as $l_0$ regularization and integer constraints.

The problem can be reformulated as a "convex" MINLP (i.e., an optimization problem with a convex objective function with integer constraints). To see this, just replace the $\|x\|_0$ term in the objective with $\sum_{i=0}^d y_i$ and add the constraints $y_i \in \{0,1\}$ and $|x_i| \leq 10 y_i$ for $i = 1,\ldots,d$ to obtain:

$\begin{align} \min_{x} & \quad f(x) + C ~\sum_{i=0}^d y_i \\ \text{s.t.} & \qquad x \in \mathbb{Z}^d \cap [10,10]^d \\ & \qquad |x_i| \leq 10 y_i \text{ for } i = 1,\ldots,d \\ & \qquad y_i \in \{0,1\} \text{ for } i = 1,\ldots,d \end{align}$

This paper argues that most convex MINLP instances are NP-hard in the introduction, but also that they might be but says that it might also be instance (since they constitute a wide variety of optimization problems).

$\endgroup$
  • 1
    $\begingroup$ To make the question meaningful, you're going to need to decide: is $f$ part of the input, or is a fixed function (that's a constant)? If it's part of the input, you need to specify how it will be represented before the question will be answerable. If it's a fixed function, you need to specify what the specific function is before the question will be answerable. $\endgroup$ – D.W. May 26 '16 at 19:54
  • $\begingroup$ @Berk U. : ​ See D.W.'s middle sentence. ​ ​ ​ ​ $\endgroup$ – user12859 May 26 '16 at 22:33
  • $\begingroup$ I see you edited the question to state that $f$ is part of the input. However, as I wrote in my prior comment, now you need to specify how $f$ will be represented before the question is answerable -- so I'm afraid you're going to need to do some more editing... $\endgroup$ – D.W. May 26 '16 at 23:37
  • $\begingroup$ No problem! I took at shot at explaining the representation in my latest edit. I'm really unfamiliar with computational complexity so I'm not sure it's right. Is this what you guys meant? $\endgroup$ – Berk U. May 26 '16 at 23:53

Your Answer

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

Browse other questions tagged or ask your own question.