Te traemos el resultado a este atolladero, al menos eso creemos. Si sigues con inquietudes coméntalo, para nosotros será un gusto responderte
Solución:
Dado que estamos tratando con el cálculo de números reales, no podemos usar la máquina de Turing tradicional para el análisis de complejidad. Siempre habrá algo de $epsilon$s al acecho allí.
Dicho esto, al analizar los algoritmos de optimización, existen varios enfoques:
- Contar el número de operaciones de punto flotante
- Complejidad basada en la información (el llamado modelo Oracle)
- Análisis local asintótico (análisis de la tasa de convergencia cerca un óptimo)
Un modelo muy popular y, de hecho, muy útil es el enfoque 2: Complejidad basada en la información. Esto, es probablemente lo más cercano a lo que tienes en mente, y comienza con el trabajo pionero de Nemirovksii y Yudin.
La complejidad depende de la estructura de la función convexa: los gradientes continuos de Lipschitz ayudan, la convexidad fuerte ayuda, cierta estructura de punto de silla ayuda, etc. Incluso si su función convexa no es diferenciable, dependiendo de su estructura, existen diferentes resultados, y algunos de estos se pueden perseguir comenzando con la “Minimización suave de funciones no suaves” de Nesterov citada por Brian en su respuesta.
Pero en aras de la claridad, ilustro a continuación el límite superior más simple de la complejidad (basada en información) del descenso de gradiente. Esta complejidad es peor que el límite inferior (existen métodos óptimos que logran esto). En cualquier caso, las referencias citadas le ayudarán a estudiar este tema con mucho más detalle.
Ejemplo concreto
En resumen, en el modelo de complejidad informacional, se asume el acceso a una oráculo que dado un vector de entrada $x$, genera los valores objetivo y de gradiente $(f(x), nabla f(x))$. Luego, la complejidad de un algoritmo de optimización convexo se mide en términos de cuántas llamadas al oráculo hace un algoritmo para poder obtener una solución precisa de $epsilon$ (por ejemplo, en términos de valor objetivo, norma de gradiente o distancia al óptimo).
Supongamos que $f$ es una función convexa $C^1$ definida sobre los reales y deseamos resolver el problema de optimización sin restricciones beginequation* min_xquad f(x) endequation*
Supongamos que resolvemos el problema anterior usando el descenso de gradiente iteración
beginecuación* x^k+1 = x^k – alpha_knabla f(x^k),quad k=0,1,ldots. endecuación*
$nuevocomandorealesmathbbR$
Teorema. (Nésterov) Sea $f$ como arriba, y tenga un gradiente continuo de Lipschitz con constante $L > 0$. Sea $alpha_k = 1/L$. Sea $x^*$ una solución óptima al problema anterior. Defina el diámetro $D:=|x_0-x^*|$. Entonces, las iteraciones $(x^k)$ producidas por el gradiente-descenso satisfacen
$$ f(x^k) – f(x^*) le frac2LD^2k+4. $$
Como corolario, vemos que el descenso de gradiente requiere $O(1/epsilon)$ llamadas al oráculo para obtener una solución de $epsilon$-exactitud (es decir, para asegurar que $f(x^k)-f( x^*) le epsilon$).
También existen límites inferiores (p. ej., $O(1/sqrtepsilon)$ para la clase anterior) en la cantidad de llamadas de Oracle y métodos como el método de gradiente óptimo de Nesterov que realmente logran el límite inferior.
De manera más general, varios otros casos especializados de complejidad basada en la información dependen de las diferentes suposiciones que uno hace sobre el oráculo (estocástico, determinista, disperso) y la función (fuertemente convexa, no suave, etc.). Por favor, eche un vistazo a las referencias citadas a continuación para obtener más información.
Referencias.
-
Nemirovsky, AS y Yudin, DB 1983. Complejidad del problema y eficiencia del método en la optimización. Wiley-Interscience. Traducido por: E.~R.~Dawson.
-
Nésterov, Yu. 2004. Conferencias introductorias sobre optimización convexa: un curso básico
Kluwer Académico (ahora Springer).
Algunos libros para comenzar con la lectura de fondo incluirían:
Y. Nesterov, Conferencias introductorias sobre optimización convexa: un curso básico, Springer, 2003.
Y. Nesterov y A. Nemirovsky, Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SIAM, 1993. (Realmente solo sobre la complejidad computacional de los problemas de optimización cónica, particularmente LP, SOCP y SDP).
Stephen Vavasis, Optimización no lineal: problemas de complejidad, Oxford University Press, 1991.
Un artículo seminal es
Y. Nésterov. Minimización suave de funciones no suaves Programación matemática 103: 127-152. 2005.
En el análisis de métodos de descenso de subgradiente para problemas de optimización convexa, el enfoque normal es analizar el número de iteraciones para obtener el valor de la función objetivo dentro de $epsilon$ del valor óptimo (esto no es lo mismo que encontrar una solución dentro de $ epsilon$ de la solución óptima!) El key los resultados son que para un problema suave con gradiente continuo de Lipschitz con la constante de Lipschitz $L$, esto se puede hacer en $O(sqrtL/epsilon)$ iteraciones (por ejemplo, usando un algoritmo publicado por Nesterov en un artículo de 1983 ), y que para problemas no suaves, se requieren $O(1/epsilon^2)$ iteraciones, y este es en general el mejor límite posible. Hay contraejemplos explícitos que muestran que no puedes hacerlo mejor.
Sin embargo, Nesterov muestra cómo en muchos casos es posible suavizar un problema no suave y luego aplicar un método óptimo al problema suavizado para obtener una solución óptima $epsilon$ al problema original no suave en $O(1/epsilon)$ tiempo. Hacer esto requiere que el problema tenga alguna estructura específica que pueda explotarse para producir un problema suave con un gradiente continuo de Lipschitz y una constante de Lipschitz tal que el método óptimo para el problema suavizado tome $O(1/epsilon)$ iteraciones. Nesterov da varios ejemplos de este proceso en el artículo de 2005.
Este trabajo teórico llegó justo en el momento en que crecía el interés en los problemas de detección de compresión (que son problemas de optimización convexos no suaves con estructura especial). En particular, muchas personas están interesadas en resolver problemas de gran escala de la forma
$ min | Hacha – b |^2_2 + lambda | x |_1 $
Las ideas de Nesterov son ciertamente aplicables en este contexto, pero no todos los métodos prácticos para estos problemas siguen este enfoque.
No está claro por qué está preguntando sobre esto, y hay mucha investigación en curso en esta área. Lo más probable es que una pregunta más específica produzca una respuesta mucho más informativa.