For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$ \max_{x \in [0,1]^n} \|Ax+b \|_1 $$
Or is this problem NP-hard?
4
-
1$\begingroup$ Would anyone care to explain the close votes? This doesn't look immediately obvious to me. $\endgroup$– Noah SteinCommented Jun 3, 2015 at 12:29
-
$\begingroup$ Is $B=(b_{i,j})_{i,j}$ quadratic? If I understand u correctly u want to minimize $\|Ax-b\|_{1}$ where $A\in \mathbb{R}^{m\times n}$ and $b\in \mathbb{R}^m$ subject to the constraint $x \in [0,1]^n$. $\endgroup$– user35593Commented Jun 3, 2015 at 12:31
-
1$\begingroup$ @user35593 : maximize, not minimize. $\endgroup$– Robert IsraelCommented Jun 3, 2015 at 18:14
-
$\begingroup$ @user35593: Yes you are correct, I can reformulate the problem to matrix form. However, as Robert Israel mentions it is a maximization problem. $\endgroup$– OleSCommented Jun 6, 2015 at 12:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Note that since the objective is convex, there are optimal solutions that are extreme points of the feasible region, i.e. we can assume all $x_i \in \{0,1\}$.
We can encode an Ising hamiltonian in this problem, with spins $\sigma_i = (-1, 1)$ corresponding to $x_i = (0, 1)$.
Thus a term $$J \sigma_1 \sigma_2 = \cases{ | J x_1 + J x_2 - 2 J| - J & if $J > 0$\cr |J x_1- J x_2| + J & if $J < 0$ }$$ while for single spins $$ h \sigma = \cases{|2h x | - h & if $h > 0$\cr |2hx - 2h| + h & if $h < 0$\cr}$$
Maximizing (or minimizing) such a Hamiltonian is well-known to be NP-hard.
answered Jun 3, 2015 at 21:29
-
$\begingroup$ Too bad it is NP-hard since I need to solve it for a real world application. I guess I need keep $n$ small in order to test all combinations. Thanks for your feedback. $\endgroup$– OleSCommented Jun 6, 2015 at 12:54
-
$\begingroup$ You can probably do a lot better than "test all combinations". $\endgroup$ Commented Jun 7, 2015 at 6:27