This might be trivial but I am struggling to justify the following simplification. from: h

Question

This might be trivial but I am struggling to justify the following simplification.from:

h (x^{*} + d) - h (x^{*}) \geq \sum_{j ⧸ \in G} \nabla_{j} f (x^{*}) * d_{j} + γ \sum_{j ⧸ \in G} | d_{j} |

to:

h (x^{*} + d) - h (x^{*}) \geq - max_{j ⧸ \in G} | \nabla_{j} f (x^{*}) | \sum_{j ⧸ \in G} | d_{j} | + γ \sum_{j ⧸ \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 ⧸ \in G} \nabla_{j} f (x^{*}) * d_{j} \geq max_{j ⧸ \in G} | \nabla_{j} f (x^{*}) | \sum_{j ⧸ \in G} | d_{j} |

provided the jacobian is nonnegative element-wise. But then why add the negative sign?

Answer 1

\sum_{j \notin G} \nabla_{j} f (x^{*}) d_{j} \geq max_{j \notin G} | \nabla_{j} f (x^{*}) | \sum_{j \notin G} | d_{j} |

is not true. For example, let

G = \emptyset

,

f (x) = - x

, and

d_{1} = 1

. Then

\sum_{j \notin G} \nabla_{j} f (x^{*}) d_{j} = - 1 \cdot 1 = - 1

but

max_{j \notin G} | \nabla_{j} f (x^{*}) | \sum_{j \notin G} | d_{j} | = | - 1 | \cdot | 1 | = 1

Answer 2

Using

a \geq - | a |

for all real number

a

, we have

\sum_{j ⧸ \in G} \nabla_{j} f (x^{*}) d_{j} \geq - \sum_{j ⧸ \in G} | \nabla_{j} f (x^{*}) | | d_{j} |

\geq - \sum_{j ⧸ \in G} (max_{k ⧸ \in G} | \nabla_{k} f (x^{*}) |) | d_{j} | = - (max_{k ⧸ \in G} | \nabla_{k} f (x^{*}) |) (\sum_{j ⧸ \in G} | d_{j} |) .

Answers (2)