First of all I want to know if following inequality is correct? $ \min (f(x)+g(x)+k(x)) \geq \min f(x)+ \min g(x)+ \min k(x) $

$f,g$ and $k$ are non-linear functions.

If it is true, how can I mathematically prove it as a lemma?

If not, why?


For all $y$, you have by definition $\min_x f(x)\leq f(y)$, $\min_x g(x)\leq g(y)$ and $\min_x k(x)\leq k(y)$ (assuming all the minima exist); adding these $3$ inequalities gives you $$\min_x f(x) + \min_x g(x) + \min_x k(x)\leq f(y)+g(y)+k(y)$$ For all $y$. This is also true if $y$ is the minimum point of $f+g+k$ (assuming it exists), and thus $$\min_x f(x) + \min_x g(x) + \min_x k(x)\leq \min_x(f(x)+g(x)+k(x)).$$

  • $\begingroup$ I like it :). I was enlightened with that last sentence/line. $\endgroup$ – ReverseFlow Dec 3 '16 at 16:36

Suppose it were not true. Then there is a $y$ such that $f(y) + g(y) + k(y) < \min f(x_1) + \min g(x_2) + \min k(x_3)$. But of course this is false, as the right hand side is at most as large as when $x_1 = x_2 = x_3 = y$, which would lead to the inequality $f(y) + g(y) + k(y) < f(y) + g(y) + k(y)$.

So we conclude by contradiction.


Here is a slightly different, more 'calculational' perspective.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

In the tradition of EWD1300, I will write $\;\langle \min x :: f(x) \rangle\;$ (instead of your $\;\min f(x)\;$) to clearly mark the scope of the dummy variable $\;x\;$.

Also one of course needs to know the basic properties of $\;\min\;$, e.g., it is at most each of its arguments, it is monotonic, and $\;+\;$ distributes over it. More formally, \begin{align} & a \min b \;\leq\; a \\ & b \leq c \;\then\; a \min b \leq a \min c \\ & (a \min b) + c \;=\; (a+c) \min (b+c) \end{align} which directly generalize to \begin{align} \tag{0} & \langle \min x :: f(x) \rangle \;\leq\; f(z) \\ \tag{1} & \langle \forall x :: f(x) \leq g(x) \rangle \;\then\; \langle \min x :: f(x) \rangle \leq \langle \min x :: g(x) \rangle \\ \tag{2} & \langle \min x :: f(x) \rangle + c \;=\; \langle \min x :: f(x) + c \rangle \end{align}

First we note the original statement is just the simpler $$ \tag{3} \langle \min x :: f(x) + g(x) \rangle \;\geq\; \langle \min x :: f(x) \rangle + \langle \min x :: g(x) \rangle $$ applied twice, as witnessed by the following calculation: $$\calc \langle \min x :: f(x) + g(x) + k(x) \rangle \op\geq\hint{by $\Ref{3}$ and monotonicity of $\;+\;$} \langle \min x :: f(x) \rangle + \langle \min x :: g(x) + k(x) \rangle \op\geq\hint{by $\Ref{3}$ and monotonicity of $\;+\;$} \langle \min x :: f(x) \rangle + \langle \min x :: g(x) \rangle + \langle \min x :: k(x) \rangle \endcalc$$

Now to prove $\Ref{3}$, the simplest strategy is to start at the most complex side, the right hand side, and calculate our way to the other side: $$\calc \langle \min x :: f(x) \rangle + \langle \min x :: g(x) \rangle \op=\hints{$\;+\;$ distributes over $\;\min\;$ $\Ref{2}$, renaming second}\hints{dummy to prevent name conflict}\hint{-- to bring $\;f\;$ and $\;g\;$ closer together} \langle \min x :: f(x) + \langle \min y :: g(y) \rangle \rangle \op\leq\hints{choose $\;y := x\;$, so that by $\Ref{0}$ we have}\hints{$\;\langle \min y :: g(y) \rangle \leq g(x)\;$; monotonicity $\Ref{1}$}\hint{-- this seems the simplest way to introduce $\;g(x)\;$} \langle \min x :: f(x) + g(x) \rangle \endcalc$$ This proves $\Ref{3}$ and completes the proof.

The above proof gives a lot of detail, probably too much depending on the target audience. On the other extreme, an average math text might write the above with no explanations at all, saying just something like

Proof. Apply twice that $$\min_x f(x) + \min_x g(x) \;=\; \min_x (f(x) + \min_y g(y)) \;\leq\; \min_x (f(x) + g(x))$$

leaving the rest up to the reader...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.