Relationship between $\langle \nabla f(\overline{x}), x - \overline{x}\rangle > 0$ and the the minimality of $\overline{x}$.

Question

Say $f$ is a differentiable function over a convex set $X$ with $\langle \nabla f(\overline{x}), x - \overline{x}\rangle > 0$ for all $x, \overline{x} \in X$ such that $x \neq \overline{x}$. Can we conclude from this alone that $\overline{x}$ is a local minimum? Certainly, if $f$ were pseudoconvex, this would hold trivially. However, I suspect that the strict inequality here may imply that $\overline{x}$ is indeed a local minimum

Answer 1

Assuming you meant that $\langle \nabla f(\bar{x}), x - \bar{x}\rangle > 0, \forall x \neq \bar{x}$, this should imply a local minimum. From the differentiability of $f$, you know that near $\bar{x}$:

$$ f(x) = f(\bar{x}) + \langle \nabla f(\bar{x}), x - \bar{x} \rangle + o(\| x - \bar{x}\|), $$

where $o(\| x - \bar{x} \|)$ is a term that satisfies $ \lim_{x \to \bar{x}} \frac{o(\| x-\bar{x}\|)}{\| x - \bar{x}\|} = 0. $ Then, assuming that $\forall \epsilon > 0$, there is a $x$ with $f(x) < f(\bar{x})$ and $\| x - \bar{x} \| < \epsilon$ (i.e. $\bar{x}$ is not a local minimum), you should be able to derive a contradiction for a sufficiently small $\epsilon$.

Answer 2

Your question is closely related to the Frank-Wolfe algorithm to find an optimal solution of a convex program or a "stationary" point in nonconvex problems. The quantity that you defined is known as (negative) surrogate duality gap or in short gap function. A stationary point can be a local minimum, local maximum, or a point in the boundary of the feasible set. You can find a solid discussion on the gap function in [1] and the application of the FW algorithm for nonconvex problems in [2].

[1] Bertsekas, D. P. (1999). Nonlinear programming. Athena Scientific

[2] Lacoste-Julien, S. (2016). Convergence rate of Frank Wolfe for non-convex objectives. arXiv:1607.00345