Convex Optimization ใช้ทำอะไรได้บ้าง? เทคนิคตอบโจทย์ 5 วิธี

1. Unconstrained Optimization (scalar case)

เนื่องจาก สถานการณ์ไวรัสโคโรนา หรือโควิด-19 นาย พิภพ จึงไม่สามารถเข้าร่วมโครงการ SuperAI ได้อย่าง onsite และเปลี่ยนเป็นรูปแบบการประชุมออนไลน์ หรือ Zoom Meeting ทุกวัน ถ้าหาก การประชุม ดังกล่าว อยู่ใน จอทีวี ความสูง hนิ้ว และอยู่ที่ระดับเหนือพื้น dนิ้ว นายพิภพ จะต้องนั่งห่างจาก จอTV ในระยะกี่ นิ้วเพื่อที่ มีองศาในการมองจอที่มากที่สุด?

ก่อนอื่น เรามาทำความเข้าใจโจทย์ โดยวาดกราฟ

จากนั้น ก็เขียน objective function ซึ่งก็คือ องศา θในรูปของ ระยะห่าง x

เช่นเดียวกับข้อที่แล้ว หาจุด x ที่ทำให้ f’(x) เท่ากับ 0

สังเกตุได้ว่าวิธีนี้มีความต้องการอยู่ว่า

• f’(x) เป็นฟังก์ชัน คอนเวกซ์ ที่หาอนุพันธ์ได้ (differentiable & convex)

2. Unconstrained Optimization (vector case)

น้องพริม ชอบนำอาหารมาทานเป็นเพื่อน พี่ๆ อยู่เรื่อยๆ และในวันนี้ ก็ได้นำอาหาร มาในพัสดุ เป็นกล่องกระดาษสี่เหลี่ยม โดยกล่องมีความหนาด้าน ข้าง 2 ชั้น ด้านหน้าและหลัง 1 ชั้น พื้นหนา 3 ชั้น และไม่มีเพดาน ถ้าหากน้องพริมต้องการที่จะใช้วัสดุในการสร้างให้น้อยที่สุด โดยมีข้อแม้ว่ากล่องต้องบรรจุอาหารได้ อย่างน้อย 20 ลูกบาศก์เซนติเมตร กล่องนี้ต้องมีสัดส่วนเช่นไร?

สังเกตุได้ว่าโจทย์นี้มีความต่างจากโจทย์ที่แล้ว อยู่หลายอย่าง ตัวแปรนี้ที่นี้เป็น สัดส่วน ความยาว x ความกว้าง y และ ความสูง z และนอกจากนั้น มีข้อจำกัดว่ากล่อง ต้องบรรจุอาหารได้ อย่างน้อย 20 ลูกบาศก์เซนติเมตร

เช่นเดียวกับด้านบน เราหาจุด x ที่ f’(x) เป็น 0 โดยมีความแตกต่างว่า input มีหลายมิติ ฉะนั้น derivative ก็มีหลายมิติเช่นกัน โดยมิติที่ หนึ่งเป็น x และที่สองเป็น y derivative ของทุกมิติสามารถเขียนได้อย่างกระฉับ เช่น ∇f เรียกว่าเป็น

จากนี้เราก็ได้สมการหลายชั้น (simultaneous equations) เพื่อที่จะมาหาค่าตัวแปรได้

3. Constrained Optimization (equality constraints)

นาย กฤตเมธ ชอบรัปประทานบราวนี่ เป็นอย่างมาก และวันหนึ่งก็ตัดสินใจ เปิดร้านบราวนี่ โดยมีฟังก์ชันการผลิต f(x,y) ด้านล่าง โดยมี x เป็นหน่วยแรงงาน และ y เป็นหน่วยทรัพย์สินทุน โดยแรงงานมีค่าใช้จ่ายหน่วยละ 200 บาท และ ทรัพย์สินทุนหน่วยละ 250 บาท หากมีข้อจำกัดว่าค่าใช้จ่ายรวมห้ามเกิน 50000 บาท จุด (x,y) ที่มีการผลิตมากที่สุด คืออะไร?

จากรูปร่างของฟังก์ชัน เราสามารถบอกได้ว่าจุดสูงสุดของฟังก์ชัน จะเกิดขั้น เมื่อเราใช้หมดทั้ง 50000 บาท

คราวนี้เราจะลองใช้เทคนิกที่มีชื่อว่า วิธีตัวคูณลากรองจ์ หรือ Lagrange Multiplier โดยเทคนิกนี้บอกว่า จุดที่ดีที่สุดจะเกิดขึ้น เมื่อ อนุพันธ์ของฟังก์ชัน f และ อนุพันธ์ของข้อจำกด g ชี้ไปในทิศเดียวกัน

สังเกตุได้ว่า ∇f(x,y) และ ∇g(x,y) ชี้ไปในทิศเดียวกัน จึงเป็นสัดสวนต่อกัน และมี λ เป็นที่เรียกกันว่า Lagrange multiplier นั้นเอง

4. Constrained Optimization (inequality constraints)

จงหาจุดที่ดีที่สุดของฟังก์ชัน f(x,y) = xy โดยมีฟังก์ชันจำกัด เป็นอสมการดังนี้: x+y² ≤ 2, และ x, y ≥ 0

โจทย์นี้เพิ่มความซับซ้อนขึ้นมาอีกระดับ โดยคราวนี้จะมีอสมการเข้ามาด้วย เรามาเริ่มโดยการเขียน objective กับ constraint ฟังก์ชันใในแบบมาตรถาณกันก่อน

เสร็จแล้วก็เขียนสมการ Lagrange Multiplier ดังนี้

โดย มาตรถาณแล้ว เราจะเขียนฟังก์ชันทั้งหมด ในรูปแบบ Lagrangian ดังนี้

แล้วก็เขียน KKT condition ออกมา

จากนั้น เราก็ลองสุ่มหาจุดที่ multiplier λ ไม่เป็น 0 เนื่องจาก จุด

ไม่ใช่คำตอบแน่นอน สมมติว่า

ซึ่งถ้า x มากกว่า 0 ก็หมายความว่า λ₂ = 0 (condition 4) ซึ่งก็หมายความว่า y = λ₁ (condition 1) และ condition 2 ก็บอกว่า

คราวนี้ เราก็รู้จุดที่ดีที่สุด

5. Linear Programming

จงหาค่า x ที่ทำให้ objective function f(x) = cᵀx มีค่าน้อยที่สุดโดยมี constraint function g(x) = Ax ≤ b โดย มี x และ c เป็น vector ขนาด n มี b เป็น vector ขนาด m และ มี A เป็น matrix ขนาด m × n

ถึงเวลาที่เรามาเลิกทำมือกัน และมาใช้คอมกันได้แล้ว โดยผมขอแนะนำตระกูล CVX ของอาจารย์ Stephen Boyd ที่เอาใว้แก้โจทย์ convex optimization โดยมีภาษา Python Julia R และ Matlab รองรับ

อันนี้เป็นโค็ตสำหรับ generate โจทย์ขนาดเล็กๆ ขึ้นมา ในภาษา python

import cvxpy as cp
import numpy as np
# Generate a random non-trivial linear program.
m = 15
n = 10
np.random.seed(1)
s0 = np.random.randn(m)
lamb0 = np.maximum(-s0, 0)
s0 = np.maximum(s0, 0)
x0 = np.random.randn(n)
A = np.random.randn(m, n)
b = A@x0 + s0
c = -A.T@lamb0
# Define and solve the convex optimization problem.
x = cp.Variable(n)
prob = cp.Problem(cp.Minimize(c.T@x),[A@x <= b])
prob.solve()
# Print result.
print("\nThe optimal value is", prob.value)
print("A solution x is")
print(x.value)

ก็จะได้ output ดึงนี้

The optimal value is -15.220912604467838 
A solution x is 
[-1.10131657 -0.16370661 -0.89711643  0.03228613  0.60662428 -1.12655967   1.12985839  0.88200333  0.49089264  0.89851057]

ผมขอจบอยู่แค่นี้นะครับ convex optimization นอกจากนี้สามารถใช้แก้ปัญหาได้มากมาย ไม่ว่าจะเป็นเรื่องของ control, supply chain, logistics, advertising, finance ก็สามารถเอา convex optimization เข้ามาประยุกต์ใช้

หากอยากเรียนเพิ่มเติมเรื่อง Optimization ผมขอแนะนำหนังสือ Convex Optimization ของอาจารย์ Stephen Boyd รวมทั้ง ฉบับสั้น ของ Rosenberg และตอนผมเรียนเอง ก็ได้ใช้วิดีโอ ของ aa4cc และ Khanacademy รวมทั้ง documentation ของ cvxpy ด้วย