การเพิ่มประสิทธิภาพแบบนูน - ปัญหาการเขียนโปรแกรม
ปัญหาการเขียนโปรแกรมนูนมีสี่ประเภท -
Step 1 - $ min \: f \ left (x \ right) $ โดยที่ $ x \ ใน S $ และ S เป็นชุดนูนที่ไม่ว่างใน $ \ mathbb {R} ^ n $ และ $ f \ left (x \ right ) $ คือฟังก์ชันนูน
Step 2 - $ min \: f \ left (x \ right), x \ in \ mathbb {R} ^ n $ ขึ้นอยู่กับ
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ และ $ g_i \ left (x \ right) $ คือฟังก์ชันนูน
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ และ $ g_i \ left (x \ right) $ เป็นฟังก์ชันเว้า
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ และ $ g_i \ left (x \ right) $ เป็นฟังก์ชันเชิงเส้น
โดยที่ $ f \ left (x \ right) $ คือ fucntion แบบนูน
Step 3 - $ max \: f \ left (x \ right) $ โดยที่ $ x \ ใน S $ และ S เป็นชุดนูนที่ไม่ว่างใน $ \ mathbb {R} ^ n $ และ $ f \ left (x \ right) $ คือฟังก์ชันเว้า
Step 4 - $ min \: f \ left (x \ right) $ โดยที่ $ x \ in \ mathbb {R} ^ n $ ขึ้นอยู่กับ
$ g_i \ left (x \ right) \ geq 0, 1 \ leq m_1 $ และ $ g_i \ left (x \ right) $ คือฟังก์ชันนูน
$ g_i \ left (x \ right) \ leq 0, m_1 + 1 \ leq m_2 $ และ $ g_i \ left (x \ right) $ เป็นฟังก์ชันเว้า
$ g_i \ left (x \ right) = 0, m_2 + 1 \ leq m $ และ $ g_i \ left (x \ right) $ เป็นฟังก์ชันเชิงเส้น
โดยที่ $ f \ left (x \ right) $ เป็นฟังก์ชันเว้า
กรวยของทิศทางที่เป็นไปได้
ให้ S เป็นชุดที่ไม่ว่างใน $ \ mathbb {R} ^ n $ และให้ $ \ hat {x} \ in \: Closure \ left (S \ right) $ จากนั้นกรวยของทิศทางที่เป็นไปได้ของ S ที่ $ \ hat {x} $ แสดงโดย D กำหนดเป็น $ D = \ left \ {d: d \ neq 0, \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta \ right), \ delta> 0 \ right \} $
เวกเตอร์ที่ไม่ใช่ศูนย์ $ d \ ใน D $ แต่ละตัวเรียกว่าทิศทางที่เป็นไปได้
สำหรับฟังก์ชันที่กำหนด $ f: \ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $ กรวยของทิศทางการปรับปรุงที่ $ \ hat {x} $ แสดงโดย F และกำหนดโดย
$$ 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 \} $$
แต่ละทิศทาง $ d \ ใน F $ เรียกว่าทิศทางการปรับปรุงหรือทิศทางการลงของ f ที่ $ \ hat {x} $
ทฤษฎีบท
Necessary Condition
พิจารณาปัญหา $ min f \ left (x \ right) $ เช่นว่า $ x \ ใน S $ โดยที่ S เป็นชุดที่ไม่ว่างใน $ \ mathbb {R} ^ n $ สมมติว่า f แตกต่างกันได้ที่จุด $ \ hat {x} \ ใน S $ ถ้า $ \ hat {x} $ เป็นโซลูชันที่เหมาะสมในท้องถิ่นดังนั้น $ F_0 \ cap D = \ phi $ โดยที่ $ F_0 = \ left \ {d: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $ และ D เป็นรูปกรวยของทิศทางที่เป็นไปได้
Sufficient Condition
ถ้า $ F_0 \ cap D = \ phi $ f เป็นฟังก์ชัน pseudoconvex ที่ $ \ hat {x} $ และมีย่าน $ \ hat {x} อยู่ N_ \ varepsilon \ left (\ hat {x} \ right) , \ varepsilon> 0 $ เช่นนั้น $ d = x- \ hat {x} \ ใน D $ สำหรับ $ x \ ใน S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ แล้ว $ \ hat {x} $ เป็นโซลูชันที่เหมาะสมที่สุดในท้องถิ่น
หลักฐาน
Necessary Condition
ให้ $ F_0 \ cap D \ neq \ phi $ กล่าวคือมี $ d \ อยู่ใน F_0 \ cap D $ ซึ่ง $ d \ ใน F_0 $ และ $ d \ ใน D $
ตั้งแต่ $ d \ ใน D $ จึงมี $ \ delta_1> 0 $ เช่น $ \ hat {x} + \ lambda d \ in S, \ lambda \ in \ left (0, \ delta_1 \ right) $
ตั้งแต่ $ d \ ใน F_0 $ ดังนั้น $ \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 $
ดังนั้นจึงมี $ \ delta_2> 0 $ ซึ่ง $ f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ in f \ left (0, \ delta_2 \ right) $
ให้ $ \ delta = min \ left \ {\ delta_1, \ delta_2 \ right \} $
จากนั้น $ \ hat {x} + \ lambda d \ in S, f \ left (\ hat {x} + \ lambda d \ right) <f \ left (\ hat {x} \ right), \ forall \ lambda \ ใน f \ left (0, \ delta \ right) $
แต่ $ \ hat {x} $ เป็นโซลูชันที่เหมาะสมที่สุดในท้องถิ่น
ดังนั้นจึงเป็นความขัดแย้ง
ดังนั้น $ F_0 \ cap D = \ phi $
Sufficient Condition
ให้ $ F_0 \ cap D \ neq \ phi $ nd ให้ f เป็นฟังก์ชัน pseudoconvex
ให้มีพื้นที่ใกล้เคียงของ $ \ hat {x}, N _ {\ varepsilon} \ left (\ hat {x} \ right) $ เช่นที่ $ d = x- \ hat {x}, \ forall x \ ใน S \ หมวก N_ \ varepsilon \ left (\ hat {x} \ right) $
ให้ $ \ hat {x} $ ไม่ใช่โซลูชันที่ดีที่สุดในท้องถิ่น
ดังนั้นจึงมี $ \ bar {x} \ อยู่ใน S \ cap N_ \ varepsilon \ left (\ hat {x} \ right) $ ซึ่ง $ f \ left (\ bar {x} \ right) <f \ left ( \ หมวก {x} \ right) $
โดยสมมติว่า $ S \ cap N_ \ varepsilon \ left (\ hat {x} \ right), d = \ left (\ bar {x} - \ hat {x} \ right) \ ใน D $
โดย pseudoconvex ของ 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 $
$ \ Rightarrow d \ ใน F_0 $
ดังนั้น $ F_0 \ cap D \ neq \ phi $
ซึ่งเป็นความขัดแย้ง
ดังนั้น $ \ hat {x} $ จึงเป็นโซลูชันที่ดีที่สุดในท้องถิ่น
พิจารณาปัญหาต่อไปนี้: $ min \: f \ left (x \ right) $ โดยที่ $ x \ ใน X $ เช่น $ g_x \ left (x \ right) \ leq 0, i = 1,2, ... , m $
$ f: X \ rightarrow \ mathbb {R}, g_i: X \ rightarrow \ mathbb {R} ^ n $ และ X เป็นชุดเปิดใน $ \ mathbb {R} ^ n $
ให้ $ S = \ left \ {x: g_i \ left (x \ right) \ leq 0, \ forall i \ right \} $
ให้ $ \ hat {x} \ ใน X $ แล้ว $ M = \ left \ {1,2, ... , m \ right \} $
ให้ $ I = \ left \ {i: g_i \ left (\ hat {x} \ right) = 0, i \ in M \ right \} $ โดยที่ฉันเรียกว่าดัชนีกำหนดไว้สำหรับข้อ จำกัด ที่ใช้งานทั้งหมดที่ $ \ hat {x } $
ให้ $ J = \ left \ {i: g_i \ left (\ hat {x} \ right) <0, i \ in M \ right \} $ โดยที่ J เรียกว่า index กำหนดไว้สำหรับข้อ จำกัด ที่ใช้งานอยู่ทั้งหมดที่ $ \ hat {x } $.
ให้ $ F_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown f \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
ให้ $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gI \ left (\ hat {x} \ right) ^ T d <0 \ right \} $
หรือ $ G_0 = \ left \ {d \ in \ mathbb {R} ^ m: \ bigtriangledown gi \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I \ right \} $
เลมมา
ถ้า $ S = \ left \ {x \ in X: g_i \ left (x \ right) \ leq 0 \ forall i \ in I \ right \} $ และ X ไม่ใช่ชุดเปิดว่างใน $ \ mathbb {R } ^ n $. ให้ $ \ hat {x} \ ใน S $ และ $ g_i $ ต่างกันที่ $ \ hat {x}, i \ in I $ และให้ $ g_i $ โดยที่ $ i \ in J $ ต่อเนื่องที่ $ \ hat {x } $ แล้ว $ G_0 \ subseteq D $
หลักฐาน
ให้ $ d \ ใน G_0 $
เนื่องจาก $ \ hat {x} \ ใน X $ และ X เป็นชุดเปิดจึงมี $ \ delta_1> 0 $ เช่นนั้น $ \ hat {x} + \ lambda d \ ใน X $ สำหรับ $ \ lambda \ in \ ซ้าย (0, \ delta_1 \ right) $
นอกจากนี้ตั้งแต่ $ g_ \ hat {x} <0 $ และ $ g_i $ ต่อเนื่องที่ $ \ hat {x} \ forall i \ ใน J $ มี $ \ delta_2> 0 $, $ g_i \ left (\ hat {x} + \ lambda d \ right) <0, \ lambda \ in \ left (0, \ delta_2 \ right) $
ตั้งแต่ $ d \ ใน G_0 $ ดังนั้น $ \ bigtriangledown g_i \ left (\ hat {x} \ right) ^ T d <0, \ forall i \ in I $ ดังนั้นจึงมี $ \ delta_3> 0, g_i \ left (\ hat {x} + \ lambda d \ right) <g_i \ left (\ hat {x} \ right) = 0 $ สำหรับ $ \ lambda \ in \ left (0, \ delta_3 \ right) i \ in J $
ให้ $ \ delta = min \ left \ {\ delta_1, \ delta_2, \ delta_3 \ right \} $
ดังนั้น $ \ hat {x} + \ lambda d \ in X, g_i \ left (\ hat {x} + \ lambda d \ right) <0, i \ in M $
$ \ Rightarrow \ hat {x} + \ lambda d \ ใน S $
$ \ Rightarrow d \ ใน D $
$ \ Rightarrow G_0 \ subseteq D $
ดังนั้นพิสูจน์แล้ว
ทฤษฎีบท
Necessary Condition
ให้ $ f $ และ $ g_i, i \ in I $ แตกต่างกันที่ $ \ hat {x} \ ใน S, $ และ $ g_j $ ต่อเนื่องที่ $ \ hat {x} \ ใน S $ ถ้า $ \ hat {x} $ เป็น minima ท้องถิ่นของ $ S $ ดังนั้น $ F_0 \ cap G_0 = \ phi $
Sufficient Condition
ถ้า $ F_0 \ cap G_0 = \ phi $ และ f เป็นฟังก์ชัน pseudoconvex ที่ $ \ left (\ hat {x}, g_i 9x \ right) i \ in I $ เป็นฟังก์ชัน pseudoconvex อย่างเคร่งครัดเหนือ $ \ varepsilon $ - พื้นที่ใกล้เคียง ของ $ \ hat {x} \ hat {x} $ เป็นโซลูชันที่เหมาะสมที่สุดในท้องถิ่น
หมายเหตุ
ให้ $ \ hat {x} $ เป็นจุดที่เป็นไปได้เช่น $ \ bigtriangledown f \ left (\ hat {x} \ right) = 0 $ แล้ว $ F_0 = \ phi $ ดังนั้น $ F_0 \ cap G_0 = \ phi $ แต่ $ \ hat {x} $ ไม่ใช่วิธีที่ดีที่สุด
แต่ถ้า $ \ bigtriangledown g \ left (\ hat {x} \ right) = 0 $ แล้ว $ G_0 = \ phi $ ดังนั้น $ F_0 \ cap G_0 = \ phi $
พิจารณาปัญหา: ขั้นต่ำ $ f \ left (x \ right) $ เช่นนั้น $ g \ left (x \ right) = 0 $
ตั้งแต่ $ g \ left (x \ right) = 0 $ ดังนั้น $ g_1 \ left (x \ right) = g \ left (x \ right) <0 $ และ $ g_2 \ left (x \ right) = - g \ ซ้าย (x \ right) \ leq 0 $.
ให้ $ \ hat {x} \ ใน S $ แล้ว $ g_1 \ left (\ hat {x} \ right) = 0 $ และ $ g_2 \ left (\ hat {x} \ right) = 0 $
แต่ $ \ bigtriangledown g_1 \ left (\ hat {x} \ right) = - \ bigtriangledown g_2 \ left (\ hat {x} \ right) $
ดังนั้น $ G_0 = \ phi $ และ $ F_0 \ cap G_0 = \ phi $