Descenso coordinado

Algoritmo matemático

El descenso de coordenadas es un algoritmo de optimización que minimiza sucesivamente a lo largo de las direcciones de coordenadas para encontrar el mínimo de una función . En cada iteración, el algoritmo determina una coordenada o un bloque de coordenadas mediante una regla de selección de coordenadas y luego minimiza de manera exacta o inexacta sobre el hiperplano de coordenadas correspondiente mientras fija todas las demás coordenadas o bloques de coordenadas. Se puede realizar una búsqueda de línea a lo largo de la dirección de coordenadas en la iteración actual para determinar el tamaño de paso apropiado. El descenso de coordenadas es aplicable tanto en contextos diferenciables como en contextos sin derivadas.

Descripción

El descenso de coordenadas se basa en la idea de que la minimización de una función multivariable se puede lograr minimizándola a lo largo de una dirección a la vez, es decir, resolviendo problemas de optimización univariados (o al menos mucho más simples) en un bucle. ^[1] En el caso más simple de descenso de coordenadas cíclico , uno itera cíclicamente a través de las direcciones, una a la vez, minimizando la función objetivo con respecto a cada dirección de coordenadas a la vez. Es decir, comenzando con valores de variable iniciales ${\displaystyle F(\mathbf {x} )}$

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

round define desde resolviendo iterativamente los problemas de optimización de una sola variable ${\displaystyle k+1}$ ${\displaystyle \mathbf {x} ^{k+1}}$ ${\displaystyle \mathbf {x} ^{k}}$

${\displaystyle x_{i}^{k+1}={\underset {y\in \mathbb {R} }{\operatorname {arg\,min} }}\;f(x_{1}^{k+1},\dots ,x_{i-1}^{k+1},y,x_{i+1}^{k},\dots ,x_{n}^{k})}$^[2]

para cada variable de , para desde 1 hasta . ${\displaystyle x_{i}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle i}$ ${\displaystyle n}$

De este modo, se comienza con una estimación inicial de un mínimo local de y se obtiene una secuencia iterativamente. ${\displaystyle \mathbf {x} ^{0}}$ ${\displaystyle F}$ ${\displaystyle \mathbf {x} ^{0},\mathbf {x} ^{1},\mathbf {x} ^{2},\dots }$

Al realizar una búsqueda de línea en cada iteración, uno automáticamente tiene

${\displaystyle F(\mathbf {x} ^{0})\geq F(\mathbf {x} ^{1})\geq F(\mathbf {x} ^{2})\geq \dots .}$

Se puede demostrar que esta secuencia tiene propiedades de convergencia similares a las del descenso más pronunciado. La ausencia de mejoras después de un ciclo de búsqueda de línea a lo largo de las direcciones de coordenadas implica que se alcanza un punto estacionario.

Este proceso se ilustra a continuación.

Caso diferenciable

En el caso de una función continuamente diferenciable F , un algoritmo de descenso de coordenadas puede esbozarse como: ^[1]

• Elija un vector de parámetros inicial x .
• Hasta que se alcance la convergencia, o durante un número fijo de iteraciones:
  • Elija un índice i de 1 a n .
  • Elija un tamaño de paso α .
  • Actualizar x _i a x _i − α ⁠∂ F/∂ x _yo⁠ ( x ) .

El tamaño del paso se puede elegir de varias maneras, por ejemplo, resolviendo el minimizador exacto de f ( x _i ) = F ( x ) (es decir, F con todas las variables excepto x _i fijas), o mediante criterios de búsqueda de línea tradicionales. ^[1]

Limitaciones

El descenso de coordenadas tiene dos problemas. Uno de ellos es el caso de una función objetivo no suave . La siguiente imagen muestra que la iteración de descenso de coordenadas puede quedarse atascada en un punto no estacionario si las curvas de nivel de la función no son suaves. Supongamos que el algoritmo está en el punto (−2, −2) ; entonces hay dos direcciones alineadas con el eje que puede considerar para dar un paso, indicadas por las flechas rojas. Sin embargo, cada paso a lo largo de estas dos direcciones aumentará el valor de la función objetivo (suponiendo un problema de minimización), por lo que el algoritmo no dará ningún paso, aunque ambos pasos juntos acercarían al algoritmo al óptimo. Si bien este ejemplo muestra que el descenso de coordenadas no necesariamente converge al óptimo, es posible demostrar convergencia formal en condiciones razonables. ^[3]

El otro problema es la dificultad del paralelismo. Dado que la naturaleza del descenso de coordenadas es recorrer las direcciones y minimizar la función objetivo con respecto a cada dirección de coordenadas, el descenso de coordenadas no es un candidato obvio para el paralelismo masivo. Investigaciones recientes han demostrado que el paralelismo masivo es aplicable al descenso de coordenadas al relajar el cambio de la función objetivo con respecto a cada dirección de coordenadas. ^{[4] [5] [6]}

Aplicaciones

Los algoritmos de descenso de coordenadas son populares entre los profesionales debido a su simplicidad, pero la misma propiedad ha llevado a los investigadores de optimización a ignorarlos en gran medida a favor de métodos más interesantes (complicados). ^[1] Una aplicación temprana de la optimización del descenso de coordenadas fue en el área de la tomografía computarizada ^[7] donde se encontró que tiene una convergencia rápida ^[8] y posteriormente se utilizó para la reconstrucción clínica de TC de exploración helicoidal de múltiples cortes. ^[9] Se ha aplicado un algoritmo de descenso de coordenadas cíclico (CCD) en la predicción de la estructura de proteínas. ^[10] Además, ha habido un mayor interés en el uso del descenso de coordenadas con el advenimiento 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 entrenamiento de máquinas de vectores de soporte lineal ^[11] (ver LIBLINEAR ) y la factorización de matrices no negativas . ^[12] Son atractivos para problemas en los que el cálculo de gradientes es inviable, tal vez porque los datos necesarios para hacerlo se distribuyen a través de redes informáticas. ^[13]

Véase también

• Descenso adaptativo de coordenadas  : mejora del algoritmo de descenso de coordenadas
• Gradiente conjugado  : algoritmo de optimización matemáticaPáginas que muestran descripciones breves de los objetivos de redireccionamiento
• Descenso de gradiente  : algoritmo de optimización
• Búsqueda de línea  – Algoritmo de optimización
• Optimización matemática  – Estudio de algoritmos matemáticos para problemas de optimización.
• Método de Newton  – Método para encontrar puntos estacionarios de una función
• Descenso de gradiente estocástico  : algoritmo de optimización: utiliza un ejemplo a la vez, en lugar de una coordenada

Referencias

1. Wright, Stephen J. (2015). "Algoritmos de descenso de coordenadas". Programación matemática . 151 (1): 3–34. arXiv : 1502.04759 . doi :10.1007/s10107-015-0892-3. S2CID  15284973.
2. Gordon, Geoff; Tibshirani, Ryan (otoño de 2012). "Descenso de coordenadas" (PDF) . Optimización 10-725 / 36-725 . Universidad Carnegie Mellon.
3. Spall, JC (2012). "Proceso de balancín cíclico para optimización e identificación". Revista de teoría y aplicaciones de optimización . 154 (1): 187–208. doi :10.1007/s10957-012-0001-1. S2CID  7795605.
4. Zheng, J.; Saquib, SS; Sauer, K.; Bouman, CA (1 de octubre de 2000). "Algoritmos de tomografía bayesiana paralelizables con convergencia rápida y garantizada". IEEE Transactions on Image Processing . 9 (10): 1745–1759. Bibcode :2000ITIP....9.1745Z. CiteSeerX 10.1.1.34.4282 . doi :10.1109/83.869186. ISSN  1057-7149. PMID  18262913. 
5. Fessler, JA; Ficaro, EP; Clinthorne, NH; Lange, K. (1997-04-01). "Algoritmos de ascenso de coordenadas agrupadas para la reconstrucción de imágenes de transmisión con verosimilitud penalizada". IEEE Transactions on Medical Imaging . 16 (2): 166–175. doi :10.1109/42.563662. hdl : 2027.42/86021 . ISSN  0278-0062. PMID  9101326. S2CID  1523517.
6. Wang, Xiao; Sabne, Amit; Kisner, Sherman; Raghunathan, Anand; Bouman, Charles; Midkiff, Samuel (1 de enero de 2016). "Reconstrucción de imágenes basada en modelos de alto rendimiento". Actas del 21.º Simposio SIGPLAN de la ACM sobre principios y prácticas de programación paralela. PPoPP '16. Nueva York, NY, EE. UU.: ACM. pp. 2:1–2:12. doi :10.1145/2851141.2851163. ISBN 9781450340922.S2CID16569156  .​
7. Sauer, Ken; Bouman, Charles (febrero de 1993). "Una estrategia de actualización local para la reconstrucción iterativa a partir de proyecciones" (PDF) . IEEE Transactions on Signal Processing . 41 (2): 534–548. Bibcode :1993ITSP...41..534S. CiteSeerX 10.1.1.135.6045 . doi :10.1109/78.193196. 
8. Yu, Zhou; Thibault, Jean-Baptiste; Bouman, Charles; Sauer, Ken; Hsieh, Jiang (enero de 2011). "Reconstrucción rápida de TC basada en modelos X mediante optimización de ICD no homogénea espacial" (PDF) . IEEE Transactions on Image Processing . 20 (1): 161–175. Bibcode :2011ITIP...20..161Y. doi :10.1109/TIP.2010.2058811. PMID  20643609. S2CID  9315957.
9. Thibault, Jean-Baptiste; Sauer, Ken; Bouman, Charles; Hsieh, Jiang (noviembre de 2007). "Un enfoque estadístico tridimensional para mejorar la calidad de imagen para la TC helicoidal de múltiples cortes" (PDF) . Física médica . 34 (11): 4526–4544. Bibcode :2007MedPh..34.4526T. doi :10.1118/1.2789499. PMID  18072519.
10. Canutescu, AA; Dunbrack, RL (2003). "Descenso cíclico de coordenadas: un algoritmo robótico para el cierre de bucles de proteínas". Protein Science . 12 (5): 963–72. doi :10.1110/ps.0242703. PMC 2323867 . PMID  12717019. 
11. Hsieh, CJ; Chang, KW; Lin, CJ; Keerthi, SS; Sundararajan, S. (2008). "Un método de descenso de coordenadas dual para SVM lineal a gran escala" (PDF) . Actas de la 25.ª conferencia internacional sobre aprendizaje automático - ICML '08 . pág. 408. doi :10.1145/1390156.1390208. ISBN . 9781605582054.S2CID 7880266  .
12. Hsieh, CJ; Dhillon, IS (2011). Métodos de descenso rápido de coordenadas con selección de variables para factorización de matrices no negativas (PDF) . Actas de la 17.ª conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '11. pág. 1064. doi :10.1145/2020408.2020577. ISBN 9781450308137.
13. Nesterov, Yurii (2012). "Eficiencia de los métodos de descenso de coordenadas en problemas de optimización a gran escala" (PDF) . SIAM J. Optim . 22 (2): 341–362. CiteSeerX 10.1.1.332.3336 . doi :10.1137/100802001. 

• Bezdek, JC; Hathaway, RJ; Howard, RE; Wilson, CA; Windham, MP (1987), "Análisis de convergencia local de una versión de variable agrupada del descenso de coordenadas", Journal of Optimization Theory and Applications , vol. 54, núm. 3, Kluwer Academic/Plenum Publishers, págs. 471–477, doi :10.1007/BF00940196, S2CID  120052975
• Bertsekas, Dimitri P. (1999). Programación no lineal, segunda edición Athena Scientific, Belmont, Massachusetts. ISBN 1-886529-00-0 . 
• Luo, Zhiquan; Tseng, P. (1992), "Sobre la convergencia del método de descenso de coordenadas para la minimización diferenciable convexa", Journal of Optimization Theory and Applications , vol. 72, núm. 1, Kluwer Academic/Plenum Publishers, págs. 7–35, doi :10.1007/BF00939948, hdl : 1721.1/3164 , S2CID  121091844.
• Wu, TongTong; Lange, Kenneth (2008), "Algoritmos de descenso de coordenadas para la regresión penalizada con Lasso", The Annals of Applied Statistics , vol. 2, núm. 1, Institute of Mathematical Statistics, págs. 224–244, arXiv : 0803.3876 , doi : 10.1214/07-AOAS147, S2CID  16350311.
• Richtarik, Peter; Takac, Martin (abril de 2011), "Complejidad de iteración de métodos de descenso de coordenadas de bloque aleatorios para minimizar una función compuesta", Mathematical Programming , vol. 144, núm. 1–2, Springer, pp. 1–38, arXiv : 1107.2848 , doi :10.1007/s10107-012-0614-z, S2CID  16816638.
• Richtarik, Peter; Takac, Martin (diciembre de 2012), "Métodos de descenso de coordenadas paralelas para la optimización de big data", ArXiv:1212.0873 , arXiv : 1212.0873.