Consider the definition of convex functions: $$ f(tx+(1-t)y) \le t f(x)+(1-t)f(y) $$ It is easy to show the definition of the convexity on sets with respect to the above definition (Specifically for a convex hull of some points $x_1, ...., x_n$, it is the points $\sum_i \alpha_i x_i$ and $ \sum_i \alpha_i = 1 $). enter image description here enter image description here

Consider the definition of strong convex functions: $$ f(tx+(1-t)y) \le t f(x)+(1-t)f(y) - \frac{1}{2} m t(1-t) \|x-y\|_2^2 $$ for some $m > 0$. How can we reinterpret this definition for sets (or discrete points)?

  • $\begingroup$ I think @gerw's answer is interesting and I voted it up. But frankly I have to ask why you're asking. Oh, sure, as a mental exercise I get it. But what would the purpose of the definition be? What could we do with these strongly convex sets that we could not do with non-strongly convex sets? My guess is that if you have a specific purpose in mind, a definition is likely to follow readily. $\endgroup$ – Michael Grant Nov 2 '14 at 19:26
  • $\begingroup$ Thanks for asking. I am curious if we can model a family of submodular functions (en.wikipedia.org/wiki/Submodular_set_function) such that their continuous extension (e.g. something like Lovasz extension) is strongly convex. Any comments on than? $\endgroup$ – Daniel Nov 2 '14 at 20:04
  • $\begingroup$ I do not have an idea at the moment, no, but I will ruminate on it! $\endgroup$ – Michael Grant Nov 3 '14 at 4:05

I do not fully understand what you would like to ask. However, a possible answer could be the following.

A set $A$ is strongly convex, if there is some $m > 0$ with $$ x,y \in A \;\Rightarrow\; \lambda \, x + (1-\lambda) \, y + m \, \lambda \, (1-\lambda) \, \mathbb{B} \subset A, $$ where $\mathbb{B}$ is the unit ball. I must admit that I do not know if this definition is used anywhere.

  • $\begingroup$ Thank you for your comment! Any suggestion on how to generalize the definition of convex hull with this? $\endgroup$ – Daniel Nov 1 '14 at 18:33
  • 1
    $\begingroup$ I think that is not possible. You could, however, define a $m$-strongly-convex hull by intersecting all $m$-strongly-convex sets containing your initial set. $\endgroup$ – gerw Nov 2 '14 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.