Assume that $x$ is a vector and we have a set of affine functions $f_i(x)$, $i=1,\ldots,N$, and $g_j(x)$, $j=1,\ldots,M$. We want to solve the following optimization problem:
\begin{align} \min_x &\Big(\max_{i=1,\ldots,N} f_i(x) + \max_{j=1,\ldots,M} g_j(x) \Big) \\ & Cx \leq d \end{align} where $C$ and $d$ are a matrix and a vector with appropriate dimensions. How can we solve this? Assume that we can evaluate the values of functions but it is not easy to compute the derivations of functions analytically. Any idea is appreciated.
What I know is that if $g_j(x)=0$, $j=1,\ldots,M$, then the above optimization is equivalent to the following LP:
\begin{align} \min_{x,z} \quad &z \\ & Cx \leq d \\ &z \geq f_i(x), \quad i=1,\ldots,N. \end{align}
What happens if you try: \begin{align} &\underset{x,z,v}{\text{minimize}}\quad z+v \\ &\text{subject to} \\ &Cx\leq d\\ &z\geq f_i(x),\quad i=1,\dots,N\\ &v\geq g_i(x), \quad j=1,\dots,M \end{align}