Monotonicity of Convex/Concave Function's Gradient Function in High Dimension

563 Views Asked by At

For a concave function $f(\mathbf{x}):[0,\infty)^n\rightarrow[0,\infty)$ in high dimension, e.g. $f(\mathbf{x}):[0,\infty)^2\rightarrow[0,\infty)$ when $f(\mathbf{x})=\sqrt{x_1x_2}$. Let $\mathbf{x}$ be element-wise less than or equal to $\mathbf{y}$, I am wondering the relationship between $\nabla f(\mathbf{x}) \cdot \mathbf{x}$ and $\nabla f(\mathbf{y}) \cdot \mathbf{x}$. I thought it would be $\nabla f(\mathbf{x}) \cdot \mathbf{x} \geq \nabla f(\mathbf{y}) \cdot \mathbf{x}$. Appraently, in one dimension we'll have $\nabla f(x) \cdot x\geq \nabla f(y)\cdot x$ when $x\leq y$ (because $\nabla f(x) \geq \nabla f(y)$ and $x\geq 0$). However, it turns out this is not true in high-dimension when $\mathbf{x}$ is element-wise less than or equal to $\mathbf{y}$.

Consider, for example when $\mathbf{x}=[4, 1]$ and $\mathbf{y}=[9,9]$ where $\mathbf{x}$ is element-wise less than or equal to $\mathbf{y}$. And we'll have $\nabla f(\mathbf{x}) =[\frac{1}{4},1]$ and $\nabla f(\mathbf{y}) =[\frac{1}{2},\frac{1}{2}]$, then we have $\nabla f(\mathbf{x}) \cdot \mathbf{x} = 2 < \nabla f(\mathbf{y}) \cdot \mathbf{x} = \frac{5}{2}$ which is very surprising to me.

So I'm wondering an even more specific case when $\mathbf{x}$ is not only element-wise less than or equal to $\mathbf{y}$ but also proportional, in other words, let $\mathbf{x} = \alpha \cdot \mathbf{y}$ where $\alpha \in [0,1]$. In this case, is it true that $\nabla f(\mathbf{x}) \cdot \mathbf{x} \geq \nabla f(\mathbf{y}) \cdot \mathbf{x}$? The previous counter-example doesn't work, but I can't prove this is true as well. I also tried several other examples, but none of them turned out to be a successful counter-example. In this case, my intuition is that $\mathbf{x}$ and $\mathbf{y}$ are in the same direction, any ideas on how to prove $\nabla f(\mathbf{x}) \cdot \mathbf{x} \geq \nabla f(\mathbf{y}) \cdot \mathbf{x}$ is true or a counter-example for this is not true will be super helpful.

1

There are 1 best solutions below

3
On BEST ANSWER

If $f$ is convex, then $\nabla f$ is monotone, in the sense that $$ (\nabla f(x) - \nabla f(y) ) ^T(x-y) \ge 0 $$ for all $x,y$. Maybe this can be useful for your computations.