Consider $V:[0,1]^2 \rightarrow[0,1]$, satisfying the following properties:
- $V(x,y) = p(x,y)x+(1-p(x,y))y$, where $p(x,y) \in [0,1]$. In other words, every point in $[0,1]^2$ is mapped to a distribution of some binary random variable $X \in \{x,y\}$, $(p(x,y), 1- p(x,y))^T$, and $V$ is the expectation of $X$ with respect to that distribution.
- $V(x,x)=x\;\forall\;x \in[0,1]. $ (Naturally)
- It is also given that $(p(x,y), 1- p(x,y))^T$ is a subgradient of $V$ at all points, i.e. $V(u) \geq V(v)+p(v)^{T}(u-v)$ for all $u,v \in [0,1]^2$.
My questions are:
Can we find such a $V$ which is convex? If yes, what can we say about the family of functions $V$ satisfying the above conditions (e.g. are they equal to each other only along the line $x=y$ or they can "cut" each other elsewhere also)?
My attempt: I impose $(\nabla V(x,y)-\nabla V(x',y'))^{T}((x,y)^T-(x',y')^T) \geq 0$ for all $(x,y),(x',y') \in [0,1]^2$ in order to get convexity. It is easy to show that this is equivalent to $(p(x,y)-p(x',y'))((x-x')-(y-y')) \geq 0$ for all $(x,y),(x',y') \in [0,1]^2$ that is sufficient for that.
But my worry is I'm not able to visualize how that is possible with $V(x,x)=x\;\forall\;x \in[0,1].$ Isn't a "wedge" getting created along the line $\{(x,x,x): x\in [0,1]\}$ in the 3 dimensions? For example, suppose you start from $x=0$ along the line $x+y=1$ and keep increasing $x$. When I'm trying to visualize this, it seems as if you have to either go down then up (not possible because the gradient vector is a Bernoulli distribution, in case of a differentiable $V$, for example) or up then down (not possible because $V$ is convex), if you have to satisfy the form of $V$. I'm neither able to construct examples. Thank you in advance for any help.
Let $$ V(x) = p(x)\cdot x $$ on some convex $X \subseteq \mathbb{R}^N$. $V(x)$ is closed, proper, and convex iff $p(x)$ is cyclically monotone: for any $m$-length sequence $\{x_0, ..., x_m\} \in X$, $$ (x_1-x_0)\cdot p(x_0) + (x_2-x_1)\cdot p(x_1) + ... + (x_0-x_m)\cdot p(x_m) \le 0. $$
If $V$ is convex, then $V(x_k) - V(x_{k-1}) \ge p(x_{k-1})\cdot (x_k-x_{k-1})$, and adding up over the chain from $0$ to $m$ gives the cyclical monotonicity inequality. In particular, $V(x_1)-V(x_0) \ge p(x_0)\cdot (x_1-x_0)$, $V(x_2)-V(x_1) \ge p(x_1)\cdot (x_2-x_1)$, and so forth, so that then added, $$ V(x_m)-V(x_0) \ge p(x_0)\cdot (x_1-x_0) + p(x_1)\cdot (x_2-x_1) + ... + p(x_{m-1})\cdot (x_m-x_{m-1}) $$ but also $V(x_0) - V(x_m) \ge (x_0-x_m)\cdot p(x_m)$, so "closing the loop" gives $$ 0 \ge (x_0 - x_m)\cdot p(x_m) + p(x_0)\cdot (x_1-x_0) + p(x_1)\cdot (x_2-x_1) + ... + p(x_{m-1})\cdot (x_m-x_{m-1}), $$ and convexity implies cyclical monotonicity.
If the cyclical monotonicity condition holds for $p$, fix some $x_0 \in X$ and define $$ V(x) = \sup_{m \text{ finite}} \left\lbrace (x-x_m)\cdot p(x_m) + ... + (x_1-x_0)\cdot p(x_0)\right\rbrace. $$ Since $f$ is a supremum of affine functions, $f$ is convex. Furthermore, $p(x)$ is the gradient of $V$. Take any $\alpha < f(x)$, and by definition of $f(x)$ as a $\sup$, there's a sequence of $x_i$'s such that $$ \alpha < (x-x_m)\cdot p(x_m) + ... + (x_1 - x_0)\cdot p(x_0) \le f(x) $$ Set $x_{m+1} = x$, and then $$ f(y) \ge (y-x_{m+1}) \cdot p(x_{m+1}) + (x_{m+1}-x_m)\cdot p(x_m) + ... + (x_1-x_0)\cdot p(x_0) > (y-x) \cdot p(x)+ \alpha. $$ Since $\alpha<f(x)$ was arbitrary, this implies $p(x)$ is the subgradient of $f$.
So monotonicity isn't enough, you need cyclical monotonicity. See Rockafellar 1970 for all this stuff.