Descenso de gradiente en forma distribuida

Question

Deje $p(x_1,x_2,x_3)$ ser una función escalar. El objetivo es encontrar a $x_1,x_2,x_3$ a minimizar $p(x_1,x_2,x_3)$. Ahora, considere el método de gradiente de la pendiente: $$\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k+1} = \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k} - \alpha_k \left( \begin{array}{c} \frac{\partial p}{\partial x_1} \\ \frac{\partial p}{\partial x_2} \\ \frac{\partial p}{\partial x_3} \\ \end{array} \right)_{k}$$ donde $\alpha_k$ es el tamaño del paso.

Mi pregunta es: ¿puede el anterior proceso iterativo llevarse a cabo de manera distribuida? Esto podría estar motivado por algunas razones, tales como, distribuidos de recursos computacionales. La siguiente es mi opinión acerca de este problema.

Reescribir la ecuación anterior para $$x_{1,k+1}=x_{1,k}-\alpha_{1,k} \frac{\partial p}{\partial x_1}$$ $$x_{2,k+1}=x_{2,k}-\alpha_{2,k} \frac{\partial p}{\partial x_2}$$ $$x_{3,k+1}=x_{3,k}-\alpha_{3,k} \frac{\partial p}{\partial x_3}$$ A continuación, las tres ecuaciones que puede ser calculado en tres equipos, respectivamente. Aquí tengo una pregunta, ¿el tamaño del paso, $\alpha_{1,k}, \alpha_{2,k}, \alpha_{3,k}$ importa? Debemos mantener el $\alpha_{1,k}=\alpha_{2,k}=\alpha_{3,k}$?? En otras palabras, es el siguiente ecuación de gradiente de la pendiente? Si $\alpha_{1,k}, \alpha_{2,k}, \alpha_{3,k}$ son diferentes el uno del otro, el movimiento global no es siempre a lo largo de con $\nabla_\mathbf{x} p(\mathbf{x})$. $$\left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k+1} = \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ \end{array} \right)_{k} - \left( \begin{array}{ccc} \alpha_{1,k} & 0 & 0 \\ 0 & \alpha_{2,k} & 0 \\ 0& 0& \alpha_{3,k}\\ \end{array} \right) \left( \begin{array}{c} \frac{\partial p}{\partial x_1} \\ \frac{\partial p}{\partial x_2} \\ \frac{\partial p}{\partial x_3} \\ \end{array} \right)_{k}$$

Answer 1

Técnicamente está permitido el uso de diferentes stepsizes de diferentes variables tanto tiempo como usted puede establecer (matemáticamente) que el linesearch procedimiento que calcula el $\alpha_{i,k}$ asegura que existen constantes $0 < l < u$ tal que $$l \ \alpha_{i,k} \leq \alpha_{j,k} \leq u \ \alpha_{i,k} \quad \text{para todas las iteraciones } k \text{ todos } i, j = 1, \ldots, n.$$ Esto se utiliza para evitar algunos steplengths de la convergencia a cero o a infinito, mientras que otros siguen siendo finito.

En su segundo punto, donde el descenso con dirección a la que tiene la forma de $Ag$, se utiliza un cuasi método de Newton. Si se utiliza el método de Newton, su dirección de búsqueda podría resolver el sistema lineal $$\nabla^2 f(x_k) d = - \nabla f(x_k).$$ (Tenga en cuenta que yo no he dicho que el de Hesse $\nabla^2 f(x_k)$ fue invertible... es lo que es.) Esta dirección de búsqueda será un descenso con dirección a la si $d^T \nabla f(x_k) < 0$. Es el caso de al $\nabla^2 f(x_k)$ es positiva definida, pero puede ocurrir en otras situaciones. Ahora si la segunda derivados no están disponibles o son demasiado costosos para evaluar puede sustituir su propia matriz del sistema lineal anterior y requieren $d$ resolver $$B d = -\nabla f(x_k).$$ Usted obtendrá un descenso con dirección a la proporcionada $B$ es positiva definida. La mayor descenso método simplemente corresponde a $B = I$. Hay una sutileza que aquí. Es probable que el uso de diferentes $B$ en cada iteración para $B$ es realmente $B_k$. Se puede garantizar la convergencia si se utiliza uno de los estándar de linesearch métodos (Armijo, Wolfe, fuerte Wolfe, Goldstein, ...) y si puede asegurarse de que $d$ nunca los enfoques de ortogonalidad con $\nabla f(x_k)$ (lo que podría suceder en un furtivo manera en el límite). Esto equivale a probar que $d^T \nabla f(x_k) \leq -\theta < 0$ para algunas constantes $\theta$ independiente de $k$. En cualquier optimización del libro, buscar Zoutendijk del teorema.

Cuasi-Newton métodos son una forma de preacondicionamiento de la mayor descenso método. En los primeros días, que fueron referidos como "variable" métrica de los métodos. Si puede ser calculada de manera distribuida, depende en gran medida de la estructura de la matriz $B$.

Answer 2

Ahora lo de averiguar.

La más empinada de gradiente de la pendiente es $$x_{k+1}=x_k-\alpha_k g$$ donde $g=\nabla p(x)$ es el gradiente. Cuando queremos utilizar $$x_{k+1}=x_k-A g$$ con $A$ como una matriz en lugar de ello, sólo tenemos que asegurar $$g^T A g>0$$ tal que $p(x)$ le siguen disminuyendo. El sentido geométrico de la ecuación anterior es: la evolución de la dirección de la $-A g$ debe hacer un ángulo estrictamente menor que $\pi/2$$-g$. Así que mientras a $A$ es positiva definida, la evolución de la dirección es siempre un descenso de la dirección (no más pronunciada).