การเพิ่มประสิทธิภาพการนูน - เงื่อนไขของ Fritz-John

เงื่อนไขที่จำเป็น

ทฤษฎีบท

พิจารณาปัญหา - $ min f \ left (x \ right) $ เช่น $ x \ in X $ โดยที่ X เป็นชุดเปิดใน $ \ mathbb {R} ^ n $ และให้ $ g_i \ left (x \ right) \ leq 0, \ สำหรับ i = 1,2, .... m $.

ให้ $ f: X \ rightarrow \ mathbb {R} $ และ $ g_i: X \ rightarrow \ mathbb {R} $

ให้ $ \ hat {x} $ เป็นทางออกที่เป็นไปได้และปล่อยให้ f และ $ g_i, i \ in I $ แตกต่างกันได้ที่ $ \ hat {x} $ และ $ g_i, i \ in J $ ต่อเนื่องที่ $ \ hat { x} $.

ถ้า $ \ hat {x} $ แก้ปัญหาข้างต้นในเครื่องแสดงว่ามี $ u_0, u_i \ in \ mathbb {R} อยู่ใน I $ เช่นนั้น $ u_0 \ bigtriangledown f \ left (\ hat {x} \ ขวา) + \ displaystyle \ sum \ LIMIT_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) $ = 0

โดยที่ $ u_0, u_i \ geq 0, i \ in I $ และ $ \ left (u_0, u_I \ right) \ neq \ left (0,0 \ right) $

นอกจากนี้หาก $ g_i, i \ in J $ ยังแตกต่างกันได้ที่ $ \ hat {x} $ เงื่อนไขข้างต้นสามารถเขียนเป็น -

$ 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 $

หมายเหตุ

• $ u_i $ เรียกว่าตัวคูณ Lagrangian

• เงื่อนไขที่ $ \ hat {x} $ เป็นไปได้กับปัญหาที่กำหนดเรียกว่าเงื่อนไขที่เป็นไปได้เบื้องต้น

• ข้อกำหนด $ u_0 \ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ LIMIT_ {i = 1} ^ m ui \ bigtriangledown g_i \ left (x \ right) = 0 $ เรียกว่า dual feasibility เงื่อนไข.

• เงื่อนไข $ u_ig_i \ left (\ hat {x} \ right) = 0, i = 1, 2, ... m $ เรียกว่าเงื่อนไขความหย่อนยานฟรี เงื่อนไขนี้ต้องใช้ $ u_i = 0, i \ in J $

• เงื่อนไขที่เป็นไปได้เบื้องต้นร่วมกันเงื่อนไขความเป็นไปได้แบบคู่และความหย่อนยานฟรีเรียกว่าเงื่อนไข Fritz-John

เงื่อนไขที่เพียงพอ

ทฤษฎีบท

หากมี $ \ varepsilon $ -neighbourhood ของ $ \ hat {x} N_ \ varepsilon \ left (\ hat {x} \ right), \ varepsilon> 0 $ นั่นแสดงว่า f เป็น pseudoconvex มากกว่า $ N_ \ varepsilon \ left ( \ hat {x} \ right) \ cap S $ และ $ g_i, i \ in I $ เป็น pseudoconvex อย่างเคร่งครัดมากกว่า $ N_ \ varepsilon \ left (\ hat {x} \ right) \ cap S $ แล้ว $ \ hat { x} $ เป็นวิธีแก้ปัญหาที่ดีที่สุดในท้องถิ่นสำหรับปัญหาที่อธิบายข้างต้น ถ้า f เป็น pseudoconvex ที่ $ \ hat {x} $ และถ้า $ g_i i \ in I $ มีทั้งฟังก์ชัน pseudoconvex และ quasiconvex อย่างเคร่งครัดที่ $ \ hat {x} \ hat {x} $ เป็นวิธีแก้ปัญหาที่ดีที่สุดระดับโลก อธิบายไว้ข้างต้น.

ตัวอย่าง

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

  เช่นนั้น $ x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 5, x_1 + 2x_2 \ leq 4, x_1, x_2 \ geq 0 $ และ $ \ hat {x} = \ left (2 , 1 \ right) $

  ให้ $ 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 $ และ $ g_4 \ left (x_1, x_2 \ right) = -x_2 $

  ดังนั้นข้อ จำกัด ข้างต้นสามารถเขียนเป็น -

  $ 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 $ และ

  $ g_4 \ left (x_1, x_2 \ right) \ leq 0 $ ดังนั้น $ I = \ left \ {1,2 \ right \} $ ดังนั้น $ 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 ) $ และ $ \ bigtriangledown g_2 \ left (\ hat {x} \ right) = \ left (1,2 \ right) $

  ดังนั้นเราจึงได้รับค่าเหล่านี้ในเงื่อนไขแรกของเงื่อนไข Fritz-John

  $ u_0 = \ frac {3} {2} u_2, \: \: u_1 = \ frac {1} {2} u_2, $ และให้ $ u_2 = 1 $ ดังนั้น $ u_0 = \ frac {3} {2} , \: \: u_1 = \ frac {1} {2} $

  ดังนั้นเงื่อนไขของ Fritz John จึงพอใจ

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

  เช่นนั้น $ x_2- \ left (1-x_1 \ right) ^ 3 \ leq 0 $,

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

  ให้ $ 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 $

  ดังนั้นข้อ จำกัด ข้างต้นจึงสามารถปรับเปลี่ยนเป็น -

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

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

  ดังนั้น $ 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) $ และ $ g_2 \ left (\ hat {x} \ right) = \ left (0, -1 \ right ) $

  ดังนั้นเราจึงได้รับค่าเหล่านี้ในเงื่อนไขแรกของเงื่อนไข Fritz-John

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

  ดังนั้นเงื่อนไขของ Fritz John จึงพอใจ