¿Cómo ejecutar el algoritmo de descenso de gradiente cuando el espacio de parámetro está restringido?

Question

Me gustaría maximizar una función con un parámetro.

Así que ejecuto el descenso del gradiente (o, en realidad, el ascenso): comienzo con un parámetro inicial y sigo agregando el gradiente (multiplicado por el factor de velocidad de aprendizaje que se vuelve cada vez más pequeño), reevalúa el gradiente dado el nuevo parámetro, y así sucesivamente hasta la convergencia.

Pero hay un problema: Mi parámetro debe permanecer positivo, por lo que no debe convertirse en < = 0 porque mi función no estará definida. Sin embargo, a veces mi búsqueda de degradado entra en dichas regiones (cuando era positiva, el gradiente indicaba que bajaba un poco y se rebasaba).

Y para empeorar las cosas, el gradiente en ese punto podría ser negativo, llevando la búsqueda hacia valores de parámetros aún más negativos. (La razón es que la función objetivo contiene registros, pero el gradiente no).

¿Cuáles son algunos algoritmos buenos (simples) que se ocupan de este problema de optimización restringida? Estoy esperando una solución simple a mi algoritmo. O tal vez ignorar el gradiente y hacer algún tipo de búsqueda de línea para el parámetro óptimo?

Answer 1

Sin saber más acerca de su problema, es difícil dar consejos específicos. Su algoritmo de ascenso de gradiente puede no ser particularmente adecuado para su espacio de función. Sin embargo, dado que eso es lo que tienes, aquí hay un truco que ayudaría.

Estás siguiendo lo que crees que es un gradiente ascendente. Pero cuando te mueves hacia adelante en la dirección del gradiente, descubres que has caído en un pozo de valor negativo. Esto implica que había un máximo local cercano, pero también un acantilado de gradiente negativo muy agudo. La solución obvia es retroceder a su posición anterior y dar un paso más pequeño (por ejemplo, la mitad del tamaño). Si aún te caes, repite con un paso aún más pequeño. Esto se repetirá hasta que encuentre el máximo local en el borde del acantilado.

El problema es que no hay garantía de que su máximo local sea global (a menos que sepa más acerca de su función que la que está compartiendo). Esta es la principal limitación del ascenso ingenuo del gradiente: siempre se fija en el primer máximo local y converge hacia él. Si no desea cambiar a un algoritmo más robusto, un enfoque simple que podría ayudar es ejecutar n iteraciones de su código, comenzando cada vez desde posiciones aleatorias en el espacio de funciones, y manteniendo el mejor máximo que encuentre en general . Este enfoque de Monte Carlo aumenta las posibilidades de que te tropieces con el máximo global, a costa de aumentar tu tiempo de ejecución por un factor n. La efectividad de esto dependerá de la "irregularidad" de su función objetivo.

Answer 2

Un truco simple para restringir que un parámetro sea positivo es volver a parametrizar el problema en términos de su logaritmo (asegúrese de cambiar el gradiente de forma apropiada). Por supuesto, es posible que el óptimo se mueva a -inquieto con esta transformación, y la búsqueda no converja.

Answer 3

1. Cada vez que actualice su parámetro, verifique si es negativo, y si lo está, sujételo a cero.
2. Si la sujeción a cero no es aceptable, intente agregar una "barrera de registro" (Google it). Básicamente, agrega una pared lisa "suave" a su función objetivo (y modifica su gradiente) para mantenerla alejada de las regiones a las que no desea que vaya. A continuación, ejecute la optimización varias veces endureciendo la pared para que sea más infinitamente vertical, pero comenzando con la solución encontrada previamente.En el límite (en la práctica solo se necesitan unas pocas iteraciones), el problema que está resolviendo es idéntico al problema original con una restricción estricta.

Answer 4

En cada paso, limite el parámetro para que sea positivo. Este es (en resumen) el método de gradiente proyectado que puede querer googlear.

Answer 5

Tengo tres sugerencias, en orden de cuánto pensamiento y trabajo desea hacer.

En primer lugar, en gradiente de descenso/ascenso, se mueve cada vez por el gradiente multiplicado por un factor, al que se refiere como un "factor de velocidad de aprendizaje". Si, como describes, este movimiento hace que x se vuelva negativo, hay dos interpretaciones naturales: o el gradiente era demasiado grande o el factor de velocidad de aprendizaje era demasiado grande. Como no puedes controlar el degradado, toma la segunda interpretación. Comprueba si tu movimiento hará que x se vuelva negativo, y si es así, reduce el factor de velocidad de aprendizaje a la mitad y vuelve a intentarlo.

En segundo lugar, para explicar la respuesta de Aniko, sea x su parámetro yf (x) sea su función. Luego defina una nueva función g (x) = f (e^x), y note que aunque el dominio de f es (0, infinito), el dominio de g es (-infinito, infinito). Entonces g no puede sufrir los problemas que sufre. Usa gradiente descendente para encontrar el valor x_0 que maximiza g. Entonces e^(x_0), que es positivo, maximiza f. Para aplicar el descenso de gradiente en g, necesita su derivada, que es f '(e^x) * e^x, según la regla de la cadena.

En tercer lugar, parece que intentas maximizar solo una función, no escribir una rutina general de maximización. Podría considerar dejar de lado el descenso de degradado y adaptar el método de optimización a la idiosincrasia de su función específica. Tendríamos que saber mucho más sobre el comportamiento esperado de f para ayudarte a hacer eso.

Answer 6

Estás recibiendo buenas respuestas aquí. Reparametrizar es lo que recomendaría. Además, ¿ha considerado otro método de búsqueda, como Metropolis-Hastings? En realidad, es bastante simple una vez que pasas por las matemáticas de aspecto aterrador, y te da errores estándar y óptimos.

Answer 7

Simplemente use Brent's method for minimization. Es estable y rápido, y es lo correcto si tiene solo un parámetro. Es lo que usa la función Roptimize. El enlace también contiene una implementación simple de C++. Y sí, puede otorgarle límites de valores de parámetros MIN y MAX.