Ottimizzazione in Python: tecniche, pacchetti e best practice

Tecniche di ottimizzazione in Python

Python offre una varietà di tecniche potenti per risolvere problemi di ottimizzazione, dai semplici metodi basati sul gradiente ad algoritmi più complessi. Queste tecniche ti permettono di trovare in modo efficiente i minimi o i massimi delle funzioni, che si tratti di machine learning, ingegneria o ricerca operativa. 

In questa sezione vedremo le tecniche di ottimizzazione comunemente implementate in Python, tra cui discesa del gradiente, metodo di Newton, metodo del gradiente coniugato, metodi quasi-Newton, metodo del Simplex e metodi a regione di fiducia. 

Nota: dai un'occhiata a questo DataLab per vedere tutto il codice usato per generare le visualizzazioni in questa sezione. 

Entriamo nel vivo!

Discesa del gradiente

La discesa del gradiente è una delle tecniche più fondamentali nell'ottimizzazione numerica. È un metodo iterativo usato per trovare il minimo di una funzione seguendo il negativo del gradiente (o pendenza) della funzione. 

L'idea di base è partire da una stima iniziale e aggiornarla iterativamente muovendosi nella direzione di massima discesa fino al raggiungimento della convergenza. È una delle tecniche di ottimizzazione più utilizzate nell'addestramento dei modelli di machine learning, dove l'obiettivo è minimizzare la funzione di perdita. 

Metodo di Newton

Il metodo di Newton è una tecnica di ottimizzazione che trova il minimo usando sia il gradiente sia la derivata seconda (la matrice Hessiana) della funzione obiettivo. A differenza della discesa del gradiente, che si basa solo sulle derivate prime, il metodo di Newton sfrutta le informazioni di curvatura, consentendo una convergenza più rapida, soprattutto per funzioni convesse.

Sebbene il metodo di Newton converga rapidamente, richiede il calcolo della matrice Hessiana, che può essere costoso dal punto di vista computazionale e poco pratico per problemi su larga scala. Tuttavia, è molto efficace per problemi convessi piccoli e regolari.

Metodo del gradiente coniugato

Il metodo del gradiente coniugato è una tecnica di ottimizzazione efficiente per problemi su larga scala, in particolare quando memorizzare la matrice Hessiana è impraticabile. Costruisce iterativamente direzioni coniugate, ottimizzando lungo di esse invece di richiedere l'Hessiana completa, il che lo rende adatto a problemi come la minimizzazione di grandi funzioni quadratiche.

Questo metodo è utile nell'analisi agli elementi finiti o in applicazioni di machine learning su larga scala, dove le operazioni su matrici diventano gravose.

Metodi quasi-Newton (BFGS)

I metodi quasi-Newton, come l'algoritmo di Broyden–Fletcher–Goldfarb–Shanno (BFGS), approssimano la matrice Hessiana invece di calcolarla direttamente. Questi metodi raggiungono una convergenza più rapida della discesa del gradiente utilizzando informazioni di secondo ordine senza l'onere computazionale di calcolare l'Hessiana completa.

Metodo del Simplex

Il metodo del Simplex è un algoritmo ampiamente utilizzato per risolvere problemi di programmazione lineare (LP), in cui la funzione obiettivo e i vincoli sono lineari. Esamina sistematicamente i vertici della regione ammissibile (un poliedro) e si sposta verso il vertice ottimale in cui la funzione obiettivo raggiunge il suo valore massimo o minimo.

Metodi a regione di fiducia

I metodi a regione di fiducia sono algoritmi di ottimizzazione che costruiscono un modello locale della funzione obiettivo all'interno di una “regione di fiducia” attorno alla soluzione corrente. 

Invece di fare passi in una direzione predefinita (come nella discesa del gradiente), l'algoritmo definisce un sottoproblema più semplice all'interno della regione di fiducia. Risolve iterativamente questo sottoproblema per affinare la soluzione. Questi metodi sono particolarmente efficaci per gestire problemi complessi e non lineari e offrono una stabilità migliore rispetto ai tradizionali metodi basati sul gradiente.

Regioni di fiducia e raggi durante la minimizzazione della funzione di Rosenbrock | Fonte: Trust Region Methods di Shivangi Khare

Pacchetti Python comuni per l'ottimizzazione

Esiste una gamma di librerie e pacchetti pensati per facilitare l'ottimizzazione numerica. Ognuno ha i propri punti di forza e ambiti di applicazione, ma qualunque sia il problema di ottimizzazione che devi affrontare, di solito c'è uno strumento solido che può aiutarti in Python. 

Ecco quattro dei pacchetti di ottimizzazione più comuni:  

Ottimizzazione con SciPy (scipy.optimize)

Il modulo scipy.optimize è una libreria dell'ecosistema SciPy versatile, che offre un'ampia gamma di algoritmi per problemi di ottimizzazione sia non vincolati sia vincolati. Include funzioni per trovare i minimi di funzioni scalari e multivariate, risolvere problemi di ricerca degli zeri e adattare curve ai dati.

Le funzioni in questo modulo includono: 

• minimize(): una funzione usata per minimizzare una funzione scalare di una o più variabili.

from scipy.optimize import minimize

def objective_function(x):
    return x[0]**2 + x[1]**2
result = minimize(objective_function, [1, 1], method='BFGS')
print(result.x)  # Optimal solution

# >>> [-1.07505143e-08 -1.07505143e-08]Offerto da

• root(): trova lo zero di una funzione vettoriale – estremamente utile per risolvere sistemi di equazioni non lineari.

from scipy.optimize import root

def equations(vars):
    x, y = vars
    return [x + 2*y - 3, x - y - 1]
result = root(equations, [0, 0])
print(result.x)

# >>> [1.66666667 0.66666667]Offerto da

• curve_fit(): questa funzione adatta una curva a un insieme di punti dati ed è utile per il fitting dei dati e la stima dei parametri.

from scipy.optimize import curve_fit
import numpy as np

def model(x, a, b):
    return a * np.exp(b * x)
x_data = np.array([1, 2, 3])
y_data = np.array([2.7, 7.4, 20.1])
params, covariance = curve_fit(model, x_data, y_data)
print(params)  # Fitted parameters

# >>> [0.9981286  1.00089935]Offerto da

CVXPY

CVXPY è una libreria Python progettata per problemi di ottimizzazione convessa. Permette di definire e risolvere questi problemi usando una sintassi dichiarativa ad alto livello. Semplifica la formulazione di problemi di ottimizzazione complessi consentendo di specificare la funzione obiettivo e i vincoli in modo naturale e leggibile.

CVXPY offre le seguenti caratteristiche:

• Sintassi dichiarativa: CVXPY fornisce un modo intuitivo per modellare problemi di ottimizzazione usando espressioni matematiche in Python.
• Solver all'avanguardia: interfaccia con solver avanzati come ECOS, SCS e OSQP, che gestiscono in modo efficiente problemi convessi.

import cvxpy as cp

# Define variables
x = cp.Variable()
y = cp.Variable()

# Define constraints
constraints = [x + y == 1, x - y >= 2]

# Define the objective function
objective = cp.Minimize(x**2 + y**2)

# Formulate the problem
prob = cp.Problem(objective, constraints)

# Solve the problem
result = prob.solve()
print(f"Optimal value: {result}")
print(f"x: {x.value}, y: {y.value}")

# >>> Optimal value: 2.5
# x: 1.5, y: -0.5000000000000001Offerto da

Pyomo

Pyomo è un pacchetto flessibile e completo per il modeling di ottimizzazione che supporta programmazione lineare, non lineare e mista intera. È progettato per problemi di ottimizzazione complessi e si integra perfettamente con solver come GLPK, CBC e CPLEX.

Le funzionalità di Pyomo includono:

• Flessibilità di modellazione: Pyomo consente di definire problemi di ottimizzazione con un alto grado di flessibilità, inclusi vincoli e obiettivi complessi.
• Integrazione con i solver: supporta un'ampia gamma di solver, offrendo flessibilità nella scelta dello strumento migliore per uno specifico problema.

Gurobi e CPLEX (via Pyomo o API diretta)

Gurobi e CPLEX sono solver ad alte prestazioni per problemi di ottimizzazione su larga scala. Sono comunemente usati nell'industria per attività come ottimizzazione della supply chain, gestione di portafogli e logistica. 

Offrono algoritmi avanzati progettati per gestire in modo efficiente problemi complessi e di grandi dimensioni.

• Gurobi: accessibile tramite Pyomo o la propria API diretta, Gurobi è noto per la velocità e l'affidabilità nella risoluzione di problemi di programmazione lineare, intera e quadratica.
• CPLEX: analogamente, CPLEX offre potenti capacità di ottimizzazione ed è usato in vari settori per risolvere problemi operativi e strategici complessi. È accessibile via Pyomo o direttamente tramite la sua API.

Questi solver sono spesso impiegati per problemi di scala industriale in cui efficienza computazionale e robustezza sono critiche.

Applicazioni reali dell'ottimizzazione numerica in Python

Come accennato nell'introduzione, l'ottimizzazione numerica svolge un ruolo cruciale in vari ambiti. Fornisce tecniche essenziali per risolvere problemi complessi e prendere decisioni guidate dai dati.

Per esempio:  

• Machine learning: i modelli sono fondamentalmente addestrati usando l'ottimizzazione numerica. Ciò implica trovare i parametri ottimali che minimizzano la funzione di perdita e quantificano quanto bene il modello predice la variabile target. 
• Ricerca operativa: le tecniche di ottimizzazione aiutano a prendere decisioni strategiche che massimizzano o minimizzano varie metriche operative. Ottimizzando funzioni obiettivo soggette a vincoli, i ricercatori operativi possono migliorare l'efficienza in processi come gestione della supply chain, schedulazione della forza lavoro e pianificazione della produzione. 
• Finanza: l'ottimizzazione numerica è cruciale nel settore finanziario per attività come l'ottimizzazione di portafoglio. Aiuta a determinare la migliore allocazione degli asset per massimizzare i rendimenti o minimizzare il rischio.
• Progettazione ingegneristica: l'ottimizzazione numerica è applicata per progettare sistemi e strutture che soddisfino specifici criteri prestazionali minimizzando i costi. Questo processo aiuta a ottenere progetti efficienti per tutto, dai ponti e gli aeromobili ai processi manifatturieri e ai sistemi energetici.

Best practice per l'ottimizzazione numerica in Python

Per ottenere i migliori risultati dai tuoi sforzi di ottimizzazione in Python, è necessario considerare diversi fattori. Assicurati di seguire le seguenti best practice: 

Scegliere l'algoritmo corretto

Selezionare l'algoritmo di ottimizzazione giusto è cruciale per ottenere risultati ottimali. La scelta dipende dalla natura del problema:

• Lineare vs. non lineare: per problemi lineari, sono appropriati tecniche di programmazione lineare come Simplex o metodi a punti interni. Per problemi non lineari, possono essere più adatti metodi come discesa del gradiente, metodo di Newton o metodi quasi-Newton (ad es. BFGS).
• Vincolato vs. non vincolato: per problemi con vincoli, sono necessari algoritmi come la Programmazione Quadratica Sequenziale (SQP) o metodi che gestiscono nativamente i vincoli (es. metodi a punti interni). I problemi non vincolati possono essere risolti in modo efficiente con discesa del gradiente o metodo di Newton.

Scegliere l'algoritmo giusto in base alle caratteristiche del problema aiuta a ottenere una convergenza più rapida e soluzioni più accurate.

Gestire i vincoli

I vincoli nei problemi di ottimizzazione possono influenzare in modo significativo la scelta dell'algoritmo e della strategia di soluzione. Per gestire i vincoli si possono usare diversi approcci:

• Metodi di penalità: incorporano i vincoli nella funzione obiettivo aggiungendo un termine di penalità per le violazioni dei vincoli. Questo approccio trasforma un problema vincolato in uno non vincolato, consentendo l'uso di metodi di ottimizzazione non vincolata.
• Metodi a barriera: usano funzioni barriera per garantire che i vincoli non vengano violati. I metodi a barriera includono un termine nella funzione obiettivo che diventa infinito all'avvicinarsi dei vincoli.
• Supporto nativo: utilizza solver che supportano intrinsecamente i vincoli. Molti solver moderni, come quelli disponibili in scipy.optimize o CVXPY, sono progettati per gestire i vincoli in modo diretto ed efficiente.

La scelta del metodo appropriato per gestire i vincoli garantisce che le soluzioni siano ammissibili e soddisfino tutti i requisiti specificati.

Scalatura e preprocessing

Una corretta scalatura e un adeguato preprocessing dei dati possono migliorare significativamente le prestazioni degli algoritmi di ottimizzazione:

• Scalatura: normalizza o standardizza i dati in ingresso per assicurare che le caratteristiche contribuiscano in modo equilibrato alla funzione obiettivo. Questo può prevenire problemi di stabilità numerica e migliorare i tassi di convergenza.
• Preprocessing: applica tecniche come feature engineering o riduzione della dimensionalità per semplificare il problema. Un buon preprocessing riduce la complessità del problema di ottimizzazione e accelera il processo di soluzione.

Interpretare i risultati

Interpretare i risultati degli algoritmi di ottimizzazione implica comprendere diversi aspetti:

• Qualità della soluzione: valuta la qualità della soluzione verificando se soddisfa le condizioni di ottimalità e i vincoli. Confronta i risultati con benchmark noti o validali tramite tecniche di cross-validation.
• Criteri di convergenza: valuta se l'algoritmo di ottimizzazione è convergito controllando messaggi di convergenza, conteggi delle iterazioni o variazioni nel valore della funzione obiettivo. Assicurati che l'algoritmo abbia raggiunto una soluzione vicina al vero ottimo.
• Precisione numerica: considera l'impatto della precisione numerica sui risultati. Piccoli errori numerici possono accumularsi e influenzare la soluzione finale, in particolare in problemi su larga scala o con tolleranze ristrette.

Conclusione

L'ottimizzazione numerica è una pietra angolare della risoluzione moderna dei problemi. Offre strumenti potenti per affrontare sfide complesse in campi come machine learning, ingegneria, finanza e ricerca operativa. 

Il ricco ecosistema di librerie di ottimizzazione di Python—come SciPy, CVXPY e Pyomo—rende queste tecniche avanzate più accessibili, permettendo a ricercatori, ingegneri e data scientist di progettare sistemi efficienti, ottimizzare modelli e prendere decisioni più intelligenti e basate sui dati. 

Con le tecniche e le best practice giuste, ora sei ben attrezzato per affrontare e risolvere anche i problemi di ottimizzazione più impegnativi in Python. Dai un'occhiata a queste risorse per continuare a imparare:

• Introduction to Optimization in Python
• Introduction to Linear Modeling in Python
• SciPy Cheat Sheet: Linear Algebra in Python
• Data Structures: A Comprehensive Guide With Python Examples