Descripción general de los métodos de gradiente en problemas de optimización matemática

Prólogo

Este artículo se centrará en los métodos para resolver problemas de optimización matemática basados ​​en el uso de un gradiente de función. El objetivo principal es recopilar en el artículo todas las ideas más importantes que de alguna manera están relacionadas con este método y sus diversas modificaciones.





UPD En los comentarios escriben que en algunos navegadores y en las aplicaciones móviles no se muestran las fórmulas. Desafortunadamente, no sé cómo lidiar con eso. Solo puedo decir que utilicé las macros "en línea" y "mostrar" del editor Habrava. Si de repente sabes cómo solucionar esto, escribe en los comentarios, por favor.

Nota del autor

Al momento de escribir, defendí una disertación, cuya tarea me exigió tener una comprensión profunda de los métodos básicamente teóricos de optimización matemática. Sin embargo, mis ojos (de todos los demás) todavía están borrosos por las largas y aterradoras fórmulas, por lo que pasé mucho tiempo para aislar las ideas clave que caracterizarían diferentes variaciones de los métodos de gradiente. Mi objetivo personal es escribir un artículo que contenga la cantidad mínima de información necesaria para una comprensión más o menos detallada del tema. Pero prepárate, uno no puede prescindir de las fórmulas de todos modos.

Declaración del problema.

Antes de describir el método, primero debe describir el problema, a saber: "Dado que hay muchos $$$\ mathcal {K}$ y función $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ necesita encontrar un punto $$$x ^ * \ in \ mathcal {K}$ tal que $$$f (x) \ geq f (x ^ *)$ para todos $$$x \ in \ mathcal {K}$ ", Que generalmente se escribe así

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}.$$

En teoría , generalmente se supone que $$$f$ Es una función diferenciable y convexa, y $$$\ mathcal {K}$ - conjunto convexo (e incluso mejor, si lo hay $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), esto nos permite dar algunas garantías del éxito de la aplicación del descenso de gradiente. En la práctica, el descenso de gradiente se aplica con éxito incluso cuando la tarea no tiene ninguna de las propiedades anteriores (un ejemplo más adelante en el artículo).

Un poco de matemática

Supongamos por ahora que solo necesitamos encontrar un mínimo de una función unidimensional

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}.$$

En el siglo XVII, Pierre Fermat ideó un criterio que permitía resolver problemas simples de optimización, a saber, si $$$x ^ *$ - punto mínimo $$$f ^ *$ entonces

$$

$$f '(x ^ *) = 0$$

donde $$$f '$ - derivado $$$f$ . Este criterio se basa en una aproximación lineal.

$$

$$f (x) \ aprox. f (x ^ *) + f '(x ^ *) (x-x ^ *).$$

Más cerca $$$x$ a $$$x ^ *$ , cuanto más precisa sea esta aproximación. En el lado derecho hay una expresión que, cuando $$$f '(x ^ *) \ neq 0$ tal vez como más $$$f (x ^ *)$ menos es la esencia principal del criterio. En el caso multidimensional, de manera similar a la aproximación lineal. $$$f (x) \ aprox. f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (en adelante $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - producto escalar estándar, la forma de escritura se debe al hecho de que el producto escalar es el mismo que el producto matricial de un vector fila por un vector columna), se obtiene el criterio

$$

$$\ nabla f (x ^ *) = 0. $$$

Valor $$$\ nabla f (x ^ *)$ - gradiente de funciones $$$f$ en el punto $$$x ^ *$ . Además, la igualdad del gradiente a cero significa la igualdad de todas las derivadas parciales a cero, por lo tanto, en el caso multidimensional, uno puede obtener este criterio simplemente aplicando secuencialmente el criterio unidimensional para cada variable por separado.

Vale la pena señalar que estas condiciones son necesarias, pero no suficientes, el ejemplo más simple es 0 para $$$f (x) = x ^ 2$ y $$$f (x) = x ^ 3$


Este criterio es suficiente en el caso de una función convexa, en gran parte debido a esto fue posible obtener tantos resultados para las funciones convexas.

Funciones cuadráticas

Funciones cuadráticas en $$$\ mathbb {R} ^ n$ Es una función de la forma

$$

$$f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$$

Para ahorrar espacio (y molestarse menos con los índices), esta función generalmente se escribe en forma de matriz:

$$

$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c,$$

donde $$$x = (x_1, \ ldots, x_n) ^ T$ , $$$b = (b_1, \ ldots, b_n) ^ T$ , $$$A$ Es una matriz en la que en la intersección $$$i$ cuerdas y $$$j$ columna es el valor
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$A$ resulta ser simétrico, esto es importante). Siguiente Al mencionar una función cuadrática, tendré la función anterior.

¿Por qué estoy hablando de esto? El hecho es que las funciones cuadráticas son importantes en la optimización por dos razones:

1. También ocurren en la práctica, por ejemplo, al construir una regresión lineal de mínimos cuadrados
2. El gradiente de una función cuadrática es una función lineal, en particular para la función anterior
   

   $$

   $$\ frac {\ partial} {\ partial x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i,$$
   
   O en forma de matriz
   

   $$

   $$\ nabla f (x) = Ax-b,$$
   
   Así el sistema $$$\ nabla f (x) = 0$ - sistema lineal. Un sistema que es más simple que lineal no existe. La idea a la que intentaba llegar es la optimización de una función cuadrática, la clase más simple de problemas de optimización . Por otro lado, el hecho de que $$$\ nabla f (x ^ *) = 0$ - las condiciones mínimas necesarias permiten resolver sistemas lineales mediante problemas de optimización. Un poco más tarde intentaré convencerte de que esto tiene sentido.
   

Propiedades útiles de gradiente

Bueno, parece que descubrimos que si una función es diferenciable (tiene derivadas con respecto a todas las variables), en el punto mínimo el gradiente debería ser igual a cero. ¿Pero el gradiente lleva alguna información útil cuando no es cero?

Intentemos resolver un problema más simple: el punto está dado $$$x$ encontrar punto $$$\ bar {x}$ tal que $$$f (\ bar {x}) <f (x)$ . Tomemos un punto al lado de $$$x$ de nuevo usando aproximación lineal $$$f (\ bar {x}) \ aprox. f (x) + \ nabla f (x) ^ T (\ bar {x} -x)$ . Si tomas $$$\ bar {x} = x- \ alpha \ nabla f (x)$ , $$$\ alpha> 0$ entonces tenemos

$$

$$f (\ bar {x}) \ aprox. f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x). $$$

Del mismo modo, si $$$\ alpha <0$ entonces $$$f (\ bar {x})$ sera mas $$$f (x)$ (en adelante $$$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~$ ) Nuevamente, dado que usamos la aproximación, estas consideraciones serán ciertas solo para pequeños $$$\ alpha$ . Para resumir lo anterior, si $$$\ nabla f (x) \ neq 0$ , entonces el gradiente indica la dirección del mayor aumento local en la función .

Aquí hay dos ejemplos para funciones bidimensionales. Imágenes de este tipo a menudo se pueden ver en demostraciones de descenso de gradiente. Las líneas de color son las llamadas líneas de nivel , este es un conjunto de puntos para los cuales la función toma valores fijos, en mi caso, estos son círculos y elipses. Marqué las líneas azules del nivel con un valor más bajo, rojo, con un valor más alto.



Tenga en cuenta que para una superficie definida por una ecuación de la forma $$$f (x) = c$ , $$$\ nabla f (x)$ establece lo normal (en personas comunes, lo perpendicular) a esta superficie. También tenga en cuenta que aunque el gradiente se muestra en la dirección del mayor aumento en la función, no hay garantía de que en la dirección opuesta al gradiente, pueda encontrar un mínimo (por ejemplo, la imagen de la izquierda).

Descenso de gradiente

Solo quedaba un pequeño paso para el método básico de descenso de gradiente: aprendimos desde el punto $$$x$ punto de conseguir $$$\ bar {x}$ con menor valor de función $$$f$ . ¿Qué nos impide repetir esto varias veces? De hecho, este es el descenso del gradiente: construimos la secuencia

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k). $$$

Valor $$$\ alpha_k$ llamado el tamaño del paso (en aprendizaje automático - la velocidad de aprendizaje ). Algunas palabras sobre la elección $$$\ alpha_k$ : si $$$\ alpha_k$ - muy pequeño, la secuencia cambia lentamente, lo que hace que el algoritmo no sea muy eficiente; si $$$\ alpha_k$ muy grande, entonces la aproximación lineal se vuelve pobre, y tal vez incluso incorrecta. En la práctica, el tamaño del paso a menudo se selecciona empíricamente; en teoría, generalmente se supone un gradiente de Lipschitz, es decir, si

$$

$$\ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | x-y \ | $$$

para todos $$$x, y$ entonces $$$\ alpha_k <\ frac {2} {L}$ garantías disminuyen $$$f (x_k)$ .

Análisis para funciones cuadráticas

Si $$$A$ Es una matriz invertible simétrica, $$$Ax ^ * = b$ entonces para la función cuadrática $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ punto $$$x ^ *$ es el punto mínimo ( UPD . siempre que este mínimo exista en absoluto - $$$f$ no se acerca $$$- \ infty$ valores solo si $$$A$ positivo definido), y para el método de descenso de gradiente podemos obtener lo siguiente

$$

$$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$$

$$

$$(x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_k A) (x_k-x ^ *),$$

donde $$$I$ Es la matriz de identidad, es decir $$$Ix = x$ para todos $$$x$ . Si $$$\ alpha_k \ equiv \ alpha$ resultará

$$

$$\ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |. $$$

La expresión de la izquierda es la distancia desde la aproximación obtenida en el paso $$$k$ Descenso de gradiente hasta el punto mínimo, a la derecha: una expresión de la forma $$$\ lambda ^ k \ beta$ que converge a cero si $$$| \ lambda | <1$ (la condición en la que escribí $$$\ alpha$ en el párrafo anterior, esto es exactamente lo que garantiza). Esta estimación básica asegura que el descenso del gradiente converja.

Modificaciones de descenso de gradiente

Ahora me gustaría hablar un poco sobre las modificaciones comúnmente utilizadas del descenso de gradiente, principalmente las llamadas

Métodos de gradiente inercial o acelerado

Todos los métodos de esta clase se expresan de la siguiente manera

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}). $$$

El último término caracteriza esta misma "inercia", el algoritmo en cada paso intenta moverse contra el gradiente, pero al mismo tiempo se mueve parcialmente por inercia en la misma dirección que en la iteración anterior. Dichos métodos tienen dos propiedades importantes:

1. Prácticamente no complican el descenso de gradiente habitual en el plan computacional.
2. Con una cuidadosa selección $$$\ alpha_k, \ beta_k$ tales métodos son un orden de magnitud más rápido que el descenso de gradiente ordinario incluso con un paso seleccionado de manera óptima.

Uno de los primeros métodos de este tipo apareció a mediados del siglo XX y se llamó método de bola pesada , que transmitía la naturaleza de la inercia del método: en este método $$$\ alpha_k, \ beta_k$ independiente de $$$k$ y cuidadosamente seleccionados según la función objetivo. Vale la pena señalar que $$$\ alpha_k$ puede ser cualquier cosa menos $$$\ beta_k$ - Por lo general, solo un poco menos de uno .

El método de bola pesada es el método de inercia más simple, pero no el primero. En este caso, en mi opinión, el primer método es bastante importante para comprender la esencia de estos métodos.

Método Chebyshev

Sí, sí, el primer método de este tipo fue inventado por Chebyshev para resolver sistemas de ecuaciones lineales. En algún momento del análisis del descenso de gradiente, se obtuvo la siguiente igualdad

$$

$$x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots =$$

$$

$$(I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *),$$

donde $$$P_k$ Es algún grado polinomial $$$k$ . ¿Por qué no intentas recoger? $$$\ alpha_k$ para que $$$P_k (A) (x_0-x ^ *)$ ¿Era más pequeño? Un nudo de polinomios universales que se desvían menos de cero es el polinomio de Chebyshev. El método de Chebyshev consiste esencialmente en seleccionar los parámetros de descenso para que $$$P_k$ fue un polinomio de Chebyshev. Realmente hay un pequeño problema: para un descenso de gradiente normal, esto simplemente no es posible. Sin embargo, para los métodos de inercia, esto es posible. Esto se debe principalmente al hecho de que los polinomios de Chebyshev satisfacen la relación de recurrencia de segundo orden

$$

$$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x),$$

por lo tanto, no se pueden construir para el descenso de gradiente, que calcula un nuevo valor a partir de un solo valor anterior, y para la inercia se hace posible debido al hecho de que se utilizan los dos valores anteriores. Resulta que la complejidad del cálculo $$$\ alpha_k, \ beta_k$ no depende de $$$k$ ni el tamaño del espacio $$$n$ .

Método de gradiente conjugado

Otro hecho muy interesante e importante (una consecuencia del teorema de Hamilton-Cayley): para cualquier matriz cuadrada $$$A$ el tamaño $$$n \ veces n$ hay un polinomio $$$P$ grado no más $$$n$ para que $$$P (A) = 0$ . ¿Por qué es esto interesante? Se trata de la misma igualdad

$$

$$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *). $$$

Si pudiéramos elegir el tamaño del paso en el descenso del gradiente de tal manera que se obtenga exactamente este polinomio de puesta a cero, entonces el descenso del gradiente convergería para un número de iteración fijo no mayor que la dimensión $$$A$ . Como ya descubrimos, no podemos hacer esto para el descenso de gradiente. Afortunadamente, para los métodos de inercia, podemos. La descripción y justificación del método es bastante técnica, me limitaré a la esencia: en cada iteración, se seleccionan parámetros que dan el mejor polinomio que se puede construir teniendo en cuenta todas las mediciones realizadas antes del paso actual de la medición de gradiente . Al mismo tiempo

1. Una iteración de descenso de gradiente (sin tener en cuenta los cálculos de parámetros) contiene una multiplicación de matriz por un vector y 2-3 adiciones de vectores
2. El cálculo de los parámetros también requiere una multiplicación de matriz 1-2 por vector, una multiplicación de vector escalar 2-3 por vector y varias adiciones de vectores.

Lo más difícil en el plan computacional es la multiplicación de la matriz por un vector, esto generalmente se hace a tiempo $$$\ mathcal {O} (n ^ 2)$ Sin embargo, para una implementación especial, esto se puede hacer en $$$\ mathcal {O} (m)$ donde $$$m$ - el número de elementos distintos de cero en $$$A$ . Dada la convergencia del método de gradiente conjugado, no más de $$$n$ las iteraciones obtienen la complejidad general del algoritmo $$$\ mathcal {O} (nm)$ , que en todos los casos no es peor $$$\ mathcal {O} (n ^ 3)$ para el método de Gauss o Cholesky, pero mucho mejor si $$$m << n ^ 2$ Eso no es tan raro.

El método de gradiente conjugado también funciona bien si $$$f$ no es una función cuadrática, pero no converge en un número finito de pasos y a menudo requiere pequeñas modificaciones adicionales

Método Nesterov

Para las comunidades de optimización matemática y aprendizaje automático, el nombre "Nesterov" ha sido durante mucho tiempo un nombre familiar. En los años 80 del siglo pasado, Yu.E. A Nesterov se le ocurrió una versión interesante del método de inercia, que tiene la forma

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}),$$

no implica ningún cálculo complicado $$$\ alpha_k, \ beta_k$ Como en el método de gradiente conjugado, en general, el comportamiento del método es similar al método de bola pesada, pero su convergencia suele ser mucho más confiable tanto en teoría como en la práctica.

Descenso de gradiente estocástico

La única diferencia formal del descenso de gradiente habitual es el uso de una función en lugar de un gradiente $$$g (x, \ theta)$ tal que $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ theta$ - expectativa al azar $$$\ theta$ ), entonces el descenso de gradiente estocástico tiene la forma

$$

$$x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k). $$$

$$$\ theta_k$ - Este es un parámetro aleatorio que no afectamos, pero al mismo tiempo, en promedio, vamos en contra del gradiente. Como ejemplo, considere las funciones

$$

$$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2, ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j)$$

y

$$

$$g (x, i) = x-y_i. $$$

Si $$$i$ toma valores $$$1, \ ldots, m$ igualmente probable solo promedio $$$g$ Es un gradiente $$$f$ . Este ejemplo también es indicativo de lo siguiente: la complejidad de calcular el gradiente en $$$m$ veces más que la complejidad computacional $$$g$ . Esto permite que el descenso de gradiente estocástico se realice al mismo tiempo en $$$m$ veces más iteraciones. A pesar de que el descenso de gradiente estocástico generalmente converge más lento de lo habitual, debido a un aumento tan grande en el número de iteraciones, es posible mejorar la tasa de convergencia por unidad de tiempo. Hasta donde yo sé, en este momento el descenso de gradiente estocástico es el método básico para entrenar la mayoría de las redes neuronales, implementado en todas las bibliotecas de ML principales: flujo de tensor, antorcha, caffe, CNTK, etc.

Vale la pena señalar que las ideas de métodos inerciales se utilizan para el descenso del gradiente estocástico y en la práctica a menudo dan un aumento, en teoría, generalmente se supone que la tasa de convergencia asintótica no cambia debido al hecho de que el error principal en el descenso del gradiente estocástico se debe a la dispersión $$$g$ .

Descenso de subgradiente

Esta variación le permite trabajar con funciones no diferenciables, lo describiré con más detalle. Nuevamente tendremos que recordar la aproximación lineal: el hecho es que hay una característica simple de convexidad a través de un gradiente, una función diferenciable $$$f$ convexo si y solo si $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ para todos $$$x, y$ . Resulta que una función convexa no tiene que ser diferenciable, pero para cualquier punto $$$x$ ciertamente hay tal vector $$$g$ eso $$$f (y) \ geq f (x) + g ^ T (y-x)$ para todos $$$y$ . Tal vector $$$g$ comúnmente llamado subgradiente $$$f$ en el punto $$$x$ , el conjunto de todos los subgradientes a puntos $$$x$ llamado subdiferencial $$$x$ y denotar $$$\ parcial f (x)$ (a pesar de la designación, no tiene nada que ver con derivadas parciales). En el caso unidimensional $$$g$ Es un número, y la propiedad anterior simplemente significa que el gráfico $$$f$ se encuentra sobre la línea que pasa $$$(x, f (x))$ y tener una pendiente $$$g$ (ver fotos a continuación). Observo que puede haber varios subgradientes para un punto, incluso un número infinito.



Por lo general, no es muy difícil calcular al menos un subgradiente para un punto; un descenso de subgradiente esencialmente usa un subgradiente en lugar de un gradiente. Resulta que esto es suficiente; en teoría, la tasa de convergencia disminuye, sin embargo, por ejemplo, en redes neuronales una función indiferenciable $$$ReLU (x) = \ max (0, x)$ les gusta usarlo solo porque el entrenamiento es más rápido (esto es, por cierto, un ejemplo de una función no convexa no diferenciable en la que el descenso del (sub) gradiente se aplica con éxito. $$$Relu$ red neuronal convexa pero de varias capas que contiene $$$Relu$ , no convexo y no diferenciable). Como ejemplo, para una función $$$f (x) = | x |$ subdifferencial se calcula de manera muy simple

$$

$$\ partial f (x) = \ begin {cases} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0. \ end {cases}$$

Quizás lo último importante que se debe saber es que el descenso del subdegradado no converge a un tamaño de paso constante . Esto es más fácil de ver para la función anterior. $$$f (x) = | x |$ . Incluso la ausencia de una derivada en un punto rompe la convergencia:

1. Digamos que comenzamos desde el punto $$$x_0$ .
2. Paso de descenso del subdegradado:
   

   $$

   $$x_ {k + 1} = \ begin {cases} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0. \ end {cases}$$
3. Si $$$x_0> 0$ entonces los primeros pasos restaremos uno, si $$$x_0 <0$ luego agregue. De una forma u otra, en algún momento nos encontraremos en el intervalo $$$[0, 1)$ de donde llegamos a $$$[- 1, 0)$ , y luego saltaremos entre dos puntos de estos intervalos.

En teoría, para el descenso de gradiente secundario, se recomienda tomar una secuencia de pasos

$$

$$\ alpha_k = \ frac {1} {(k + 1) ^ c}. $$$

Donde $$$c$ por lo general $$$1$ o $$$\ frac {1} {2}$ . En la práctica, a menudo veía pasos exitosos. $$$\ alpha_k = e ^ {- ck}$ , aunque para tales pasos en general no habrá convergencia.

Métodos proximales

Desafortunadamente, no conozco una buena traducción para "proximal" en el contexto de la optimización, por eso llamaré a este método. Los métodos proximales aparecieron como una generalización de los métodos de gradiente proyectivo. La idea es muy simple: si hay una función $$$f$ representado como una suma $$$f (x) = \ varphi (x) + h (x)$ donde $$$\ varphi$ Es una función convexa diferenciable, y $$$h (x)$ - convexo, para el cual hay un operador proximal especial $$$prox_h (x)$ (en este artículo me limitaré solo a ejemplos, no describiré en términos generales), luego las propiedades de convergencia del descenso de gradiente para $$$\ varphi$ permanecer y para el descenso de gradiente para $$$f$ si después de cada iteración aplica este operador proximal para el punto actual $$$x_k$ En otras palabras, la forma general del método proximal se ve así:

$$

$$x_ {k + 1} = prox _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k))$$

Creo que hasta ahora es completamente incomprensible por qué esto puede ser necesario, especialmente teniendo en cuenta que no expliqué qué es un operador proximal. Aquí hay dos ejemplos:

1. $$$h (x)$ - función indicadora de un conjunto convexo $$$\ mathcal {K}$ eso es
   

   $$

   $$h (x) = \ begin {cases} 0, & x \ in \ mathcal {K}, \\ + \ infty, & x \ notin \ mathcal {K}. \\ \ end {cases}$$
   
   En este caso $$$prox _ {\ alpha_kh} (x)$ Es una proyección en el set $$$\ mathcal {K}$ es decir, "más cercano a $$$x$ punto de ajuste $$$\ mathcal {K}$ ". Por lo tanto, restringimos el descenso del gradiente solo al conjunto $$$\ mathcal {K}$ , lo que nos permite resolver problemas con restricciones. Desafortunadamente, calcular la proyección en el caso general puede ser aún más difícil, por lo que este método generalmente se usa si las restricciones son simples, por ejemplo, las llamadas restricciones de caja: para cada coordenada
   

   $$

   $$l_i \ leq x_i \ leq r_i$$
   
   
2. $$$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ - $$$\ ell_1$ -regularización. Les gusta agregar este término a los problemas de optimización en el aprendizaje automático para evitar el reentrenamiento. La regularización de este tipo también tiende a anular los componentes menos significativos. Para tal función, el operador proximal tiene la forma (a continuación se describe una expresión para una sola coordenada):
   

   $$

   $$[prox _ {\ alpha h} (x)] _ i = \ begin {cases} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, & x_i <- \ alpha, \\ 0, & x_i \ en [- \ alpha, \ alpha], \ end {cases}$$
   
   lo cual es bastante fácil de calcular.

Conclusión

Esto pone fin a las principales variaciones del método de gradiente conocido por mí. Quizás al final quisiera señalar que todas estas modificaciones (excepto quizás el método de gradiente conjugado) pueden interactuar fácilmente entre sí. Deliberadamente no incluí el método de Newton y los métodos cuasi-Newton (BFGS y otros) en esta lista: aunque usan un gradiente, son métodos más complejos y requieren cálculos adicionales específicos, que generalmente son más costosos computacionalmente que calcular un gradiente. Sin embargo, si este texto tiene demanda, me complacerá hacer una revisión similar sobre ellos.

Literatura usada / recomendada

Boyd S, Vandenberghe L. Optimización convexa
Shewchuk JR Una introducción al método de gradiente conjugado sin el dolor agonizante
Teoría de optimización convexa de Bertsekas DP

Nesterov Yu. E. Métodos de optimización convexa
Gasnikov A.V. Descenso de gradiente universal