1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.