1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ FWIW, I'm a physicist/mathematician, and not a CS expert. Any literature on this would be most appreciated. $\endgroup$
    – Yly
    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$
    – Martin Berger
    Oct 10, 2022 at 15:17
  • $\begingroup$ what do you want to do to $f(x)=-x^2$? $\endgroup$
    – mathworker21
    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
    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$
    – Chandra Chekuri
    Oct 11, 2022 at 13:07

0

Reset to default

Your Answer

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