Revisions to Hardness of concave minimization problem

Bumped by Community user

occurred Aug 31, 2021 at 17:00

Bumped by Community user

occurred May 3, 2021 at 16:05

Bumped by Community user

occurred Jan 3, 2021 at 16:01

Bumped by Community user

occurred Sep 5, 2020 at 15:06

Bumped by Community user

occurred May 8, 2020 at 15:01

added 84 characters in body

Source Link

edited Apr 8, 2020 at 15:00

Francis

29
2

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.

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

added 84 characters in body

Source Link

edited Apr 8, 2020 at 14:51

Francis

29
2

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}, \text{and } \|C\|_2 \leq \gamma$$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 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}, \text{and } \|C\|_2 \leq \gamma$. 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 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$.

added 42 characters in body

Source Link

edited Apr 7, 2020 at 22:48

Francis

29
2

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$ and, $x \in \mathbb{R}^d_{\geq 0}$$x \in C \subseteq \mathbb{R}^d_{\geq 0}, \text{and } \|C\|_2 \leq \gamma$. 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 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$ and $x \in \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 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}, \text{and } \|C\|_2 \leq \gamma$. 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?