3
$\begingroup$

Suppose I have two convex functions $f$ and $g$ mapping $\mathbb{R}^{n}\to\mathbb{R}$ (so they are 'more' than proper). Suppose $\|f-g\|_{\infty}<\epsilon$, the sup-norm. In particular, the subdifferentials are bounded, non-empty sets (Theorem 23.4 in Rockafellar). For a given $x$, can we say anything about the Hausdorff distance between $\partial f(x)$ and $\partial g(x)$?

What I have found so far:

Attouch's Theorem proving the convergence of the subdifferentials given some convergence in the functions called epi-convergence.

On the convergence of subdifferentials of convex functions Hedy Attouch, Gerald Beer http://link.springer.com/article/10.1007%2FBF01207197?LI=true

On the convergence of subdifferentials of convex functions Jean-Paul Penot

http://www.sciencedirect.com/science/article/pii/0362546X9390040Y

There is a short section on primal estimates for the convergence of subdifferentials, and although I have a hunch that this can be reformulated to include the Hausdorff distance, I'm wondering if there are any newer results that might generalize this.

Improve this question
$\endgroup$
3
  • $\begingroup$ Other than the Jean Paul Penot paper, nothing else seems to come up with a quantitative estimate using the Hausdorff distance. $\endgroup$
    – Pallen
    Commented Oct 20, 2014 at 17:50
  • $\begingroup$ The evident estimates seem to be optimal, but why do you need it? $\endgroup$
    – Anton Petrunin
    Commented Oct 20, 2014 at 23:04
  • $\begingroup$ I was hoping Hausdorff distance would be easier to handle; and I wanted something where there wasn't a dependence on the $r$. I think in that paper if I choose $r$ to be large enough, since $\partial f(x)$ and $\partial g(x)$ are bounded, the metric $d_{r}$ becomes the Hausdorff distance, but this isn't uniform in $x$, which is something I need. $\endgroup$
    – Pallen
    Commented Oct 21, 2014 at 16:32

1 Answer 1

Reset to default
5
$\begingroup$

I doubt that there is a simple bound without some other restriction. Consider $f(x) = C|x|$, i.e. $\partial f(0) = [-C,C]$. Then there is a convex $g$ with $\|f-g\|_\infty\leq\epsilon$ but $g\equiv 0$ in a neighborhood of $0$, hence $\partial g(0) = \{0\}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Dirk. I tried looking, but would you know whether there has been some work in this area recently? I can't seem to get anything quantitative beyond the 1993 paper I linked above. $\endgroup$
    – Pallen
    Commented Oct 20, 2014 at 19:58
  • $\begingroup$ Don't know of anything, but have you checked Rockafellar and Wets' "Variational Analysis"? By the way, I suspect that the situation could be different for smooth $f$ and $g$… $\endgroup$
    – Dirk
    Commented Oct 20, 2014 at 20:01
  • 1
    $\begingroup$ You can easily modify this example to come up with smooth $f$ and $g$ with $\|f - g\|_\infty$ but $\delta f(0) = \{C\}$ and $\delta g(0) = \{-C\}$, $f$ and $g$ being translates of smoothed versions of $C |x|$. $\endgroup$
    – Robert Israel
    Commented Oct 20, 2014 at 20:25
  • $\begingroup$ @RobertIsrael Right, it's indeed simple. Well, this simply reflects that uniform convergence does not imply convergence of the derivative (although, in principle convexity could change things but apparently it doesn't). $\endgroup$
    – Dirk
    Commented Oct 21, 2014 at 6:49
  • $\begingroup$ @RobertIsrael @Dirk; Thanks for the answer and the comments. It was helpful. I think this shows that there isn't a nice Lipschitz-like bound for any two functions, but uniform convergence of convex functions does still imply convergence of the derivative -- isn't this what Theorem 25.7 in Rockafellar states? $\endgroup$
    – Pallen
    Commented Oct 21, 2014 at 16:35

You must log in to answer this question.

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