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 Stein– Noah Stein2015-06-03 12:29:56 +00:00Commented 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$user35593– user355932015-06-03 12:31:38 +00:00Commented Jun 3, 2015 at 12:31
- 1$\begingroup$ @user35593 : maximize, not minimize. $\endgroup$Robert Israel– Robert Israel2015-06-03 18:14:10 +00:00Commented 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$OleS– OleS2015-06-06 12:52:35 +00:00Commented 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.
- $\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$OleS– OleS2015-06-06 12:54:19 +00:00Commented Jun 6, 2015 at 12:54
- $\begingroup$ You can probably do a lot better than "test all combinations". $\endgroup$Robert Israel– Robert Israel2015-06-07 06:27:29 +00:00Commented Jun 7, 2015 at 6:27