A condensing approach for linear-quadratic optimization with geometric constraints

1. Il Problema

Il lavoro si concentra su una classe di problemi di ottimizzazione a dimensione finita che combinano un costo quadratico convesso con vincoli geometrici, potenzialmente non convessi. La formulazione generale è:

$$\begin{aligned} & \underset{x}{\text{minimizzare}} & & f(x) := \frac{1}{2}\langle x, Qx\rangle + \langle q, x\rangle \\ & \text{soggetto a} & & Ax \in C \end{aligned}$$

Dove:

• $x \in \mathbb{R}^n$ sono le variabili decisionali.
• $f(x)$ è una funzione quadratica convessa definita da una matrice simmetrica $Q$ e un vettore $q$.
• $A \in \mathbb{R}^{m \times n}$ è una matrice.
• $C \subset \mathbb{R}^m$ è un insieme chiuso, non necessariamente convesso.

Significato e Applicazioni:
Questa formulazione generalizza i classici programmi quadratici (QP) permettendo a $C$ di essere non convesso. Ciò è cruciale per modellare:

• Vincoli logici e di cardinalità: Ad esempio, vincoli "o-o" (either-or), di commutazione (switching) o di complementarità (complementarity).
• Controlli ottimi discreti: Problemi derivanti dalla discretizzazione di sistemi dinamici lineari-quadratici con vincoli complessi (es. contatto meccanico, dinamiche non lisce).
• Regolarizzazione sparsa: Insiemi che promuovono la sparsità o vincoli binari.

La sfida principale risiede nel fatto che i metodi di programmazione non lineare standard spesso falliscono su questi problemi a causa del mancato soddisfacimento delle qualifiche dei vincoli (constraint qualifications) nei punti fattibili interessanti.

2. Metodologia

L'approccio proposto combina il framework del Lagrangiano Aumentato (Augmented Lagrangian - AL) con una tecnica di condensazione (condensing) che sfrutta la struttura lineare-quadratica del problema.

A. Formulazione Augmentata Lagrangiana

Il problema viene riscritto introducendo una variabile ausiliaria $z$ per separare l'operatore lineare $A$ dall'insieme $C$:
$$\min_{x, z} f(x) + \mathcal{I}_C(z) \quad \text{soggetto a} \quad Ax - z = 0$$
Dove $\mathcal{I}_C$ è la funzione indicatrice dell'insieme $C$.
Viene definito il Lagrangiano aumentato:
$$\mathcal{L}_\sigma(x, z, \hat{x}, \hat{y}) = \mu f(x) + \frac{1}{2}\|Ax - z + \hat{y}\|^2 + \frac{\rho}{2}\|x - \hat{x}\|^2$$
Il metodo risolve una sequenza di sottoproblemi (AL) aggiornando i moltiplicatori di Lagrange e i parametri di penalità. La convergenza globale è garantita dal framework AL, assumendo che i sottoproblemi siano risolti fino a una stazionarietà approssimata.

B. La Tecnica di Condensazione (Il Contributo Chiave)

Il cuore dell'innovazione risiede nella risoluzione efficiente del sottoproblema AL. Invece di risolvere il problema accoppiato su $(x, z)$, l'autore sfrutta il fatto che, fissato $z$, il problema rispetto a $x$ è un problema quadratico non vincolato (o con vincoli lineari "sicuri") con soluzione analitica unica.

1. Mappatura $X_k(z)$: Per ogni $z \in C$, esiste un unico minimizzatore $x = X_k(z)$ che può essere trovato risolvendo un sistema lineare.
2. Funzione Marginale: Si definisce una funzione marginale $M_k(z) = \min_x \mathcal{L}_\sigma(x, z, \dots)$ che dipende solo da $z$.
3. Sottoproblema Condensato: Il problema originale viene ridotto a:
   $$\min_{z \in C} M_k(z)$$
   Questo riduce la dimensione del problema da $n+m$ variabili a sole $m$ variabili.
4. Vantaggi Computazionali:
   • Dimensione ridotta: Meno variabili da ottimizzare.
   • Migliore condizionamento: Il problema condensato è meglio condizionato.
   • Gradiente calcolabile: La funzione $M_k$ è differenziabile con gradiente Lipschitziano, calcolabile efficientemente tramite la regola della catena senza bisogno di derivare esplicitamente $X_k(z)$ in modo numerico complesso.
   • Gestione dei vincoli di uguaglianza: Vincoli lineari "sicuri" (es. dinamiche di stato $A_{eq}x = b_{eq}$) possono essere mantenuti come vincoli di livello inferiore (hard constraints) nel sottoproblema quadratico, evitando di rilassare vincoli che sono intrinsecamente soddisfatti, migliorando ulteriormente la velocità.

3. Contributi Chiave

• Approccio Ibrido: Unisce le garanzie teoriche di convergenza del Lagrangiano Aumentato (anche per insiemi non convessi) con l'efficienza computazionale dello sfruttamento della struttura lineare-quadratica.
• Condensazione Analitica: Introduce una riformulazione che elimina le variabili di stato $x$ a favore delle variabili ausiliarie $z$, riducendo drasticamente la dimensione del sottoproblema interno.
• Indipendenza dal Risolutore (Solver-Agnostic): Il metodo richiede solo un "oracolo di proiezione" per l'insieme $C$ ($\text{proj}_C$), rendendolo applicabile a una vasta gamma di vincoli geometrici complessi senza bisogno di derivare specifiche funzioni di penalità o regolarizzazione per ogni caso.
• Robustezza: Il metodo gestisce vincoli ridondanti e mantiene la convergenza anche in presenza di punti singolari (dove le qualifiche dei vincoli falliscono).

4. Risultati Numerici

L'autore valida l'approccio su tre benchmark di controllo ottimo:

1. Problema a Valore Iniziale (Discontinuo): Un sistema dinamico con un singolo switch, riformulato come sistema di complementarità.
2. Problema dell'Ostacolo (Obstacle Problem): Un problema di controllo ottimo con vincoli di complementarità su un operatore di Laplace discretizzato.
3. Controllo di Tracciamento AFTI-16: Un modello aereo con vincoli di tipo "o-o" (either-or) sugli input di controllo (es. alettoni o flap, ma non entrambi).

Confronto delle Configurazioni:
Sono stati confrontati sei configurazioni di solver, variando:

• Formulazione: Estesa (standard) vs. Condensata (proposta).
• Gestione vincoli lineari: Vincoli "soft" (rilassati) vs. "hard" (mantenuti come equazioni).
• Sottorisolutore: nmpg (gradiente proiettato con passo spettrale) vs. panoc+ (estrapolazione quasi-Newton).

Risultati Principali:

• La formulazione condensata supera costantemente quella estesa in termini di tempo di esecuzione e numero di iterazioni.
• Il trattamento "hard" dei vincoli di uguaglianza (dinamiche) fornisce le prestazioni migliori.
• Il sottorisolutore panoc+ tende a essere superiore a nmpg.
• Il metodo proposto raggiunge prestazioni paragonabili a solver specializzati per vincoli di complementarità, pur mantenendo un approccio generico.
• È possibile risolvere istanze con discretizzazioni molto più fini (es. $N=256$ vs $N=64$) mantenendo tempi di calcolo ragionevoli, cosa non fattibile con approcci precedenti.

5. Significato e Conclusioni

Il paper dimostra che è possibile trattare problemi di ottimizzazione complessi con vincoli non convessi e logici senza sacrificare l'efficienza computazionale. La tecnica di condensazione trasforma un problema potenzialmente malcondizionato e di grandi dimensioni in un problema più piccolo e meglio strutturato, sfruttando la natura quadratica del costo e la linearità delle dinamiche.

Questo approccio è particolarmente rilevante per l'ingegneria dei sistemi di controllo, dove la capacità di modellare vincoli logici (come la commutazione tra modalità operative o vincoli di contatto) in modo nativo, mantenendo la scalabilità necessaria per l'implementazione in tempo reale o per l'ottimizzazione su orizzonti temporali lunghi, è fondamentale. L'uso di un oracolo di proiezione rende il metodo flessibile e applicabile a una vasta gamma di scenari reali senza necessità di ri-adattare l'algoritmo per ogni specifico tipo di vincolo.