A Slow-Fast Stochastic Framework for Zeroth-Order Distributed Time-Varying Optimization

Sintesi Tecnica: Un Framework Stocastico Slow-Fast per l'Ottimizzazione Distribuita Tempo-Variante di Ordine Zero

Formulazione del Problema
Questo articolo affronta la sfida dell'ottimizzazione distribuita tempo-variante per Sistemi Multi-Agente Stocastici (SMAS) sotto vincoli di informazione di ordine zero. A differenza dell'ottimizzazione statica, l'obiettivo qui consiste nel tracciare una traiettoria ottimale globale tempo-variante dove le funzioni di costo locali evolvono continuamente. Il sistema opera sotto vincoli significativi:

1. Informazione di Ordine Zero: Gli agenti non hanno accesso alle informazioni esatte del gradiente; sono disponibili solo i valori della funzione.
2. Stocasticità: Il sistema è soggetto a disturbi ambientali, rumori di comunicazione e perturbazioni esterne casuali modellate tramite equazioni differenziali stocastiche (SDE).
3. Vincoli di Consenso: Gli agenti devono cooperare per tracciare la traiettoria ottimale mantenendo al contempo un consenso rilassato (consenso distorto) a causa dell'impossibilità intrinseca di mantenere un consenso stretto in presenza di moto browniano.

I metodi esistenti spesso si affidano a gradienti di primo ordine o framework a tempo discreto, che non riescono a catturare l'evoluzione continua dei processi fisici (ad esempio, coordinamento di robot multipli, sciami di UAV) o sono inapplicabili quando i gradienti non sono disponibili.

Metodologia
Gli autori propongono un nuovo Framework Stocastico Slow-Fast basato sulla teoria della perturbazione singolare stocastica. L'innovazione centrale è la costruzione di un sistema a due scale temporali:

1. Sottosistema Fast (Stima del Gradiente): Viene introdotta una variabile veloce ausiliaria $g_i$ per ogni agente. Questo sottosistema agisce come uno stimatore del gradiente fluido. Utilizza un metodo di stima del gradiente a due punti con perturbazioni coordinate-wise per generare una stima del gradiente stocastico istantaneo. La dinamica veloce è progettata per tracciare e smorzare rapidamente queste stime, agendo efficacemente come un filtro passa-basso adattivo contro il rumore e il bias di stima.
2. Sottosistema Slow (Ottimizzazione e Consenso): Lo stato dell'agente $x_i$ evolve come il sottosistema lento. La sua dinamica è guidata dalle stime del gradiente smorzate dal sottosistema veloce, combinate con protocolli di consenso che coinvolgono interazioni tra vicini (utilizzando funzioni lineari e non lineari di tipo signum).
3. Analisi Teorica: L'analisi impiega tecniche di perturbazione singolare stocastica per disaccoppiare il sistema. Gli autori costruiscono un "sistema ridotto" (R-SMASs) in cui la variabile veloce è sostituita dal suo valore di quasi-stato stazionario. Utilizzando la teoria di Lyapunov stocastica, dimostrano che l'originale sistema slow-fast approssima il sistema ridotto con un limite di errore dipendente dal parametro di perturbazione $\epsilon$.

Contributi Chiave

• Framework Unificato: L'articolo formula un problema di ottimizzazione distribuita di ordine zero che unifica obiettivi tempo-varianti, strutture informative prive di gradiente e dinamiche multi-agente stocastiche all'interno di un framework in tempo continuo.
• Accoppiamento Slow-Fast Innovativo: È progettata un'architettura di sistema nuova in cui uno stimatore del gradiente fluido ausiliario (sottosistema veloce) fornisce stime del gradiente robuste e in tempo reale per l'evoluzione dello stato (sottosistema lento). Ciò separa le scale temporali di stima e ottimizzazione.
• Analisi della Perturbazione Singolare Stocastica: Gli autori stabiliscono un rigoroso framework di analisi dimostrando che lo stimatore ausiliario raggiunge il tracciamento esponenziale del gradiente stocastico istantaneo. Derivano una relazione approssimativa tra il sistema completo slow-fast e il sistema ridotto, mostrando che l'errore di approssimazione svanisce quando $\epsilon \to 0$.
• Garanzie di Convergenza: L'articolo stabilisce che il sistema raggiunge un Consenso a Tempo Fisso Pratico (Pfxc) in probabilità e un Tracciamento del Traiettoria Ottimale Tempo-Variante Globalmente Esponenzialmente Limitatamente Finale in Media (MS-GEUB). Vengono forniti limiti espliciti per caratterizzare gli effetti dei parametri di progettazione, dei disturbi stocastici e delle proprietà della funzione obiettivo sulla prestazione.

Risultati
I risultati teorici dimostrano che, nonostante le perturbazioni stocastiche e gli errori di stima del gradiente:

• Il sottosistema veloce converge rapidamente alle stime del gradiente stocastico istantaneo.
• Il sottosistema lento raggiunge il consenso in probabilità entro un tempo fisso (tempo di assestamento con valore atteso limitato).
• Gli stati degli agenti tracciano asintoticamente la traiettoria ottimale tempo-variante con un errore limitato.
• L'errore di tracciamento e l'errore di consenso sono esplicitamente limitati da funzioni del parametro di perturbazione $\epsilon$, dell'intensità del rumore e del bias della stima del gradiente.

Simulazioni numeriche che coinvolgono 10 agenti che tracciano una traiettoria ottimale sinusoidale validano questi risultati teorici. I risultati mostrano che gli agenti raggiungono il consenso e tracciano la traiettoria ottimale con errori significativamente inferiori ai loro limiti superiori teorici, confermando l'efficacia dello schema proposto.

Significatività
L'articolo sostiene di fornire una base teorica sistematica per l'ottimizzazione distribuita di ordine zero in ambienti stocastici. Utilizzando la modellazione in tempo continuo e l'analisi della perturbazione singolare, rivela la dinamica interna degli algoritmi di ottimizzazione che i modelli a tempo discreto potrebbero oscurare. Il framework proposto consente l'applicazione di metodi della teoria dei sistemi dinamici e del controllo per risolvere problemi di ottimizzazione complessi dove l'informazione del gradiente non è disponibile e l'incertezza è prevalente. Il lavoro suggerisce che la ricerca futura potrebbe concentrarsi su meccanismi di tempo scala adattivi, ottimizzazione non convessa e architetture basate sull'apprendimento, ma il contributo attuale è l'instaurazione del fondamentale framework stocastico slow-fast e delle sue proprietà di convergenza.