¿Son estos dos problemas de optimización equivalentes entre sí?

Question

Deje que $ \mathbf {x}=[x_1, \ldots ,x_K]^T$ . Para un vector fijo $ \mathbf {a}$ Tengo el siguiente problema de optimización: \begin {array}{rl} \min \limits_ { \mathbf {x}} & | \mathbf {a}}T \mathbf {x} | \\ \mbox {s.t.} & x_k \ge 0, \forall k \\ & \sum_k x_k=1 \end {arriba} El segundo problema de optimización es: \begin {array}{rl} \min \limits_ { \mathbf {x}} & ( \mathbf {a}}T \mathbf {x})^2 \\ \mbox {s.t.} & x_k \ge 0, \forall k \\ & \sum_k x_k=1 \end {\i1}{\b1}

Mi pregunta: ¿son estos dos problemas equivalentes el uno al otro? si es así, ¿cómo resolverlos? y ¿cuál es más fácil de resolver?

Answer 1

¿Qué es más fácil? Ninguna. Ambos modelos pueden resolverse analíticamente, y exactamente de la misma manera. Primero, eliminemos los casos fáciles:

1. Si cualquier $a_i=0$ para algunos $i$ entonces el valor óptimo de cualquiera de los dos modelos es claramente $0$ como lo demuestra la selección de la configuración $x$ para ser el $i$ vector unitario (el vector con $1$ en la posición $i$ y ceros en el resto).

2. Si $a_i>0$ y $a_j<0$ para algún par $(i,j)$ entonces de nuevo el valor óptimo es cero. Sólo hay que poner $$x_i=-a_j/(a_i-a_j), \quad x_j = a_i/(a_i-a_j)$$ y los demás elementos de $x$ a cero.

3. Los casos que quedan son aquellos en los que $a$ es totalmente positivo o totalmente negativo. Pero si $a$ es negativo, entonces sustituyendo $a$ para $-a$ no cambiará el valor óptimo ni los valores de $x$ que alcanzan este valor, gracias a la presencia del valor absoluto o cuadrado.

4. Así que ahora nos queda un caso: cuando $a$ es un vector positivo. Pero en este caso, $a^Tx$ ¡es positivo sobre el simplex, lo que nos permite dejar de lado el valor absoluto! \begin {array}{ll} \text {minimizar} & a^T x \\ \text {sujeto a} & \mathbf {1}^T x = 1 \\ & x \geq 0 \end {array} Podemos resolverlo por inspección: el valor óptimo es $\min_i a_i$ para el primer modelo, y $\min_i a_i^2$ para el segundo. Si la minimización $a_i$ es única, entonces la solución única es la $i$ vector unitario. Pero si hay varios elementos de $a$ con la misma magnitud, cualquier combinación convexa de esos vectores unitarios correspondientes es una solución.

Si lo ponemos todo junto, la solución es $\min_i |a_i|$ o $\min_i a_i^2$ si $a\succeq 0$ o $a\preceq 0$ y $0$ de lo contrario. Realmente no era necesario el caso 1, pero era fácil de ver.

Answer 2

Vamos a por una construcción analítica explícita del conjunto de todo el soluciones a su problema.

Notación básica: $e_K := \text{ column vector of }K\text{ }1'$ s. $\langle x, y \rangle$ denota el producto interior entre dos vectores $x$ y $y$ . Por ejemplo $\langle e_K, x\rangle$ simplemente equivale a sumar los componentes de $x$ .

Recordemos las siguientes definiciones, que se utilizarán sin más explicaciones.

Preimage: Dados conjuntos abstractos $X$ , $Y$ , $Z \subseteq Y$ ., el preimagen de $Z$ en $f$ se define por $f^{-1}Z := \{x \in X | f(x) \in Z\}$ . Esto no tiene nada que ver con la inversión de funciones.

Casco convexo: Dado un subconjunto $C$ de $\mathbb{R}^K$ , su convexo casco se define por $\textit{conv }C :=$ el subconjunto convexo más pequeño de $\mathbb{R}^K$ que contiene $C$ .

Función de indicador: Dado un subconjunto $C$ de $\mathbb{R}^K$ su función indicadora $i_C:\mathbb{R}^K \rightarrow (-\infty, +\infty]$ se define por $i_C(x) = 0$ si $x \in C$ ; de lo contrario $i_C(x) = +\infty$ .

Simplex: El $K$ -se define por $\Delta_K := \{x \in \mathbb{R}^K|x\ge 0, \langle e_K, x\rangle = 1\}$ . Equivalentemente, $\Delta_K = \{\text{rows of the }K \times K\text{ identity matrix }I_K\}$ . Cada fila de $I_K$ es un vértice de $\Delta_K$ .

Las caras de un simplex: Dado un subconjunto de índices $I \subseteq \{1,2,...,K\}$ El cara de $\Delta_K$ abarcados por $I$ , denotado como $F_K(I)$ se define como el casco convexo de las filas de $I_k$ indexado por $I$ . Trivialmente, $\Delta_K$ es una cara de sí mismo. Geométricamente, $F_K(I)$ es un $\#I$ -simplex de una dimensión cuyos vértices son los vértices de $\Delta_K$ que etiquetados por $I$ .

Dejemos que $f:\mathbb{R}^K \rightarrow (-\infty,+\infty]$ sea una función de valor real función de valor real.

Subdiferencial: $\partial f(x) := \{g \in \mathbb{R}^K| f(z) \ge f(s) + \langle g, z - x\rangle, \forall z \in \mathbb{R}^K\}$ .

Transformación de Fenchel-Legengre: $f^*(x) := \underset{z \in \mathbb{R}^K}{\text{max }}\langle x, z\rangle - f(z)$ .

El valor óptimo de su objetivo bajo las restricciones dadas puede ser convenientemente escrito como \begin {eqnarray} v = \underset {x \in \mathbb {R}^K}{ \text {min }}g(x) + f(Dx), \end {eqnarray} donde $D := a^T \in \mathbb{R}^{1 \times K}$ , $g := i_{\Delta_K}$ y $f:s \mapsto \frac{1}{2}s^2$ . Se reconoce el problema anterior como el primal forma del problema del punto de equilibrio \begin {eqnarray*} \underset {x \in \mathbb {R}^K}{ \text {min }} \underset {s \in \mathbb {R}}{ \text {max }} \langle s, Dx \rangle + g(x) - f^*(s) \end {eqnarray*} Dada una solución dual $\hat{s} \in \mathbb{R}$ el conjunto de soluciones primarias de soluciones primarias $\hat{X}$ está dada por (se puede comprobar que las condiciones suficientes que garantizan la fuerte Dualidad de Fenchel Teorema ) \begin {eqnarray*} \hat {X} = \partial g^*(-D^T \hat {s}) \cap D^{-1} \partial f^*( \hat {s}). \end {eqnarray*} Para su problema, uno calcula fácilmente, $g^*(y) = \underset{x \in \Delta_K}{\text{max }}\langle x, y\rangle$ y, por tanto, por el teorema de Bertsekas-Danskin (véase Propuesta A.22 de la tesis doctoral de Bertsekas) para las subdiferenciales, tenemos \begin {eqnarray*} \begin {split} \partial g^*(-D^T \hat {s}) &= \partial g^*(- \hat {s}a) = ... \text ( algunos cálculos enmascarados )} \\ &= F_K \left (\{1 \le i \le K | \hat {s}a_i \text { es un componente mínimo de } \hat {s}a\a} \right ). \end {split} \end {eqnarray*} También $\partial f^*(\hat{s}) = \{\hat{s}\}$ y así $D^{-1}\partial f^*(\hat{s}) = \{x \in \mathbb{R}^K|\langle a, x\rangle = \hat{s}\}$ . Por lo tanto, el conjunto de todas las soluciones primarias es \begin {eqnarray*} \hat {X} = F_K \left (\{1 \le i \le K | \hat {s}a_i \text { es un componente mínimo de } \hat {s}a\a} \right ) \cap \{x \in \mathbb {R}^K| \langle a, x \rangle = \hat {s}\}. \end {eqnarray*} Ahora queda encontrar una solución dual. Definir $\alpha := \underset{1 \le i \le K}{\text{min }}a_i \le \beta := \underset{1 \le i \le K}{\text{max }}a_i$ . Se calcula \begin {eqnarray*} \begin {split} v &= \underset {x \in \Delta_K }{ \text {min }} \underset {s \in \mathbb {R}}{ \text {max }}s \langle a, x \rangle - \frac {1}{2}s^2 = \underset {s, \lambda \in \mathbb {R}}{ \text {max }} \underset {x \ge 0}{ \text {min }} \langle sa + \lambda e_K, x \rangle - \frac {1}{2}s^2 - \lambda\\ &= \underset {s, \lambda \in \mathbb {R}}{ \text {max }}- \frac {1}{2}s^2 - \lambda\text { sujeto a }sa + \lambda e_K \ge 0 \\ &=- \underset {s, \lambda \in \mathbb {R}}{ \text {min }} \frac {1}{2}s^2 + \lambda\text { sujeto a } \lambda \ge - \underset {1 \le i \le K}{ \text {min }}sa_i \\ &= - \underset {s \in \mathbb {R}}{ \text {min }} \frac {1}{2}s^2 - \underset {1 \le i \le K}{ \text {min }}sa_i = - \frac {1}{2} \underset {s \in \mathbb {R}}{ \text {min }} \begin {casos}(s - \alpha )^2 - \alpha ^2, & \mbox { si }s \ge 0, \\ (s - \beta )^2 - \beta ^2, & \mbox {de lo contrario} \end {casos} \end {split} \end {eqnarray*} Así, \begin {eqnarray*} \hat {s} = \begin {casos} \beta , & \mbox { si } \beta < 0, \\0 , & \mbox { si } \alpha \le 0 \le \beta , \\\alpha , & \mbox { si } \alpha > 0. \end {casos} \end {eqnarray*} Por lo tanto, el conjunto de todo soluciones al problema original / primario es \begin {eqnarray*} \hat {X} = \begin {casos}F_K \left (\{1 \le i \le K | a_i = \beta\ } \right ), & \mbox { si } \beta < 0, \\ \Delta_K \cap \{x \in \mathbb {R}^K| \langle a, x \rangle = 0\}, & \mbox { si } \alpha \le 0 \le \beta , \\ F_K \left (\{1 \le i \le K | a_i = \alpha\ } \right ), & \mbox { si } \alpha > 0, \end {casos} \end {eqnarray*}

Ahora que tienes el martillo, busca los clavos...

• Caso (1) : $\beta < 0$ . Elija cualquier $k \in \{1,2,...,K\}$ tal que $a_k = \beta$ y tomar $\hat{x} = k$ La fila de $I_K$ .

• Caso (2a) : $a_k = 0$ para algunos $k$ . Toma $\hat{x} = k$ La fila de $I_K$ .

• Caso (2b) : $\alpha < 0 < \beta$ y $a_k \ne 0 \forall k$ . Elija $k_1, k_2 \in \{1,2,...,k\}$ tal que $a_{k_1} < 0 < a_{k_2}$ , y tomar $\hat{x}_k = \frac{1}{{a_{k_2} - a_{k_1}}}\begin{cases}a_{k_2}, &\mbox{ if }k = k_1,\\-a_{k_1},&\mbox{ if }k = k_2,\\0, &\mbox{ otherwise.}\end{cases}$

• Caso (3) : $\alpha > 0$ . Elija cualquier $k \in \{1,2,...,K\}$ tal que $a_k = \alpha$ y tomar $\hat{x} = k$ La fila de $I_K$ .