<p>I have a problem for which the solution is known to be a <em>convex</em> <span class="math-container">$f:[a,b]\times[c,d] \rightarrow \mathbb{R}$</span> over some rectangular domain (<span class="math-container">$a&lt;b$</span> and <span class="math-container">$c&lt;d$</span>).  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 <em>while maintaining convexity</em>.</p>
<p><strong>Question: What techniques exist for &quot;minimally modifying a function to make it convex&quot;?</strong></p>
<p>For instance, suppose I numerically approximate the solution <span class="math-container">$f$</span> and the approximation turns out to not be convex.  How can I find a &quot;closest&quot; convex function?</p>
<p>The most obvious thing I can think of is to take a convex hull of the graph of <span class="math-container">$f$</span>, but this itself seems like a non-trivial problem.  Any references are appreciated.</p>

CC BY-SA 4.0
2022-10-10T05:49:16.640Z
FWIW, I'm a physicist/mathematician, and not a CS expert.  Any literature on this would be most appreciated.
Yly
CC BY-SA 4.0
2022-10-10T15:17:39.273Z
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 https://en.wikipedia.org/wiki/Convex_hull_algorithms
Martin Berger
CC BY-SA 4.0
2022-10-10T16:06:41.687Z
what do you want to do to $f(x)=-x^2$?
mathworker21
CC BY-SA 4.0
2022-10-10T16:40:56.647Z
@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
CC BY-SA 4.0
2022-10-11T13:07:31.320Z
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 https://arxiv.org/abs/0912.0322
Chandra Chekuri
CC BY-SA 4.0
2022-10-13T18:58:25.480Z
What do you know about your $f$?
Rodrigo de Azevedo
<approximation-algorithms><approximation><convex-hull>
How to enforce convexity?
Yly
# How to enforce convexity?

(Asked by: username_0 on 2022-10-10)

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.

**Tags:** approximation-algorithms, approximation, convex-hull

> **Comments:**
> **username_0**: FWIW, I'm a physicist/mathematician, and not a CS expert.  Any literature on this would be most appreciated.  
> **username_1**: 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 https://en.wikipedia.org/wiki/Convex_hull_algorithms  
> **username_2**: what do you want to do to $f(x)=-x^2$?  
> **username_0**: @username_2 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.  
> **username_3**: 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 https://arxiv.org/abs/0912.0322  
> **username_4**: What do you know about your $f$?  

---

## 0 answers

