Ottimizzazione convessa
L' ottimizzazione convessa è una sotto-disciplina dell'ottimizzazione matematica , in cui il criterio da minimizzare è convesso e l' insieme ammissibile è convesso . Questi problemi sono più facili da analizzare e risolvere rispetto ai problemi di ottimizzazione non convessa, sebbene possano essere NP-hard (questo è il caso dell'ottimizzazione copositiva ).
La teoria per analizzare questi problemi non richiede la differenziabilità delle funzioni. Questa generalità è motivata dal fatto che alcuni metodi di costruzione di problemi di ottimizzazione convessa portano a problemi non differenziabili ( funzione marginale , dualizzazione dei vincoli, ecc .). Se questa generalità è un vantaggio, consentendo di prendere in considerazione più problemi, anche l'approccio alla teoria è più difficile.
L'ottimizzazione convessa si basa sull'analisi convessa .
Background e introduzione
L'ottimizzazione convessa è un tipo di ottimizzazione matematica , cioè una disciplina che studia problemi del tipo: ottimizzare una data funzione in un dato spazio. Generalizza l'ottimizzazione lineare e l' ottimizzazione semi-definita positiva , ma anche l' ottimizzazione conica e l' ottimizzazione copositiva .
Definizioni del problema
Formulazione generale
Sia uno spazio vettoriale. Un problema di ottimizzazione convessa consiste nel minimizzare una funzione convessa su cui scriviamo in uno dei seguenti modi:
E{\ displaystyle \ mathbb {E}} f:E→R¯: =R∪{-∞,+∞}{\ displaystyle f: \ mathbb {E} \ to {\ bar {\ mathbb {R}}}: = \ mathbb {R} \ cup \ {- \ infty, + \ infty \}}E{\ displaystyle \ mathbb {E}}
infX∈Ef(X)oinf{f(X):X∈E}oinff(E)o{inff(X)X∈E.{\ displaystyle \ inf _ {x \ in \ mathbb {E}} \, f (x) \ quad {\ mbox {o}} \ quad \ inf \, \ {f (x): x \ in \ mathbb { E} \} \ quad {\ mbox {o}} \ quad \ inf \, f (\ mathbb {E}) \ quad {\ mbox {o}} \ quad \ left \ {{\ begin {array} {l } \ inf \, f (x) \\ x \ in \ mathbb {E}. \ end {array}} \ right.}
Se notiamo
A≡domf: ={X∈E:f(X)<+∞}{\ displaystyle {\ mathcal {A}} \ equiv \ operatorname {dom} f: = \ {x \ in \ mathbb {E}: f (x) <+ \ infty \}}
il dominio (effettivo) di , il problema è identico a quello di minimizzare su :
f{\ displaystyle f}f{\ displaystyle f}A{\ displaystyle {\ mathcal {A}}}
infX∈Af(X).{\ displaystyle \ inf _ {x \ in {\ mathcal {A}}} \, f (x).}
Se , vale a dire, se questo termine è ancora valido, poiché per convenzione . L'interesse di avere una funzione che possa assumere il valore è quindi quello di introdurre vincoli nel problema di minimizzazione (si costringe ad essere nella soluzione del problema ).
A=∅{\ displaystyle {\ mathcal {A}} = \ varnothing}f≡+∞{\ displaystyle f \ equiv + \ infty}inff(∅)=+∞{\ displaystyle \ inf f (\ varnothing) = + \ infty}f{\ displaystyle f}+∞{\ displaystyle + \ infty}A{\ displaystyle {\ mathcal {A}}}
Soluzione
Una soluzione (globale) al problema è tale
inf{f(X):X∈E}{\ displaystyle \ inf \ {f (x): x \ in \ mathbb {E} \}}X¯∈E{\ displaystyle {\ bar {x}} \ in \ mathbb {E}}
∀X∈E:f(X¯)≤f(X).{\ displaystyle \ forall \, x \ in \ mathbb {E}: \ quad f ({\ bar {x}}) \ leq f (x).}
Chiaramente, se prende il valore , abbiamo ; e se non è identicamente uguale a , abbiamo .
f{\ displaystyle f}-∞{\ displaystyle - \ infty}f(X¯)=-∞{\ displaystyle f ({\ bar {x}}) = - \ infty}f{\ displaystyle f}+∞{\ displaystyle + \ infty}f(X¯)<+∞{\ displaystyle f ({\ bar {x}}) <+ \ infty}
If è uno spazio vettoriale topologico , è una soluzione locale al problema se
E{\ displaystyle \ mathbb {E}}X¯{\ displaystyle {\ bar {x}}}inf{f(X):X∈E}{\ displaystyle \ inf \ {f (x): x \ in \ mathbb {E} \}}
∃V quartiere di X¯,∀X∈V:f(X¯)≤f(X).{\ displaystyle \ esiste \, V ~ {\ mbox {quartiere di}} ~ {\ bar {x}}, \ quad \ forall \, x \ in V: \ quad f ({\ bar {x}}) \ leq f (x).}
In realtà una soluzione locale è una soluzione globale nel senso precedente.
Soluzioni di un problema di ottimizzazione convessa -
- L'insieme di soluzioni di un problema di ottimizzazione convesso è convesso .
- Se è strettamente convesso , il problema di ottimizzazione convesso ha al massimo una soluzione.f{\ displaystyle f}
- Se è uno spazio vettoriale topologico e se è una soluzione locale di un problema di ottimizzazione convessa, allora è una soluzione globale del problema.E{\ displaystyle \ mathbb {E}}X¯{\ displaystyle {\ bar {x}}}X¯{\ displaystyle {\ bar {x}}}
Vincoli funzionali
Invece di dare il valore infinito al criterio al di fuori dell'insieme ammissibile, si possono specificare esplicitamente i vincoli da applicare. Il problema è scritto ad esempio come segue
{inff(X)X∈VSAX=bvs(X)⩽0,{\ displaystyle \ left \ {{\ begin {array} {l} \ inf \, f (x) \\ x \ in C \\ Ax = b \\ c (x) \ leqslant 0, \ end {array} } \ giusto.}
in cui minimizziamo una funzione a valori finiti e l'ignoto deve
f:X∈E↦f(X)∈R{\ Displaystyle f: x \ in \ mathbb {E} \ mapsto f (x) \ in \ mathbb {R}}X∈E{\ displaystyle x \ in \ mathbb {E}}
- appartengono a un insieme convesso di ,VS{\ displaystyle C}E{\ displaystyle \ mathbb {E}}
- controlla un vincolo affine ( è una mappa lineare tra e un altro spazio vettoriale e ) eAX=b{\ displaystyle Ax = b}A:E→F{\ displaystyle A: \ mathbb {E} \ to \ mathbb {F}}E{\ displaystyle \ mathbb {E}}F{\ displaystyle \ mathbb {F}}b∈F{\ displaystyle b \ in \ mathbb {F}}
- verificare un numero finito di vincoli funzionali convessi dati da una funzione le cui componenti sono convesse e la disuguaglianza del vettore deve essere intesa componente per componente (è equivalente ai vincoli di disuguaglianza per ).vs:E→Rm{\ displaystyle c: \ mathbb {E} \ to \ mathbb {R} ^ {m}}m{\ displaystyle m}vs(X)⩽0{\ displaystyle c (x) \ leqslant 0}m{\ displaystyle m}vsio(X)⩽0{\ displaystyle c_ {i} (x) \ leqslant 0}io∈[[1,m]]{\ displaystyle i \ in [\! [1, m] \!]}
La serie ammissibile di questo problema è convessa e è scritta
X: ={X∈E:X∈VS, AX=b, vs(X)⩽0}.{\ displaystyle X: = \ {x \ in \ mathbb {E}: x \ in C, ~ Ax = b, ~ c (x) \ leqslant 0 \}.}
Il problema è abbastanza convesso poiché si tratta di minimizzare la funzione definita da
E{\ displaystyle \ mathbb {E}}f~:X∈E↦f~(X)∈R¯{\ displaystyle {\ tilde {f}}: x \ in \ mathbb {E} \ mapsto {\ tilde {f}} (x) \ in {\ bar {\ mathbb {R}}}}
f~(X)={f(X)Se X∈X+∞altrimenti,{\ displaystyle {\ tilde {f}} (x) = \ left \ {{\ begin {array} {ll} f (x) & {\ mbox {si}} ~ x \ in X \\ + \ infty & {\ mbox {altrimenti}}, \ end {array}} \ right.}
che è una funzione convessa .
Condizioni di ottimalità
Condizione generale
La condizione di ottimalità corrispondente alla formulazione generale del problema è la seguente. Indichiamo il sub-differenziale di in un punto tale che .
∂f(X){\ Displaystyle \ partial f (x)}f{\ displaystyle f}X{\ displaystyle x}f(X)∈R{\ displaystyle f (x) \ in \ mathbb {R}}
Condizione generale di ottimalità - Se è tale , allora è la soluzione del problema convesso se e solo se .
X¯∈E{\ displaystyle {\ bar {x}} \ in \ mathbb {E}}f(X¯)∈R{\ displaystyle f ({\ bar {x}}) \ in \ mathbb {R}}X¯{\ displaystyle {\ bar {x}}}inf{f(X):X∈E}{\ displaystyle \ inf \ {f (x): x \ in \ mathbb {E} \}}0∈∂f(X¯){\ displaystyle 0 \ in \ partial f ({\ bar {x}})}
Caso di vincoli funzionali
Ci interessano qui le condizioni di ottimalità per il problema espresso mediante vincoli funzionali .
Note e riferimenti
-
Stephen Boyd e Lieven Vandenberghe, Convex Optimization , Cambridge University Press ,2009( leggi online ).
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">