Global Optimization เมื่อเกี่ยวข้องกับฟังก์ชันเอกซ์โพเนนเชียล
ฉันสงสัยว่ามีวิธีการในการกำหนดปัญหา MINLP ที่เหมาะสมทั่วโลกหรือไม่เมื่อฟังก์ชันที่ไม่ใช่เชิงเส้นเกี่ยวข้องเป็นเพียงรูปแบบเท่านั้น $Z = Y e^{- \alpha X}$, ที่ไหน $Y \ge 0$ และ $X \ge 0$.
มีเอกสารที่อธิบายถึงแนวทางดังกล่าวหรือไม่? ฟังก์ชันเหล่านี้มีลักษณะที่อาจถูกใช้ประโยชน์หรือไม่?
การใช้ลอการิทึมฉันสามารถเขียนฟังก์ชันใหม่เป็นไฟล์ $\log(Z) = \log(Y) - \alpha X$แต่ฉันไม่คิดว่าฉันจะชนะอะไรเลย
คำตอบ
นี่คือปัญหาการเพิ่มประสิทธิภาพสากลที่ไม่นูน วิธีที่ล้ำสมัยในการแก้ปัญหานี้คือการใช้ความผ่อนคลายอย่างแท้จริง
ข้อมูลเชิงลึกที่สำคัญก็คือ $e^{-\alpha X}$ นูน (เนื่องจากไฟล์ $\alpha$ เป็นบวก)
วิธีการจะเป็นดังนี้:
- แนะนำตัวแปรเสริมใหม่ $w=e^{-\alpha X}$
- ตอนนี้คุณมี $Z=Yw$และ $w=e^{-\alpha X}$
- เนื่องจากข้อ จำกัด ทั้งสองไม่นูนคุณจึงแบ่งอสมการออกเป็นสองข้อ:
$Z\leq Yw, -Z\leq -Yw$
$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$
ชุดแรกของความไม่เท่าเทียมกันสามารถ convexified ใช้ผ่อนคลายแมค
อสมการชุดที่สองคือนูนและเว้าตามลำดับ อสมการนูนสามารถผ่อนคลายได้โดยใช้การประมาณภายนอกและอสมการเว้าโดยใช้ซีแคนต์
จากนั้นคุณเสียบปัญหาที่ผ่อนคลายของคุณเข้ากับอัลกอริธึมแบบสาขาและขอบเขตและมันจะรวมกันเป็นกำลังสอง
โปรดทราบว่าวิธีการนี้ไม่ขึ้นอยู่กับสัญญาณของ $Z,Y,X$.
หรือคุณสามารถเสียบสิ่งนี้เข้ากับตัวแก้ปัญหาระดับโลกซึ่งจะทำทั้งหมดนี้ให้คุณโดยอัตโนมัติ Couenneเป็นตัวเลือกโอเพ่นซอร์สและหากคุณเป็นนักวิชาการ / นักเรียนคุณสามารถใช้ SCIP หรือOcteract Engineของเราได้ฟรี
สมมติว่าการผ่อนคลายอย่างต่อเนื่องเป็นส่วนนูนคุณมักจะใช้การเพิ่มประสิทธิภาพรูปกรวยกับกรวยเลขชี้กำลัง Mosek การสร้างแบบจำลองตำราจะมีรายละเอียด
ไม่น่าแปลกใจที่Mosekสามารถแก้ปัญหาดังกล่าวได้
คุณอาจพบคำตอบบางส่วนสำหรับคำถามของคุณในบทความต่อไปนี้ (เตรียมพร้อมใน OR) โดย JP Vielma และ J Huchette https://arxiv.org/abs/1708.00050
ในบทความนั้นผู้เขียนพิจารณาถึงปัญหาในการประมาณฟังก์ชันที่ไม่ใช่เชิงเส้นของตัวแปรหนึ่งหรือสองตัวแปรในวัตถุประสงค์ผ่านการแยกส่วนของไฮเปอร์เพลนหลายตัว จากนั้นคุณสามารถส่ง MIP ที่เป็นผลลัพธ์ไปยังตัวแก้จำนวนเต็มผสมสำหรับวัตถุประสงค์ทั่วไป
บทความนั้นมีการอ้างอิงถึงแหล่งที่มาอื่น ๆ ที่อาจช่วยได้เช่นกัน