Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length 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.
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.)