# 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.)

• Thanks! (If I am allowed to say that on this site.) – David E Speyer May 17 at 14:45
• @DavidESpeyer are there sites where you're not? Sounds sad to me that a site would enforce a certain level of incivility. – Joshua Grochow Jun 14 at 12:48
• 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/… – David E Speyer Jun 15 at 3:42