Ottimizzazione convessa - Problema di programmazione
Esistono quattro tipi di problemi di programmazione convessi:
Step 1 - $ min \: f \ left (x \ right) $, dove $ x \ in S $ e S è un insieme convesso non vuoto in $ \ mathbb {R} ^ n $ e $ f \ left (x \ right ) $ è una funzione convessa.
Step 2 - $ min \: f \ sinistra (x \ destra), x \ in \ mathbb {R} ^ n $ soggetto a
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ e $ g_i \ left (x \ right) $ è una funzione convessa.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ e $ g_i \ left (x \ right) $ è una funzione concava.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ e $ g_i \ left (x \ right) $ è una funzione lineare.
dove $ f \ left (x \ right) $ è una funzione convessa.
Step 3 - $ max \: f \ left (x \ right) $ dove $ x \ in S $ e S è un insieme convesso non vuoto in $ \ mathbb {R} ^ n $ e $ f \ left (x \ right) $ è una funzione concava.
Step 4 - $ min \: f \ left (x \ right) $, dove $ x \ in \ mathbb {R} ^ n $ soggetto a
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ e $ g_i \ left (x \ right) $ è una funzione convessa.
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ e $ g_i \ left (x \ right) $ è una funzione concava.
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ e $ g_i \ left (x \ right) $ è una funzione lineare.
dove $ f \ left (x \ right) $ è una funzione concava.
Cono di direzione fattibile
Sia S un insieme non vuoto in $ \ mathbb {R} ^ n $ e $ \ hat {x} \ in \: Closure \ left (S \ right) $, quindi il cono della direzione ammissibile di S in $ \ hat {x} $, indicato con D, è definito come $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
Ogni vettore $ d \ in D $ diverso da zero è chiamato direzione ammissibile.
Per una data funzione $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ il cono della direzione di miglioramento in $ \ hat {x} $ è indicato da F ed è dato da
$$ F = \ left \ {d: f \ left (\ hat {x} + \ lambda d \ right) \ leq f \ left (\ hat {x} \ right), \ forall \ lambda \ in \ left ( 0, \ delta \ right), \ delta> 0 \ right \} $$
Ogni direzione $ d \ in F $ è chiamata direzione di miglioramento o direzione di discesa di f in $ \ hat {x} $
Teorema
Necessary Condition
Considera il problema $ min f \ left (x \ right) $ tale che $ x \ in S $ dove S è un insieme non vuoto in $ \ mathbb {R} ^ n $. Supponiamo che f sia differenziabile in un punto $ \ hat {x} \ in S $. Se $ \ hat {x} $ è una soluzione ottimale locale, allora $ F_0 \ cap D = \ phi $ dove $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ e D è un cono di direzione ammissibile.
Sufficient Condition
Se $ F_0 \ cap D = \ phi $ f è una funzione pseudoconvessa in $ \ hat {x} $ ed esiste un vicinato di $ \ hat {x}, N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ tale che $ d = x- \ hat {x} \ in D $ per ogni $ x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $, quindi $ \ hat {x} $ è la soluzione ottimale locale.
Prova
Necessary Condition
Sia $ F_0 \ cap D \ neq \ phi $, cioè esiste un $ d \ in F_0 \ cap D $ tale che $ d \ in F_0 $ e $ d \ in D $
Poiché $ d \ in D $, quindi esiste $ \ delta_1> 0 $ tale che $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right). $
Da $ d \ in F_0 $, quindi $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
Quindi, esiste $ \ delta_2> 0 $ tale che $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ sinistra (0, \ delta_2 \ destra) $
Lascia $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
Quindi $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ sinistra (0, \ delta \ destra) $
Ma $ \ hat {x} $ è la soluzione ottimale locale.
Quindi è contraddizione.
Quindi $ F_0 \ cap D = \ phi $
Sufficient Condition
Sia $ F_0 \ cap D \ neq \ phi $ nd sia f una funzione pseudoconvessa.
Lascia che esista un quartiere di $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ tale che $ d = x- \ hat {x}, \ forall x \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $
Sia $ \ hat {x} $ non una soluzione ottimale locale.
Quindi, esiste $ \ bar {x} \ in S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ tale che $ f \ left (\ bar {x} \ right) <f \ left ( \ hat {x} \ right) $
Per ipotesi su $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ in D $
Per pseudoconvesso di f,
$$ f \ left (\ hat {x} \ right)> f \ left (\ bar {x} \ right) \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (\ bar {x} - \ hat {x} \ right) <0 $$
$ \ Rightarrow \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
$ \ Freccia destra d \ in F_0 $
quindi $ F_0 \ cap D \ neq \ phi $
che è una contraddizione.
Quindi, $ \ hat {x} $ è la soluzione ottimale locale.
Considera il seguente problema: $ min \: f \ left (x \ right) $ dove $ x \ in X $ tale che $ g_x \ left (x \ right) \ leq 0, i = 1,2, ..., m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ e X è un insieme aperto in $ \ mathbb {R} ^ n $
Sia $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
Lascia $ \ hat {x} \ in X $, quindi $ M = \ left \ {1,2, ..., m \ right \} $
Sia $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ dove I è chiamato index set per tutti i vincoli attivi in $ \ hat {x } $
Sia $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ dove J è chiamato index set per tutti i vincoli attivi in $ \ hat {x } $.
Lascia $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
Sia $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
oppure $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
Lemma
Se $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0, \ forall i \ in I \ right \} $ e X è un insieme aperto non vuoto in $ \ mathbb {R } ^ n $. Siano $ \ hat {x} \ in S $ e $ g_i $ diversi in $ \ hat {x}, i \ in I $ e $ g_i $ dove $ i \ in J $ sono continui in $ \ hat {x } $, quindi $ G_0 \ subseteq D $.
Prova
Sia $ d \ in G_0 $
Poiché $ \ hat {x} \ in X $ e X è un insieme aperto, quindi esiste $ \ delta_1> 0 $ tale che $ \ hat {x} + \ lambda d \ in X $ per $ \ lambda \ in \ sinistra (0, \ delta_1 \ destra) $
Inoltre, poiché $ g_ \ hat {x} <0 $ e $ g_i $ sono continui in $ \ hat {x}, \ forall i \ in J $, esiste $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
Poiché $ d \ in G_0 $, quindi, $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ quindi esiste $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $, per $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J $
Lascia $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
quindi, $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M $
$ \ Rightarrow \ hat {x} + \ lambda d \ in S $
$ \ Freccia destra d \ in D $
$ \ Rightarrow G_0 \ subseteq D $
Quindi dimostrato.
Teorema
Necessary Condition
Siano $ f $ e $ g_i, i \ in I $, sono diversi in $ \ hat {x} \ in S, $ e $ g_j $ sono continui in $ \ hat {x} \ in S $. Se $ \ hat {x} $ è il minimo locale di $ S $, allora $ F_0 \ cap G_0 = \ phi $.
Sufficient Condition
Se $ F_0 \ cap G_0 = \ phi $ ef è una funzione pseudoconvessa in $ \ left (\ hat {x}, g_i 9x \ right), i \ in I $ sono strettamente pseudoconvesse su alcuni $ \ varepsilon $ - vicinanze di $ \ hat {x}, \ hat {x} $ è una soluzione ottimale locale.
Osservazioni
Sia $ \ hat {x} $ un punto ammissibile tale che $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $, quindi $ F_0 = \ phi $. Quindi, $ F_0 \ cap G_0 = \ phi $ ma $ \ hat {x} $ non è una soluzione ottimale
Ma se $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $, allora $ G_0 = \ phi $, quindi $ F_0 \ cap G_0 = \ phi $
Considera il problema: min $ f \ sinistra (x \ destra) $ tale che $ g \ sinistra (x \ destra) = 0 $.
Poiché $ g \ sinistra (x \ destra) = 0 $, quindi $ g_1 \ sinistra (x \ destra) = g \ sinistra (x \ destra) <0 $ e $ g_2 \ sinistra (x \ destra) = - g \ sinistra (x \ destra) \ leq 0 $.
Sia $ \ hat {x} \ in S $, quindi $ g_1 \ left (\ hat {x} \ right) = 0 $ e $ g_2 \ left (\ hat {x} \ right) = 0 $.
Ma $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
Quindi, $ G_0 = \ phi $ e $ F_0 \ cap G_0 = \ phi $.