I have a problem for which the solution is known to be a convex $f:[a,b]\times[c,d] \rightarrow \mathbb{R}$ over some rectangular domain ($a<b$ and $c<d$). There are many situations (e.g. finding solutions numerically, or generating data for machine learning applications) where one would like to perform some operation on such a function while maintaining convexity.

Question: What techniques exist for "minimally modifying a function to make it convex"?

For instance, suppose I numerically approximate the solution $f$ and the approximation turns out to not be convex. How can I find a "closest" convex function?

The most obvious thing I can think of is to take a convex hull of the graph of $f$, but this itself seems like a non-trivial problem. Any references are appreciated.

  • $\begingroup$ FWIW, I'm a physicist/mathematician, and not a CS expert. Any literature on this would be most appreciated. $\endgroup$
    – Yly
    Commented Oct 10, 2022 at 5:49
  • $\begingroup$ I don't know if this is of relevance, but computing convex hulls, is one of the most well-studied algorithmic problems, we can even do it fast for low dimensions, and it is often taught in undergraduate algorithms courses, cf en.wikipedia.org/wiki/Convex_hull_algorithms $\endgroup$ Commented Oct 10, 2022 at 15:17
  • $\begingroup$ what do you want to do to $f(x)=-x^2$? $\endgroup$ Commented Oct 10, 2022 at 16:06
  • $\begingroup$ @mathworker21 My hope was that this would be a studied problem, and there would be a natural answer to such situations. If I had to guess, I'd say the case $f(x)=-x^2$ should correspond to the convex function with minimum $L^2$ distance to $f$, which in this case I think is an affine linear function. $\endgroup$
    – Yly
    Commented Oct 10, 2022 at 16:40
  • 1
    $\begingroup$ Suppose you have a discrete set function $f: 2^{0,1} \rightarrow \mathbb{R}$ over $n$ elements. One can ask how to extend this discrete set function to obtain a continuous function $g: [0,1]^n \rightarrow \mathbb{R}$ such that $g$ is convex and agrees with $f$ at the corners of the hypercube. There is a canonical way to do this and the resulting function $f^-$ is called the convex closure. However, in general, this function $f^-$ would be hard to evaluate. If it was always easy then one can minimize an arbitrary set function efficiently. See arxiv.org/abs/0912.0322 $\endgroup$ Commented Oct 11, 2022 at 13:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.