# How do I evaluate the summation of a maximum function?

Question:

$f(x)=max_{a∈[1,−1]} \sum^d_{j=1}ax_j$ and $g(x)=\sum^d_{j=1}max_{a∈[1,−1]}ax_j$. and where $x=(x_1,…,x_d)∈\Bbb R ^d$ is a real vector.

What is the relationship between $f(x)$ and $g(x)$?

--

I know that the relationship should be $f(x) \leq g(x)$, but I can't prove it mathematically. (Please do correct me if I'm wrong).

My high level thinking is that you evaluate the maximum a for each list element $x_i$ in $g(x)$, while you evaluate the maximum of a summation in $f(x)$, so $g(x)$ is in a sense more optimized than $f(x)$. You take the summation of always a positive elements for $g(x)$, while in $f(x)$, the summation may include both positive and negative elements in $f(x)$. Therefore, $f(x) \leq g(x)$.

How can I prove this in a rigorous way? I'm looking for a proof with explanation.

PS. What is the difference between $\Bbb R ^d$ and $\Bbb R$?

All we know about $x_1,x_2,\dots,x_d$ is that they are real numbers which may be positive or negative. So $\sum_{j=1}^dx_j$ is a real number which may be positive or negative. Suppose it is $k$. Then $\max_{a\in[-1,1]}ak=|k|=|\sum x_j|$. Similarly, $\max_{a\in[-1,1]}ax_j=|x_j|$, so $\sum\max ax_j=\sum|x_j|$.
We have $|\sum x_j|\le\sum|x_j|$, so $f(x)\le g(x)$.
On your postscript, an element of $\mathbb{R}$ is just a real number, an element of $\mathbb{R}^d$ is a $d$-tuple, such as $(x_1,x_2,\dots,x_d)$.