Upper (or lower) envelope of some linear functions
Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints, in linear time, given the breakpoints for the linear functions $(m_i + M)x + b_i$.

Now let $M = \max (-m_i)$, which can be found in linear time. The functions $(m_i + M)x + b_i$ all satisfy your condition. Hence if you could solve your problem in $f(n)$, then you could solve the original problem in $f(n) + O(n)$. Therefore you need not expect a more efficient solution for your special case.