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).
