# Absolute value optimization

If you have an LP

Maximize/Minimize:

$c_1|x_1| + c_2|x_2| ... c_n|x_n|$

Subject to:

$Ax = b$

Can this be solved in polynomial time with respect to the amount of data used to represent the problem?

• On average? Yes. In every case, I don't think so. See if this helps. Of course, simplex is not the only option, so ... – AnonSubmitter85 Jun 30 '13 at 3:57
• If Ax = b specifies a unit hypercube located in the all positive quadrant, with a corner at 0,0,0,0...0 and the absolute value was basically measuring the absolute value of $x_i - 1/2$ for all the $x_i$ in x – frogeyedpeas Jun 30 '13 at 6:08

minimize $\sum_i c_i y_i$ s.t. $Ax=b$, $y_i \ge x_i$, and $y_i \ge -x_i$. $y_i = |x_i|$ in any optimal solution. This is solvable in polynomial time, but not by the simplex method, although that is likely the fastest method.
For maximizing absolute value you have a NP hard problem. Consider the number partitioning problem. If the values to be partitioned are $w_i$. The optimization problem maximize $\sum_i |x_i|$ subject to $\sum_i w_i x_i = 0$, $x_i \le 1$, and $x_i \ge -1$ will have an optimal value of $|I|$ if and only there is a partitioning of the $w_i$ into two equal subsets.
• +1. I believe your answer is correct except that in the first part (minimize) the objective function should be $\min$ $\sum_i c_iy_i$ not $\sum_i c_i x_i$ – Inquest Jun 30 '13 at 22:26