characterization of a certain closed convex cone

Question

Consider $x_1,\cdots,x_n \in \mathbb{R}^d$, and the closed convex cone in $\mathbb{R}^n$ defined by $$\mathcal{K}(\underline{x}):=\{(\varphi(x_1),\cdots,\varphi(x_n)):\varphi \textrm{ convex on }\mathbb{R}^d\}.$$ I am looking for a good/efficient characterization for this cone or its polar cone. The motivation for this problem is trying to solve the projection of an given point $y\in \mathbb{R}^n$ onto $\mathcal{K}(\underline{x})$ numerically. In dimension $1$, a straightforward characterization would be given by $(\theta_1,\cdots,\theta_n) \in \mathcal{K}(\underline{x})$ if and only if $$\frac{\theta_{i+1}-\theta_{i}}{x_{i+1}-x_i}\leq \frac{\theta_{i+2}-\theta_{i+1}}{x_{i+2}-x_{i+1}},\forall i=1,\cdots n-2.$$ This means that in one dimension, the projection problem can be solved by a simple quadratic programming with $n-2$ constraints.

Comments and suggestions are greatly appreciated.

Answer 1

The paper http://arxiv.org/abs/1402.1561 might be of use in case $d = 2$.

Your set $\mathcal{K}(\underline x)$ is denoted as $\mathrm{Conv}(X)$, see (3). A characterization of this set can be found in Theorem 1.4 and Theorem 1.8 provides certain relaxations, if your points are on a regular grid (subset of $\mathbb{Z}^2$).

In the case that your points $x_i$ are in general position, you will end up with roughly $O(n^2)$ linear inequality constraints, see http://dx.doi.org/10.1007/s002110000235; Theorem 2.

Maybe the results can be generalized to $d > 2$, but you will end up with many linear constraints.