1

This question mainly deals with subdifferential of a convex function with respect to the cost function $c(x,y)=\frac{|x-y|^2}{2}$

I want to compute the cost-subdifferential $\partial^{c}\phi$ of the cost-convex function

$\phi(x)=\max\{-|x-y_0|^2,|x-y_1|^2\}$

For a cost function $c:X\times Y \longrightarrow R, \phi:X\longrightarrow R$ is called cost-convex, if there exists another function $\psi:Y\longrightarrow R$ such that $\phi(x)=\sup_{y\in Y} -c(x,y)- \psi(y)$.

Moreover, at point $x\in \mathbb{R}^n$ the subdifferential at $x$ is;

$ \partial^{c}\phi(x)=\{y\in Y |\phi(z)\geq \phi(x)-c(z,y)+c(x,y)\quad \forall z\in X\} $

Any help would be appreciated.

ali
  • 169

2 Answers2

1

Note that $-c(z,y) + c(x,y) = \frac{|x|^2}{2} - \frac{|z|^2}{2} - \langle y,x-z\rangle$ and hence, $y$ is in the $c$-subdifferential if for all $z$ it holds that $$ \phi(z) + \frac{|z|^2}{2} \geq \phi(x) + \frac{|x|^2}{2} + \langle y,z-x\rangle. $$ This says that some $y$ is in the $c$-subdifferential of $\phi$ at $x$ if and only if it is in the usual subdifferential of the function $f(x) = \phi(x) + |x|^2/2$ at $x$.

Using that your function is the pointwise maximum of two differentiable functions, that the subdifferential is just the usual derivative for differentiable functions and the rule that the subdifferential of the maximum of two functiona is the subdifferential of the function where the maximum is attained (at the points where there is only one such function) should get you the answer.

Dirk
  • 11,680
0

Thank you for your helpful comment Dirk. I also had a similar question.

By the way, for the cost $c(x,y)=|x-y|$, if we want to find the subdifferential of $\phi(x)=|x|$, it would be;

$$y\in \partial^c\phi\quad then\quad |z|\geq|x|+|x-y|-|z-y|$$

$$|z-x|\geq|z-y|-|x-y|\geq|x|-|z|$$

which is true for any $y\in R^n$

so is it true to conclude that $\partial \phi=R^n$?

Community
  • 1
shirin
  • 1