การเพิ่มประสิทธิภาพการนูน - ฟังก์ชันที่แตกต่างได้

ให้ S เป็นชุดเปิดที่ไม่ว่างใน $ \ mathbb {R} ^ n $ จากนั้น $ f: S \ rightarrow \ mathbb {R} $ จะกล่าวว่าแตกต่างกันได้ที่ $ \ hat {x} \ ใน S $ if มีเวกเตอร์ $ \ bigtriangledown f \ left (\ hat {x} \ right) $ เรียกว่าเวกเตอร์ลาดและฟังก์ชัน $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ เช่นนั้น

$ f \ left (x \ right) = f \ left (\ hat {x} \ right) + \ bigtriangledown f \ left (\ hat {x} \ right) ^ T \ left (x- \ hat {x} \ ขวา) + \ ซ้าย \ | x = \ hat {x} \ right \ | \ alpha \ left (\ hat {x}, x- \ hat {x} \ right), \ forall x \ ใน S $ โดยที่

$ \ alpha \ left (\ hat {x}, x- \ hat {x} \ right) \ rightarrow 0 \ bigtriangledown f \ left (\ hat {x} \ right) = \ left [\ frac {\ partial f} {\ partial x_1} \ frac {\ partial f} {\ partial x_2} ... \ frac {\ partial f} {\ partial x_n} \ right] _ {x = \ hat {x}} ^ {T} $

ทฤษฎีบท

ให้ S เป็นชุดนูนที่ไม่ว่างเปล่าใน $ \ mathbb {R} ^ n $ และปล่อยให้ $ f: S \ rightarrow \ mathbb {R} $ แตกต่างกับ S จากนั้น f จะนูนถ้าหากเป็นเพียง $ x_1, x_2 \ in S, bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

หลักฐาน

ให้ f เป็นฟังก์ชันนูน กล่าวคือสำหรับ $ x_1, x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

$ f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

$ \ Rightarrow f \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] \ leq \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right ) + f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 + \ lambda \ left (x_1-x_2 \ right) \ right) - f \ left (x_2 \ right) $

$ \ Rightarrow \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_2 \ right) \ right) \ geq f \ left (x_2 \ right) + \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ lambda + $

$ \ left \ | \ lambda \ left (x_1-x_2 \ right) \ right \ | \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) -f \ left (x_2 \ right) \ right) $

โดยที่ $ \ alpha \ left (x_2, \ lambda \ left (x_1 - x_2 \ right) \ right) \ rightarrow 0 $ เป็น $ \ lambda \ rightarrow 0 $

หารด้วย $ \ lambda $ ทั้งสองข้างเราจะได้ -

$ f \ left (x_1 \ right) -f \ left (x_2 \ right) \ geq \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) $

Converse

ให้ $ x_1, x_2 \ in S, bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $

เพื่อแสดงว่า f นูน

เนื่องจาก S นูน, $ x_3 = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S, \ lambda \ in \ left (0, 1 \ right) $

ตั้งแต่ $ x_1, x_3 \ ใน S $ ดังนั้น

$ f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 -x_3 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_1 \ right) -f \ left (x_3 \ right) \ geq \ left (1- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1 - x_2 \ right) $

เนื่องจาก $ x_2, x_3 \ ใน S $ ดังนั้น

$ f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2-x_3 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_2- \ lambda x_1- \ left (1- \ lambda \ right) x_2 \ right) $

$ \ Rightarrow f \ left (x_2 \ right) -f \ left (x_3 \ right) \ geq \ left (- \ lambda \ right) \ bigtriangledown f \ left (x_3 \ right) ^ T \ left (x_1-x_2 \ ขวา) $

ดังนั้นเมื่อรวมสมการข้างต้นเราจะได้ -

$ \ lambda \ left (f \ left (x_1 \ right) -f \ left (x_3 \ right) \ right) + \ left (1- \ lambda \ right) \ left (f \ left (x_2 \ right) -f \ left (x_3 \ right) \ right) \ geq 0 $

$ \ Rightarrow f \ left (x_3 \ right) \ leq \ lambda f \ left (x_1 \ right) + \ left (1- \ lambda \ right) f \ left (x_2 \ right) $

ทฤษฎีบท

ให้ S เป็นชุดนูนเปิดที่ไม่ว่างใน $ \ mathbb {R} ^ n $ และปล่อยให้ $ f: S \ rightarrow \ mathbb {R} $ แตกต่างกันได้บน S จากนั้น f จะนูนบน S ถ้าหาก $ x_1, x_2 \ ใน S, ซ้าย (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

หลักฐาน

ให้ f เป็นฟังก์ชันนูนจากนั้นใช้ทฤษฎีบทก่อนหน้า -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) \ leq f \ left (x_1 \ right) -f \ left (x_2 \ right) $ และ

$ \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

เมื่อเพิ่มสองสมการข้างต้นเราจะได้ -

$ \ bigtriangledown f \ left (x_2 \ right) ^ T \ left (x_1-x_2 \ right) + \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_1-x_2 \ right) \ leq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

Converse

ปล่อยให้ $ x_1, x_2 \ in S, \ left (\ bigtriangledown f \ left (x_2 \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x_2-x_1 \ right) \ geq 0 $

เพื่อแสดงว่า f นูน

ให้ $ x_1, x_2 \ ใน S $ ดังนั้นโดยใช้ทฤษฎีบทค่าเฉลี่ย $ \ frac {f \ left (x_1 \ right) -f \ left (x_2 \ right)} {x_1-x_2} = \ bigtriangledown f \ left ( x \ right), x \ in \ left (x_1-x_2 \ right) \ Rightarrow x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ เพราะ S เป็นชุดนูน

$ \ Rightarrow f \ left (x_1 \ right) - f \ left (x_2 \ right) = \ left (\ bigtriangledown f \ left (x \ right) ^ T \ right) \ left (x_1-x_2 \ right) $

ในราคา $ x, x_1 $ เรารู้ -

$ \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (x-x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2- x_1 \ right) \ geq 0 $

$ \ Rightarrow \ left (\ bigtriangledown f \ left (x \ right) - \ bigtriangledown f \ left (x_1 \ right) \ right) ^ T \ left (1- \ lambda \ right) \ left (x_2-x_1 \ right ) \ geq 0 $

$ \ Rightarrow \ bigtriangledown f \ left (x \ right) ^ T \ left (x_2-x_1 \ right) \ geq \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) $

เมื่อรวมสมการข้างต้นเราจะได้ -

$ \ Rightarrow \ bigtriangledown f \ left (x_1 \ right) ^ T \ left (x_2-x_1 \ right) \ leq f \ left (x_2 \ right) -f \ left (x_1 \ right) $

ดังนั้นการใช้ทฤษฎีบทสุดท้าย f คือฟังก์ชันนูน

ฟังก์ชันที่แตกต่างกันสองเท่า

ให้ S เป็นเซตย่อยที่ไม่ว่างเปล่าของ $ \ mathbb {R} ^ n $ และปล่อยให้ $ f: S \ rightarrow \ mathbb {R} $ จากนั้น f จะบอกว่าแตกต่างกันสองเท่าที่ $ \ bar {x} \ ใน S $ ถ้ามีเวกเตอร์ $ \ bigtriangledown f \ left (\ bar {x} \ right), a \: nXn $ matrix $ H \ left (x \ right) $ (เรียกว่าเมทริกซ์ Hessian) และฟังก์ชัน $ \ alpha: \ mathbb {R} ^ n \ rightarrow \ mathbb {R} $ เช่นนั้น $ f \ left (x \ right) = f \ left (\ bar {x} + x- \ bar {x} \ right) = f \ ซ้าย (\ bar {x} \ right) + \ bigtriangledown f \ left (\ bar {x} \ right) ^ T \ left (x- \ bar {x} \ right) + \ frac {1} {2} \ ซ้าย (x- \ bar {x} \ right) H \ left (\ bar {x} \ right) \ left (x- \ bar {x} \ right) $

โดยที่ $ \ alpha \ left (\ bar {x}, x- \ bar {x} \ right) \ rightarrow Oasx \ rightarrow \ bar {x} $