Acabo de leer sobre el descenso de gradiente proyectado pero no vi la intuición para usar el proyectado en lugar del descenso de gradiente normal. ¿Podrías decirme la razón y las situaciones preferibles del descenso de gradiente proyectado? ¿Qué aporta esa proyección?
Respuestas
¿Demasiados anuncios?
A un nivel básico, el descenso de gradiente proyectado no es más que un método más general para resolver un problema más general.
El descenso gradiente minimiza una función moviéndose en la dirección negativa del gradiente en cada paso. No existe ninguna restricción sobre la variable. $$ \text{Problem 1:} \min_x f(x) $$ $$ x_{k+1} = x_k - t_k \nabla f(x_k) $$
Por otro lado, el descenso de gradiente proyectado minimiza una función sujeta a una restricción. En cada paso nos movemos en la dirección del gradiente negativo, y luego "proyectamos" sobre el conjunto factible.
$$ \text{Problem 2:} \min_x f(x) \text{ subject to } x \in C $$
$$ y_{k+1} = x_k - t_k \nabla f(x_k)\\ x_{k+1} = \text{arg} \min_{x \in C} \|y_{k+1}-x\| $$
wwehner
Puntos
41
He encontrado dos enfoques para el algoritmo.
Enfoque 1:
- $d_k = Pr(x_k-\nabla f(x_k)) - x_k$ dirección de búsqueda proyectada sobre el conjunto factible
- $x_{k+1} = x_k + t_k d_k$
Enfoque 2: (Igual que la respuesta de p.s.)
- $y_k = x_k - t_k \nabla f(x_k)$
- $x_{k+1} = Pr(y_k)$ : Proyecto $y_k$ en un conjunto factible
donde $Pr$ es el operador de proyección.
He comprobado que el método 1 funciona de forma más fiable. El enfoque 2 no converge si el minimizador está en el borde del conjunto factible y ese borde es perpendicular al gradiente del objetivo. Por ejemplo, las direcciones de búsqueda rebotan alrededor del minimizador en el algoritmo 2.
Vea aquí la implementación en matlab https://github.com/wwehner/projgrad
