Ottimizzazione convessa: differenze tra le versioni
Etichetta: Editor wikitesto 2017 |
→Bibliografia: +1 |
||
| Riga 1: | Riga 1: | ||
L{{'}}''' |
L{{'}}'''ottimizzazione convessa''' è un sottocampo dell'[[Ottimizzazione (matematica)|ottimizzazione matematica]] che studia il problema della minimizzazione delle [[funzione convessa|funzioni convesse]] (o, in modo equivalente, la massimizzazione di funzioni concave) su [[insieme convesso|insiemi convessi]]. Molte classi di problemi di ottimizzazione convessa ammettono algoritmi con [[Complessità temporale|tempo polinomiale]] dove l'ottimizzazione matematica in generale è [[NP-hard]].<ref> |
||
{{cita pubblicazione |
{{cita pubblicazione |
||
|cognome= Murty |
|cognome= Murty |
||
| Riga 25: | Riga 25: | ||
== Applicazioni == |
== Applicazioni == |
||
L'ottimizzazione convessa ha applicazioni in diverse discipline come nei sistemi di controllo, stima ed elaborazione dei segnali, nella progettazione di circuiti elettronici, e nelle reti, nell'analisi di dati e nella modellazione, in finanza e in statistica |
L'ottimizzazione convessa ha applicazioni in diverse discipline come nei sistemi di controllo, stima ed elaborazione dei segnali, nella progettazione di circuiti elettronici, e nelle reti, nell'analisi di dati e nella modellazione, in finanza e in statistica<ref>{{Cita|Boyd e Vandenberghe|p. xii}}.</ref>. Con i recenti avanzamenti nel calcolo e negli algoritmi di ottimizzazione, la programmazione convessa è quasi semplice come la [[programmazione lineare]]. |
||
== Note == |
== Note == |
||
| Riga 31: | Riga 31: | ||
== Bibliografia == |
== Bibliografia == |
||
* {{Cita libro|autore=Stephen Boyd|autore2=Lieven Vandenberghe|titolo=Convex Optimization|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|annooriginale=2004|anno=2009|editore=Cambridge University Press|lingua=en|cid=Boyd e Vandenberghe}} |
* {{Cita libro|autore=Stephen Boyd|autore2=Lieven Vandenberghe|titolo=Convex Optimization|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|annooriginale=2004|anno=2009|editore=Cambridge University Press|lingua=en|cid=Boyd e Vandenberghe}} |
||
* {{cita libro|autore=Peter W. Christensen|autore2=Anders Klarbring|anno=2008|titolo=An introduction to structural optimization|editore=Springer Science & Business Media|lingua=en|cid=Christensen e Klarbring|ISBN=9781402086663}} |
|||
== Voci correlate == |
== Voci correlate == |
||
Versione delle 18:29, 5 mar 2024
L'ottimizzazione convessa è un sottocampo dell'ottimizzazione matematica che studia il problema della minimizzazione delle funzioni convesse (o, in modo equivalente, la massimizzazione di funzioni concave) su insiemi convessi. Molte classi di problemi di ottimizzazione convessa ammettono algoritmi con tempo polinomiale dove l'ottimizzazione matematica in generale è NP-hard.[1][2][3]
Proprietà
La convessità induce alcune proprietà interessanti che semplificano l’analisi.
- Un ottimo locale è anche un ottimo globale.[4]
- Se la funzione obiettivo è strettamente convessa, allora esiste al più un ottimo.[5]
La prima proprietà si dimostra per assurdo. Assumendo l'esistenza di un ottimo locale e di un ottimo globale , si impone la condizione di convessità per mostrare che non esiste un intorno di raggio nel quale può soddisfare la definizione di ottimo locale.
Applicazioni
L'ottimizzazione convessa ha applicazioni in diverse discipline come nei sistemi di controllo, stima ed elaborazione dei segnali, nella progettazione di circuiti elettronici, e nelle reti, nell'analisi di dati e nella modellazione, in finanza e in statistica[6]. Con i recenti avanzamenti nel calcolo e negli algoritmi di ottimizzazione, la programmazione convessa è quasi semplice come la programmazione lineare.
Note
- ^ Katta Murty e Santosh Kabadi, Some NP-complete problems in quadratic and nonlinear programming, in Mathematical Programming, vol. 39, n. 2, 1987, pp. 117–129, DOI:10.1007/BF02592948.
- ^ Sahni, S. "Computationally related problems," in SIAM Journal on Computing, 3, 262--279, 1974.
- ^ Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.
- ^ Boyd e Vandenberghe, p. 138.
- ^ Boyd e Vandenberghe, p. 137
- ^ Boyd e Vandenberghe, p. xii.
Bibliografia
- (EN) Stephen Boyd e Lieven Vandenberghe, Convex Optimization (PDF), Cambridge University Press, 2009 [2004].
- (EN) Peter W. Christensen e Anders Klarbring, An introduction to structural optimization, Springer Science & Business Media, 2008, ISBN 9781402086663.
Voci correlate
Altri progetti
Wikimedia Commons contiene immagini o altri file su ottimizzazione convessa
Collegamenti esterni
- EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
- 6.253: Convex Analysis and Optimization, an MIT OCW course homepage
- Brian Borchers, An overview of software for convex optimization
