caracterización de un cierto cono convexo cerrado

Question

Considere $x_1,\cdots,x_n \in \mathbb{R}^d$ y el cono convexo cerrado en $\mathbb{R}^n$ definido por $$\mathcal{K}(\underline{x}):=\{(\varphi(x_1),\cdots,\varphi(x_n)):\varphi \textrm{ convex on }\mathbb{R}^d\}.$$ Estoy buscando una buena/eficiente caracterización para este cono o su cono polar. La motivación de este problema es tratar de resolver la proyección de un punto dado $y\in \mathbb{R}^n$ en $\mathcal{K}(\underline{x})$ numéricamente. En la dimensión $1$ una caracterización directa vendría dada por $(\theta_1,\cdots,\theta_n) \in \mathcal{K}(\underline{x})$ si y sólo si $$\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.$$ Esto significa que, en una dimensión, el problema de proyección puede resolverse mediante una simple programación cuadrática con $n-2$ limitaciones.

Se agradecen mucho los comentarios y sugerencias.

Answer 1

El papel http://arxiv.org/abs/1402.1561 puede ser útil en caso de que $d = 2$ .

Su conjunto $\mathcal{K}(\underline x)$ se denota como $\mathrm{Conv}(X)$ (3). Una caracterización de este conjunto se puede encontrar en el Teorema 1.4 y el Teorema 1.8 proporciona ciertas relajaciones, si sus puntos están en una cuadrícula regular (subconjunto de $\mathbb{Z}^2$ ).

En el caso de que sus puntos $x_i$ están en posición general, terminará con aproximadamente $O(n^2)$ Restricciones de desigualdades lineales, véase http://dx.doi.org/10.1007/s002110000235 ; Teorema 2.

Tal vez los resultados puedan generalizarse a $d > 2$ pero terminará con muchas restricciones lineales.