Mínimos cuadrados sobre el simplex unitario

Question

Me interesa el problema de mínimos cuadrados no negativos sujeto a una restricción de igualdad

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & \mathrm 1_n^T \mathrm x = 1\\ & \mathrm x \geq 0_n\end{array}$$

Cada elemento del vector $\mathrm x$ es no negativo y suman uno. ¿Existe alguna solución cerrada o un método iterativo rápido? La dimensión de $\mathrm x$ no es muy grande, pero necesito un método rápido ya que esta optimización se va a ejecutar muchas veces para diferentes conjuntos de datos submuestreados.

Answer 1

Este es un enfoque que funciona si $A$ es invertible:

Estás proyectando $b$ en el conjunto convexo $A \Sigma$ , donde $\Sigma = \{ x | x_k \ge 0, \sum_k x_k = 1\}$ .

Dejemos que $C = \operatorname{co} \{ A e_k \}_k$ entonces el problema se convierte en uno de encontrar el punto más cercano $c\in C$ a $b$ . Entonces la solución es $x=A^{-1} c$ .

No soy actual, pero un algoritmo eficiente para resolver este problema se dado en Wolfe, P. ,Finding the Nearest Point in a Polytope, Mathematical Programming, Vol. 11, pp. 128-149,1976.

Si $A$ no es invertible, hay que resolver $Ax = c$ para obtener una solución.