¿Cómo elegir el algoritmo de optimización adecuado?

Question

Necesito encontrar el mínimo de una función. Leyendo la documentación en http://docs.scipy.org/doc/scipy/reference/optimize.html Veo que hay varios algoritmos que hacen lo mismo, es decir, encontrar el mínimo. Cómo sé cuál debo elegir?

algunos de los algoritmos enumerados

• Minimizar una función mediante el algoritmo simplex descendente.
• Minimizar una función utilizando el algoritmo BFGS.
• Minimizar una función con el algoritmo de gradiente conjugado no lineal.
• Minimizar la función f mediante el método Newton-CG.
• Minimizar una función utilizando el método de Powell modificado.

Mi función es lineal. dimensionalidad es de alrededor de 232750 (este es el número de gradientes diferentes que tengo que calcular cada vez), se tarda unos 2 minutos para calcular el gradiente y el costo de una vez, así que no es barato. No creo que tengo restricciones. es determinista y continua.

Answer 1

Basándome en lo que has dicho: Asumo que tienes que optimizar para 50 variables; también asumo que te encuentras en una situación en la que es muy costoso encontrar derivadas analíticas (no digamos ya sacar numéricas) y que tu optimización no tiene restricciones.

Permíteme subrayar que tienes un poco de mala suerte porque entre 25-30 y 100 variables es un poco la zona de penumbra cuando se trata de elegir entre rutinas de optimización a gran o pequeña escala. Dicho esto, nada está perdido.

Teniendo en cuenta que incluso las derivadas de primer orden son caras de obtener, eso acaba con la idea del método de Newton. Es posible que tengas algo de suerte con Quasi-Newton (BFGS), aunque si su Hessian es ligeramente diagonal como para empezar. C-G suele ser un poco más lento que BFGS por lo que probablemente no mejorará mucho las cosas; utilízalo si la memoria también es un problema (o simplemente utiliza L-BFGS en ese caso). Además, teniendo en cuenta lo lento que es evaluar tu función, un simple algoritmo de búsqueda de línea/descenso más pronunciado sería tortuosamente lento; lo mismo ocurre con Simulated Annealing y otras variantes de búsqueda aleatoria (supongo que no tienes acceso a HMC y todo ese jazz).

Así pues, cuando necesite la mejor relación calidad-precio en lo que respecta a la evaluación de una única función: Vaya con el método de Powell y también pruebe COBYLA; a pesar de ser un algoritmo de optimización restringido porque internamente aproximará linealmente el gradiente de su función para acelerar las cosas, será capaz de aprovechar la linealidad de su función. También definitivamente pruebe NLopt para Python . Tienen muchos optimizadores sin gradiente; pruebe UOBYQA; también es obra de Powell (Unconstrained Optimization BY Quadratic Approximations).

Muy brevemente : Los algoritmos N-CG dependen del cálculo del hessiano, y tu hessiano parece muy caro de calcular. Los algoritmos NLCG y BFGS no lo requieren, aunque podrían intentar calcularlo una vez en su primer paso.

He omitido el algoritmo simplex a propósito porque es una bestia totalmente diferente; nada que ver con los gradientes como tales. Pruébalo, pero no puedo opinar; depende mucho de la naturaleza de tu problema.

Para una primera buena referencia sobre optimización numérica, el libro de C.T.Kelly Métodos iterativos de optimización te llevará bastante lejos, bastante bien.

Answer 2

Quizá deberías comprarte un libro de introducción a la optimización numérica. Tendrás que tener en cuenta tu función para decidirte por el algoritmo.

Entre los algoritmos que menciona, las diferencias importantes son si el jacobiano o el hessiano o sólo la propia función.

Teniendo en cuenta que se trata de un estadísticas Q&A y, por tanto, trata con variables aleatorias: asegúrese de que su función es determinista puede evaluarse de forma que arroje resultados continuos sobre el espacio de búsqueda.