Skip to content
กลับไปยังผลการค้นหา

การโปรแกรมเชิงเส้นไม่ตรง

ผู้เสนอ
Jorge Nocedal & Stephen Wright
ปี
2006
ประเภท
Continuous mathematical optimization
กลุ่มวิธี
Mathematical programming

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

การโปรแกรมเชิงเส้นไม่ตรง (NLP) เป็นสาขาหนึ่งของการหาค่าเหมาะสมที่สุดเชิงคณิตศาสตร์ที่เกี่ยวข้องกับปัญหาซึ่งฟังก์ชันวัตถุประสงค์หรืออย่างน้อยหนึ่งข้อจำกัดไม่เป็นเชิงเส้น การกำหนดรูปแบบอย่างครอบคลุมโดย Jorge Nocedal และ Stephen Wright ในตำราสำคัญปี 2006 ของพวกเขา NLP ครอบคลุมอัลกอริทึมที่ใช้เกรเดียนต์ — รวมถึงการโปรแกรมกำลังสองตามลำดับ (SQP), วิธีการภายในจุด และแนวทางควอซี-นิวตัน — สำหรับการค้นหาผลลัพธ์ที่เหมาะสมที่สุดในระดับท้องถิ่นหรือระดับโลกสำหรับปัญหาการตัดสินใจแบบต่อเนื่องที่เกิดขึ้นในสาขาวิศวกรรม เศรษฐศาสตร์ และวิทยาศาสตร์กายภาพ

แนวคิดเบื้องหลังวิธีการ

ลองจินตนาการถึงการลงจากภูมิประเทศที่เป็นเนินเขาปกคลุมด้วยหมอก ขณะที่ยังคงอยู่ภายในบริเวณที่ถูกกั้นรั้ว คุณไม่สามารถมองเห็นภูมิประเทศทั้งหมดได้ ดังนั้นคุณจึงรู้สึกถึงความลาดชันใต้ฝ่าเท้า (เกรเดียนต์) ปรับทิศทางการก้าวของคุณให้ลงเขา และตรวจสอบในแต่ละก้าวว่าคุณไม่ได้ข้ามรั้ว (ข้อจำกัด) หากรั้วโค้งงอหรือเนินเขาทับซ้อนกัน เส้นทางตรงธรรมดาจะไม่สามารถใช้ได้ — คุณต้องโค้งเส้นทางของคุณ การโปรแกรมเชิงเส้นไม่ตรงกำหนดรูปแบบกระบวนการนี้อย่างแม่นยำ โดยแทนที่การเดินบนเขาอย่างสัญชาตญาณด้วยกฎขนาดก้าวและทิศทางที่เข้มงวดทางคณิตศาสตร์

ประวัติศาสตร์

รากฐานทางทฤษฎีของการโปรแกรมเชิงเส้นไม่ตรงสืบย้อนไปถึงเงื่อนไข KKT ที่ได้มาจาก Karush (1939) และ Kuhn และ Tucker (1951) อัลกอริทึมที่ใช้งานได้จริงเร่งความเร็วในช่วงทศวรรษ 1960–1980 ด้วยการพัฒนาวิธีการ SQP, แนวทาง Lagrangian เสริม และการอัปเดตควอซี-นิวตัน รวมถึง BFGS (1970) หนังสือ Numerical Optimization ฉบับที่สองปี 2006 ของ Nocedal และ Wright กลายเป็นแหล่งอ้างอิงที่ชัดเจน โดยสังเคราะห์ทฤษฎีการลู่เข้า กรอบการค้นหาตามแนวเส้นและบริเวณความเชื่อมั่น และวิธีการภายในจุด ให้เป็นการรักษาที่ทันสมัยที่สอดคล้องกัน

ควรใช้เมื่อใด

ใช้การโปรแกรมเชิงเส้นไม่ตรงเมื่อฟังก์ชันวัตถุประสงค์หรือข้อจำกัดไม่สามารถทำให้เป็นเชิงเส้นได้โดยไม่สูญเสียความแม่นยำอย่างมีนัยสำคัญ และตัวแปรตัดสินใจเป็นแบบต่อเนื่อง การตั้งค่าทั่วไป ได้แก่ การออกแบบทางวิศวกรรมพร้อมข้อจำกัดกฎทางกายภาพ การหาค่าเหมาะสมของพอร์ตโฟลิโอด้วยมาตรวัดความเสี่ยงที่ไม่เป็นเชิงเส้น และการถดถอยด้วยรูปแบบโมเดลที่ไม่เป็นเชิงเส้น ข้อสมมติฐานหลักคือ f และ c อย่างน้อยก็หาอนุพันธ์ต่อเนื่องสองครั้ง (สำหรับตัวแก้ที่ใช้เกรเดียนต์) และคุณสมบัติของข้อจำกัดเป็นจริง เมื่อตัวแปรเป็นจำนวนเต็ม ส่วนขยายของการโปรแกรมเชิงเส้นไม่ตรงแบบผสมจำนวนเต็ม (MINLP) จะถูกนำมาใช้ สำหรับปัญหาแบบคอนเวกซ์ วิธีการภายในจุดรับประกันความเป็นเหมาะสมระดับโลก สำหรับปัญหาที่ไม่ใช่แบบคอนเวกซ์ มีเพียงการรับประกันระดับท้องถิ่นเท่านั้น

ข้อจำกัดและข้อควรพิจารณา

  • ปัญหาที่ไม่ใช่แบบคอนเวกซ์ให้การรับประกันความเป็นเหมาะสมในระดับท้องถิ่นเท่านั้น การแก้ปัญหาระดับโลกต้องใช้กลยุทธ์การค้นหาระดับโลกเพิ่มเติม
  • ต้องการให้ฟังก์ชันวัตถุประสงค์และข้อจำกัดมีความเรียบ (อย่างน้อยก็หาอนุพันธ์ได้) ปัญหาที่ไม่เรียบต้องการวิธีการอนุพันธ์ย่อยแบบพิเศษ
  • ต้นทุนการคำนวณเพิ่มขึ้นอย่างมากตามขนาดของปัญหาเมื่อต้องการการประเมิน Hessian ที่แน่นอน
  • คุณสมบัติของข้อจำกัดอาจล้มเหลว (เช่น ที่จุดที่เป็นไปได้แบบเสื่อม) ทำให้เงื่อนไข KKT สูญเสียพื้นฐานทางทฤษฎี

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • จัดการกับปัญหาในโลกแห่งความเป็นจริงที่หลากหลายซึ่งการประมาณค่าเชิงเส้นหรือกำลังสองไม่เพียงพอ
  • ทฤษฎีอัลกอริทึมที่สมบูรณ์พร้อมการรับประกันการลู่เข้าที่ศึกษามาอย่างดีสำหรับกรณีที่เป็นคอนเวกซ์
  • ตัวแก้ที่ใช้เกรเดียนต์อย่างมีประสิทธิภาพ (SQP, ภายในจุด) สามารถปรับขนาดได้ถึงหลายพันตัวแปรในทางปฏิบัติ
  • กรอบการทำงาน Lagrangian แบบรวมสามารถรองรับข้อจำกัดสมการและอสมการแบบผสมได้อย่างเป็นธรรมชาติ

การประยุกต์ใช้

  • วิศวกรรมโครงสร้างและอากาศยาน: การลดน้ำหนักให้เหลือน้อยที่สุดภายใต้ข้อจำกัดความเค้นและการโก่งตัว
  • การบริหารพอร์ตโฟลิโอ: การเพิ่มผลตอบแทนที่คาดหวังภายใต้งบประมาณความแปรปรวน (ความเสี่ยง) ที่ไม่เป็นเชิงเส้น
  • การออกแบบกระบวนการทางเคมี: การหาค่าเหมาะสมของผลผลิตจากเครื่องปฏิกรณ์ภายใต้ข้อจำกัดทางอุณหพลศาสตร์และความปลอดภัย
  • การเรียนรู้ของเครื่อง: การฝึกโครงข่ายประสาทเทียมและโมเดลเคอร์เนลผ่านตัวแก้ NLP แบบไม่มีข้อจำกัดหรือมีข้อจำกัด
  • ระบบพลังงาน: ปัญหาการไหลของกำลังไฟฟ้าที่เหมาะสมในการจ่ายไฟฟ้าของกริดพร้อมข้อจำกัดทางกายภาพที่ไม่เป็นเชิงเส้น

วิธีการทำงาน

วิธีการทำงาน

1

นักวิเคราะห์กำหนดฟังก์ชันวัตถุเชิงสเกลาร์ f(x) เพื่อลดค่าหรือเพิ่มค่าสูงสุดเหนือตัวแปรตัดสินใจ x ใน R^n ร่วมกับข้อจำกัดสมการ c_i(x) = 0 และข้อจำกัดอสมการ c_j(x) >= 0 การระบุว่าข้อจำกัดใดที่ทำงานอยู่ที่จุดที่คาดคะเน และเงื่อนไขความเป็นปกติ (คุณสมบัติของข้อจำกัด) เป็นสิ่งสำคัญในขั้นตอนนี้ และกำหนดว่าทฤษฎีความเป็นเหมาะสมใดที่นำมาใช้

สูตร
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}
2

เงื่อนไข Karush-Kuhn-Tucker (KKT) ให้เงื่อนไขที่จำเป็นอันดับแรกสำหรับค่าเหมาะสมที่สุดในระดับท้องถิ่น พวกมันต้องการความคงที่ของ Lagrangian, ความสมบูรณ์ของส่วนที่เหลือสำหรับตัวคูณอสมการ (lambda_j c_j = 0), ความเป็นไปได้ของคู่ขนาน (lambda_j >= 0) และความเป็นไปได้ของคู่เอกภพ อัลกอริทึมสร้างการวนซ้ำอย่างต่อเนื่องที่ตอบสนองเงื่อนไขเหล่านี้อย่างเข้มงวดมากขึ้นเรื่อยๆ โดยมีเงื่อนไขเพียงพออันดับสองยืนยันว่าจุดคงที่นั้นเป็นค่าต่ำสุดในระดับท้องถิ่นจริง

สูตร
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}
3

ในการวนซ้ำแต่ละครั้ง k อัลกอริทึมจะคำนวณทิศทางการค้นหา p_k — โดยทั่วไปผ่านการประมาณค่าควอซี-นิวตัน B_k ของ Hessian (เช่น BFGS) หรือระบบอนุพันธ์อันดับสองที่แน่นอน — และความยาวก้าว alpha_k ที่เป็นไปตามเงื่อนไข Wolfe หรือ Armijo วิธีการ SQP แก้ปัญหาย่อยกำลังสองสำหรับ p_k ในขณะที่วิธีการภายในจุดจะเพิ่มพจน์กั้นเพื่อจัดการกับข้อจำกัดอสมการและขับเคลื่อนการวนซ้ำไปสู่ภายในที่เป็นไปได้

สูตร
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)
4

การสิ้นสุดเกิดขึ้นเมื่อทั้งนอร์มของเกรเดียนต์ของ Lagrangian และการละเมิดข้อจำกัดสูงสุดลดลงต่ำกว่าค่าที่กำหนดไว้ (epsilon และ delta) เนื่องจาก NLP โดยทั่วไปไม่ใช่แบบคอนเวกซ์ อัลกอริทึมอาจลู่เข้าสู่ค่าเหมาะสมที่สุดในระดับท้องถิ่น การเริ่มต้นใหม่หลายครั้งจากจุดเริ่มต้นที่แตกต่างกัน หรือกลยุทธ์การค้นหาระดับโลก (branch-and-bound, multistart) ขอแนะนำเมื่อต้องการความเป็นเหมาะสมระดับโลก

สูตร
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \delta

ข้อผิดพลาดที่พบบ่อย

  • การละเลยคุณสมบัติของข้อจำกัดและการใช้เงื่อนไข KKT อย่างไม่เลือกที่จุดเสื่อมหรือจุดที่เป็นไปไม่ได้ นำไปสู่ผลลัพธ์ที่ผิดพลาด
  • การใช้ตัวแปรที่มีการปรับขนาดไม่ดีทำให้การประมาณค่า Hessian มีสภาพไม่ดี และการลู่เข้าช้าหรือล้มเหลว
  • การยอมรับค่าต่ำสุดในระดับท้องถิ่นแรกที่พบโดยไม่มีการเริ่มต้นใหม่หลายครั้งในกรณีที่ไม่ใช่แบบคอนเวกซ์ อาจทำให้พลาดค่าเหมาะสมที่สุดระดับโลกไปอย่างมาก
  • การประมาณค่าเกรเดียนต์ด้วยผลต่างจำกัดนำมาซึ่งข้อผิดพลาดเชิงตัวเลข การหาอนุพันธ์เชิงวิเคราะห์หรืออัตโนมัติเป็นที่ต้องการอย่างยิ่ง

คำถามที่พบบ่อย

โปรแกรมเชิงเส้นทุกโปรแกรมเป็นโปรแกรมเชิงเส้นไม่ตรงด้วยหรือไม่?

ใช่ การโปรแกรมเชิงเส้นเป็นกรณีพิเศษของการโปรแกรมเชิงเส้นไม่ตรง ซึ่งทั้งฟังก์ชันวัตถุประสงค์และข้อจำกัดทั้งหมดเป็นแบบสัมพรรค อย่างไรก็ตาม LP ยอมรับอัลกอริทึมซิมเพล็กซ์และภายในจุดที่ใช้ประโยชน์จากความเป็นเชิงเส้นและมีประสิทธิภาพมากกว่าตัวแก้ NLP ทั่วไป การใช้ตัวแก้ NLP ทั่วไปสำหรับ LP นั้นสิ้นเปลืองแต่ถูกต้องตามหลักคณิตศาสตร์

เมื่อใดที่ฉันสามารถเชื่อได้ว่าจุด KKT เป็นค่าต่ำสุดระดับโลก?

เมื่อ NLP เป็นแบบคอนเวกซ์ — หมายความว่า f เป็นแบบคอนเวกซ์และเซตที่เป็นไปได้เป็นเซตแบบคอนเวกซ์ — จุด KKT ใดๆ ก็ตามจะเป็นค่าต่ำสุดระดับโลก สำหรับปัญหาที่ไม่ใช่แบบคอนเวกซ์ การรับประกันนี้ไม่เป็นจริง และจุด KKT เป็นเพียงค่าต่ำสุดในระดับท้องถิ่น (ภายใต้เงื่อนไขเพียงพออันดับสอง) วิธีการหาค่าเหมาะสมระดับโลก เช่น branch-and-bound หรือ convex relaxations จำเป็นต้องใช้ในกรณีอื่น

ความแตกต่างระหว่างวิธีการ SQP และภายในจุดคืออะไร?

SQP แก้ปัญหาย่อยของการโปรแกรมกำลังสองเป็นระยะๆ ซึ่งประมาณค่า NLP ในระดับท้องถิ่น และมักจะเลือกสำหรับปัญหาขนาดเล็กถึงปานกลางที่มีข้อจำกัดที่ทำงานอยู่จำนวนมาก วิธีการภายในจุด (barrier) จะอยู่ภายในขอบเขตที่เป็นไปได้เสมอ และมีแนวโน้มที่จะปรับขนาดได้ดีกว่าสำหรับปัญหาขนาดใหญ่ที่มีโครงสร้างเบาบาง ทั้งสองวิธีลู่เข้าแบบซูเปอร์ลีเนียร์ภายใต้เงื่อนไขความเป็นปกติที่เหมาะสม

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN: 978-0-387-30303-1
    คัดลอกแล้ว