Optimization Toolbox

Funzionalità principali

Uso di un problema di programmazione lineare mista intera per stabilire il modo migliore per rifornire i punti vendita dai magazzini e dalle fabbriche
Uso di un problema di programmazione lineare mista intera per stabilire il modo migliore per rifornire i punti vendita dai magazzini e dalle fabbriche

Definizione e soluzione di problemi di ottimizzazione

Definizione di un problema di ottimizzazione

Le tecniche di ottimizzazione vengono utilizzate per trovare una serie di parametri di progettazione che dia il miglior risultato possibile. In un problema di ottimizzazione ci sono due componenti-chiave:

La funzione obiettivo calcola la quantità desiderata da minimizzare o massimizzare. È possibile aggiungere vincoli che limitino i valori possibili per i parametri progettuali.

Modellazione matematica con ottimizzazione, parte 1 8:51
Transformare una descrizione di problema in un programma matematico che può essere risolto mediante l'ottimizzazione, usando come esempio un impianto per la generazione di vapore ed energia elettrica.

Modellazione matematica con ottimizzazione, parte 2 10:46
Risolvere un programma lineare mediante i solutori di Optimization Toolbox™, usando come esempio un impianto per la generazione di vapore ed energia elettrica.

Utilizzo dell’app di ottimizzazione

Le funzioni e i solutori di Optimization Toolbox sono accessibili in modo programmatico o dall’app di ottimizzazione.

L’app di ottimizzazione semplifica le operazioni di ottimizzazione comuni. Consente di:

  • selezionare un solutore e definire un problema di ottimizzazione.
  • impostare e ispezionare le opzioni di ottimizzazione con i rispettivi valori predefiniti per il solutore selezionato.
  • eseguire i problemi e visualizzare i risultati intermedi e finali.
  • visualizzare la documentazione specifica del solutore in una finestra opzionale di riferimento rapido.
  • importare ed esportare le definizioni dei problemi, le opzioni dell’algoritmo e i risultati tra il workspace MATLAB® e l’app di ottimizzazione.
  • generare automaticamente il codice MATLAB per registrare il lavoro svolto e automatizzare le operazioni.
  • accedere ai solutori di Global Optimization Toolbox.

Primi passi con Optimization Tool 6:08
Impostare ed eseguire problemi di ottimizzazione e visualizzare i risultati intermedi e finali.

Scelta di un solutore

Optimization Toolbox contiene vari solutori per tipologie diverse di obiettivi e vincoli. La Tabella decisionale per l’ottimizzazione aiuta a scegliere il solutore migliore per il problema specifico in questione.

Impostazione delle opzioni

Le opzioni del solutore consentono di regolare o modificare il processo di ottimizzazione e di visualizzare il progresso del solutore. L’impostazione delle opzioni può avvenire in modo programmatico o attraverso l’app di ottimizzazione.

Setting Options for Optimizations 4:48
Set options with optimoptions in Optimization Toolbox™ to tune solvers and monitor optimization progress.

Ottimizzazione non lineare

Optimization Toolbox fornisce algoritmi di ottimizzazione di uso diffuso per risolvere problemi di programmazione non lineare in MATLAB. Il toolbox include solutori per l’ottimizzazione non lineare vincolata e non e solutori per l’ottimizzazione dei minimi quadrati.

Ottimizzazione non lineare non vincolata

Optimization Toolbox utilizza tre algoritmi per risolvere problemi di ottimizzazione non lineare non vincolata:

  • l’algoritmo Quasi-Newton utilizza una procedura di ricerca lineare mista quadratica e cubica e la formula di Broyden-Fletcher-Goldfarb-Shanno (BFGS) per aggiornare l’approssimazione della matrice hessiana.
  • l’algoritmo di Nelder-Mead è un algoritmo a ricerca diretta che utilizza solamente i valori della funzione (non richiede il calcolo delle derivate) e agisce sulle funzioni obiettivo non-smooth; Global Optimization Toolbox fornisce altri algoritmi di ottimizzazione senza calcolo delle derivate per l’ottimizzazione non lineare.
  • l’algoritmo trust-region viene utilizzato per problemi non lineari non vincolati, soprattutto per problemi su larga scala in cui sia possibile sfruttare la sparsità o la struttura.
Ottimizzazione non lineare non vincolata utilizzata per la ricerca dell’efficienza di picco in una mappa di performance di un motore
Ottimizzazione non lineare non vincolata utilizzata per la ricerca dell’efficienza di picco in una mappa di performance di un motore

Ottimizzazione non lineare vincolata

I problemi di ottimizzazione non lineare vincolata sono composti da funzioni obiettivo lineari o non lineari e possono essere soggetti a vincoli lineari e non lineari. Optimization Toolbox utilizza quattro algoritmi per risolvere i seguenti problemi.

  • L’algoritmo a punto interno viene utilizzato per l’ottimizzazione non lineare generale. È soprattutto utile per problemi su larga scala con sparsità o struttura e tollera errori di valutazione nella funzione obiettivo definita dall’utente e nella funzione di vincolo. Si basa su una funzione di barriera e, a scelta, assicura la fattibilità di tutte le iterazioni rispetto ai limiti durante un’ottimizzazione.
  • L’algoritmo SQP viene utilizzato per l’ottimizzazione non lineare generale. Rispetta i limiti e tutte le iterazioni e tollera errori di valutazione nella funzione obiettivo definita dall’utente e nella funzione di vincolo.
  • L’algoritmo active-set viene utilizzato per l’ottimizzazione non lineare generale.
  • L’algoritmo riflessivo trust-region viene utilizzato solamente per problemi con vincoli al contorno o con uguaglianze lineari. È utile soprattutto per problemi su larga scala.

L’algoritmo a punto interno e l’algoritmo riflessivo trust-region consentono di calcolare le matrici hessiane con approcci diversi.

Per l’algoritmo a punto interno, è possibile stimare le matrici hessiane usando:

  • BFGS (densa).
  • BFGS a memoria ridotta (per problemi su larga scala).
  • funzione di moltiplicazione hessiana.
  • hessiana reale (sparsa o densa).
  • differenza finita di gradienti, senza necessità di conoscenza della struttura di sparsità.differenza finita di gradienti, senza necessità di conoscenza della struttura di sparsità.

Per l’algoritmo riflessivo trust-region, è possibile usare:

  • differenza finita di gradienti, struttura di sparsità dell’hessiana.
  • hessiana reale (sparsa o densa).
  • funzione di moltiplicazione hessiana.

Inoltre, gli algoritmi punto interno e riflessivo trust-region consentono di calcolare i prodotti tra la matrice hessiana e un vettore senza dover allocare esplicitamente la matrice stessa.

Ottimizzazione non lineare vincolata utilizzata per progettare un sistema di sospensioni ottimale
Ottimizzazione non lineare vincolata utilizzata per progettare un sistema di sospensioni ottimale

Programmazione lineare e quadratica

Optimization Toolbox può risolvere problemi di programmazione lineare su larga scala e quadratica.

Programmazione lineare

I problemi di programmazione lineare riguardano la minimizzazione o la massimizzazione di una funzione obiettivo lineare soggetta a limiti e vincoli di uguaglianza e disuguaglianza lineare. La programmazione lineare viene utilizzata in finanza, nel settore dell’energia, nella ricerca operativa e in altre applicazioni in cui è possibile esprimere linearmente le relazioni tra le variabili.

Optimization Toolbox include tre algoritmi utilizzati per risolvere i problemi di programmazione lineare:

  • l’algoritmo simplesso è una procedura sistematica per generare e testare le soluzioni al vertice candidate di un programma lineare; l’algoritmo simplesso è quello maggiormente utilizzato per la programmazione lineare.
  • l’algoritmo punto interno si basa su un algoritmo predittore-correttore primario-duale utilizzato per risolvere problemi della programmazione lineare; è utile soprattutto per problemi su larga scala strutturati o definibili mediante matrici sparse.
  • l’algoritmo active-set minimizza l’obiettivo a ciascuna iterazione di tutto il set attivo (un subset dei vincoli attivi localmente) fino a convergere in una soluzione.
Programmazione lineare utilizzata nella progettazione di un impianto di generazione di vapore ed energia elettrica.
Programmazione lineare utilizzata nella progettazione di un impianto di generazione di vapore ed energia elettrica.

Programmazione quadratica

I problemi di programmazione quadratica riguardano la minimizzazione di una funzione quadratica multivariata soggetta a limiti e vincoli di uguaglianza e di disuguaglianza lineare. La programmazione quadratica viene utilizzata per l’ottimizzazione di portafoglio in campo finanziario, per l’ottimizzazione della generazione di energia nelle compagnie pubbliche del settore elettrico, per l’ottimizzazione dei progetti in campo ingegneristico e in altre applicazioni.

Optimization Toolbox contiene tre algoritmi per la soluzione di programmi quadratici:

  • l’algoritmo convesso a virgola interna risolve problemi complessi con qualsiasi combinazione di vincoli.
  • l’algoritmo riflessivo trust-region risolve problemi con vincoli di limite o problemi con vincoli di uguaglianza lineare.
  • l’algoritmo active-set risolve problemi con qualsiasi combinazione di vincoli.

Optimization in MATLAB: An Introduction to Quadratic Programming 36:35
In this webinar, you will learn how MATLAB can be used to solve optimization problems using an example quadratic optimization problem and the symbolic math tools in MATLAB.

Sia l’algoritmo convesso a virgola interna che quello riflessivo trust-region sono su larga scala, ossia possono gestire problemi di ampie dimensioni e sparsi. Inoltre, l’algoritmo convesso a virgola interna ha routine algebriche lineari ottimizzate e un nuovo modulo di presoluzione che può migliorare la velocità, la stabilità numerica e la rilevazione dell’infattibilità.

Programmazione quadratica utilizzata per eseguire un’analisi di stile basata sulla redditività di tre fondi d’investimento.
Programmazione quadratica utilizzata per eseguire un’analisi di stile basata sulla redditività di tre fondi d’investimento.

Programmazione lineare mista intera

La programmazione lineare mista intera espande il problema di programmazione lineare aggiungendo il vincolo in base a cui alcune o tutte le variabili della soluzione ottimali devono essere numeri interi.

Per alcuni problemi di ottimizzazione, le variabili non possono assumere valori frazionari. Per esempio, se una variabile rappresenta il numero di azioni da acquistare, allora può assumere solo valori interi. Analogamente, se una variabile rappresenta lo stato acceso/spento di un generatore, allora può assumere solo valori binari (0 o 1). Il problema di programmazione lineare mista intera consente di modellare questo comportamento aggiungendo il vincolo in base al quale, nella soluzione ottimale, tali variabili possono essere solo numeri interi.

Solutore Misto per la Programmazione Lineare in MATLAB 34:08
Impara ad utilizzare il nuovo solutore misto nella programmazione lineare, presente nella Release 2014a. Questo nuovo solutore ti permetterà di risolvere problemi di ottimizzazione nei quali alcune o tutte le variabili sono vincolate ad assumere valori interi.

Optimization Toolbox risolve i problemi di programmazione lineare mista intera utilizzando un algoritmo che:

  • esegue la pre-elaborazione della programmazione intera per restringere l’area praticabile.
  • applica piani di taglio per restringere l’area praticabile.
  • usa l’euristica per cercare soluzioni fattibili intere.
  • verifica che non esista una soluzione migliore, con un algoritmo di branch&bound che risolve una serie di problemi di rilassamento della programmazione lineare.
Utilizzo di un problema di programmazione intera per stabilire quali investimenti fare
Utilizzo di un problema di programmazione intera per stabilire quali investimenti fare

Distribuzione

I solutori di Optimization Toolbox possono essere utilizzati con MATLAB Compiler™ per creare strumenti di supporto alle decisioni che possano essere condivisi con gli utenti che non hanno MATLAB. Tali applicazioni standalone possono essere distribuite senza royalty a un numero illimitato di utenti finali. Gli algoritmi di ottimizzazione MATLAB possono essere integrati anche con altri linguaggi, come Java® e .NET, usando i prodotti MATLAB Builder™.

Ottimizzazione multiobiettivo

L’ottimizzazione multiobiettivo si concentra sul minimizzare le funzioni multiobiettivo soggette a una serie di vincoli. Optimization Toolbox fornisce le funzioni per la soluzione di due formulazioni di problemi di ottimizzazione multiobiettivo.

  • Il problema del raggiungimento degli obiettivi riguarda la riduzione del problema di una funzione vettoriale lineare o non lineare per raggiungere i valori obiettivo di un vettore obiettivo. L’importanza relativa degli obiettivi è indicata tramite un vettore di pesi. Il problema del raggiungimento degli obiettivi può anche essere soggetto a vincoli lineari e non lineari.
  • Il problema minimax riguarda la minimizzazione del valore di caso peggiore di una serie di funzioni multivariate eventualmente soggetto a vincoli lineari e non lineari.

Optimization Toolbox trasforma entrambi i tipi di problemi multiobiettivo in normali problemi di ottimizzazione vincolata, quindi li risolve secondo un approccio active-set.

Global Optimization Toolbox fornisce un ulteriore solutore multiobiettivo per problemi non-smooth.

Ottimizzazione multiobiettivo utilizzata per progettare un filtro passa-basso.
Ottimizzazione multiobiettivo utilizzata per progettare un filtro passa-basso.

Minimi quadrati non lineari, fitting dei dati ed equazioni non lineari

Optimization Toolbox è in grado di risolvere problemi di minimi quadrati non lineari, problemi di fitting dei dati ed equazioni non lineari.

Ottimizzazione lineare e non lineare dei minimi quadrati

Il toolbox utilizza due algoritmi per risolvere i problemi di minimi quadrati non lineari:

  • L’algoritmo active-set viene utilizzato per risolvere problemi con bound e disuguaglianze o uguaglianze lineari.
  • L’algoritmo riflessivo trust-region viene utilizzato per risolvere problemi su larga scala aventi solo vincoli di bound.

Il toolbox utilizza due algoritmi per risolvere i problemi di minimi quadrati non lineari:

  • l’algoritmo riflessivo trust-region implementa l’algoritmo di Levenberg-Marquardt utilizzando un approccio trust-region; viene utilizzato per problemi non vincolati e problemi con vincoli di contorno.
  • l’algoritmo di Levenberg-Marquardt implementa un metodo standard di Levenberg-Marquardt; viene utilizzato per problemi non vincolati.
Fitting di un’equazione trascendentale utilizzando i minimi quadrati non lineari
Fitting di un’equazione trascendentale utilizzando i minimi quadrati non lineari

Fitting dei dati

Il toolbox comprende anche un’interfaccia specializzata per problemi di fitting dei dati nei quali si vuole trovare il rappresentante più adatto di una famiglia di funzioni non lineari per un set di punti di dati. Il toolbox utilizza gli stessi algoritmi per risolvere i problemi di fitting dei dati utilizzati per i problemi di minimi quadrati non lineari.

Fitting di un’equazione esponenziale non lineare mediante la curva dei minimi quadrati.
Fitting di un’equazione esponenziale non lineare mediante la curva dei minimi quadrati.

Soluzione di equazioni non lineari

Optimization Toolbox implementa un algoritmo trust-region “dogleg” per risolvere un sistema di ‘n’ equazioni non lineari. Il toolbox è anche in grado di risolvere questo tipo di problemi utilizzando l’algoritmo riflessivo trust-region o l’algoritmo di Levenberg-Marquardt.

Soluzione di una funzione Rosenbrock <i>n</i>-dimensionale utilizzando il solutore per equazioni non lineari
Soluzione di una funzione Rosenbrock n-dimensionale utilizzando il solutore per equazioni non lineari

Calcolo parallelo e derivate

I solutori di Optimization Toolbox per i problemi non lineari usano metodi basati sul calcolo del gradiente per minimizzare o massimizzare un obiettivo. Le informazioni sul gradiente della funzione obiettivo possono essere stimate dal solutore usando differenze finite oppure possono essere fornite dall’utente al solutore.

Calcolo parallelo

Optimization Toolbox può essere utilizzato insieme a Parallel Computing Toolbox per risolvere problemi che possono trarre vantaggio dal calcolo parallelo. È possibile abilitare il supporto integrato del calcolo parallelo per ridurre i tempi necessari alla soluzione oppure definendo un’implementazione di calcolo parallelo personalizzata di un problema di ottimizzazione.

Il supporto integrato per il calcolo parallelo in Optimization Toolbox consente di velocizzare la fase di stima del gradiente in solutori specifici per problemi di ottimizzazione non lineare vincolata e per problemi multiobiettivo di raggiungimento degli obiettivi e minimax.

Accelerazione del tempo della soluzione di un problema elettrostatico utilizzando il supporto integrato per calcolo parallelo in un solutore di ottimizzazione non lineare La funzionalità integrata viene abilitata specificando l’opzione <tt>UseParallel</tt> (a sinistra) per la funzione obiettivo (al centro a destra) e la funzione vincolo (in basso a destra). La soluzione è mostrata in alto a destra.
Accelerazione del tempo della soluzione di un problema elettrostatico utilizzando il supporto integrato per calcolo parallelo in un solutore di ottimizzazione non lineare La funzionalità integrata viene abilitata specificando l’opzione UseParallel (a sinistra) per la funzione obiettivo (al centro a destra) e la funzione vincolo (in basso a destra). La soluzione è mostrata in alto a destra.

È possibile personalizzare un’implementazione di calcolo parallelo definendo esplicitamente il problema di ottimizzazione per l’utilizzo della funzionalità di calcolo parallelo. È possibile definire una funzione obiettivo o una funzione vincolo per utilizzare il calcolo parallelo, e ciò consente di ridurre il tempo necessario per valutare l’obiettivo o il vincolo.

Accelerazione del tempo di soluzione (in alto a destra) per il progetto di un sistema di sospensioni (in basso a sinistra e a destra) soggetto ad aleatorietà, personalizzando la funzione obiettivo con una semplice modifica di una riga del codice (in alto a sinistra)
Accelerazione del tempo di soluzione (in alto a destra) per il progetto di un sistema di sospensioni (in basso a sinistra e a destra) soggetto ad aleatorietà, personalizzando la funzione obiettivo con una semplice modifica di una riga del codice (in alto a sinistra)

Accelerare i problemi di ottimizzazione usando il calcolo parallelo 55:41
Risolvere più rapidamente i problemi di ottimizzazione con Parallel Computing Toolbox.

Come fornire le derivate

I solutori di Optimization Toolbox minimizzano le funzioni non lineari facendo una stima delle derivate parziali della funzione obiettivo usando le differenze finite. In alternativa è possibile definire funzioni che calcolino i valori delle derivate parziali, riducendo in modo significativo il sovraccarico dovuto alla fase di stima delle derivate.

Calcolare le derivate parziali di una funzione obiettivo può essere un compito noioso. Esprimendo simbolicamente il problema con Symbolic Math Toolbox™, le derivate parziali della funzione obiettivo possono essere calcolate automaticamente utilizzando funzioni integrate. Si può poi generare il codice MATLAB da usare con i solutori di Optimization Toolbox.

Ottimizzazione usando le derivate simboliche (articolo tecnico)

Prova Optimization Toolbox

Richiedi la versione di prova

Data Mining in ambiente MATLAB

Visualizza webinar