Ottimizzazione convessa - Condizioni Fritz-John

Condizioni necessarie

Teorema

Considera il problema: $ min f \ left (x \ right) $ tale che $ x \ in X $ dove X è un insieme aperto in $ \ mathbb {R} ^ n $ e lascia $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Siano $ f: X \ rightarrow \ mathbb {R} $ e $ g_i: X \ rightarrow \ mathbb {R} $

Sia $ \ hat {x} $ una soluzione fattibile e siano f e $ g_i, i \ in I $ differenziabili in $ \ hat {x} $ e $ g_i, i \ in J $ sono continui in $ \ hat { x} $.

Se $ \ hat {x} $ risolve il problema precedente localmente, allora esiste $ u_0, u_i \ in \ mathbb {R}, i \ in I $ tale che $ u_0 \ bigtriangledown f \ left (\ hat {x} \ destra) + \ displaystyle \ sum \ limits_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

dove $ u_0, u_i \ geq 0, i \ in I $ e $ \ sinistra (u_0, u_I \ destra) \ neq \ sinistra (0,0 \ destra) $

Inoltre, se $ g_i, i \ in J $ sono anche differenziabili in $ \ hat {x} $, allora le condizioni sopra possono essere scritte come -

$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0 $

$ u_ig_i \ left (\ hat {x} \ right) $ = 0

$ u_0, u_i \ geq 0, \ forall i = 1,2, ...., m $

$ \ left (u_0, u \ right) \ neq \ left (0,0 \ right), u = \ left (u_1, u_2, s, u_m \ right) \ in \ mathbb {R} ^ m $

Osservazioni

• $ u_i $ sono chiamati moltiplicatori lagrangiani.

• La condizione che $ \ hat {x} $ sia fattibile per il problema dato è chiamata condizione ammissibile primaria.

• Il requisito $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limits_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ è chiamato doppia fattibilità condizione.

• La condizione $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ è chiamata condizione di lentezza complementare. Questa condizione richiede $ u_i = 0, i \ in J $

• Insieme, la condizione fattibile primaria, la condizione di doppia fattibilità e la lentezza complementare sono chiamate Condizioni di Fritz-John.

Condizioni sufficienti

Teorema

Se esiste un $ \ varepsilon $ -neighbourhood di $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ tale che f è pseudoconvesso su $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ e $ g_i, i \ in I $ sono rigorosamente pseudoconvessi su $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, quindi $ \ hat { x} $ è la soluzione ottimale locale al problema descritto sopra. Se f è pseudoconvesso in $ \ hat {x} $ e se $ g_i, i \ in I $ sono entrambi strettamente pseudoconvessi e quasiconvessi in $ \ hat {x}, \ hat {x} $ è la soluzione ottimale globale al problema descritto sopra.

Esempio

• $ min \: f \ sinistra (x_1, x_2 \ destra) = \ sinistra (x_1-3 \ destra) ^ 2 + \ sinistra (x_2-2 \ destra) ^ 2 $

  tale che $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ e $ \ hat {x} = \ left (2 , 1 \ destra) $

  Lascia $ g_1 \ left (x_1, x_2 \ right) = x_ {1} ^ {2} + x_ {2} ^ {2} -5, $

  $ g_2 \ sinistra (x_1, x_2 \ destra) = x_1 + 2x_2-4, $

  $ g_3 \ sinistra (x_1, x_2 \ destra) = - x_1 $ e $ g_4 \ sinistra (x_1, x_2 \ destra) = -x_2 $.

  Pertanto i vincoli di cui sopra possono essere scritti come:

  $ g_1 \ sinistra (x_1, x_2 \ destra) \ leq 0, $

  $ g_2 \ sinistra (x_1, x_2 \ destra) \ leq 0, $

  $ g_3 \ sinistra (x_1, x_2 \ destra) \ leq 0 $ e

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Quindi, $ I = \ left \ {1,2 \ right \} $ quindi, $ u_3 = 0, u_4 = 0 $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (2, -2 \ right), \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (4,2 \ destra ) $ e $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  Mettendo quindi questi valori nella prima condizione delle condizioni di Fritz-John, otteniamo:

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ e lascia $ u_2 = 1 $, quindi $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Così le condizioni di Fritz John sono soddisfatte.

• $ min f \ sinistra (x_1, x_2 \ destra) = - x_1 $.

  tale che $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

  $ -x_2 \ leq 0 $ e $ \ hat {x} = \ left (1,0 \ right) $

  Lascia $ g_1 \ sinistra (x_1, x_2 \ destra) = x_2- \ sinistra (1-x_1 \ destra) ^ 3 $,

  $ g_2 \ sinistra (x_1, x_2 \ destra) = - x_2 $

  Pertanto i vincoli di cui sopra possono essere scritti come:

  $ g_1 \ sinistra (x_1, x_2 \ destra) \ leq 0, $

  $ g_2 \ sinistra (x_1, x_2 \ destra) \ leq 0, $

  Quindi, $ I = \ left \ {1,2 \ right \} $

  $ \ bigtriangledown f \ left (\ hat {x} \ right) = \ left (-1,0 \ right) $

  $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = \ left (0,1 \ right) $ e $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right ) $

  Mettendo quindi questi valori nella prima condizione delle condizioni di Fritz-John, otteniamo:

  $ u_0 = 0, \: \: u_1 = u_2 = a> 0 $

  Così le condizioni di Fritz John sono soddisfatte.