Funzioni Convesse e Problemi di Ottimizzazione Convessa e non

Definizione 12   Una funzione $f : \mathbb{R}^n \rightarrow \mathbb{R}$ si dice convessa se, per ogni coppia di punti $\boldsymbol{x}, \boldsymbol{y}$ nel dominio di $f$ e per ogni $\lambda \in [0,1]$, vale la disuguaglianza:

$$f \left( \lambda \boldsymbol{x} + (1-\lambda)\boldsymbol{y} ... ...\leq \lambda f(\boldsymbol{x}) + (1-\lambda) f(\boldsymbol{y})$$ (3.71)

Una funzione è detta concava se la sua opposta, $-f$, è convessa. Le funzioni convesse presentano proprietà strutturali che le rendono particolarmente adatte alla formulazione e risoluzione di problemi di ottimizzazione:

• L'intersezione di insiemi convessi è ancora un insieme convesso.
• L'epigrafo della funzione, definito come $(\boldsymbol{x},t) \in \mathbb{R}^n \times \mathbb{R} ,\vert, f(\boldsymbol{x}) \leq t$, è un insieme convesso.
• Se $f$ è due volte differenziabile ($f \in C^2$), la convessità è equivalente alla semidefinità positiva della matrice hessiana $\boldsymbol{\nabla}^2 f(\boldsymbol{x})$ in ogni punto del dominio.
• La disuguaglianza di Jensen fornisce una caratterizzazione alternativa della convessità:
  

  $$f \left( \mathbf{E}[\boldsymbol{X}] \right) \leq \mathbf{E}[f(\boldsymbol{X})]$$ (3.72)

  
  

Esempi tipici di funzioni convesse includono: funzioni quadratiche con matrice $\boldsymbol{Q} \succeq 0$, norme $\ell_p$ come $\vert\boldsymbol{x}\vert _1$, $\vert\boldsymbol{x}\vert _2$, $\vert\boldsymbol{x}\vert _\infty$, e la funzione log-sum-exp $f(\boldsymbol{x}) = \log \left(\sum_i e^{x_i}\right)$, frequentemente impiegata in machine learning.

In visione artificiale, formulazioni convesse compaiono in numerosi contesti: stima di parametri tramite minimi quadrati, matching tra feature come problema lineare, segmentazione e clustering basati su rilassamenti convessi. I problemi convessi risultano particolarmente vantaggiosi perché ogni minimo locale coincide con il minimo globale, esistono algoritmi numerici efficienti per la loro risoluzione (metodi del gradiente, simplesso, metodi a punto interno), e molti problemi pratici possono essere riformulati in modo convesso.

Un problema di programmazione lineare (LP) assume la forma:

$$\min_{\boldsymbol{x}} \boldsymbol{c}^\top \boldsymbol{x} \qu... ...{s.t.} \quad \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}$$ (3.73)

dove $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ e $\boldsymbol{b} \in \mathbb{R}^m$. La regione ammissibile è un poliedro convesso, e la soluzione ottima, se esiste, si trova in corrispondenza di uno dei suoi vertici. Esempi di programmazione lineare in visione artificiale sono i problemi di assegnamento e matching, flussi su grafo per segmentazione o stereo.

Un problema di programmazione quadratica (QP) si scrive come:

$$\min_{\boldsymbol{x}} \tfrac{1}{2} \boldsymbol{x}^\top \bold... ...{s.t.} \quad \boldsymbol{A} \boldsymbol{x} \leq \boldsymbol{b}$$ (3.74)

con $\boldsymbol{Q} \succeq 0$. Si tratta di un'estensione della LP che include un termine quadratico convesso. Esempi di programmazione quadratica in visione artificiale sono Support Vector Machines (SVM) e fitting di modelli geometrici con vincoli.

Oltre a LP e QP, esistono classi più generali di problemi convessi:

• Second-Order Cone Programming (SOCP): impiegato in contesti di ottimizzazione robusta.
• Semidefinite Programming (SDP): utilizzato nei rilassamenti convessi di problemi combinatori.

Tuttavia, molti problemi di visione artificiale non sono convessi. In tali casi la funzione obiettivo può presentare più minimi locali e non esistono garanzie di convergenza verso la soluzione globale. Esempi tipici sono la stima della posa (PnP), il bundle adjustment o la ricostruzione tridimensionale. Per affrontare tali difficoltà si ricorre a:

• inizializzazioni robuste, per ridurre il rischio di convergere verso minimi locali indesiderati;
• rilassamenti convessi o approssimazioni, che consentono di trattare un problema non convesso come se fosse convesso;
• strategie iterative (RANSAC, multi-start), che esplorano più soluzioni candidate;
• metodi che sfruttano la struttura del problema, come l'ottimizzazione su gruppi di Lie.

Nella pratica, gran parte dell'ottimizzazione in visione artificiale avviene su problemi non convessi, e la qualità della soluzione dipende fortemente dalla bontà dell'inizializzazione e dalla modellazione del problema.