¿Algoritmo de optimización Dimensional alta?

Question

Tengo un problema de optimización que al principio suena bastante libro de texto. Tengo un convexo de la función objetivo en $D$-dimensiones del espacio que es dos veces diferenciable en todas partes y no tiene local optima.

Normalmente sería un candidato perfecto para el numérico de Newton-Raphson métodos. Sin embargo, Newton-Raphson requiere resolver un sistema de ecuaciones lineales de tamaño $D$. Esto se lleva a $O(D^3)$ cálculos, al menos con cualquier razonablemente posibles de implementar el algoritmo soy consciente de. En mi caso $D$ está en el orden de varios miles. Puede alguien sugerir un algoritmo de optimización que normalmente es más eficaz que el de Newton-Raphson para $D$ este grande? Traté de gradiente de la pendiente, pero empíricamente se parecía absurdamente lento para converger.

Answer 1

¿Conoces gradientes conjugados? (http://en.wikipedia.org/wiki/Conjugate_gradient_method) Hice mucho trabajo con eso método de tiempo atrás; Si tienes preguntas sobre dude en preguntar.

Answer 2

Incluso si su matriz es de orden de varios miles, una resolución lineal debe estar bastante rápido, y métodos de Newton no requieren muchas iteraciones. Si la matriz es escasa o estructura especial, será aún más rápido. Mi Matlab resuelve un sistema de 2000 de rango en 3 segundos. Si usted necesita incluso más velocidad, puede tratar de resolver el sistema sólo aproximadamente utilizando un método iterativo con algunos número fijo de pasos (entonces se convierte en $O(D^2)$ y ver si todavía converge la iteración del neutonio.

Answer 3

¿Por qué el método de BFGS? Se comporta asintóticamente como método de Newton, pero construye el Hessian implícitamente sin resolver las ecuaciones de cualquier.