Descenso coordinado

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de abril de 2022; la verificación requiere 1 edición .

El descenso de coordenadas es un algoritmo de optimización que minimiza secuencialmente una función a lo largo de direcciones de coordenadas. En cada iteración, el algoritmo determina una variable de coordenadas o un bloque de coordenadas por medio de una regla de selección de coordenadas, luego minimiza exactamente o aproximadamente sobre el hiperplano de coordenadas correspondiente mientras fija otras coordenadas o bloques de coordenadas. En la iteración actual, se puede realizar una búsqueda lineal a lo largo de la dirección de coordenadas para encontrar un tamaño de paso adecuado. El descenso de coordenadas se puede aplicar tanto en el caso diferenciable como en el caso de contexto cuando no se calculan derivadas.

Descripción

El descenso de coordenadas se basa en la idea de que se puede minimizar una función de muchas variables minimizando en una dirección a la vez, por ejemplo, resolviendo un problema de optimización de una sola variable (o al menos un problema más simple) en un bucle [1] . En el caso más simple de descenso de coordenadas cíclicas , el algoritmo itera sobre las direcciones de coordenadas una por iteración, minimizando la función objetivo sobre cada coordenada a la vez. Es decir, partiendo de los valores iniciales $F(\mathbf{x} )$

\mathbf {x} ^{0}=(x_{1}^{0},\ldots,x_{n}^{0})

la iteración se determina a partir de la resolución iterativa de problemas de optimización a partir de una variable $k+1$ $\mathbf {x} ^{k+1}$ ${\ estilo de visualización \ mathbf {x} ^ {k}}$

x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+ 1 },\puntos,x_{i-1}^{k+1},y,x_{i+1}^{k},\puntos,x_{n}^{k})

[2]

para cada variable vectorial de 1 a . $x_{yo}$ $\mathbf{x}$ $i$ $norte$

Así, el algoritmo parte de una aproximación inicial del mínimo local de la función y obtiene iterativamente una secuencia de vectores. ${\ estilo de visualización \ mathbf {x} ^ {0))$ $F$ $\mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\puntos$

Al realizar una búsqueda lineal en cada iteración, obtenemos

F(\mathbf {x} ^{0})\geqslant F(\mathbf {x} ^{1})\geqslant F(\mathbf {x} ^{2})\geqslant \dots .

Se puede demostrar que esta secuencia tiene propiedades de convergencia similares al método de descenso más pronunciado. La falta de mejora en la función objetivo después del siguiente ciclo de búsquedas lineales a lo largo de las direcciones de las coordenadas indica que se ha alcanzado un punto estacionario.

El funcionamiento del algoritmo se muestra a continuación.

Caso diferenciable

En el caso de diferenciabilidad continua de la función F , el algoritmo de descenso de coordenadas se puede resumir como [1] :

Elegimos el vector inicial x .
Hasta que se alcanza un nivel de convergencia o se realiza un número fijo de iteraciones:
- Elija un índice i del intervalo de 1 a n .
- Elegimos el tamaño de paso α .
- Reemplazamos con . $x_{yo}$ $x_{i}-\alpha {\tfrac {\parcial F}{\parcial x_{i))}(\mathbf {x} )$

El paso se puede elegir de muchas maneras, por ejemplo, resolviendo un problema de minimización (es decir, minimizando F con variables fijas excepto ), o mediante la búsqueda lineal tradicional [1] . $f(x_{i})=F(\mathbf {x} )$ $x_{yo}$

Restricciones

El descenso coordinado tiene dos problemas. Uno de ellos es la presencia de una función no suave de varias variables. La figura muestra que las iteraciones de descenso de coordenadas pueden llegar a un punto no estacionario si las curvas de nivel de la función no son uniformes. Supongamos que el algoritmo terminó en el punto (-2, -2) . Entonces hay dos direcciones paralelas a los ejes a lo largo de los cuales se debe dar el siguiente paso. Se muestran con flechas rojas. Sin embargo, cualquier paso en estas dos direcciones conducirá a un aumento en el valor de la función (se supone que se está resolviendo el problema de minimización), por lo que el algoritmo no dará un solo paso, aunque dos pasos juntos traerían el algoritmo más cercano al óptimo. Aunque este ejemplo muestra que el descenso de coordenadas no conduce necesariamente a una solución óptima, es posible mostrar convergencia formal en condiciones normales [3] .

Otro problema es la dificultad en la paralelización. Dado que la naturaleza del descenso de coordenadas es recorrer direcciones y minimizar una función a lo largo de cada dirección de coordenadas, el descenso de coordenadas no es un candidato obvio para la paralelización. Investigaciones recientes han demostrado que la paralelización se puede utilizar para el descenso coordinado con algunos trucos especiales [4] [5] [6] .

Aplicaciones

Los algoritmos de descenso de coordenadas son populares por su simplicidad, pero la misma propiedad anima a los investigadores a ignorarlos en favor de métodos más interesantes (más complejos) [1] . Las primeras aplicaciones de la optimización del descenso de coordenadas se dieron en el campo de la tomografía computarizada [7] , donde el método mostró una convergencia rápida [8] y se utilizó para reconstruir imágenes de tomografía computarizada helicoidal multicapa [9] . El algoritmo de descenso de coordenadas cíclicas se ha aplicado en la predicción de estructuras de proteínas [10] . Además, ha habido un interés creciente en la aplicación del descenso de coordenadas con la aparición de problemas a gran escala en el aprendizaje automático , donde se ha demostrado que el descenso de coordenadas es competitivo con otros métodos cuando se aplica a problemas como el aprendizaje automático de vectores de soporte lineal . 11] (ver LIBLINEAR ) y expansión de matriz no negativa [12] . Los métodos son atractivos para problemas en los que el cálculo de gradientes no es factible, quizás porque los datos requeridos se distribuyen a través de redes informáticas [13] .

Véase también

Notas

↑ 1 2 3 4 Wright, 2015 , pág. 3–34.
↑ Copia archivada . Consultado el 6 de febrero de 2022. Archivado desde el original el 6 de febrero de 2022. (indefinido)
↑ Spall, 2012 , pág. 187–208.
↑ Zheng, Saquib, Sauer, Bouman, 2000 , pág. 1745-1759
↑ Fessler, Ficaro, Clinton, Lange, 1997 , p. 166–175.
↑ Wang, Sabne, Kisner, 2016 , pág. 2:1–2:12.
↑ Sauer, Bouman, 1993 , pág. 534–548.
↑ Yu, Thibault, Bouman, Sauer, 2011 , pág. 161–175.
↑ Thibault, Sauer, Bouman, Hsieh, 2007 , pág. 4526–4544.
↑ Canutescu, Dunbrack, 2003 , pág. 963–72.
↑ Hsieh, Chang, Lin, Keerthi, 2008 , pág. 408.
↑ Hsieh, Dhillon, 2011 , pág. 1064.
↑ Nésterov, 2012 , pág. 341–362.

Literatura

Stephen J. Wright. Algoritmos de descenso de coordenadas // Programación Matemática. - 2015. - T. 151 , núm. 1 . -doi : 10.1007/ s10107-015-0892-3 . -arXiv : 1502.04759 . _
Proceso de oscilación cíclica Spall JC para optimización e identificación // Revista de teoría y aplicaciones de optimización. - 2012. - T. 154 , núm. 1 . -doi : 10.1007/ s10957-012-0001-1 .
Zheng J., Saquib SS, Sauer K., Bouman CA Algoritmos de tomografía bayesiana paralelizables con convergencia rápida y garantizada // IEEE Transactions on Image Processing. - 2000. - T. 9 , núm. 10 _ — ISSN 1057-7149 . -doi : 10.1109/ 83.869186 . - . — PMID 18262913 .
Fessler JA, Ficaro EP, Clinthorne NH, Lange K. Algoritmos de ascenso de coordenadas agrupadas para la reconstrucción de imágenes de transmisión de probabilidad penalizada // IEEE Transactions on Medical Imaging. - 1997. - T. 16 , núm. 2 . — ISSN 0278-0062 . -doi : 10.1109/ 42.563662 . —PMID 9101326 .
Xiao Wang, Amit Sabne, Sherman Kisner, Anand Raghunathan, Charles Bouman, Samuel Midkiff. Reconstrucción de imágenes basada en modelos de alto rendimiento . — Actas del XXI Simposio ACM SIGPLAN sobre Principios y Práctica de la Programación Paralela. — Nueva York, NY, EE. UU.: ACM, 2016. — ISBN 9781450340922 . -doi : 10.1145/ 2851141.2851163 .
Ken Sauer, Charles Bowman. Una estrategia de actualización local para la reconstrucción iterativa a partir de proyecciones // Transacciones IEEE en el procesamiento de señales. - 1993. - febrero ( vol. 41 , número 2 ). -doi : 10.1109/ 78.193196 . - .
Zhou Yu, Jean-Baptiste Thibault, Charles Bouman, Ken Sauer, Jiang Hsieh. Reconstrucción rápida de tomografía computarizada de rayos X basada en modelos usando optimización ICD espacialmente no homogénea // Transacciones IEEE en procesamiento de imágenes. - 2011. - Enero ( vol. 20 , número 1 ). -doi : 10.1109/ TIP.2010.2058811 . - . —PMID 20643609 .
Jean-Baptiste Thibault, Ken Sauer, Charles Bouman, Jiang Hsieh. Un enfoque estadístico tridimensional para mejorar la calidad de imagen para CT helicoidal multicorte // Física médica. - 2007. - noviembre ( vol. 34 , número 11 ). -doi : 10.1118 / 1.2789499 . - . — PMID 18072519 .
Canutescu AA, Dunbrack RL Descenso de coordenadas cíclicas: un algoritmo robótico para el cierre de bucles de proteínas. // Ciencia de las proteínas. - 2003. - T. 12 , núm. 5 . -doi : 10.1110 / ps.0242703 . —PMID 12717019 .
Hsieh CJ, Chang KW, Lin CJ, Keerthi SS, Sundararajan S. Un método de descenso de coordenadas duales para SVM lineal a gran escala // Actas de la 25.ª conferencia internacional sobre aprendizaje automático - ICML '08. - 2008. - ISBN 9781605582054 . -doi : 10.1145/ 1390156.1390208 .
Hsieh CJ, Dhillon IS Métodos de descenso de coordenadas rápidas con selección de variables para factorización de matrices no negativas // Actas de la 17.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '11 . - 2011. - ISBN 9781450308137 . -doi : 10.1145/ 2020408.2020577 .
Yuri Nésterov. Eficiencia de los métodos de descenso de coordenadas en problemas de optimización a gran escala // SIAM J. Optim.. - 2012. - V. 22 , no. 2 . -doi : 10.1137/ 100802001 .
Bezdek JC, Hathaway RJ, Howard RE, Wilson CA, Windham MP Análisis de convergencia local de una versión variable agrupada del descenso de coordenadas // Journal of Optimization Theory and Applications. - Kluwer Academic / Plenum Publishers, 1987. - V. 54 , no. 3 . - Pág. 471-477. -doi : 10.1007/ BF00940196 .
Dimitri P. Bertsekas,. programación no lineal. - Segunda edicion. - Belmont, Massachusetts: Athena Scientific, 1999. - ISBN 1-886529-00-0 .
Zhiquan Luo, Tseng P. Sobre la convergencia del método de descenso de coordenadas para la minimización diferenciable convexa // Journal of Optimization Theory and Applications. - Kluwer Academic / Plenum Publishers, 1992. - T. 72 , no. 1 . — pág. 7–35. -doi : 10.1007/ BF00939948 . .
Tong Tong Wu, Kenneth Lange. Coordine los algoritmos de descenso para la regresión penalizada por Lasso // The Annals of Applied Statistics. - Instituto de Estadística Matemática, 2008. - Vol. 2 , núm. 1 . - Pág. 224-244. -doi : 10.1214 / 07-AOAS147 . -arXiv : 0803.3876 . _ .
Peter Richtarik, Martin Takac. Complejidad de iteración de métodos de descenso de coordenadas de bloques aleatorios para minimizar una función compuesta // Programación matemática. - Springer, abril de 2011. - Vol. 144 , no. 1–2 . — pág. 1–38. -doi : 10.1007 / s10107-012-0614-z . -arXiv : 1107.2848 . _
Peter Richtarik, Martin Takac. Métodos de descenso de coordenadas paralelas para la optimización de big data // ArXiv:1212.0873. - Diciembre 2012. - arXiv : 1212.0873 .

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial