การหาค่าเหมาะที่สุดแบบนูน (Convex Optimization)
- ผู้เสนอ
- Stephen Boyd & Lieven Vandenberghe
- ปี
- 2004
- ประเภท
- Mathematical optimization framework
- กลุ่มวิธี
- Mathematical programming
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การหาค่าเหมาะที่สุดแบบนูน (Convex optimization) เป็นสาขาย่อยของการหาค่าเหมาะที่สุดทางคณิตศาสตร์ (mathematical optimization) ที่ศึกษาปัญหาการหาค่าต่ำสุดของฟังก์ชันนูน (convex functions) บนเซตนูน (convex sets) กรอบการทำงานนี้ซึ่งได้รับการทำให้เป็นทางการและเผยแพร่โดย Stephen Boyd และ Lieven Vandenberghe ในตำราเรียนสำคัญปี 2004 ของพวกเขา ได้รวมชุดปัญหาที่หลากหลายเข้าไว้ด้วยกัน — รวมถึงการโปรแกรมเชิงเส้น (linear programming), การโปรแกรมกำลังสอง (quadratic programming), การโปรแกรมกึ่งนิยาม (semidefinite programming), และการโปรแกรมกรวยอันดับสอง (second-order cone programming) — ภายใต้กรอบทฤษฎีเดียว คุณสมบัติที่บ่งชี้คือคำตอบที่เหมาะสมที่สุดเฉพาะที่ (locally optimal solution) จะเป็นคำตอบที่เหมาะสมที่สุดทั่วโลก (globally optimal) ด้วยเสมอ ทำให้สามารถจัดการได้และเชื่อถือได้สำหรับวิศวกรรม สถิติ การเรียนรู้ของเครื่อง และการวิจัยดำเนินงาน
แนวคิดเบื้องหลังวิธีการ
ลองนึกภาพหุบเขาที่มีลักษณะคล้ายชาม: ไม่ว่าคุณจะเริ่มกลิ้งลูกบอลจากที่ใดก็ตาม มันจะตกลงสู่จุดที่ต่ำที่สุดเดียวกันเสมอ การหาค่าเหมาะที่สุดแบบนูนเป็นการทำให้เรขาคณิตนี้เป็นทางการทางคณิตศาสตร์ ฟังก์ชันวัตถุประสงค์ (objective function) คือชาม, ขอบเขตที่ทำได้ (feasible region) คือภูมิประเทศที่มีรูปร่างนูน, และอัลกอริทึมคือลูกบอลที่เคลื่อนที่ตามความลาดชัน เนื่องจากไม่มีหลุมที่ต่ำเฉพาะที่ที่ซ่อนอยู่หรือสันเขาที่หลอกลวง คุณจึงรับประกันว่าจะพบค่าต่ำสุดทั่วโลกที่แท้จริง — ทำให้แนวทางนี้แตกต่างอย่างสิ้นเชิงและน่าเชื่อถือกว่าการหาค่าเหมาะที่สุดแบบไม่เป็นเชิงเส้นทั่วไป
ประวัติศาสตร์
รากฐานทางทฤษฎีของการวิเคราะห์แบบนูนย้อนกลับไปถึงผลงานของ Minkowski และ Farkas ในช่วงต้นศตวรรษที่ยี่สิบ โดยมีการโปรแกรมเชิงเส้นปรากฏขึ้นในทศวรรษที่ 1940 ผ่าน Dantzig วิธีการภายในจุด ซึ่งนำเสนอโดย Karmarkar ในปี 1984 และได้รับการปรับปรุงในช่วงทศวรรษที่ 1990 ทำให้โปรแกรมแบบนูนทั่วไปสามารถคำนวณได้ ตำราเรียนปี 2004 ของ Boyd และ Vandenberghe จาก Cambridge University Press ซึ่งมีให้ใช้งานออนไลน์ฟรี ได้สังเคราะห์ผลลัพธ์หลายทศวรรษให้เป็นกรอบการทำงานที่สอดคล้องกันและเข้าถึงได้ และได้ก่อให้เกิดกระบวนทัศน์การโปรแกรมแบบนูนที่มีระเบียบวินัย (disciplined convex programming paradigm) ซึ่งนำไปใช้ใน CVX, CVXPY และเครื่องมือที่เกี่ยวข้อง
ควรใช้เมื่อใด
ใช้การหาค่าเหมาะที่สุดแบบนูนเมื่อวัตถุประสงค์และข้อจำกัดทั้งหมดสามารถแสดงหรือปรับรูปแบบใหม่ให้เป็นฟังก์ชันนูนได้ เหมาะสำหรับการหาค่าเหมาะที่สุดของพอร์ตโฟลิโอ (portfolio optimization), การถดถอยพร้อมการทำให้เป็นระเบียบ (regression with regularization), การไหลของเครือข่าย (network flow), เครื่องมือสนับสนุนเวกเตอร์ (support vector machines), และการออกแบบระบบควบคุม (control design) ข้อสมมติฐานหลักคือความเป็นนูนของเซตที่ทำได้และวัตถุประสงค์ การละเมิดข้อสมมติฐานเหล่านี้จะทำให้การรับประกันความเป็นค่าเหมาะที่สุดทั่วโลกหายไป เมื่อปัญหามีลักษณะไม่นูน (nonconvex) ให้พิจารณาการผ่อนคลายแบบนูน (convex relaxations) หรือตัวแก้ปัญหาแบบไม่เป็นเชิงเส้นเฉพาะที่ (local nonlinear solvers) เลือกใช้ตัวแก้ปัญหาการโปรแกรมเชิงเส้น (linear programming solvers) เมื่อปัญหามีลักษณะเป็นเชิงเส้นเพื่อเพิ่มประสิทธิภาพ
ข้อจำกัดและข้อควรพิจารณา
- ความสามารถในการนำไปใช้ขึ้นอยู่กับว่าปัญหาสามารถกำหนดหรือประมาณในรูปแบบนูนได้หรือไม่ ปัญหาในโลกแห่งความเป็นจริงหลายอย่างมีลักษณะไม่เป็นนูนโดยเนื้อแท้
- วิธีการภายในจุดจะจัดเก็บและแยกวิเคราะห์เมทริกซ์ขนาดใหญ่ ทำให้ข้อกำหนดด้านหน่วยความจำและเวลาสูงสำหรับปัญหาที่มีมิติสูงมาก
- การผ่อนคลายแบบนูนของปัญหาเชิงการจัด (combinatorial) หรือปัญหาจำนวนเต็ม (integer problems) อาจให้ผลลัพธ์ที่เป็นเศษส่วนซึ่งไม่สามารถนำไปปฏิบัติได้โดยตรงหากไม่มีฮิวริสติกการปัดเศษ
- การสร้างแบบจำลองปัญหาต้องใช้ความเชี่ยวชาญ: การยืนยันความเป็นนูนที่ไม่ถูกต้องจะทำให้การรับประกันทางทฤษฎีหายไปโดยไม่แสดงผล ในขณะที่ตัวแก้ปัญหาจะยังคงให้คำตอบ
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- รับประกันคำตอบที่เหมาะสมที่สุดทั่วโลกเสมอเมื่อสามารถสร้างรูปแบบที่เป็นนูนได้ — ไม่มีความเสี่ยงที่จะลู่เข้าสู่ค่าต่ำสุดเฉพาะที่
- สามารถแก้ปัญหาได้ในเวลาพหุนามโดยใช้วิธีการภายในจุด ให้ประสิทธิภาพที่ใช้งานได้จริงแม้สำหรับปัญหาขนาดใหญ่
- ทฤษฎีความเป็นคู่ (Duality theory) ให้ใบรับรองความเป็นค่าเหมาะที่สุด, ตัวแปรคู่ที่มีการตีความทางเศรษฐศาสตร์, และการวิเคราะห์ความไวโดยไม่มีค่าใช้จ่ายเพิ่มเติม
- ชุดกฎการประกอบที่หลากหลาย (DCP) ช่วยให้สามารถตรวจสอบความเป็นนูนได้อย่างเป็นระบบและแปลงเป็นรูปแบบที่พร้อมสำหรับตัวแก้ปัญหาโดยอัตโนมัติ
การประยุกต์ใช้
- การหาค่าเหมาะที่สุดของพอร์ตโฟลิโอ: การหาค่าต่ำสุดของความแปรปรวน (variance) หรือ CVaR ภายใต้เป้าหมายผลตอบแทนและข้อจำกัดการจัดสรรในด้านการเงินเชิงปริมาณ
- การเรียนรู้ของเครื่อง: การฝึกเครื่องมือสนับสนุนเวกเตอร์, การถดถอยแบบ Lasso และ Ridge, และการถดถอยโลจิสติก (logistic regression) เป็นโปรแกรมแบบนูนที่เป็นแบบฉบับ
- การประมวลผลสัญญาณและภาพ: การวัดค่าแบบบีบอัด (compressed sensing), การลดทอนสัญญาณรบกวนแบบผลรวมแปรผัน (total-variation denoising), และการกู้คืนแบบเบาบาง (sparse recovery) ถูกกำหนดรูปแบบเป็นโปรแกรมแบบนูน
- การจัดสรรเครือข่ายและทรัพยากร: การกำหนดเส้นทางที่เหมาะสมที่สุด, การควบคุมพลังงานในเครือข่ายไร้สาย, และการจัดสรรแบนด์วิดท์ภายใต้ข้อจำกัดด้านความจุ
- ระบบควบคุม: การสังเคราะห์ตัวควบคุม H-infinity โดยใช้การโปรแกรมกึ่งนิยาม และการตรวจสอบเสถียรภาพของ Lyapunov
วิธีการทำงาน
วิธีการทำงาน
นักวิเคราะห์กำหนดปัญหาการตัดสินใจให้เป็นโปรแกรมแบบนูนมาตรฐาน: หาค่าต่ำสุดของฟังก์ชันวัตถุประสงค์แบบนูน f0(x) ภายใต้ข้อจำกัดอสมการแบบนูน fi(x) ≤ 0 และข้อจำกัดสมการแบบสัมพรรค (affine equality constraints) Ax = b การกำหนดรูปแบบให้ถูกต้อง — การเลือกการแสดงตัวแปรที่เหมาะสมและการแสดงข้อจำกัดทั้งหมดในรูปแบบนูน — เป็นขั้นตอนแรกที่สำคัญซึ่งกำหนดว่าการรับประกันที่มีประสิทธิภาพจะสามารถนำมาใช้ได้หรือไม่
สูตร
\min_{x \in \mathcal{C}} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0,\; i=1,\ldots,m,\; Ax = bก่อนทำการแก้ปัญหา ฟังก์ชันทุกตัวในปัญหาจะได้รับการตรวจสอบว่าเป็นฟังก์ชันนูน ซึ่งหมายความว่าอพิกราฟ (epigraph) ของฟังก์ชันนั้นเป็นเซตนูน หรือเทียบเท่ากัน ฟังก์ชันนั้นสอดคล้องกับอสมการจุดกึ่งกลาง (midpoint inequality) ชุดกฎการโปรแกรมแบบนูนที่มีระเบียบวินัย (disciplined convex programming - DCP) ของ Boyd และ Vandenberghe ให้วิธีการที่เป็นระบบในการยืนยันความเป็นนูนโดยใช้กฎการประกอบ (composition rules) ดังนั้นนักวิเคราะห์จึงไม่ต้องพิสูจน์ความเป็นนูนตั้งแต่ต้นสำหรับแต่ละปัญหา
สูตร
f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y), \quad \forall x,y \in \text{dom}\,f,\; \theta \in [0,1]ลากรางเจียน (Lagrangian) L(x, λ, ν) ถูกสร้างขึ้นโดยการผ่อนคลายข้อจำกัดด้วยตัวคูณคู่ (dual multipliers) ภายใต้คุณสมบัติคุณสมบัติการคัดกรองของสเลเตอร์ (Slater's constraint qualification) ความเป็นคู่ที่แข็งแกร่ง (strong duality) จะเป็นจริง: ค่าเหมาะที่สุดของคู่สามีภรรยา (primal) และคู่ (dual) จะตรงกัน และเงื่อนไข KKT (KKT conditions) — ความคงที่ (stationarity), ความเป็นไปได้ของคู่สามีภรรยา/คู่ (primal/dual feasibility), และความหย่อนคล้อยส่วนเติมเต็ม (complementary slackness) — เป็นทั้งเงื่อนไขที่จำเป็นและเพียงพอสำหรับความเป็นค่าเหมาะที่สุดทั่วโลก ความเป็นคู่ยังให้ใบรับรองความเป็นค่าเหมาะที่สุดและข้อมูลความไว (sensitivity information) เกี่ยวกับว่าค่าเหมาะที่สุดเปลี่ยนแปลงไปอย่างไรตามข้อมูลของปัญหา
สูตร
L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^{m}\lambda_i f_i(x) + \nu^T(Ax-b), \quad \lambda_i \geq 0วิธีการภายในจุด (interior-point methods), รูปแบบต่างๆ ของการไล่ระดับ (gradient descent variants), หรืออัลกอริทึมใกล้เคียง (proximal algorithms) จะเคลื่อนที่ซ้ำๆ ผ่านเซตที่ทำได้ (feasible set) ไปสู่ค่าเหมาะที่สุด สำหรับปัญหาที่ไม่มีข้อจำกัดและเรียบ (smooth unconstrained problems) ขั้นตอนการไล่ระดับด้วยขนาดขั้นตอนที่เหมาะสมจะลู่เข้าในอัตราที่ทราบ สำหรับปัญหาที่มีข้อจำกัดหรือมีโครงสร้าง วิธีการภายในจุดจะบรรลุการลู่เข้าในเวลาพหุนาม (polynomial-time convergence) ด้วยความแม่นยำสูง และวิธีการลำดับแรก (first-order methods) เช่น ADMM จะปรับขนาดให้เข้ากับอินสแตนซ์ขนาดใหญ่มาก
สูตร
x^{(k+1)} = x^{(k)} - t_k \nabla f_0(x^{(k)}), \quad t_k > 0ข้อผิดพลาดที่พบบ่อย
- การสมมติว่าปัญหามีลักษณะเป็นนูนโดยไม่มีการตรวจสอบอย่างเป็นทางการ — ต้องตรวจสอบกฎการประกอบอย่างเข้มงวด ไม่ใช่ด้วยการตรวจสอบด้วยสายตาของฟังก์ชันวัตถุประสงค์
- การละเลยการปรับสภาพเชิงตัวเลข (numerical conditioning): ปัญหาที่มีการปรับสเกลไม่ดีทำให้ตัวแก้ปัญหาให้ผลลัพธ์ที่ไม่ถูกต้องหรือไม่สามารถทำได้ แม้ว่าในทางทฤษฎีจะสามารถทำได้ก็ตาม
- การละเลยช่องว่างความเป็นคู่ (duality gaps) ในตัวแก้ปัญหาที่ไม่ใช่มาตรฐานหรือในสถานการณ์ที่เงื่อนไขของสเลเตอร์ไม่เป็นจริง ซึ่งอาจทำให้การอ้างสิทธิ์ความเป็นค่าเหมาะที่สุดตาม KKT ไม่ถูกต้อง
- การปฏิบัติต่อคำตอบของการผ่อนคลายแบบนูนเสมือนเป็นคำตอบของปัญหาเดิม เมื่อข้อจำกัดจำนวนเต็มหรือเชิงการจัดถูกละทิ้งระหว่างการปรับรูปแบบ
คำถามที่พบบ่อย
ฉันจะทราบได้อย่างไรว่าปัญหาของฉันเป็นปัญหาแบบนูนหรือไม่?
ตรวจสอบว่าฟังก์ชันวัตถุประสงค์และฟังก์ชันข้อจำกัดแต่ละรายการเป็นไปตามอสมการความเป็นนูนของจุดกึ่งกลางหรือไม่ หรือตรวจสอบความเป็นนูนโดยใช้ชุดกฎการโปรแกรมแบบนูนที่มีระเบียบวินัย หากฟังก์ชันทุกตัวถูกสร้างขึ้นจากส่วนประกอบพื้นฐานที่เป็นนูนที่ทราบซึ่งรวมกันตามกฎการประกอบที่รักษาความเป็นนูน (ฟังก์ชันภายนอกที่ไม่ลดลงและเป็นนูน, ฟังก์ชันภายในที่เป็นนูน ฯลฯ) ปัญหานั้นจะเป็นปัญหาแบบนูน บทที่ 3 ของ Boyd และ Vandenberghe นำเสนอรายการฟังก์ชันนูนที่ครอบคลุม
อะไรคือความแตกต่างระหว่างการหาค่าเหมาะที่สุดแบบนูนและการโปรแกรมเชิงเส้น?
การโปรแกรมเชิงเส้นเป็นกรณีพิเศษของการหาค่าเหมาะที่สุดแบบนูน ซึ่งทั้งวัตถุประสงค์และข้อจำกัดทั้งหมดเป็นฟังก์ชันสัมพรรค (เชิงเส้น) การหาค่าเหมาะที่สุดแบบนูนมีความครอบคลุมมากกว่ามาก รวมถึงโปรแกรมกำลังสอง, โปรแกรมกรวยอันดับสอง, และโปรแกรมกึ่งนิยาม แม้ว่าวิธีการซิมเพล็กซ์ (simplex) และวิธีการภายในจุดจะแก้ปัญหาการโปรแกรมเชิงเส้นได้ แต่เฉพาะวิธีการภายในจุดเท่านั้นที่สามารถขยายไปยังคลาสแบบนูนทั้งหมดได้โดยตรง
การหาค่าเหมาะที่สุดแบบนูนสามารถจัดการกับตัวแปรจำนวนเต็มหรือไบนารีได้หรือไม่?
โดยตรงไม่ได้ — ข้อจำกัดจำนวนเต็มทำให้ปัญหามีความซับซ้อนเชิงการจัด (combinatorially hard) และโดยทั่วไปไม่เป็นนูน แนวทางทั่วไปคือการแก้ปัญหาการผ่อนคลายแบบนูน (โดยละทิ้งความเป็นจำนวนเต็ม) เพื่อให้ได้ขอบเขตล่าง จากนั้นจึงใช้การแตกแขนงและขอบเขต (branch-and-bound) หรือการปัดเศษ ตัวแก้ปัญหาการโปรแกรมแบบผสมจำนวนเต็มแบบนูน (Convex mixed-integer programming solvers) จะรวมแนวคิดเหล่านี้เข้าด้วยกัน แต่การรับประกันความเป็นค่าเหมาะที่สุดทั่วโลกของการหาค่าเหมาะที่สุดแบบนูนบริสุทธิ์จะไม่สามารถนำมาใช้ได้ในความทั่วไปทั้งหมด
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
ISBN: 978-0-521-83378-3คัดลอกแล้ว