2
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Would anyone care to explain the close votes? This doesn't look immediately obvious to me. $\endgroup$
    – Noah Stein
    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
    Jun 3, 2015 at 12:31
  • 1
    $\begingroup$ @user35593 : maximize, not minimize. $\endgroup$ 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
    Jun 6, 2015 at 12:52

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\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
    Jun 6, 2015 at 12:54
  • $\begingroup$ You can probably do a lot better than "test all combinations". $\endgroup$ Jun 7, 2015 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.