4
$\begingroup$

I'm wondering where to find a proof and reference for the following facts, which I feel sure must be true.

(1) Suppose we are given a finite set of points in $\mathbb{R}^{d+1}$. For each point, we are given a closed halfspace tangent to it and strictly containing all others. Then there exists a strictly convex set contained in the intersection of the halfspaces with all the given points on the boundary.

(If I drop "strictly", then the convex hull of the points works.)

a strictly convex set drawn inside the lines

(2) Suppose we are given a finite set of pairs $(x,y)$ with $x \in \mathbb{R}^d$ and $y \in \mathbb{R}$. For each point, we are given a linear function through it and strictly below the others. Then there exists a strictly convex function passing through the points whose gradient at each given point matches the given linear function's.

(If I drop "strictly", then "convex closure" of the pairs works.)

a strictly convex function through the given points with the given gradients

$\endgroup$
5
$\begingroup$

Both facts have short proofs. We first prove (1) and then get a stronger statement for (2) - so that the result is $C^{\infty}$ smooth.

Proof of (1). By assumptions, for each point $x$ of the set there is a half-space $H_x$ containing $x$ in its boundary and containing all other points in its interior. So there is also a radius $R$ ball $B_x^R$ contained in $H_x$, tangent to $\partial H_x$ at $x$ and containing all the other points of the set (just take $R$ large enough). Now, the intersection of all balls $B_x^R$ is the desired strictly convex set.

Proof of (2). Let's show how to construct such a strictly convex function in the $C^{\infty}$ class. So suppose that our collection of points is $(x_i,y_i)$ and the planes are defined by $y=L_i(x)$ (so that $y_i=L_i(x)$). It is clear than the for $\varepsilon>0$ small enough the function $$F(x)=\max_i(L_i(x)+\varepsilon|x-x_i|^2)$$ solves the problem. However $F_{\varepsilon}$ is not smooth. To find a smooth function let's choose a symmetric density $\rho_{\varepsilon}(x)\ge 0$ satisfying

1) $\rho_{\varepsilon }(x)=\rho_{\varepsilon }(-x)$, 2) $\int \rho_{\varepsilon }=1$, and 3) $\rho_{\varepsilon }(x)=0$ for $|x|>\varepsilon$.

The following claim is easy.

Claim. The convolution $\widetilde F_{\varepsilon}=F_{\varepsilon}*\rho_{\varepsilon }$ has the property that $\widetilde F_{\varepsilon}-F_{\varepsilon}=const(\varepsilon)>0$ at points that are on distance more than $\varepsilon$ from the locus of non-smoothness of $F_{\varepsilon}$.

So it is easy to see that for $\varepsilon$ small enough the function $\widetilde F_{\varepsilon}-const(\varepsilon)$ will do the job.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice and short! The pictures in the question look like OP would also like additional smoothness. Do you know how to handle this, too? $\endgroup$ – Dirk Apr 14 '19 at 15:21
  • $\begingroup$ It is easy to make this $C^{\infty}$ smooth in the second case by taking a convolution with some smooth measure supported in a small enough ball (though convolution should be taken with a slightly different function). In the first case it easy to make it $C^1$-smooth - by first constructing a similar domain which is slightly smaller and then taking an $\varepsilon$-neighbourhood of it. I guess it should be possible to make it $C^{\infty}$-smooth as well (should follow from some general results on smoothing of convex sets...) $\endgroup$ – Dmitri Panov Apr 14 '19 at 16:28
  • $\begingroup$ Is it clear that convolution will still interpolatate the points and first derivatives? $\endgroup$ – Dirk Apr 14 '19 at 17:48
  • $\begingroup$ Drik, I added some details for the second case which show how to make the function smooth. $\endgroup$ – Dmitri Panov Apr 14 '19 at 18:56
  • $\begingroup$ Really awesome! I hadn't thought about smoothness, but hmm, it might actually be a useful bonus for my application. Thank you. $\endgroup$ – usul Apr 15 '19 at 11:48
1
$\begingroup$

Since the topic of smoothness came up in the other answer: Here is a reference for the case where one asks for the function to be convex and $C^{1,1}$, i.e. Lipschitz continuous derivative.

In general, the problem of constructing a function from some function values and (possibly higher) derivatives is called the "Whitney extension problem". So if you want to read more about this you can look for "convex Whitney extension".

| cite | improve this answer | |
$\endgroup$

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.