Deje $n, m \in \mathbb{N}$, $q \geq 2$, e $x^j \in \mathbb{R}^n$ para $j=1, \cdots, m$.
¿Cómo podemos demostrar que la siguiente función $f$ es noconvexo? $$ f : \mathbb{R^{cn}} = \mathbb{R}^n \times \cdots \times \mathbb{R}^n \to \mathbb{R} \\ f(z) = f(z^1, \cdots, z^q) := \sum_{j=1}^m \min_{\ell = 1, \cdots, q}\| x^j - z^\ell \| = \left\| \begin{pmatrix} \min_{\ell = 1, \cdots, q} \| x^1 - z^\ell \| \\ \vdots \\ \min_{\ell = 1, \cdots, q} \| x^m - z^\ell \| \end{pmatrix} \right\|_1 $$
Mi trabajo/pensamientos hasta el momento:
El problema es el $\min$ funciones, ya $f$ sería convexa en $\mathbb{R}^{nq}$ si $\ell(j)$ ya eran conocidos (ya que acababa de tener una suma de funciones convexas).
He demostrado que $f$ no es complejo en virtud de cierta simplificación de las circunstancias. Es decir, si $x^j = 0$ para $j= 1, \cdots, m$ , y dejamos $n=1$, $q = 2$. Entonces podemos tomar $z := (6,8)^T$, $w := (4,2)^T$, e $\lambda := 1/2$, lo que produce $$ f(\lambda w + (1- \lambda) z) = 5m > 4m = \lambda f(w) + (1-\lambda) f(z). $$ Es decir, he mostrado (Suposiciones $\nRightarrow$ $f$ convexo). Pero ese no es el mismo como se muestra (Suposiciones $\Rightarrow$ $f$ NO convexo), que es el objetivo.
- Además, el uso de la inversa de la desigualdad del triángulo, puedo demostrar que para todos los $\lambda \in (0,1)$, $z = (z^1, \cdots, z^q),w= (w^1, \cdots, w^q) \in \mathbb{R}^{nq}$ $$ f(\lambda z + (1-\lambda)w) \geq \lambda f(z) + (\lambda - 1) f(w) $$ Pero, también, no lo que yo quiero.
Procedencia de ejercicio:
- Este problema se deja como ejercicio para el lector en un texto de optimización estoy leyendo (Grundzüge der Globalen Optimierung por Stein).
- Es parte de una muestra permanente sobre la búsqueda de $q$ centros de cluster ( $z^j$, $j=1, \cdots, q$) entre una nube de datos (la $x^j$, $j=1, \cdots, m$). Aquí $f$ es una opción razonable para la función de destino que queremos minimizar.
