Pattab

2022-07-02

This might be trivial but I am struggling to justify the following simplification.from:
$h\left({x}^{\ast }+d\right)-h\left({x}^{\ast }\right)\ge \sum _{j\text{⧸}\in G}{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)\ast {d}_{j}+\gamma \sum _{j\text{⧸}\in G}|{d}_{j}|$
to:
$h\left({x}^{\ast }+d\right)-h\left({x}^{\ast }\right)\ge -\underset{j\text{⧸}\in G}{max}|{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)|\sum _{j\text{⧸}\in G}|{d}_{j}|+\gamma \sum _{j\text{⧸}\in G}|{d}_{j}|$

Specifically, why is there a negative in front of the maximization?

Note:
I can get behind the fact that
$\sum _{j\text{⧸}\in G}{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)\ast {d}_{j}\ge \underset{j\text{⧸}\in G}{max}|{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)|\sum _{j\text{⧸}\in G}|{d}_{j}|$
provided the jacobian is nonnegative element-wise. But then why add the negative sign?

$\sum _{j\notin G}{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right){d}_{j}\ge \underset{j\notin G}{max}|{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)|\sum _{j\notin G}|{d}_{j}|$
is not true. For example, let $G=\mathrm{\varnothing }$, $f\left(x\right)=-x$, and ${d}_{1}=1$. Then
$\sum _{j\notin G}{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right){d}_{j}=-1\cdot 1=-1$
but
$\underset{j\notin G}{max}|{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)|\sum _{j\notin G}|{d}_{j}|=|-1|\cdot |1|=1$

Jonathan Miles

Using $a\ge -|a|$ for all real number $a$, we have
$\sum _{j\text{⧸}\in G}{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right){d}_{j}\ge -\sum _{j\text{⧸}\in G}|{\mathrm{\nabla }}_{j}f\left({x}^{\ast }\right)|\phantom{\rule{thinmathspace}{0ex}}|{d}_{j}|$
$\ge -\sum _{j\text{⧸}\in G}\left(\underset{k\text{⧸}\in G}{max}|{\mathrm{\nabla }}_{k}f\left({x}^{\ast }\right)|\right)\phantom{\rule{thinmathspace}{0ex}}|{d}_{j}|=-\left(\underset{k\text{⧸}\in G}{max}|{\mathrm{\nabla }}_{k}f\left({x}^{\ast }\right)|\right)\left(\sum _{j\text{⧸}\in G}|{d}_{j}|\right).$

Do you have a similar question?