top of page
รูปภาพนักเขียนThasvarit Kruerklai

วิธีแก้ปัญหา Optimization บน Python ด้วย CVXPY


บทความนี้เราจะมาพูดเรื่องการใช้ Python แก้ปัญหา Optimization กัน


เท้าความก่อนว่า โอเค ตอนนี้เรารู้แล้วว่าการทำ Portfolio Optimization คือการปรับพอร์ตโดยเอาไอเดียเรื่องการทำ optimization มาจับ (โดยการปรับที่ว่าจะบอกสิ่งที่ดีที่สุดที่ตั้งอยู่บน “view” ของเรา)

ไอเดียหลัก ๆ ของการทำ optimization จะมีส่วนประกอบหลัก ๆ 2 อย่าง คือ objective function คือ function ที่เราอยากหา max หรือ min กับ constraint คือข้อจำกัดที่จะเหมือนมาเป็นตัวตีกรอบให้กับ objective function


(ย่อหน้าถัดไป จะอธิบายโดยทุกคนสามารถเปิด colab run code ไปด้วยกันได้นะ, รวบรวม/จัดทำโดย อาจารย์อุดมศักดิ์ รักวงษ์วาน และคุณกฤติพัฒน์ กฤตาคม)


ทีนี้แล้วถ้าเราจะเอาสมองเราไปใส่ python แล้วล่ะ จะต้องทำยังไงบ้าง เราก็จะ Intro ด้วยการแก้ปัญหารูปแบบที่ Basic ที่สุดในบรรดาการทำ optimization คือการทำ linear programming

linear programming เป็นการ optimize ที่ทั้ง objective function และ constraint เป็นเส้นตรง (ก็ linear แปลว่าตรงเนอะ) โดยวิธีทำก็เรียบง่ายมาก คือก่อนอื่นก็เขียนใส่กระดาษก่อนว่าถ้าอยากให้สมการอยู่ในรูป matrix ต้องเขียนว่ายังไง


จากนั้นก็เอา matrix ที่เขียนไปกรอก ๆ ๆ ลง numpy array แล้วเอาตัวแปรแต่ละตัวไปยัด function linprog ของ scipy สำหรับคำนวณของ linear programming เท่านี้เราก็ได้คำตอบกลับมาแล้ว

ความยากอย่างหนึ่งของการทำ optimization คือการจัดรูปให้ถูก form เพื่อให้ solver แก้ถูก (อย่างตะกี้ก็คือเราต้องเขียนในรูป matrix ก่อน) ซึ่งก็มี library บางตัวที่เอื้อเรื่องนี้ คือคุณไม่ต้องจัดเข้า standard form ก็ได้ จะยัดเข้ามาในรูปไหนก็ได้ เดี๋ยวจัดเข้า form ที่ต้องให้เอง และหนึ่งในนั้นคือ CVXPY

ซึ่งถ้าลองไปกดดูใน colab ก็จะเห็นว่า section linear ที่ใช้ CVXPY ไม่ต้องจัดรูปอะไรเลย ได้สมการมายังไงก็ยัดเข้าไปทั้งอย่างนั้น โดยถ้าเลื่อนลงไปดูผลการคำนวณ ก็จะเห็นว่ามันเท่า ๆ กับวิธีก่อนหน้าเลย


ทีนี้เราจะขยับขึ้นมาหาปัญหาที่ยากขึ้นมาอีกนิดดูบ้าง คือการทำ quadratic programming

quadratic ก็คือสมการกำลัง 2 เนอะ ไส้ในก็จะมีส่วนประกอบ เช่น xx = x^2, yy = y^2, x*y = xy และถ้าเอาไปพล็อตก็จะได้กราฟที่มีหน้าตาเป็นเส้นโค้ง


ซึ่งก็เหมือนเดิมเลย เราจะแก้ด้วยวิธีแรก หรือวิธีที่ 2 ที่สำเร็จรูปมากกว่าก็ได้ แต่สำหรับวิธีที่ 2 เรื่องสำคัญที่เราต้องรู้เพราะมันแตกต่างจากตอนแก้ linear programming ก็คือถ้าเจอตัวแปรคนละตัวคูณกัน เช่น xy ตัว solver ของ CVXPY จะแก้สมการไม่ออก


ดังนั้นเราต้องช่วยจัด form (ทำลาย xy แล้วเปลี่ยนเป็นรูปอื่นโดยที่ค่ายังคงเดิม) โดยการใช้เลขมัธยมเลย จัดเข้ากำลัง 2 สมบูรณ์ แล้วบวกเข้าลบออกให้ค่าเท่าเดิม โดยถ้าลืมเรื่องนี้ไปแล้ว สามารถศึกษาได้จากวิดิโอของ Khan Academy คลิปนี้เลยครับ https://www.youtube.com/watch?v=bNQY0z76M5A


โอเค ทีนี้เราก็พอมีไอเดียแล้วเรื่อง linear กับ quadratic programming แล้ว ก็เสร็จสิ้นการปูพื้นเข้าสู่หัวข้อสำคัญ คือ convex programming


ก่อนอื่นถามว่าแล้วเจ้า convex นี่คืออะไร อธิบายง่าย ๆ มันคือ function ที่ถ้าเราสุ่มสร้างจุดขึ้นมา 2 จุดบนกราฟของ function เราจะสามารถลากเชื่อม 2 จุดนั้นได้เสมอ โดยเส้นที่ลากจะต้องไม่อยู่ใต้ส่วนไหนก็ตามของกราฟ (อยู่เหนือกราฟตลอด) โดยจริง ๆ ประเด็นก็คือมันเหมือนเป็นตัว general ที่ใช้พูดถึง linear ทุกตัวและ quadratic บางตัว (มีตัวยกเว้นเช่นกราฟรูปตัว U คว่ำ ที่ถ้าลองลากเส้นเชื่อมจุดดู เส้นจะอยู่ใต้ function)


ซึ่งความเจ๋งของ convex optimization มันอยู่ที่การหาค่าต่ำสุด เพราะถ้าเจอ local minimum (ลองดูจุดต่ำสุดของกราฟรูปตัว U ดู ก็จะเห็นว่าจุดที่อยู่ต่ำกว่าจุดข้าง ๆ ซ้ายขวา มันมีแค่จุดเดียวเลย คือตรงกลาง) แล้ว เราก็บอกได้เลยว่านั่นต้องเป็น global minimum ด้วย ก็คือนอกจากมันจะใช้ได้ มันก็แก้ไม่ยากด้วย นี่คือความพิเศษของปัญหา convex



โดยเรื่องนึงที่เราควรรู้ในการแก้ปัญหา convex programming คือ function ของ CVXPY ถูกสร้างขึ้นมาโดย base มาจาก disciplined convex programming (DCP) ที่เป็นคล้าย ๆ blue print ในการ formulate ปัญหา convex (”ถ้าเขียนตามนี้ได้ล่ะก็ ยังไงปัญหาที่คุณกำลังแก้ก็เป็น convex แน่ ๆ ก็จะได้แก้ออก”) โดยคุณสามารถเข้าไปดู function พวกนั้นได้ที่ https://www.cvxpy.org/tutorial/functions/index.html

0 ความคิดเห็น

Comments


bottom of page