(This is adapted from the paper Scenarios and Policy Aggregation in Optimization Under Uncertainty by Rockafellar and Wets)
Let $F:\mathbb{R}^n\to\mathbb{R}$ be a convex function, and let $\mathcal{C}\subseteq\mathbb{R}^n$ be closed and convex. Define the function $\varphi:\mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$ by
$$\varphi(U,V)=F(U+V)+\delta_\mathcal{C}(U+V),$$
where $\delta_\mathcal{C}$ is the indicator function on $\mathcal{C}$ (i.e. $\delta_\mathcal{C}(X)=+\infty$ if $X\not\in\mathcal{C}$ and $0$ otherwise).
Equation (5.15) in the linked paper asserts that
$$ (Y,-\bar{W})\in\partial\varphi(V,U)\Leftrightarrow Y-\bar{W}\in\partial(F+\delta_\mathcal{C})(X)\text{ where }X=U+V. $$
Why is this true? I know that the subdifferential is a closed convex set, so I would expect that, say the midpoint $\tfrac{1}{2}(Y-\bar{W})$ would lie in the subdifferential, but not the sum…
Am I missing something? I suspect this may be connected to Minty's theorem but I can't quite see it.
Best Answer
Per definition in that paper $\phi : N \times N^\perp\to \mathbb R$, $f:X\to \mathbb R$, $X=N \oplus N^T$. Assume $\phi(u,v) = f(u+v)$, and $f(x) = \phi(Kx,Jx)$, where $J,K$ are orthogonal projectors onto a subspace $N$ and its complement $N^\perp$.
Note that the subdifferentials $\partial \phi$ and $\partial f$ are subsets of two different vector spaces. The first is a subset of $N\times N^\perp \subset X\times X$, while the latter is a subset of $X$.
Let $(y,-w) \in \partial \phi(u,v)\subset N\times N^\perp$. Then $$ \langle y, a \rangle - \langle w,b\rangle \le \phi(u+a,v+b)-\phi(u,v) = f( u+v +a+b) - f(u+v) \quad \forall a\in N,b\in N^\perp. $$ Due to the orthogonality relations, we get $$ \langle y-w, a+b\rangle \le f( u+v +a+b) - f(u+v) \quad \forall a\in N,b\in N^\perp. $$ Clearly $y-w\in \partial f(u+v)$.
Now let $y\in N$, $w\in N^\perp$ be given such that $y-w\in \partial f(x)$. Define $u:=Kx$, $v:=Jx$. Now we can reverse the above reasoning to obtain $(y,-w) \in \partial \phi(u,v)\subset N\times N^\perp$.