Here excerpt from a book:

Аssume that $f$ satisfies $\nabla f(x) \ge 0$ for all $x$, but is not nondecreasing, i.e., there exist $x,y$ with $x < y$ and $f(y) < f(x)$. By differentiability of $f$ there exists at $t\in[0,1]$ with

$$\frac{d}{dt}f\left(x+t(y−x)\right) =\nabla f\left(x+t\left(y−x\right)\right)^T(y−x)<0.$$

I don't understand why the derivative is less than zero? The function could look like on the image. enter image description here

The book is Convex Optimization by Stephen Boyd and Lieven Vandenberghe, page 109.

  • $\begingroup$ It's not that it's always negative, it's that its negative somewhere. $\endgroup$ – πr8 Jun 30 '16 at 15:41
  • $\begingroup$ It isn't saying for all but rather for some. $\endgroup$ – Cameron Williams Jun 30 '16 at 15:41
  • $\begingroup$ Suppose otherwise that $\frac{d}{dt}f(x+t(y-x))\geq 0$ for all $t\in[0,1]$. Can you find a contradiction? $\endgroup$ – yurnero Jun 30 '16 at 16:48

Let $g(t)\equiv f(x+t(y-x))$ be defined on $[0,1]$. Then, $g$ is continuous on $[0,1]$ and differentiable on $(0,1)$. So by the Mean Value Theorem, there is some $t^*\in(0,1)$ such that $$ g'(t^*)=\frac{g(1)-g(0)}{1-0}=f(y)-f(x)<0. $$ It remains to expand the leftmost expression above.

| cite | improve this answer | |

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.