# Hardness of concave minimization problem

I have an optimization problem $$\underset{x}{\min} ~ c(x) - k \cdot x$$ where $$c(x)$$ is a non-decreasing concave function with $$c(0) = 0$$, $$x \in C \subseteq \mathbb{R}^d_{\geq 0}$$. By non-decreasing, I mean the partial derivative of $$c(x)$$ for every dimension of $$x$$ is positive. Is this problem NP-Hard?

I am aware that harish (https://cstheory.stackexchange.com/users/10385/harish) asked a question, Maximizing a convex function with linear constraints, URL (version: 2012-10-17): https://cstheory.stackexchange.com/q/12310 and that one is NP-Hard. In addition, I also searched online and found that concave minimization problems can be NP-hard in general [Pardalos and Rosen] (https://epubs.siam.org/doi/pdf/10.1137/1028106). I am just wondering for my specific concave minimization problem, is it hard to solve? In addition, are there any survey papers on the hardness of some specific concave minimization problems?

I apologize, but I forgot to mention that the feasible region $$C$$ is bounded, i.e. $$\|C\|_2 \leq \gamma$$.

I think I found one paper by Pardalos, Panos M., and Stephen A. Vavasis. "Quadratic programming with one negative eigenvalue is NP-hard." Journal of Global Optimization 1.1 (1991): 15-22. They have the conclusion that $$\min f(x) = \frac{1}{2} x^T Q x + c^T, s.t. Ax \leq b$$ is NP-hard when $$Q$$ is $$n\times n$$ symmetric negative semidefinite matrix. Does this prove my question? Because $$c(x)$$ in my question will be concave if and only if its Hessian matrix is negative semidefinite.

• What do you mean by non-decreasing function $c:\mathbb R^d \rightarrow \mathbb R$ ? Mar 26, 2020 at 7:15

If your problem has a solution $$x^* \ne 0$$, then $$0$$ is also a solution. Indeed, consider the function $$\varphi(t) = c(t \, x^*) - k\cdot (t \, x^*).$$ Since $$x^*$$ is a solution, we have $$\varphi(0) \ge \varphi(1).$$ However, if we would assume $$\varphi(0) > \varphi(1),$$ concavity implies $$\varphi(t) \to -\infty$$ as $$t \to \infty$$. This is a contradiction since $$1$$ is the minimizer of $$\varphi$$.
Hence, $$\varphi(0) = \varphi(1)$$ and this implies that $$x^{**} = 0$$ is also a solution to your original problem.
• The proof makes sense, but the conclusion seems kind of strange to me. Does this mean $\underset{x}{\min} c(x) - k\cdot x$ = 0? However, consider a simple example when $c(x) = \sqrt{x}$ and $k = 1$. Apparently, $\underset{x}{\min} \sqrt{x} - x = - \infty$ instead of 0? So where goes wrong in this problem. Apr 7, 2020 at 16:30
• Your example does not have a minimizer. If the problem has a minimizer, then $0$ is a minimizer. Otherwise, the infimal value is $-\infty$.
• What if the feasible region of $x$ is bounded? Specifically, $x \in X \subseteq \mathbb{R}^d$ and $\|X\|_2 \leq \gamma$, does your conclusion still hold? As far as I can understand, the contradiction doesn't exist because 1 is only the minimizer of $\phi$ within the bounded region $X$, but it's not the minimizer for the whole infty range. Apr 7, 2020 at 22:44
• If the feasible region is bounded, my conclusion fails. The main argument was that we can look at rays starting in $0$.