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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityFor 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?
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.