How to prove that $\text{argmin}_x f(x) \leq \text{argmin}_x (f(x) - mx)$ for any function $f(x)$ and $m\geq0$?
Asked
Active
Viewed 298 times
0
-
This might just be my lack of background in optimization, but what is the definition of $\operatorname{argmin}$? – Brett Frankel Oct 22 '13 at 18:50
-
Please see the Wikipedia article for argmax (argmin is defined analogously). – Uwe Oct 22 '13 at 18:53
1 Answers
1
Hint: Let $y = \mathrm{argmin}_x f(x)$ and $z = \mathrm{argmin}_x (f(x) - mx)$. Write inequalities for $f(y)$ and $f(z)$ and for $f(y)-my$ and $f(z)-mz$.
JiK
- 5,815
- 19
- 39
-
My solution:
Let $g(x) = f(x) - mx$ and $y = \text{argmin}_x f(x), z = \text{argmin}_x g(x)$. Then we have $f(z) \geq f(y)$ because $f(y) = \min_x f(x)$ and also $g(z) \leq g(y)$ because $g(z) = \min_x g(x)$ Putting it all together (assuming $m>0$, case $m=0$ trivial anyway): \begin{align} g(y) &\geq g(z) \ f(y)-my &\geq f(z)-mz \ f(y)-my &\geq f(y)-mz \ -my &\geq -mz \ y &\leq z \ \text{argmin}_x f(x) &\leq \text{argmin}_x (f(x) - mx) \ \end{align}
– Uwe Oct 22 '13 at 19:32