Robust Optimization — การหาค่าเหมาะสมที่สุดภายใต้ความไม่แน่นอนแบบแย่ที่สุด
- ผู้เสนอ
- Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
- ปี
- 1970s theoretical roots; modern tractable form from late 1990s–2004
- ประเภท
- Mathematical programming framework
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
Robust optimization เป็นกรอบการหาค่าเหมาะสมที่สุดเชิงคณิตศาสตร์ (mathematical programming) ซึ่งถูกกำหนดรูปแบบอย่างเป็นทางการโดย Ben-Tal และ Nemirovski ในช่วงปลายทศวรรษ 1990 และทำให้สามารถแก้ปัญหาได้ในวงกว้างโดย Bertsimas และ Sim (2004) โดยมีเป้าหมายเพื่อหาทางเลือกที่รับประกันว่าจะให้ผลลัพธ์ที่ยอมรับได้ภายใต้ทุกสถานการณ์ภายในชุดความไม่แน่นอนที่กำหนดไว้ล่วงหน้า แทนที่จะสมมติว่าค่าพารามิเตอร์เป็นที่ทราบแน่ชัด แทนที่จะหาค่าเหมาะสมที่สุดสำหรับผลลัพธ์ที่คาดหวังเพียงค่าเดียว การหาค่าเหมาะสมที่สุดแบบ Robust จะลดค่าวัตถุประสงค์ในกรณีที่แย่ที่สุด (worst-case objective) ในทุกความเป็นไปได้ของข้อมูลที่ไม่แน่นอน
แนวคิดเบื้องหลังวิธีการ
การหาค่าเหมาะสมที่สุดแบบปกติ (Ordinary optimisation) จะเชื่อถือตัวเลขที่คุณป้อนเข้าไป แต่ Robust optimisation จะตั้งคำถามว่า 'จะเกิดอะไรขึ้นหากตัวเลขเหล่านั้นผิดพลาด — ภายในช่วงที่กำหนด?' มันจะหาทางเลือกที่สร้างความเสียหายได้น้อยที่สุดเมื่อธรรมชาติเลือกอินพุตที่แย่ที่สุดภายในช่วงนั้น ลองนึกภาพว่าเป็นการออกแบบสะพานเพื่อทนทานต่อการรับน้ำหนักสูงสุดที่เชื่อถือได้ ไม่ใช่การรับน้ำหนักเฉลี่ย โดยยอมรับต้นทุนด้านประสิทธิภาพที่ลดลงเล็กน้อยในกรณีทั่วไป เพื่อแลกกับการรับประกันในกรณีที่เลวร้าย
ประวัติศาสตร์
รากฐานทางทฤษฎีของ Robust optimisation สืบย้อนไปถึง Soyster (1971) และทฤษฎีการตัดสินใจแบบ minimax ของ Wald (1945) สาขานี้ได้รับการวางรากฐานที่ทันสมัยและสามารถแก้ปัญหาได้โดย Arkadi Nemirovski และ Aharon Ben-Tal ในชุดบทความตั้งแต่ปี 1997 เป็นต้นไป ซึ่งรวมอยู่ในตำราปี 2009 ของพวกเขากับ El Ghaoui Dimitris Bertsimas และ Melvyn Sim (2004) ได้นำเสนอรูปแบบงบประมาณความไม่แน่นอน (budget-uncertainty) (polyhedral) ที่รักษาความเป็นเชิงเส้นของปัญหาแบบปกติ และทำให้ Robust linear programming เข้าถึงได้ในวงกว้าง นับตั้งแต่นั้นมา Robust optimisation ได้ขยายขอบเขตไปยังโปรแกรมจำนวนเต็ม (integer programs) รูปแบบสองขั้นตอน (two-stage formulations) และชุดความไม่แน่นอนที่ขับเคลื่อนด้วยข้อมูล (data-driven uncertainty sets) ซึ่งได้มาจากข้อสังเกตในอดีต
ควรใช้เมื่อใด
Robust optimisation เหมาะสมเมื่อความไม่แน่นอนของพารามิเตอร์มีขอบเขต แต่การแจกแจงไม่ทราบแน่ชัดหรือไม่น่าเชื่อถือ เมื่อต้องการการรับประกันกรณีที่แย่ที่สุด (safety-critical หรือ regulatory contexts) และเมื่อต้องการการตัดสินใจเดียวที่สามารถนำไปปฏิบัติได้ แทนที่จะเป็นนโยบายการกระจาย (policy distribution) เช่นใน stochastic programming วิธีนี้ใช้ได้กับตัวแปรตัดสินใจแบบต่อเนื่อง (continuous decision variables) ไม่จำเป็นต้องมีขนาดตัวอย่างขั้นต่ำ — ชุดความไม่แน่นอนถูกกำหนดโดยใช้การวิเคราะห์ ไม่ใช่การประมาณค่าจากข้อมูล วิธีนี้ไม่เหมาะเมื่อความไม่แน่นอนไม่มีขอบเขต เมื่อมีการแจกแจงความน่าจะเป็นสำหรับพารามิเตอร์ที่ไม่แน่นอนที่ถูกต้องและแม่นยำ (ควรใช้ stochastic optimisation แทน) หรือเมื่อการประเมินสถานการณ์น้อยกว่าประมาณ 1,000 ครั้งสามารถทำได้สำหรับการตรวจสอบตามสถานการณ์
ข้อจำกัดและข้อควรพิจารณา
- ผลลัพธ์ที่ได้จะระมัดระวังมากกว่าค่าเหมาะสมที่สุดแบบปกติอย่างหลีกเลี่ยงไม่ได้ ราคาของความ Robust อาจมีนัยสำคัญเมื่อชุดความไม่แน่นอนมีขนาดใหญ่
- การกำหนดชุดความไม่แน่นอนที่สมจริงต้องอาศัยความรู้เฉพาะทาง หากเลือกชุดที่ไม่เหมาะสม อาจจะระมัดระวังเกินไปหรือไม่ครอบคลุมการเปลี่ยนแปลงที่แท้จริง
- สำหรับปัญหาที่ไม่ใช่นูน (non-convex problems) หรือโปรแกรมจำนวนเต็มผสมทั่วไป (general mixed-integer programs) การปรับรูปแบบแบบ Robust อาจเป็น NP-hard และต้องใช้อัลกอริทึมการแยกส่วน (decomposition algorithms) แบบพิเศษ
- Robust optimisation ไม่ได้รวมข้อมูลความน่าจะเป็น เมื่อมีการแจกแจงที่น่าเชื่อถือ Stochastic programming อาจให้ประสิทธิภาพที่คาดหวังสูงกว่า
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- ให้การรับประกันกรณีที่แย่ที่สุดแบบกำหนดแน่นอนโดยไม่ต้องใช้การแจกแจงความน่าจะเป็นสำหรับพารามิเตอร์ที่ไม่แน่นอน
- การปรับรูปแบบสำหรับชุดความไม่แน่นอนแบบนูนมักจะสามารถแก้ปัญหาได้เทียบเท่ากับปัญหาแบบปกติ — ไม่มีการระเบิดของความซับซ้อนในการคำนวณเพิ่มเติม
- ระดับการระมัดระวังสามารถควบคุมได้โดยตรงผ่านขนาดและรูปร่างของชุดความไม่แน่นอน ทำให้การแลกเปลี่ยนระหว่างความ Robust และประสิทธิภาพมีความชัดเจนและโปร่งใส
- สามารถนำไปประยุกต์ใช้ได้ในหลากหลายสาขา — ห่วงโซ่อุปทาน การเงิน การออกแบบทางวิศวกรรม ระบบพลังงาน — ทุกที่ที่มีความไม่แน่นอนของพารามิเตอร์ที่มีขอบเขต
การประยุกต์ใช้
- การออกแบบเครือข่ายห่วงโซ่อุปทานและโลจิสติกส์ภายใต้ความต้องการและระยะเวลานำที่ไม่แน่นอน
- การหาค่าเหมาะสมที่สุดของพอร์ตการลงทุนภายใต้ความไม่แน่นอนของผลตอบแทนสินทรัพย์ — เส้นขอบเขตเฉลี่ย-ความแปรปรวนแบบ Robust (robust mean-variance frontier)
- การออกแบบทางวิศวกรรม (โครงสร้าง เครื่องกล การบินและอวกาศ) ที่ความคลาดเคลื่อนในการผลิตทำให้เกิดความไม่แน่นอนของพารามิเตอร์
- การวางแผนระบบพลังงานภายใต้การผลิตพลังงานหมุนเวียนและราคาเชื้อเพลิงที่ไม่แน่นอน
- ปัญหาการจัดตารางเวลาและการจัดเส้นทางที่เวลาประมวลผลหรือเวลาเดินทางไม่ทราบแน่ชัด
วิธีการทำงาน
วิธีการทำงาน
ผู้วิเคราะห์จะระบุชุดความไม่แน่นอน (uncertainty set) ซึ่งเป็นขอบเขตของการเปลี่ยนแปลงที่น่าจะเป็นไปได้รอบๆ ค่าพารามิเตอร์อ้างอิง (nominal parameter values) รูปทรงที่พบบ่อย ได้แก่ กล่อง (box) (แต่ละพารามิเตอร์เปลี่ยนแปลงอย่างอิสระภายในช่วง) รูปวงรี (ellipsoidal) (การเปลี่ยนแปลงถูกจำกัดด้วยนอร์มแบบยุคลิด) รูปทรงหลายเหลี่ยม (polyhedral) และชุดที่มีงบประมาณจำกัด (budget-constrained) (Bertsimas-Sim) การเลือกนี้จะเข้ารหัสสมมติฐานเกี่ยวกับความสัมพันธ์และความรุนแรงของความไม่แน่นอน และควบคุมระดับการระมัดระวัง (conservatism) ของผลลัพธ์ที่ได้โดยตรง
ปัญหาการหาค่าเหมาะสมที่สุดจะถูกกำหนดในรูปแบบ minimax: หาค่าต่ำสุดของ x สำหรับค่าสูงสุดของ f(x, u) เมื่อ u อยู่ใน U โดยมีเงื่อนไขว่าต้องเป็นจริงสำหรับทุก u ในชุดความไม่แน่นอน U การหาค่าสูงสุดภายในนี้จะจำลองการเลือกสถานการณ์ที่เลวร้ายที่สุดของพารามิเตอร์ที่ไม่แน่นอนโดยธรรมชาติ
สำหรับชุดความไม่แน่นอนแบบนูน (convex uncertainty sets) ปัญหา minimax จะเทียบเท่าทางคณิตศาสตร์กับโปรแกรมแบบนูนที่กำหนดแน่นอน (deterministic convex program) ซึ่งมักจะเป็นโปรแกรมรูปกรวยอันดับสอง (second-order cone program) สำหรับชุดรูปวงรี หรือโปรแกรมเชิงเส้น (linear program) สำหรับชุดรูปทรงหลายเหลี่ยม การปรับรูปแบบที่สามารถแก้ปัญหาได้นี้เป็นหัวใจสำคัญของ Ben-Tal และ Nemirovski: counterpart แบบ Robust ของปัญหาคลาสสิกหลายอย่างสามารถแก้ได้ไม่ยากไปกว่าปัญหาแบบปกติ สำหรับโครงสร้างที่ไม่ใช่นูน (non-convex structures) Benders decomposition จะแบ่งปัญหาออกเป็นปัญหาย่อยหลัก (master subproblem) และปัญหาย่อยฝ่ายตรงข้าม (adversarial subproblem) ซึ่งจะถูกแก้สลับกันไป
โปรแกรมที่กำหนดแน่นอนที่ปรับรูปแบบแล้วจะถูกส่งไปยังตัวแก้ปัญหาแบบนูน (convex solver) หรือตัวแก้ปัญหาแบบผสมจำนวนเต็ม (mixed-integer solver) มาตรฐาน เนื่องจากโดยทั่วไปแล้วการปรับรูปแบบจะเป็นโปรแกรมรูปกรวยหรือโปรแกรมเชิงเส้น ตัวแก้ปัญหาสำเร็จรูปสามารถจัดการได้ด้วยประสิทธิภาพ ตัวแก้ปัญหาจะส่งคืนเวกเตอร์การตัดสินใจเดียว ซึ่งเป็นผลลัพธ์ที่เหมาะสมที่สุดแบบ Robust (robust optimal solution) ที่มีความเป็นไปได้และใกล้เคียงค่าเหมาะสมที่สุดสำหรับทุกสถานการณ์ในชุดความไม่แน่นอน
ผู้วิเคราะห์จะตรวจสอบราคาของความ Robust (price of robustness) ซึ่งคือช่องว่างระหว่างค่าวัตถุประสงค์ที่เหมาะสมที่สุดแบบปกติ (ไม่มีความไม่แน่นอน) และค่าวัตถุประสงค์ที่เหมาะสมที่สุดแบบ Robust ชุดความไม่แน่นอนที่แคบจะให้ช่องว่างน้อยแต่มีการรับประกันที่อ่อนแอกว่า ชุดที่ใหญ่จะให้การป้องกันกรณีที่แย่ที่สุดที่แข็งแกร่งโดยมีต้นทุนด้านประสิทธิภาพที่สูงขึ้นในสถานการณ์ทั่วไป การวิเคราะห์ความไว (sensitivity analysis) ต่อขนาดของชุดความไม่แน่นอนจะช่วยในการตัดสินใจเลือกระดับการระมัดระวังขั้นสุดท้าย
ข้อผิดพลาดที่พบบ่อย
- การเลือกชุดความไม่แน่นอนที่ใหญ่เกินไปจะให้ผลลัพธ์ที่ระมัดระวังมากจนแทบจะไร้ประโยชน์ — ควรปรับขนาดชุดให้สอดคล้องกับความรู้เฉพาะทางหรือขอบเขตความผันแปรในอดีต
- ความสับสนระหว่าง Robust optimisation และ Stochastic optimisation: หากการแจกแจงความน่าจะเป็นสำหรับพารามิเตอร์ที่ไม่แน่นอนได้รับการจัดตั้งและเชื่อถือได้ Stochastic programming น่าจะเหมาะสมกว่า
- การใช้ Robust optimisation เมื่อความไม่แน่นอนไม่มีขอบเขตอย่างแท้จริงจะทำให้การรับประกันกรณีที่แย่ที่สุดเป็นโมฆะ — Robust optimisation สมมติว่ามีการเปลี่ยนแปลงที่มีขอบเขต
- การละเลยการตรวจสอบราคาของความ Robust หลังจากการแก้ปัญหา: ช่องว่างขนาดใหญ่ระหว่างวัตถุประสงค์แบบปกติและแบบ Robust บ่งชี้ว่าชุดความไม่แน่นอนอาจกว้างเกินจริงและควรได้รับการทบทวน
คำถามที่พบบ่อย
Robust optimisation แตกต่างจาก Stochastic programming อย่างไร?
Robust optimisation แสวงหาการตัดสินใจเดียวที่สามารถนำไปปฏิบัติได้และใกล้เคียงค่าเหมาะสมที่สุดสำหรับทุกสถานการณ์ในชุดความไม่แน่นอนที่มีขอบเขต โดยไม่ต้องสมมติการแจกแจงความน่าจะเป็นใดๆ เหนือสถานการณ์เหล่านั้น Stochastic programming ใช้การแจกแจงความน่าจะเป็นที่ทราบ (หรือประมาณค่า) เพื่อหาค่าเหมาะสมที่สุดของประสิทธิภาพที่คาดหวัง โดยทั่วไปจะให้ผลลัพธ์เป็นนโยบายหรือการดำเนินการแก้ไข (recourse actions) แทนที่จะเป็นผลลัพธ์เดียวที่ตายตัว เลือ Robust optimisation เมื่อการรับประกันกรณีที่แย่ที่สุดมีความสำคัญและไม่มีการแจกแจงที่น่าเชื่อถือ เลือ Stochastic programming เมื่อมีการแจกแจงที่ดีและประสิทธิภาพเฉลี่ยเป็นเกณฑ์หลัก
ราคาของความ Robust คืออะไร?
ราคาของความ Robust คือการเพิ่มขึ้นของค่าวัตถุประสงค์ (สำหรับปัญหาการหาค่าต่ำสุด) เมื่อเทียบกับผลลัพธ์ที่เหมาะสมที่สุดแบบปกติที่ได้มาโดยไม่ได้คำนึงถึงความไม่แน่นอน Bertsimas และ Sim (2004) แสดงให้เห็นว่าสำหรับรูปแบบงบประมาณความไม่แน่นอนของพวกเขา ราคานี้จะเพิ่มขึ้นตามรากที่สองของจำนวนพารามิเตอร์ที่ไม่แน่นอนเท่านั้น ทำให้มีค่าไม่มากนักในทางปฏิบัติ การตรวจสอบช่องว่างนี้หลังจากการแก้ปัญหาเป็นสิ่งจำเป็น: หากมีขนาดใหญ่มาก ชุดความไม่แน่นอนอาจจะระมัดระวังเกินไป
ฉันควรเลือกรูปร่างของชุดความไม่แน่นอนแบบใด?
ชุดแบบกล่อง (Box sets) เป็นชุดที่ง่ายที่สุดและระมัดระวังที่สุด — แต่ละพารามิเตอร์เปลี่ยนแปลงอย่างอิสระ ชุดรูปวงรี (Ellipsoidal sets) (Ben-Tal & Nemirovski) จำลองการเปลี่ยนแปลงที่สัมพันธ์กันซึ่งถูกจำกัดด้วยนอร์มแบบยุคลิด และนำไปสู่โปรแกรมรูปกรวยอันดับสอง ชุดรูปทรงหลายเหลี่ยม / ชุดงบประมาณจำกัด (Polyhedral / budget-constrained sets) (Bertsimas & Sim) ควบคุมจำนวนพารามิเตอร์ที่สามารถเปลี่ยนแปลงพร้อมกันได้ รักษาความเป็นเชิงเส้น และลดการระมัดระวัง เลือกลักษณะตามความรู้เฉพาะทางเกี่ยวกับวิธีการเปลี่ยนแปลงที่เกิดขึ้นร่วมกันและประเภทของตัวแก้ปัญหาที่มีอยู่
Robust optimisation สามารถจัดการกับตัวแปรตัดสินใจที่เป็นจำนวนเต็มได้หรือไม่?
ได้ แต่ Robust integer programming และ Robust mixed-integer programming นั้นยากกว่ามาก Robust counterpart ของ mixed-integer linear programs มักจะเป็น NP-hard ในกรณีที่แย่ที่สุด Benders decomposition และ column-and-constraint generation algorithms เป็นแนวทางมาตรฐาน แต่ขนาดของปัญหาและความซับซ้อนของชุดความไม่แน่นอนต้องถูกควบคุมให้อยู่ในระดับที่จัดการได้
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.
ISBN: 9780691143682คัดลอกแล้วBertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.
เปิดเอกสารอ้างอิง DOIคัดลอกแล้ว