Funzioni Convesse e Problemi di Ottimizzazione Convessa e Non Convessa

Una proprietà fondamentale di un problema di ottimizzazione è la forma della funzione costo da minimizzare.

All'interno di questo libro sono già stati, o verranno, introdotti diversi problemi formulati come minimizzazione di una funzione obiettivo: stima di omografie, calibrazione di una camera, problema PnP, minimizzazione dell'errore di riproiezione e Bundle Adjustment. Il comportamento degli algoritmi di ottimizzazione dipende in maniera sostanziale dalla struttura di tale funzione.

Definizione 12   Una funzione $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ si dice convessa se, per ogni coppia di punti $\boldsymbol{x},\boldsymbol{y}$ del dominio 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}).$$ (4.76)

Geometricamente, il segmento che unisce due punti qualsiasi del grafico della funzione giace sempre al di sopra del grafico stesso.

Una funzione è detta concava se la sua opposta, $-f$, è convessa.

Le funzioni convesse sono particolarmente importanti in ottimizzazione poiché possiedono una proprietà fondamentale:

Ogni minimo locale è anche minimo globale.

Ne consegue che un algoritmo iterativo che converga ad un minimo locale risolve automaticamente il problema globale.

Un'altra caratterizzazione importante riguarda la matrice Hessiana.

Teorema 2   Se $f$ è due volte differenziabile ($f \in C^2$), allora $f$ è convessa se e solo se la matrice Hessiana

$$\nabla^2 f(\boldsymbol{x})$$ (4.77)

è semidefinita positiva in ogni punto del dominio.

Le funzioni convesse presentano inoltre ulteriori proprietà notevoli:

• l'intersezione di insiemi convessi è ancora un insieme convesso;
• l'epigrafo della funzione,
  

  $$\left\{ (\boldsymbol{x},t) \in \mathbb{R}^{n}\times\mathbb{R} \;\vert\; f(\boldsymbol{x}) \leq t \right\},$$ (4.78)

  
  
  è un insieme convesso;
• vale la disuguaglianza di Jensen:
  

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

  
  

Esempi tipici di funzioni convesse sono:

• funzioni quadratiche con matrice $\boldsymbol{Q}\succeq 0$:
  

  $$f(\boldsymbol{x}) = \boldsymbol{x}^{\top} \boldsymbol{Q} \boldsymbol{x} + \boldsymbol{b}^{\top} \boldsymbol{x} + c;$$ (4.80)

  
  

• le norme $\ell_1$, $\ell_2$ e $\ell_\infty$;
• la funzione log-sum-exp
  

  $$f(\boldsymbol{x}) = \log \left( \sum_i e^{x_i} \right).$$ (4.81)

  
  

In visione artificiale numerosi problemi possono essere formulati come problemi convessi: minimi quadrati lineari, problemi di matching, flussi su grafo, segmentazione e numerosi rilassamenti utilizzati nel riconoscimento di oggetti.

Un problema di programmazione lineare (LP) assume la forma

$$\min_{\boldsymbol{x}} \boldsymbol{c}^{\top}\boldsymbol{x} \q... ...s.t.} \qquad \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}.$$ (4.82)

La regione ammissibile è un poliedro convesso e, se la soluzione esiste, l'ottimo si trova in uno dei vertici del poliedro stesso.

Una generalizzazione importante è la programmazione quadratica (QP)

$$\min_{\boldsymbol{x}} \frac{1}{2} \boldsymbol{x}^{\top} \bol... ...{s.t.} \qquad \boldsymbol{A}\boldsymbol{x} \leq \boldsymbol{b}$$ (4.83)

con $\boldsymbol{Q}\succeq 0$.

Altre classi importanti includono:

• Second-Order Cone Programming (SOCP);
• Semidefinite Programming (SDP).

Purtroppo gran parte dei problemi più interessanti della visione artificiale non appartiene alla classe dei problemi convessi.

La calibrazione di una camera, il problema PnP, il Bundle Adjustment, la stima di pose relative, la triangolazione multi-vista e la maggior parte dei problemi SLAM generano infatti funzioni costo non convesse. In tali casi possono esistere molteplici minimi locali, punti di sella e regioni piatte dello spazio delle soluzioni.

Di conseguenza algoritmi quali Newton, Gauss-Newton e Levenberg-Marquardt non possiedono in generale garanzie di convergenza verso il minimo globale e la qualità della soluzione dipende fortemente dalla stima iniziale.

Per affrontare tali difficoltà si ricorre frequentemente a:

• inizializzazioni robuste;
• strategie multi-scala o coarse-to-fine;
• tecniche robuste agli outlier quali RANSAC;
• rilassamenti convessi e approssimazioni;
• ottimizzazione direttamente su varietà geometriche;
• esecuzione di molteplici ottimizzazioni da punti iniziali differenti (multi-start).

Nella pratica, gran parte dell'ottimizzazione in visione artificiale consiste proprio nel trasformare un problema fortemente non convesso in un problema sufficientemente ben condizionato da poter essere risolto in modo affidabile mediante tecniche iterative.