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.

  • 2
    $\begingroup$ What do you mean by non-decreasing function $c:\mathbb R^d \rightarrow \mathbb R$ ? $\endgroup$ – dohmatob Mar 26 '20 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.

  • $\begingroup$ 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. $\endgroup$ – Francis Apr 7 '20 at 16:30
  • $\begingroup$ Your example does not have a minimizer. If the problem has a minimizer, then $0$ is a minimizer. Otherwise, the infimal value is $-\infty$. $\endgroup$ – gerw Apr 7 '20 at 17:40
  • $\begingroup$ 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. $\endgroup$ – Francis Apr 7 '20 at 22:44
  • $\begingroup$ If the feasible region is bounded, my conclusion fails. The main argument was that we can look at rays starting in $0$. $\endgroup$ – gerw Apr 8 '20 at 6:14

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.