Hace poco conocí la pendiente de gradiente proyectada y tengo una pregunta. Según tengo entendido, cuando tiene un problema de optimización limitado, utiliza la dualidad para resolver un problema dual más fácil, que también da una respuesta al problema original. ¿El descenso de gradiente proyectado es solo otro método para resolver problemas de optimización restringidos? Si es así, ¿cuándo utilizan las personas el descenso de gradiente proyectado en lugar de la dualidad y viceversa?
Respuestas
¿Demasiados anuncios?
Max
Puntos
1424
Básicamente sí, proyectada gradiente de la pendiente es otro método para resolver problemas de optimización restringida. Sólo es útil cuando la proyección de la operación es fácil o tiene una forma cerrada, por ejemplo, restricciones de caja o lineal conjuntos de restricciones.
Además de directamente de solución limitada de problemas con simples conjuntos de restricciones, que puede ser utilizado en el dual, con buenos resultados en algunos problemas. Por ejemplo, hay muchos problemas en el primal es ilimitada, sino que implica no liso términos. Tomando el doble de la no-liso términos pueden ser (a menudo), convertido en simple restricciones, dejando el resto del problema diferenciable. Proyectado gradiente de la pendiente se puede utilizar. Ejemplos de esto incluyen L1 norma regularización de problemas; particularmente me gusta esta aplicación de la técnica.
David
Puntos
41
AaronDefazio tenido una muy buena respuesta:
Sólo es útil cuando la proyección de la operación es fácil o tiene una forma cerrada, por ejemplo, restricciones de caja o lineal conjuntos de restricciones.
Estoy añadiendo algunos detalles y un ejemplo de esta afirmación.
Tenga en cuenta que, en el Gradiente Proyectado Decente, la proyección de paso es otro problema de optimización. En este problema, queremos encontrar un punto en $C$ (conjunto de restricciones), este punto es el más cercano a un punto dado,$x^*$. Que es $$ \underset{x \in C}{\text{arg min}} \|x-x^*\| $$
En ciertos casos, este problema de optimización es fácil de resolver y se han cerrado. AaronDefazio mencionado cuadro de restricción y el conjunto de restricciones lineales. Voy a utilizar incluso un simple ejemplo, la esfera de la restricción de demostrar (Esfera restricción es L2, y el cuadro de restricción es L1).
$$ \underset{x \in C}{\text{arg min}} \|x-x^*\|=\left\{ \begin{array}{ll} x^* & \|x^*\| \leq r \\ r \frac {x^*} {\|x\|} & \text{otherwise} \\ \end{array} \right. $$
La ecuación dice que, si el punto está en el interior de la restricción de dominio, a continuación, la proyección es el punto.
Y voy a demostrar la $r \frac {x^*} {\|x\|}$ de los casos de forma gráfica, compruebe los puntos (marcados con los números) en pista de color azul y rojo de la pista, la relación es fácil: conectar los puntos de color azul con el centro del círculo (línea discontinua gris), la intersección con el círculo es la proyección.
El punto de este ejemplo está tratando de mostrar a encontrar la proyección es fácil e intuitivo, en este caso, y tiene una forma cerrada de la solución. Por otro lado, si tenemos un muy complicados $C$, solución de $\underset{x \in C}{\text{arg min}} \|x-x^*\|$ va a ser que no este trivial. En tal caso, no podemos utilizar las proyecciones de gradiente de la pendiente.
