If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then $$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$ is a convex piecewise linear function of $(x_1, \ldots, x_n) \in \mathbb{R}^n$. We can minimize it efficiently using linear programming.

I want to minimize an expression of the form $$\sum_h \max_i \sum_j (a_{hij} x_j + b_{hj}) \qquad (\dagger)$$ where $a_{hij}$ is an $\ell \times m \times n$ array of integers of bounded size and $b_{hj}$ is an an $\ell \times n$ array of integers of bounded size.

Is there a method to do this, polynomially in $(\ell, m, n)$?

Note that $(\dagger)$ is equivalent to an expression of the form $(\ast)$, so it is convex and piecewise linear, but writing it that way involves the $\max$ of $m^{\ell}$ terms.


1 Answer 1

  • Introduce variables $y_{hi}$ together with constraints $y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$.

  • Introduce variables $z_h$ together with constraints $z_h\ge y_{hi}$ for all $h$ and $i$.

  • Then minimize $\sum_h z_h$.

The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost coefficient.

(I am not sure whether you are asking for a strongly polynomial solution. This seems to be out of reach.)

  • $\begingroup$ Thanks! (If I am allowed to say that on this site.) $\endgroup$ May 17, 2019 at 14:45
  • $\begingroup$ @DavidESpeyer are there sites where you're not? Sounds sad to me that a site would enforce a certain level of incivility. $\endgroup$ Jun 14, 2019 at 12:48
  • $\begingroup$ When I click on the add comment box, it says "avoid comments like "+1" or "thanks"." I know that MO and math.SE don't take that seriously, but I think some cites do. See meta.stackoverflow.com/questions/258004/… $\endgroup$ Jun 15, 2019 at 3:42

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.