The definition of monotonically non-decreasing is:

Suppose h: R^n -> R^n, and if

enter image description here

then h is said to be monotonically non-decreasing.

I know that if a function is convex and continuously differentiable then we have:

enter image description here enter image description here

Then can I add these two inequality together to prove the assumption?

  • 1
    $\begingroup$ h is R^n -> R^n because f is R^n -> R and the gradient of f is thus R^n -> R^n. So that the gradient of f can be inner product with n-dimension vector. $\endgroup$ – Parting Dec 8 '16 at 22:17

Yes, by adding your two inequalities, we discover that \begin{align} &\quad f(x) + f(y) \geq f(x) + f(y) + \langle \nabla f(y) - \nabla f(x),x - y \rangle\\ \iff & \quad \langle \nabla f(x) - \nabla f(y), x - y \rangle \geq 0. \end{align}

Edit: Here are a few intermediate steps shown in more detail. \begin{align} \langle \nabla f(y),x - y \rangle + \langle \nabla f(x), y - x) \rangle &= \langle \nabla f(y),x - y \rangle + \langle -\nabla f(x), x - y) \rangle \\ &= \langle \nabla f(y) - \nabla f(x), x - y \rangle. \end{align}

Also, \begin{align} & 0 \geq \langle \nabla f(y) - \nabla f(x), x - y \rangle \\ \implies & 0 \leq - \langle \nabla f(y) - \nabla f(x), x - y \rangle \\ \implies & 0 \leq \langle \nabla f(x) - \nabla f(y), x - y \rangle. \end{align}

  • $\begingroup$ Thank you! But why ⟨ ∇f(y), x−y⟩+⟨∇f(x), y-x⟩ = ⟨∇f(y)−∇f(x),x−y⟩? And why 0 ≥ ⟨∇f(y)−∇f(x),x−y⟩ ⟺ ⟨∇f(x)−∇f(y),x−y⟩≥0? Is there any rule behind this? $\endgroup$ – Parting Dec 8 '16 at 21:56
  • $\begingroup$ Yes, in those steps I'm just using some basic properties of inner products, such as $\langle u, -v \rangle = \langle -u, v \rangle$ and $\langle u, v \rangle + \langle w, v \rangle = \langle u + w, v \rangle$. $\endgroup$ – littleO Dec 8 '16 at 22:09

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.