1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ What do you mean by non-decreasing function $c:\mathbb R^d \rightarrow \mathbb R$ ? $\endgroup$
    – dohmatob
    Commented Mar 26, 2020 at 7:15

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Apr 7, 2020 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
    Commented Apr 7, 2020 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
    Commented Apr 7, 2020 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
    Commented Apr 8, 2020 at 6:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .