Come eseguire l'algoritmo di discesa del gradiente quando lo spazio dei parametri è limitato?

Question

Mi piacerebbe massimizzare una funzione con un parametro.

Allora corro discesa del gradiente (o, salita in realtà): Parto da un parametro iniziale e continuare ad aggiungere il gradiente (volte qualche fattore tasso di apprendimento che diventa sempre più piccola), rivalutare il gradiente dato il nuovo parametro, e così via fino alla convergenza.

Ma c'è un problema: il mio parametro deve rimanere positivo, quindi non dovrebbe diventare < = 0 perché la mia funzione non sarà definita. La mia ricerca con gradiente a volte andrà in tali regioni (quando è stato positivo, il gradiente ha detto di andare un po 'più in basso e ha superato).

E per peggiorare le cose, il gradiente in tale punto potrebbe essere negativo, spingendo la ricerca verso valori di parametri ancora più negativi. (La ragione è che la funzione obiettivo contiene log, ma il gradiente no.)

Quali sono alcuni algoritmi buoni (semplici) che gestiscono questo problema di ottimizzazione vincolata? Spero solo una semplice correzione al mio algoritmo. O forse ignori il gradiente e fai qualche tipo di ricerca di linee per il parametro ottimale?

Answer 1

Senza saperne di più sul tuo problema, è difficile dare consigli specifici. L'algoritmo di salita del gradiente potrebbe non essere particolarmente adatto al tuo spazio funzionale. Tuttavia, dato che è quello che hai, ecco un tweak che potrebbe aiutare.

Stai seguendo ciò che credi sia un gradiente ascendente. Ma quando ti muovi in ​​avanti nella direzione del gradiente, scopri di essere caduto in una fossa di valore negativo. Ciò implica che ci fosse un massimo locale vicino, ma anche un picco di gradiente negativo molto pronunciato. L'ovvia soluzione è tornare indietro alla posizione precedente e fare un passo più piccolo (ad esempio metà delle dimensioni). Se cadi ancora, ripeti con un passo ancora più piccolo. Questo itererà fino a trovare il massimo locale sul bordo della scogliera.

Il problema è che non esiste alcuna garanzia che il proprio massimo locale sia effettivamente globale (a meno che non si conosca meglio la propria funzione di quella che si sta condividendo). Questo è il limite principale dell'innalzamento graduale naive - si risolve sempre sul primo massimo locale e converge ad esso. Se non si desidera passare a un algoritmo più robusto, un approccio semplice che potrebbe aiutare è quello di eseguire n iterazioni del codice, partendo ogni volta da posizioni casuali nella funzione di spazio, e mantenere i migliori massima a trovare complessiva . Questo approccio Monte Carlo aumenta le probabilità che inciampi sul massimo globale, al costo di aumentare il tempo di esecuzione di un fattore n. Quanto sarà efficace dipenderà dal "malumore" della funzione obiettivo.

Answer 2

Un semplice trucco per restringere un parametro è la riprogrammazione del problema in termini di logaritmo (assicurarsi di modificare il gradiente in modo appropriato). Naturalmente è possibile che le mosse ottimali per -infettare con questa trasformazione, e la ricerca non converga.

Answer 3

1. Ogni volta che si aggiorna il parametro, controllare se è negativo e, se lo è, bloccarlo a zero.
2. Se il blocco a zero non è accettabile, provare ad aggiungere una "barriera di registro" (Google it). Fondamentalmente, aggiunge una parete liscia "morbida" alla funzione obiettivo (e modifica la sfumatura) per tenerlo lontano dalle regioni in cui non vuoi che vada. Quindi esegui ripetutamente l'ottimizzazione indurendo il muro per renderlo più infinitamente verticale, ma a partire dalla soluzione trovata in precedenza.Nel limite (in pratica sono necessarie solo alcune iterazioni), il problema che si sta risolvendo è identico al problema originale con un vincolo difficile.

Answer 4

Ad ogni passaggio, il parametro deve essere positivo. Questo è (in breve) il metodo di sfumatura proiettata di cui potresti voler parlare su Google.

Answer 5

Ho tre suggerimenti, in ordine di quanto pensiero e lavoro si vuole fare.

Per prima cosa, in discesa/salita del gradiente, si sposta ogni volta il gradiente per un fattore, a cui si fa riferimento come "fattore di velocità di apprendimento". Se, come descrivi, questa mossa fa sì che x diventi negativo, ci sono due interpretazioni naturali: o il gradiente era troppo grande, o il fattore del tasso di apprendimento era troppo grande. Dal momento che non puoi controllare il gradiente, prendi la seconda interpretazione. Controlla se la tua mossa farà sì che x diventi negativo, e in tal caso, taglia il fattore di velocità di apprendimento a metà e riprova.

In secondo luogo, per elaborare la risposta di Aniko, sia x il tuo parametro e f (x) sia la tua funzione. Quindi definire una nuova funzione g (x) = f (e^x), e notare che sebbene il dominio di f sia (0, infinito), il dominio di g è (-infinità, infinito). Quindi g non può soffrire i problemi che soffre. Usa la discesa del gradiente per trovare il valore x_0 che massimizza g. Quindi e^(x_0), che è positivo, massimizza f. Per applicare la discesa del gradiente su g, hai bisogno della sua derivata, che è f '(e^x) * e^x, secondo la regola della catena.

In terzo luogo, sembra che si stia tentando di massimizzare una sola funzione, non di scrivere una routine di massimizzazione generale. Potresti considerare la discesa del gradiente di scaffalatura e personalizzare il metodo di ottimizzazione alle idiosincrasie della tua funzione specifica. Dovremmo sapere molto di più sul comportamento previsto di f per aiutarti a farlo.

Answer 6

Stai ottenendo buone risposte qui. Reparameterizing è quello che vorrei raccomandare. Inoltre, hai considerato un altro metodo di ricerca, come Metropolis-Hastings? In realtà è abbastanza semplice una volta che ti fai strada attraverso la matematica dall'aspetto spaventoso, e ti dà errori standard e anche un ottimo.

Answer 7

Basta usare Brent's method for minimization. È stabile e veloce e la cosa giusta da fare se si dispone di un solo parametro. È ciò che usa la funzione Roptimize. Il collegamento contiene anche una semplice implementazione in C++. E sì, puoi dargli limiti di valori dei parametri MIN e MAX.