- เป็นตำราที่อธิบายหลักการและอัลกอริทึมของการหาค่าที่เหมาะที่สุดเชิงคณิตศาสตร์อย่างเป็นระบบ ครอบคลุมทั้งปัญหาแบบต่อเนื่องและไม่ต่อเนื่อง
- อธิบายแนวทางที่หลากหลายอย่างเป็นลำดับ ตั้งแต่เทคนิคที่อิงอนุพันธ์ไปจนถึงวิธีเชิงความน่าจะเป็นและเชิงวิวัฒนาการ
- ครอบคลุมโครงสร้างทางคณิตศาสตร์ที่จำเป็นต่อการประยุกต์ใช้จริง เช่น ข้อจำกัด, ภาวะคู่, การโปรแกรมเชิงเส้น และการโปรแกรมกำลังสอง
- ในแต่ละบทมีสรุปและแบบฝึกหัด เพื่อให้เรียนรู้ควบคู่กับการลงมือปฏิบัติ
- เผยแพร่ภายใต้โอเพนไลเซนส์ของ MIT Press (CC BY-NC-ND)
คำนำและภาพรวม
- หนังสือเล่มนี้เป็นตำราว่าด้วยทฤษฎีและการนำอัลกอริทึมสำหรับแก้ปัญหาการหาค่าที่เหมาะที่สุดไปใช้งานจริง โดยตีพิมพ์เป็นฉบับที่ 2
- ผู้เขียนคือ Mykel J. Kochenderfer และ Tim A. Wheeler
- จัดพิมพ์โดย MIT Press และเผยแพร่ภายใต้ไลเซนส์ Creative Commons แบบห้ามใช้เชิงพาณิชย์และห้ามดัดแปลง
- หลังคำนำและกิตติกรรมประกาศ เนื้อหาประกอบด้วย 13 บท
- แต่ละบทจัดโครงสร้างแบบเน้นการเรียนรู้ โดยประกอบด้วยแนวคิดหลัก, สรุป, และแบบฝึกหัด
บทที่ 1. บทนำ
- แนะนำประวัติศาสตร์, กระบวนการ, การนิยามเชิงคณิตศาสตร์, และสาขาการประยุกต์ใช้ของการหาค่าที่เหมาะที่สุด
- อธิบายค่าสุดขั้ว (minima) และ เงื่อนไขความเป็นค่าที่เหมาะที่สุด (optimality conditions)
- มีภาพรวมและสรุป, พร้อมแบบฝึกหัดของทั้งบท
บทที่ 2. อนุพันธ์และเกรเดียนต์
- อธิบายคำนิยามและวิธีคำนวณของอนุพันธ์ตัวแปรเดียวและหลายตัวแปร
- ครอบคลุมเทคนิคการหาอนุพันธ์เชิงตัวเลข (numerical differentiation) และ การหาอนุพันธ์อัตโนมัติ (automatic differentiation)
- กล่าวถึงregression gradient และ เทคนิคการประมาณเชิงสุ่ม (SPSA)
บทที่ 3. การครอบช่วง (Bracketing)
- อธิบายแนวคิดของเอกยอด (unimodality) และขั้นตอนของการหาช่วงตั้งต้น
- รวมอัลกอริทึมแบบอิงช่วง เช่น การค้นหาแบบฟีโบนัชชี, การค้นหาแบบอัตราส่วนทองคำ, และการค้นหาแบบประมาณกำลังสอง
- ครอบคลุมวิธี Shubert-Piyavskii และ การแบ่งครึ่งช่วง (bisection)
บทที่ 4. การลดลงเฉพาะที่ (Local Descent)
- อธิบายแนวคิดของการวนซ้ำตามทิศทางการลดลง (descent direction iteration) และ ขนาดก้าว (step factor)
- ครอบคลุมเทคนิคการค้นหาตามเส้น (line search) และ การค้นหาตามเส้นแบบประมาณ
- กล่าวถึงแนวทางtrust region และ เงื่อนไขการยุติ
บทที่ 5. วิธีอันดับหนึ่ง (First-Order Methods)
- ครอบคลุมวิธีสำคัญ เช่น gradient descent, conjugate gradient, momentum, Nesterov momentum
- รวมอัลกอริทึมสมัยใหม่ เช่น AdaGrad, RMSProp, Adadelta, Adam, Hypergradient Descent
- มีสรุปลักษณะเด่นและการเปรียบเทียบของแต่ละวิธี
บทที่ 6. วิธีอันดับสอง (Second-Order Methods)
- อธิบายวิธีของนิวตัน (Newton’s Method) และ วิธีเส้นตัด (Secant Method)
- ครอบคลุมอัลกอริทึม Levenberg-Marquardt และวิธีแบบกึ่งนิวตัน (Quasi-Newton)
- ปิดท้ายด้วยสรุปและแบบฝึกหัด
บทที่ 7. วิธีตรง (Direct Methods)
- แนะนำ coordinate search, Powell, Hooke-Jeeves, pattern search, และวิธีซิมเพล็กซ์ของ Nelder-Mead
- รวมเทคนิคDivided Rectangles
- เน้นแนวทางการหาค่าที่เหมาะที่สุดที่ไม่อาศัยอนุพันธ์
บทที่ 8. วิธีเชิงสุ่ม (Stochastic Methods)
- กล่าวถึงแนวทางเชิงสุ่ม เช่น noisy descent, mesh adaptive search, derivative-free optimization
- ครอบคลุม simulated annealing, cross-entropy, natural evolution strategies, covariance matrix adaptation (CMA)
- เน้นประสิทธิภาพของการค้นหาแบบอิงความน่าจะเป็น
บทที่ 9. วิธีแบบประชากร (Population Methods)
- อธิบายเทคนิคการค้นหาแบบประชากร เช่น genetic algorithms, differential evolution, particle swarm optimization (PSO)
- รวม Firefly, Cuckoo Search, และวิธีแบบไฮบริด
- แก้ปัญหาด้วยโครงสร้างของการวนซ้ำแบบประชากร (population iteration)
บทที่ 10. ข้อจำกัด (Constraints)
- อธิบายแนวคิดพื้นฐานของการหาค่าที่เหมาะที่สุดภายใต้ข้อจำกัด (constrained optimization) และประเภทของข้อจำกัด
- ครอบคลุม วิธีตัวคูณลากร็องจ์, ตัวแปรส่วนเกิน, penalty และวิธี interior point
- กล่าวถึงการแปลงเพื่อลดข้อจำกัด (transformations) และ method of multipliers
บทที่ 11. ภาวะคู่ (Duality)
- อธิบายปัญหาคู่ (dual problem) และ วิธี primal-dual
- ครอบคลุม dual ascent และ ADMM (Alternating Direction Method of Multipliers)
- กล่าวถึงการประยุกต์ใช้กับการหาค่าที่เหมาะที่สุดแบบกระจาย (distributed methods)
บทที่ 12. การโปรแกรมเชิงเส้น (Linear Programming)
- อธิบายการนิยามปัญหา, Simplex Algorithm, และ dual certificates
- นำเสนอโครงสร้างของการหาค่าที่เหมาะที่สุดภายใต้ข้อจำกัดเชิงเส้นอย่างเป็นระบบ
บทที่ 13. การโปรแกรมกำลังสอง (Quadratic Programming)
- การนิยามปัญหาที่มีฟังก์ชันวัตถุประสงค์กำลังสองและข้อจำกัดเชิงเส้น
- กล่าวถึงปัญหาleast squares และ ข้อจำกัดอสมการเชิงเส้น
- ครอบคลุมleast distance programming
ภาคผนวกและข้อมูลอื่น ๆ
- ท้ายแต่ละบทมีสรุปและแบบฝึกหัด
- จัดพิมพ์โดย MIT Press ฉบับปี 2025 และอนุญาตให้เผยแพร่ต่อแบบไม่ใช้เชิงพาณิชย์ (CC BY-NC-ND)
- จัดหน้าเอกสารด้วย LaTeX และระบุช่องทางติดต่อที่ bugs@algorithmsbook.com
4 ความคิดเห็น
ตอนนี้เข้าไม่ได้แล้วครับ ฮือ
https://algorithmsbook.com/optimization/#download
ตอนนี้ลิงก์เหมือนจะเปลี่ยนไปนิดหน่อย สามารถดูหรือดาวน์โหลด PDF ได้จากที่นี่ครับ
ขอบคุณครับ!!
ความคิดเห็นจาก Hacker News
ดีใจที่ได้เห็นหัวข้อ optimization ขึ้นหน้าแรกของ HN
อยากแนะนำ เว็บสำหรับทำภาพข้อมูล LP ที่ผมทำขึ้นมา สามารถดูได้แบบภาพว่าอัลกอริทึมของ Linear Programming ตอบสนองอย่างไรเมื่อเงื่อนไขข้อจำกัดหรือฟังก์ชันวัตถุประสงค์เปลี่ยนไป
ถ้าเข้าไปที่ หน้าเดโม จะมีการวาดรูปหลายเหลี่ยมให้อัตโนมัติ และสามารถลากจุดยอดหรือเส้นข้อจำกัดเพื่อสังเกต iteration ของอัลกอริทึมได้
ตอนนี้ยังไม่ค่อยสมบูรณ์นัก แต่ถ้าเป็นคนที่ชอบการเรียนรู้แบบ เห็นภาพ น่าจะลองเล่นได้สนุก ยินดีรับฟีดแบ็ก
อยากแชร์แหล่งข้อมูลเกี่ยวกับ metaheuristics
ที่ Timefold ซึ่งผมทำงานอยู่ เราใช้อัลกอริทึมอย่าง Tabu Search และ Simulated Annealing ที่มีในหนังสือเหล่านี้เพื่อหา คำตอบใกล้เคียงที่เหมาะที่สุด ได้อย่างรวดเร็ว
แผนภาพ อัลกอริทึม local search ในเอกสารของ Timefold ก็น่าดูเช่นกัน
เป็น ตำรา optimization ภายใต้ไลเซนส์ CC ความยาว 521 หน้า และดูยอดเยี่ยมมาก
ช่วงต้นเล่มพูดถึง gradient-based algorithm สมัยใหม่ที่อิง automatic differentiation (เช่น Adam) และช่วงท้ายเล่ม (บทที่ 12) ว่าด้วย linear optimization (เช่น simplex)
มีแบบฝึกหัดเยอะมาก และเป็นหนังสือแบบที่ผมรอมานานพอดี
ผมคิดว่าอัลกอริทึม optimization ไม่ได้มีไว้แค่แก้ปัญหา แต่เป็นความพยายามไปสู่ “ตัวแก้ปัญหาทั่วไป” ด้วย กล่าวคือแทนที่โปรแกรมจะหาคำตอบโดยตรง เรากลับนิยามว่า ‘คำตอบควรมีลักษณะอย่างไร’ แล้วจึงใช้ optimization กับสิ่งนั้น
AI ในปัจจุบันก็อิงอยู่บนแนวทางแบบนี้เช่นกัน
หนังสือเล่มนี้ของ Kochenderfer และงานก่อนหน้าของเขา Decision Making Under Uncertainty(PDF) เป็นหนังสือเทคนิคที่ผมชอบที่สุดเล่มหนึ่ง
คำอธิบายชัดเจน งานภาพยอดเยี่ยม และครอบคลุม วิธีคิดเรื่อง optimization ที่หลากหลายนอกเหนือจาก gradient descent
แม้โค้ดจะเขียนด้วย Julia แต่ก็ย้ายไปภาษาอื่นได้ไม่ยาก ไม่ควรยึดติดกับภาษา แต่ควรโฟกัสที่แนวคิด
optimization ไม่ใช่แค่เทคนิค แต่คือ วิธีคิดในการแก้ปัญหาที่ยาก โดยตัวมันเอง
หนังสือเล่มนี้เป็นแหล่งข้อมูลหายากที่รวม CMA-ES, surrogate model, Gaussian process ไว้ในเล่มเดียว
ถ้ามีหนังสือแบบนี้ตอนทำวิจัยระดับปริญญาตรีคงช่วยได้มาก สมัยก่อนเนื้อหาแนวนี้กระจัดกระจายอยู่ตามงานวิจัยและหนังสือต่าง ๆ
ตอนเรียนปริญญาเอก ผมอ่านหนังสือเล่มนี้อย่างละเอียดหลายรอบ ผมทำวิจัยด้าน โครงข่ายประสาทเทียมและการวิเคราะห์เชิงตัวเลข และรู้สึกว่าหนังสือนี้บาลานซ์ระหว่างความลึกกับความกว้างได้ดีมาก
ตอนนี้ก็ยังหยิบมาใช้อ้างอิงอยู่บ่อย ๆ
รู้สึกแปลกใจที่หนังสือใส่เมตาฮิวริสติกอย่าง Firefly, Cuckoo Search มาด้วย
อัลกอริทึมพวกนี้ไม่ได้รับความเชื่อถือในแวดวงวิชาการ และก็ถูกวิจารณ์ไว้ในบทความ ITOR ด้วย
มีชุมชนขนาดเล็กที่ทำวิจัยแนวนี้โดยเฉพาะและอ้างอิงกันเองจนเกิดเป็นฟองสบู่ บางครั้งก็เป็นประเด็นถกเถียงในงานประชุมวิชาการ
บท multiobjective optimization ทำได้ดีมาก
อยากรู้ว่ามีหนังสือหรือแหล่งข้อมูลอื่นที่โฟกัสหัวข้อนี้โดยตรงไหม
อยากให้ช่วยเปรียบเทียบหนังสือเล่มนี้กับ Numerical Optimization ของ Nocedal & Wright