# How to enforce convexity?

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 and $$c). 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.

• FWIW, I'm a physicist/mathematician, and not a CS expert. Any literature on this would be most appreciated.
– Yly
Commented Oct 10, 2022 at 5:49
• 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 Commented Oct 10, 2022 at 15:17
• what do you want to do to $f(x)=-x^2$? Commented Oct 10, 2022 at 16:06
• @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.
– Yly
Commented Oct 10, 2022 at 16:40
• 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 Commented Oct 11, 2022 at 13:07