24
$\begingroup$

Recently in a seminar someone mentioned that monotone maps are equivalent to gradients of scalar convex functions, but it's not clear to me why this is true. One direction of the equivalence is straightforward but the other is not (as far as I can tell).

Definition. A map $F:\mathbb{R}^n \rightarrow \mathbb{R}^n$ is monotone on a convex set $C$ if $$(y-x)^T(F(y)-F(x))\ge0$$ for all $x,y \in C$.

One direction of the equivalence:

Prop. Let $f:\mathbb{R}^n \rightarrow \mathbb{R}$ be convex and sufficiently differentiable. Then $\nabla f$ is monotone.

Pf. Convex differentiable functions satisfy $$f(y) \ge f(x) + \nabla f(x)(y-x).$$

By choosing the points in reverse, we also have, $$f(x) \ge f(y) + \nabla f(y)(x-y).$$ Add these inequalities and rearrange to get $(\nabla f(y)-\nabla f(x))(y-x) \ge 0$.∎

Now the other direction:

Prop. Let $F:\mathbb{R}^n \rightarrow \mathbb{R}^n$ be monotone and sufficiently differentiable. Then there exists a convex function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ such that $F=\nabla f$.

Pf. ???

It seems like this should be easy, but I'm stuck and google/wikipedia have been of little help. I'm actually starting to doubt whether it is true.

$\endgroup$
6
  • $\begingroup$ By "sufficiently differentiable", I believe you mean that the gradient exists? You assume nothing else... I think you really need more precise conditions to know what happens next, but I'm not confident about the truth behind this result. $\endgroup$ Feb 21 '12 at 19:26
  • $\begingroup$ The obvious thing to try would be $f(x) = \int_0^1 F(xt) \, dt$. A simple computation shows that $\nabla f = F$. Then maybe the monotonicity of $F$ can be used to show that $f$ is convex? $\endgroup$
    – Jeff
    Feb 21 '12 at 20:06
  • $\begingroup$ @PatrickDaSilva The point was to allow anyone answering to use as many derivatives as needed. I don't think it even needs a single derivative though so long as the gradient is generalized to an element of the subderivative, but this is not really important to me so feel free to assume it is smooth. $\endgroup$
    – Nick Alger
    Feb 21 '12 at 20:28
  • $\begingroup$ @Jeff Yeah, so for 1D that's totally right. But does it also hold for higher dimensions? This line of thought makes me think the result may be related to the subject of integrable systems. $\endgroup$
    – Nick Alger
    Feb 21 '12 at 20:30
  • $\begingroup$ Not all fields $F$ are gradients. If $F=(F_1,\dots,F_n)$ is $C^1$, a necessary condition for $F$ to be a gradient is that $\partial F_i/\partial x_j=\partial F_j/\partial x_i$for $1\le i<j\le n$. $\endgroup$ Feb 21 '12 at 23:14
9
$\begingroup$

Not all fields $F$ are gradients. If $F=(F_1,\dots,F_n)$ is $C^1$, a necessary condition for $F$ to be a gradient is that $$ \frac{\partial F_i}{\partial x_j}=\frac{\partial F_j}{\partial x_i},\quad 1\le i<j\le n. $$

$\endgroup$
4
  • 1
    $\begingroup$ A counterexample being, for example F(x,y)=(x+y,y), which is monotone but fails this criterion so is not a gradient field. $\endgroup$
    – Nick Alger
    Feb 22 '12 at 17:56
  • $\begingroup$ Additional note: if one tries to compute something like an antiderivative of a function (like $\int_C \langle F(x), \mathbf{dx} \rangle$) that does not have a property listed above then it will depend on path, not on end values. $\endgroup$
    – Ben Usman
    Aug 6 '18 at 19:00
  • $\begingroup$ I can not edit my older comments, here are two more links: [2] [3] $\endgroup$
    – Ben Usman
    Aug 6 '18 at 19:10
  • $\begingroup$ One more intuition on why this is required: if there was a continuous function $f$ that had a gradient field $F$ that did not satisfy property above (i.e. not conservative), function $f$ would have had an asymmetric hessian, which is weird for a continuous functions. $\endgroup$
    – Ben Usman
    Aug 6 '18 at 19:22
18
$\begingroup$

There's still a bit missing from this. First, the concepts of convex functions and monotone operators are unrelated to Euclidean space, so giving the answers in terms of a coordinate choice $F = (F_1,F_2,...,F_n)$ is not ideal. Secondly, convex functions are not necessarily differentiable; instead, they have a subdifferential, and the subdifferential map is monotone.

So the broader question: when is a monotone map the subdifferential of a convex function?

That's a good question and it was answered by the pioneer of convex analysis, Rockafellar. In his 1970 book he has Thm 24.8 which covers the Euclidean space case, and he has papers (1966 and this 1970 correction https://sites.math.washington.edu/~rtr/papers/rtr031-MaxMonoSubdiff.pdf ) which cover the general Banach space case.

The result is: let $F$ be a mapping, then it is the subdifferential of a closed (lower semi-continuous) proper convex function $f$ if and only if $F$ is maximally cyclically monotone.

The definition of maximally cyclically monotone can be found on the first page of the 1970 paper above (in the definition, there are $n$ points, and this $n$ is arbitrary, not linked to the dimension).

$\endgroup$
7
$\begingroup$

Lion's answer has a correct statement about convexity, but without proof. I think a proof should be given in this thread, for future references.

Proposition. Suppose $f:U\to \mathbb R$ is a $C^1$ function, where $U$ is a convex domain. Then the following are equivalent:

  1. $f$ is convex.
  2. The restriction of $f$ to every line segment contained in $U$ is convex.
  3. $\nabla f$ is monotone.

Proof. The equivalence of 1 and 2 is immediate from the definition of convexity. Since the derivative of $f(x+tv)$ is $\langle\nabla f(x+tv), v\rangle$, the equivalence of 2 and 3 amounts to the fact that a one-variable function is convex if and only if its derivative is nondecreasing. $\Box$

$\endgroup$
5
$\begingroup$

Consider a $C^1$ monotone vector field $f=(f_1,\ldots,f_n)$ on $\mathbb R^n$. If there exists a function $G$ on $\mathbb R^n$ such that $G'=f$ than $G$ is automatically convex. So the existance of $G$ is the only thing one should verify.

Prop. The function $G$ exists if and only if $\frac{\partial f_i}{\partial x_j} = \frac{\partial f_j}{\partial x_i}$ for all $i$ and $j$.

The space $\mathbb R^n$ in contraclible. So $H^1(\mathbb R^n)=0$. Consequently $f=dG$ when $df=0$. It is equivalent to condition $\frac{\partial f_i}{\partial x_j} = \frac{\partial f_j}{\partial x_i}$.

$\endgroup$
3
  • $\begingroup$ The word you want is "then", not "than". $\endgroup$
    – Pedro Tamaroff
    Jun 2 '13 at 23:55
  • $\begingroup$ @PeterTamaroff It's also "existEnce". Maybe you can spare five seconds to edit the post... Lion isn't here often. $\endgroup$ Jun 3 '13 at 0:12
  • $\begingroup$ @user79365 But otherwise he won't learn! $\endgroup$
    – Pedro Tamaroff
    Jun 3 '13 at 0:30
4
$\begingroup$

I would like to give a counterexample

Let $F(x_1,x_2)=(-x_2, x_1)$. Then $F$ is differentiable and monotone. Indeed, for all $(x_1, x_2), (y_1, y_2)\in\mathbb{R}^2$ we have \begin{eqnarray*} \langle F(x_1, x_2)-F(y_1, y_2), (x_1, x_2)-(y_1, y_2)\rangle&=&\langle(-x_2+y_2, x_1-y_1), (x_1-y_1, x_2-y_2)\rangle\\ & =& -(x_2-y_2)(x_1-y_1)+(x_1-y_1)(x_2-y_2)\\ &=&0. \end{eqnarray*} Suppose that there exists a differentiable function $f(x_1, x_2)$ such that $F(x_1, x_2)=\nabla f(x_1, x_2)$. Then $$ \frac{\partial f}{\partial x_1}=-x_2, \quad \frac{\partial f}{\partial x_2}=x_1. $$ By the Schwarz's theorem we have $$ -1=\frac{\partial^2f}{\partial x_1\partial x_2}=\frac{\partial^2f}{\partial x_2\partial x_1}=1, $$ which is a contradiction.

$\endgroup$
4
$\begingroup$

So the answer is in short: "Yes if the map is the gradient of a function."

Let $f$ be Gateaux differentiable (same this as differentiable in finite dimensions), and proper, with an open and convex domain. Then $f$ is convex if and only if $f$'s derivative is monotone.

See Convex Analysis and Monotone Operator Theory in Hilbert Spaces by Bauschke and Combettes, proposition 17.10.

$\endgroup$
1
$\begingroup$

If $A $ is a real $n \times n $ skew-symmetric matrix, then the operator $T (x) = Ax $ is monotone, but it is not the gradient of a convex function.

(The Hessian of a smooth convex function must be symmetric positive semidefinite. )

$\endgroup$
2

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.