Konvexe Optimierung - Fritz-John-Bedingungen

Notwendige Bedingungen

Satz

Betrachten Sie das Problem - $ min f \ left (x \ right) $ so, dass $ x \ in X $ wobei X eine offene Menge in $ \ mathbb {R} ^ n $ ist, und lassen Sie $ g_i \ left (x \ right) \ leq 0, \ forall i = 1,2, .... m $.

Sei $ f: X \ rightarrow \ mathbb {R} $ und $ g_i: X \ rightarrow \ mathbb {R} $

Sei $ \ hat {x} $ eine praktikable Lösung und sei f und $ g_i, i \ in I $ sind differenzierbar bei $ \ hat {x} $ und $ g_i, i \ in J $ sind stetig bei $ \ hat { x} $.

Wenn $ \ hat {x} $ das obige Problem lokal löst, gibt es $ u_0, u_i \ in \ mathbb {R}, i \ in I $, so dass $ u_0 \ bigtriangledown f \ left (\ hat {x} \ rechts) + \ displaystyle \ sum \ limit_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

Dabei ist $ u_0, u_i \ geq 0, i \ in I $ und $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

Wenn $ g_i, i \ in J $ auch bei $ \ hat {x} $ differenzierbar sind, können die obigen Bedingungen wie folgt geschrieben werden:

$ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {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 $

Bemerkungen

• $ u_i $ heißen Lagrange-Multiplikatoren.

• Die Bedingung, dass $ \ hat {x} $ für das gegebene Problem realisierbar ist, wird als primär realisierbare Bedingung bezeichnet.

• Die Anforderung $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ wird als doppelte Machbarkeit bezeichnet Bedingung.

• Die Bedingung $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ wird als komplementäre Schlaffheitsbedingung bezeichnet. Diese Bedingung erfordert $ u_i = 0, i \ in J $

• Zusammen werden die ursprüngliche Durchführbarkeitsbedingung, die doppelte Durchführbarkeitsbedingung und die komplementäre Schlaffheit als Fritz-John-Bedingungen bezeichnet.

Ausreichende Bedingungen

Satz

Wenn es eine $ \ varepsilon $ -Nachbarschaft von $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right) gibt, \ varepsilon> 0 $, so dass f pseudokonvex über $ N_ \ varepsilon \ left ist ( \ hat {x} \ right) \ cap S $ und $ g_i, i \ in I $ sind streng pseudokonvex über $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $, dann $ \ hat { x} $ ist eine lokal optimale Lösung für das oben beschriebene Problem. Wenn f bei $ \ hat {x} $ pseudokonvex ist und wenn $ g_i, i \ in I $ bei $ \ hat {x} sowohl streng pseudokonvex als auch quasikonvex sind, ist \ hat {x} $ eine globale optimale Lösung für das Problem oben beschrieben.

Beispiel

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

  so dass $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ und $ \ hat {x} = \ left (2 , 1 \ rechts) $

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

  $ g_2 \ left (x_1, x_2 \ right) = x_1 + 2x_2-4, $

  $ g_3 \ left (x_1, x_2 \ right) = - x_1 $ und $ g_4 \ left (x_1, x_2 \ right) = -x_2 $.

  Somit können die obigen Einschränkungen wie folgt geschrieben werden:

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_3 \ left (x_1, x_2 \ right) \ leq 0 $ und

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ Somit ist $ I = \ left \ {1,2 \ right \} $, also $ 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 \ right) ) $ und $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  Wenn wir diese Werte in die erste Bedingung der Fritz-John-Bedingungen setzen, erhalten wir -

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ und lass $ u_2 = 1 $, daher $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  Damit sind die Bedingungen von Fritz John erfüllt.

• $ min f \ left (x_1, x_2 \ right) = - x_1 $.

  so dass $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

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

  Sei $ g_1 \ left (x_1, x_2 \ right) = x_2- \ left (1-x_1 \ right) ^ 3 $,

  $ g_2 \ left (x_1, x_2 \ right) = - x_2 $

  Somit können die obigen Einschränkungen wie folgt geschrieben werden:

  $ g_1 \ left (x_1, x_2 \ right) \ leq 0, $

  $ g_2 \ left (x_1, x_2 \ right) \ leq 0, $

  Somit ist $ 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) $ und $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right) ) $

  Wenn wir diese Werte in die erste Bedingung der Fritz-John-Bedingungen setzen, erhalten wir -

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

  Damit sind die Bedingungen von Fritz John erfüllt.