$ {L}_{1} $ Proyección sobre el Simplex de Probabilidad

Question

Dejemos que $\Delta^n$ denotan el $n$ -de probabilidad simplex. Proyección sobre un simplex de Yunmei Chen y Xiaojing Ye ofrece un algoritmo para la $\ell_2$ -proyección de un vector sobre $\Delta^n$ es decir, dado $y \in \mathbb R^n$ dan un método no iterativo para encontrar un minimizador $x^\ast(y)$ de $$ \min_{x \in \Delta^n} \|x-y\|_p $$ donde $p = 2$ .

Me interesa el caso de que $p = 1$ . ¿Existe un método que calcule un optimizador $x^\ast(y)$ para $p = 1$ que no utiliza un solucionador convexo?

Answer 1

Esta es una buena pregunta. Así que la resolví aunque hay una respuesta.

El problema

El problema viene dado por:

$$\begin{aligned} \arg \min_{x} \quad & {\left\| x - y \right\|}_{1} \\ \text{subject to} \quad & \boldsymbol{1}^{T} x = 1 \\ & {x}_{i} \geq 0 \; \forall i \end{aligned}$$

Solución 001 - Programación lineal

La función objetivo es:

$$ {\left\| x - y \right\|}_{1} = \sum_{i = 1}^{n} \left| {x}_{i} - {y}_{i} \right| = \sum_{i = 1}^{n} {t}_{i} $$

Ahora, al establecer $ \left| {x}_{i} - {y}_{i} \right| \leq {t}_{i} $ implícitamente sugiere que $ {t}_{i} \geq 0 $ . Entonces podemos reescribir el problema como

$$\begin{aligned} \arg \min_{t, x} \quad & \sum_{i = 1}^{n} {t}_{i} \\ \text{subject to} \quad & \left| {x}_{i} - {y}_{i} \right| \leq {t}_{i} \; \forall i \\ & \boldsymbol{1}^{T} x = 1 \\ & {x}_{i} \geq 0 \; \forall i \end{aligned}$$

Ahora bien, como $ \left| {x}_{i} - {y}_{i} \right| \leq {t}_{i} \Leftrightarrow {x}_{i} - {t}_{i} \leq {y}_{i} \wedge -{x}_{i} - {t}_{i} \leq - {y}_{i} $ podemos reescribir el problema como

$$\begin{aligned} \arg \min_{t, x} \quad & \sum_{i = 1}^{n} {t}_{i} \\ \text{subject to} \quad & - {t}_{i} + {x}_{i} \leq {y}_{i} \; & \forall i \\ & - {t}_{i} -{x}_{i} \leq {y}_{i} \; & \forall i \\ & \boldsymbol{1}^{T} x = 1 \\ & {x}_{i} \geq 0 \; & \forall i \end{aligned}$$

Que es un Programación lineal Problema que puede formarse y resolverse fácilmente.

Solución 002 - Solución directa

Nota: : Esto es muy similar a la solución de @ Maziar Sanjabi acaba de escribirlo de forma clara para mí.

La función objetivo viene dada por $ \sum_{i = 1}^{n} \left| {x}_{i} - {y}_{i} \right| $ que es optimizado por cada término.

Para cualquier término en el que $ {y}_{i} \leq 0 $ lo mejor que se puede hacer, debido a las limitaciones, es establecer $ {x}_{i} = 0 $ para minimizar el coste de este término.

Al definir $ \mathcal{S} = \left\{ i \mid {y}_{i} > 0 \right\} $ y $ s = \sum_{i \in \mathcal{S}} {y}_{i} $ podemos analizar 3 casos:

Caso I: $ s = 1 $

En este caso, fijamos $ {x}_{j} = {y}_{j}, \; \forall j \in \mathcal{S} $ . Desde $ x $ entonces obedece a todas las restricciones esta es la solución óptima.

Este es el único caso con solución única.

Caso II: $ s < 1 $

En primer lugar, fijamos $ {x}_{j} = {y}_{j}, \; \forall j \in \mathcal{S} $ . Entonces, en este caso tenemos un presupuesto $ r = 1 - s $ para gastar. En este caso, gastar significa añadiendo a los elementos de $ x $ .
Como la función objetivo es la suma del valor absoluto, podemos repartir este presupuesto como queramos siempre que mantengamos $ {x}_{i} \geq {y}_{i}, \; \forall i $ . Una forma es añadir a cada elemento de $ x $ la misma cantidad, podemos repartir el importe en $ \mathcal{S} $ o incluso añadirlo a un solo elemento de $ x $ . Ya que en cualquier combinación su contribución será la misma (Función absoluta por elemento).
Desde el punto de vista del rendimiento, probablemente lo mejor sea añadirlo a un solo elemento.

Está claro que en este caso hay muchas opciones de solución.

Caso III: $ s > 1 $

En primer lugar, fijamos $ {x}_{j} = {y}_{j}, \; \forall j \in \mathcal{S} $ . Entonces, en este caso tenemos un presupuesto $ r = s - 1 $ para gastar. En este caso, gastar significa restando a partir de elementos de $ x $ .
Como no podemos restar ningún valor a $ i \notin \mathcal{S} $ debemos hacerlo sólo para los elementos en $ \mathcal{S} $ . Una estrategia sencilla es restar del primer elemento todo lo que podamos pero sin que sea negativo. Entonces, si todavía el presupuesto es positivo podemos pasar al siguiente elemento y así sucesivamente.

Está claro que en este caso hay muchas opciones de solución.

Resumen

He implementado ambos métodos en MATLAB y he verificado el código frente a CVX.
El código MATLAB es accesible en mi StackExchange Matemáticas Q2477400 Repositorio GitHub .

Answer 2

En el caso de p=1, a diferencia de la norma euclidiana, el optimizador no es único. Por lo tanto, no tiene buenas propiedades y si se piensa un poco se puede ver que en algunos casos no será intuitivo. Pero el siguiente procedimiento debería dar uno de los muchos optimizadores posibles: Si $y_i\leq0$ set $x_i=0$ . Ahora denota el resto de índices i tales que $y_i>0$ como $S$ . Si $s=\sum_{i\in S} y_i\geq 1$ entonces simplemente elija $x_i\leq y_i, ~i\in S$ , de tal manera que $\sum_{i\in S} x_i=1$ (Es fácil elegir un punto así). Cualquier punto de este tipo sería un optimizador. Ahora, para el caso en que $s=\sum_{i\in S} y_i <1$ simplemente elija $x_i\geq y_i, ~i\in S$ , de tal manera que $\sum_{i\in S} x_i=1$ Por ejemplo $x_i = y_i + \frac{1-s}{|S|}$ .

En el caso de que todos los índices de y tengan un valor no positivo, entonces cualquier punto del simplex es un optimizador.