L'ottimizzazione non smooth

L'ottimizzazione non smooth

L’ottimizzazione non smooth

In analisi matematica i problemi di massimo e di minimo, ossia di ottimizzazione, vengono solitamente affrontati in ipotesi di differenziabilità. Si suppone cioè che la funzione obiettivo ƒ (di una o più variabili) sia differenziabile almeno due volte. La ricerca dei punti e dei valori di massimo o di minimo locale comincia allora con l’individuazione dei punti stazionari (che annullano la derivata prima della funzione ƒ o, nel caso di funzioni di più variabili, il suo gradiente) e la precisazione della loro natura, tramite lo studio del segno del differenziale secondo della funzione obiettivo calcolato in ciascuno di tali punti stazionari. Le condizioni di ottimalità sono costituite da relazioni che riguardano le derivate delle funzioni coinvolte nel problema di ottimizzazione.

La formalizzazione rigorosa del concetto di differenziabilità per funzioni reali di n variabili risale ai primi del Novecento, e in particolare al matematico francese M.-R. Fréchet. Tuttavia l’ipotesi “classica” di differenziabilità è un’ipotesi forte: occorre tener presente che non solo le funzioni non continue non sono differenziabili, ma anche che all’interno della classe delle funzioni continue le funzioni differenziabili costituiscono una sottoclasse ristretta. Sin dall’inizio è emersa quindi l’esigenza di individuare una definizione più debole di differenziabilità, in grado di assicurare a una nuova e più generale classe di funzioni (quasi) tutte le proprietà di cui godono le funzioni differenziabili. Dal punto di vista della teoria e dei metodi di ottimizzazione, l’esigenza era quella di affrontare problemi di ottimizzazione nel caso in cui le funzioni coinvolte non siano necessariamente differenziabili. Con l’espressione «ottimizzazione non smooth» si indicano appunto i metodi di ottimizzazione che utilizzano ipotesi più deboli di quella classica di differenziabilità, intendendo il termine «non smooth» (ingl., letteralmente «non liscio») come sinonimo di «non necessariamente differenziabile». Le ricerche in questo campo diventano particolarmente interessanti nella seconda metà del Novecento e si sviluppano inizialmente con le funzioni convesse (o concave) e successivamente con quelle lipschitziane. Nel 1970, R.T. Rockafellar pubblicò Convex analysis (Analisi convessa) in cui introdusse, per le funzioni convesse, i concetti di subgradiente e di subdifferenziale. Il semplice esempio ƒ(x) = |x| mostra che anche una funzione convessa non è sempre differenziabile; il suo grafico non ammette in ogni punto la retta tangente che si mantiene sempre al di sotto, o comunque non al di sopra, di esso. In termini geometrici, l’idea di Rockafellar è stata quella di sostituire la retta tangente, non sempre esistente, con una pluralità di semirette passanti per un punto del grafico della funzione e situate sempre al di sotto o non al di sopra di esso.

Più precisamente, un vettore m ∈ Rⁿ è un subgradiente per la funzione convessa ƒ: Rⁿ → R in un punto x⁰ se per ogni x è soddisfatta la disuguaglianza ƒ(x) ≥ ƒ(x⁰) + m(x − x⁰). L’insieme dei subgradienti è chiamato subdifferenziale di ƒ in x⁰ e indicato con il simbolo ∂ƒ(x⁰). È un insieme chiuso e convesso in Rⁿ; quando non è vuoto, la funzione ƒ si dice subdifferenziabile. Il subdifferenziale è costituito dall’unico vettore gradƒ(x⁰) se e solo ƒ è differenziabile in x⁰. In generale, la corrispondenza x⁰ → ∂ƒ(x⁰) è una funzione set-valued. Per esempio, sempre per la funzione ƒ(x) = |x|, il subdifferenziale nell’origine è costituito da tutti i punti dell’intervallo [−1, 1].

Proprio perché ∂f è una funzione set-valued, le classiche uguaglianze dell’ottimizzazione differenziabile si trasformano in relazioni di appartenenza. Questo vale per la condizione di Fermat che per le funzioni convesse esprime una condizione necessaria e sufficiente per i punti di massimo e di minimo locale: l’uguaglianza dƒ(x⁰) = 0 diventa 0 ∈ ∂ƒ(x⁰). Infatti, se è ƒ(x) ≥ ƒ(x⁰), risulta anche per ogni x: ƒ(x) ≥ ƒ(x⁰) + 0(x − x⁰), cioè 0 ∈ ∂ƒ(x⁰); viceversa, da questa appartenenza segue subito ƒ(x) ≥ ƒ(x⁰) per ogni x.

Per le funzioni convesse si dimostra che la derivata di ƒ in un punto x⁰ e lungo la direzione y:

esiste sempre e che un vettore m ∈ ∂ƒ(x⁰) se e solo se risulta ƒ′ (x⁰, y) ≥ my per ogni y. La condizione 0 ∈ ∂ƒ(x⁰) può allora essere equivalentemente sostituita dalla richiesta che risulti ƒ′ (x⁰, y) ≥ 0 per ogni y. L’osservazione è significativa anche perché permette un rapido confronto con la successiva generalizzazione introdotta da Frank H. Clarke che, con Rockafellar, aveva discusso la tesi di dottorato all’inizio degli anni Settanta e che nel 1983 pubblica Optimization and nonsmooth analysis (Ottimizzazione e analisi non smooth). Clarke tratta il caso delle funzioni localmente lipschitziane. Si dimostra che ogni funzione convessa, superiormente limitata in un intorno di un punto del suo dominio, soddisfa localmente la disuguaglianza di Lipschitz (con k > 0):

Per le funzioni localmente lipschtziane, si può definire la derivata direzionale generalizzata data da:

La generalizzazione è evidente: ora nel rapporto incrementale si ha il punto perturbato x (anziché x⁰) e si calcola il limite superiore. La funzione ƒ ⁰ è convessa (addirittura sublineare, ossia omogenea e subadditiva) rispetto alla direzione y: per questa derivata, anche se la funzione originaria non era convessa, si hanno quindi a disposizione i teoremi di separazione e tutti gli strumenti “classici” dell’analisi convessa. Purtroppo, in generale, la nuova derivata non coincide con la derivata direzionale ƒ′ (x⁰, y), anche quando questa esistesse; l’uguaglianza ƒ′ (x⁰, y) = ƒ ⁰(x⁰, y) vale solo in una più ristretta classe di funzioni, che contiene comunque quelle convesse.

Attraverso la definizione di derivata direzionale generalizzata, è possibile introdurre – in vari modi equivalenti – la nozione di gradiente generalizzato ∂f (x⁰).

Si può, per esempio, porre:

L’insieme ∂ƒ(x⁰), che nel caso di una funzione convessa coincide con il subdifferenziale di Rockafellar, è un sottoinsieme convesso e compatto di Rⁿ; risulta ƒ ⁰(x⁰, y) = max{uy, u ∈ ∂ƒ(x⁰)}. Anche in questo caso, definizione e regole di calcolo dei gradienti generalizzati portano rapidamente ad applicare il nuovo calcolo ai problemi di ottimo e la condizione necessaria ƒ′ (x⁰) = 0 oppure grad ƒ(x⁰) = 0 per un estremante porta all’inclusione 0 ∈ ∂ƒ(x⁰) oppure, equivalentemente, alla disuguaglianza ƒ ⁰(x⁰, y) ≥ 0 per ogni y.