<ul>
<li><p>Introduce variables <span class="math-container">$y_{hi}$</span> together with constraints 
<span class="math-container">$y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$</span> for all <span class="math-container">$h$</span> and <span class="math-container">$i$</span>.</p></li>
<li><p>Introduce variables <span class="math-container">$z_h$</span> together with constraints 
<span class="math-container">$z_h\ge y_{hi}$</span> for all <span class="math-container">$h$</span> and <span class="math-container">$i$</span>.</p></li>
<li><p>Then minimize <span class="math-container">$\sum_h z_h$</span>.</p></li>
</ul>

<p>The resulting linear program can be solved in time polynomially bounded in <span class="math-container">$\ell, m, n$</span> and the logarithm of the largest cost coefficient. </p>

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

CC BY-SA 4.0
2019-05-17T14:45:50.830Z
Thanks! (If I am allowed to say that on this site.)
David E Speyer
CC BY-SA 4.0
2019-06-14T12:48:06.380Z
@DavidESpeyer are there sites where you're not? Sounds sad to me that a site would enforce a certain level of incivility.
Joshua Grochow
CC BY-SA 4.0
2019-06-15T03:42:19.927Z
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 https://meta.stackoverflow.com/questions/258004/should-thank-you-comments-be-flagged
David E Speyer
CC BY-SA 4.0
2019-05-16T16:58:16.320Z
2019-05-16T16:58:16.320Z
Gamow
<p>If <span class="math-container">$a_{ij}$</span> is an <span class="math-container">$m \times n$</span> matrix of real numbers, and <span class="math-container">$b_j$</span> are <span class="math-container">$n$</span> more real numbers, then 
<span class="math-container">$$\max_i  \sum_j (a_{ij} x_j + b_j)  \qquad (\ast)$$</span>
is a convex piecewise linear function of <span class="math-container">$(x_1, \ldots, x_n) \in \mathbb{R}^n$</span>. We can minimize it efficiently using linear programming.</p>

<p>I want to minimize an expression of the form
<span class="math-container">$$\sum_h \max_i  \sum_j (a_{hij} x_j + b_{hj}) \qquad (\dagger)$$</span>
where <span class="math-container">$a_{hij}$</span> is an <span class="math-container">$\ell \times m \times n$</span> array of integers of bounded size and <span class="math-container">$b_{hj}$</span> is an an <span class="math-container">$\ell \times n$</span> array of integers of bounded size. </p>

<blockquote>
  <p>Is there a method to do this, polynomially in <span class="math-container">$(\ell, m, n)$</span>?</p>
</blockquote>

<p>Note that <span class="math-container">$(\dagger)$</span> is equivalent to an expression of the form <span class="math-container">$(\ast)$</span>, so it is convex and piecewise linear, but writing it that way involves the <span class="math-container">$\max$</span> of <span class="math-container">$m^{\ell}$</span> terms.</p>

<optimization><linear-programming><convex-optimization>
Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
David E Speyer
# Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

(Asked by: username_0 on 2019-05-16)

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.

**Tags:** optimization, linear-programming, convex-optimization

---

## 1 answers

### Answer by username_1 on 2019-05-16. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks! (If I am allowed to say that on this site.)  
> **username_2**: @DavidESpeyer are there sites where you're not? Sounds sad to me that a site would enforce a certain level of incivility.  
> **username_0**: 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 https://meta.stackoverflow.com/questions/258004/should-thank-you-comments-be-flagged  

---

