6
$\begingroup$

Cyclic monotonicity says that if we have a correspondence, $x(w)$, the $x$ is cyclically monotone in $w$ if for a finite sequence $w_1,\cdots w_k$ and $x^*(w_i)\in x(w_i)$, we have $\sum_{i=1}^k (w_i-w_{i+1})\cdot x^*(w_i) \leq 0$ (I guess this is technically the definition for cyclically monotone increasing).

I am wondering if there is some intuition (or clear) explanation of what this says.

To me, it seems to say that when $w_{i+1} >w_i$ then $x_i > x_{i+1}$, in some sort of "general" sense.

$\endgroup$

2 Answers 2

5
$\begingroup$

R.T. Rockefellar was the convex analyst who showed that a (multivalued) linear operator is the subdifferential of a convex function iff the operator is cyclically monotone. To quote one of his papers on that topic:

The cyclic monotonicity condition can be viewed heuristically as a discrete substitute for two classical conditions: that a smooth convex function has a positive semi-definite second differential, and that all circuit integrals of an integrable vector field must vanish.

$\endgroup$
1
  • $\begingroup$ Can you give some intuition about this property vs the general statement of maximal monotonicity? It's clear that maximal monotone implies maximal cyclically monotone. However, when I read papers, they almost always consdier maximal monotone operators and not non maximal cyclically monotone operators - why? $\endgroup$ Feb 21, 2023 at 15:10
1
$\begingroup$

Here's my very intuitive, hand-wavey approach - apologies for using the opposite sign convention, following Wikipedia, which makes more sense to me.

It helps to start thinking about this in the $k=2$ case in $\mathbb R$ first. There, you have that $x$ is cyclically monotone iff $$w_1 x^*(w_1)+w_2 x^*(w_2)\ge w_1 x^*(w_2)+w_2 x^*(w_1).$$ If $x$ is actually monotone increasing, then the LHS is where we "multiply the bigger $w_i$ by the bigger $x^*(w_i)$." The same holds for larger $k$, e.g. if $k=3$ then $$w_1 x^*(w_1)+w_2x^*(w_2)+w_3x^*(w_3)\ge w_1x^*(w_2)+w_2x^*(w_3)+w_3x^*(w_1)$$ whenever $x$ is monotone increasing, because we "multiply the biggest $w_i$ by the biggest $x^*(w_i)$, the second-biggest $w_i$ by the second-biggest $x^*(w_i)$, and so on."

In the $\mathbb{R}^n$ case, we compare in multiple directions. Here I find starting with $k=3$ to be more helpful intuitively. Now, cyclic monotonicity requires $$w_1x^*(w_1)+w_2x^*(w_2)+w_3x^*(w_3)\ge w_1x^*(w_2)+w_2x^*(w_3)+w_3x^*(w_1).$$ I think of this as being "$x^*(w_1)$ is the vector which points the most in the $w_1$ direction, as opposed to the $w_2$ and $w_3$ directions". That is:

  • If all the vectors are off in the same direction from $0$, then the largest $w_i$ is multiplied by the largest $x^*(w_i)$.
  • If the vectors all point in different directions, then the $x^*(w_i)$ vector points the most in the actual $w_i$ direction. In theory, I think this wouldn't need to be strict, i.e. a priori there's nothing which says $x^*(w_2)$ couldn't point slightly more in the $w_1$ direction than $x^*(w_1)$ does, as long as (say) $w_3x^*(w_3)$ was large enough. In fact, I suspect that the subdifferential-of-convex-function result above may mean this doesnt.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .