I matematici sono spesso impegnati a calcolare i valori di minimo di una funzione. Questi spesso possono rappresentare il compromesso ottimale fra criteri in combinazione fra loro: fra l’area di una superficie, il peso e la resistenza al vento di un telaio di un’automobile, per esempio.

Per le funzioni complesse, trovare un minimo globale può essere molto difficile. Ma il problema diventa molto più semplice se si sa in anticipo che la funzione è convessa, il che significa che il grafico della funzione ‘pende’ ovunque verso il minimo. La convessità è una proprietà così utile che, nel 1992, quando una importante conferenza sull’ottimizzazione designò i sette problemi aperti più importanti del settore, uno di essi fu se la convessità di una arbitraria funzione polinomiale potrebbe essere determinata in modo efficiente.

Circa 20 anni dopo, i ricercatori del MIT (Massachusetts Institute of Technology), precisamente del Laboratory for Information and Decision Systems, hanno alla fine risposto alla domanda, e la risposta, riportata in un articolo presentato alla Society for Industrial and Applied Mathematics (SIAM) Conference on Optimization è ‘no’.

Determinare la convessità di una funzione polinomiale arbitraria –che è una funzione in cui le variabili hanno esponente intero, come 13x⁴ + 7xy² + yz – è dunque un problema chiamato NP-hard. «una rivoluzione non solo sorprendente ma anche interessante»ha dichiarato Etienne de Klerk, della Università di Tilburg, in Olanda.  «In un qualunque libro di testo sull’ottimizzazione che usiamo per insegnare all’università, tutte le funzioni sono quasi sempre convesse. Questo lavoro ci fa vedere il mondo dell’ottimizzazione in un modo diverso» ha aggiunto Klerk.

Un problema NP-hard è un problema a cui il più potente computer del mondo non potrebbe fornire una risposta in tempo ragionevole. Durante la conferenza, tuttavia, Pablo Parrilo, uno degli autori dello studio, ha mostrato che in molti casi una proprietà che può essere determinata in modo efficiente è quella nota come “convessità della somma dei quadrati”, un pratico sostituto della convessità. Inoltre, è stato fornito anche un algoritmo per determinare quando una funzione ha questa proprietà.

Per avere un’idea di quanto la convessità sia utile, immaginiamo un aeroplano in volo, e supponiamo che si conosca una funzione che lega la sua altitudine alla velocità e alla quantità di carburante che consumerà, una quantità, naturalmente, che si vuole minimizzare. Sela funzione è convessa, il suo grafico, tridimensionale, sembra come quello di una grande scodella, con al fondo la combinazione dei valori di altitudine e velocità che minimizzano il consumo di carburante. Tutti gli algoritmi di controllo devono trovare continuamente nuova altitudine e velocità che porti il mezzo verso il “fondo della scodella”. Ma se la funzione non è convessa, il suo grafico potrebbe sembrare quello di una montagna. Il minimo valore potrebbe giacere fra molti picchi e bacini, e trovarlo potrebbe richiedere troppo tempo, mentre si è in volo.

Ovviamente, il tipo di funzioni che i reali algoritmi di controllo devono affrontare è molto più complesso. Ma questa complessità aumenta solo il vantaggio della convessità: garantisce infatti che si possono prendere decisioni informate usando solo limitate, locali informazioni.

«Nella Teoria del controllo c’è stato un grande cambiamento negli ultimi anni verso l’ottimizzazione online», spiega Parrilo. «Ora, grazie al potere di calcolo raggiunto, si può permettere ai controllori di fare cose che sono molto complicate. E possono davvero risolvere problemi di ottimizzazione in volo» continua Parrillo «ma se si vuol fare questo,hai bisogno di un qualche tipo di garanzia che la decisione che stai per andare a prendere sia ottimale, o quasi, a anche che tu possa fare questo in un certo periodo di tempo».La convessità fornisce questa garanzia.

Dal momento che le circostanze intorno alle operazioni di un sistema elettromeccanico sono in costante cambiamento, lo sono anche le funzioni che descrivono lo stato ottimale del sistema. Sarebbe auspicabile riuscire a dire in anticipo se queste funzioni sono convesse, ma purtroppo lo studio dei ricercatori del MIT ha mostrato che non sempre questo possibile.

Gli scienziati hanno anche mostrato che, per le funzioni polinomiali con poche variabili o piccoli esponenti, la convessità coincide con la convessità della somma dei quadrati, che è più facile da verificare (“somma dei quadrati” vuol dire che un polinomio, come x² –2xy + y² + z² può essere riscritto come somma di quadrati, appunto, in questo caso (x – y)² + z².

Ma i ricercatori ci hanno tenuto a sottolineare che funzione convessa per somma di quadrati e funzione convessa non significano la stessa cosa, presentando anche alcuni contro-esempi.

A cura di Stefano Pisani