# How can I find the maximum value of this function?

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?

• Would anyone care to explain the close votes? This doesn't look immediately obvious to me. Jun 3, 2015 at 12:29
• 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$. Jun 3, 2015 at 12:31
• @user35593 : maximize, not minimize. Jun 3, 2015 at 18:14
• @user35593: Yes you are correct, I can reformulate the problem to matrix form. However, as Robert Israel mentions it is a maximization problem.
– OleS
Jun 6, 2015 at 12:52

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}$$
• 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.