การเขียนโปรแกรมเชิงกำลังสอง (Quadratic ProgrammingหรือQP ) คือกระบวนการแก้ปัญหาการหาค่าเหมาะสมที่สุดทางคณิตศาสตร์ บางอย่าง ที่เกี่ยวข้อง กับ ฟังก์ชันกำลังสองโดยเฉพาะอย่างยิ่ง คือการหาค่าเหมาะสมที่สุด (ลดค่าหรือเพิ่มค่าสูงสุด) ของฟังก์ชันกำลังสองหลายตัวแปรภายใต้ข้อจำกัด เชิงเส้น ของตัวแปร การเขียนโปรแกรมเชิงกำลังสองเป็นประเภทหนึ่งของ การเขียนโปรแกรม แบบ ไม่เชิงเส้น

"การเขียนโปรแกรม" ในบริบทนี้หมายถึงขั้นตอนที่เป็นทางการสำหรับการแก้ปัญหาทางคณิตศาสตร์ การใช้งานนี้มีมาตั้งแต่ทศวรรษ 1940 และไม่ได้เชื่อมโยงกับแนวคิด "การเขียนโปรแกรมคอมพิวเตอร์" ในปัจจุบันโดยเฉพาะ เพื่อหลีกเลี่ยงความสับสน ผู้ปฏิบัติงานบางคนจึงนิยมใช้คำว่า "การเพิ่มประสิทธิภาพ" เช่น "การเพิ่มประสิทธิภาพกำลังสอง" ^{[ 1 ]}

ปัญหาการเขียนโปรแกรมกำลังสองที่มี ตัวแปร nตัวและ ข้อจำกัด mข้อสามารถกำหนดได้ดังนี้^{[ 2 ]} กำหนดให้:

• เวกเตอร์cที่ มีค่าเป็นจำนวน จริงและ มีมิติ n
• เมทริกซ์สมมาตรจริงมิติn × n Q
• เมทริกซ์จริงA ที่มีมิติ m × nและ
• เวกเตอร์จริงมิติm b ,

วัตถุประสงค์ของการเขียนโปรแกรมเชิงกำลังสองคือการหา เวกเตอร์ nมิติxที่จะ

ลดให้น้อยที่สุด	${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$
ขึ้นอยู่กับ	${\displaystyle A\mathbf {x} \preceq \mathbf {b} ,}$

โดยที่x ^Tแทนเวกเตอร์ทรานสโพสของxและสัญลักษณ์A x ⪯ bหมายความว่า สมาชิกทุกตัวของเวกเตอร์A xมีค่าน้อยกว่าหรือเท่ากับสมาชิกที่สอดคล้องกันของเวกเตอร์b (ความไม่เท่ากันแบบรายองค์ประกอบ)

ในกรณีพิเศษ เมื่อQเป็นเมทริกซ์สมมาตรบวกแน่นอนฟังก์ชันต้นทุนจะลดลงเหลือเพียงวิธีกำลังสองน้อยที่สุด:

ลดให้น้อยที่สุด	${\displaystyle {\tfrac {1}{2}}\|R\mathbf {x} -\mathbf {d} \|^{2}}$
ขึ้นอยู่กับ	${\displaystyle A\mathbf {x} \preceq \mathbf {b} ,}$

โดยที่Q = R ^T Rมาจากการแยกตัวประกอบ CholeskyของQและc = − R ^T d ในทางกลับกัน โปรแกรม กำลังสองน้อยที่สุดแบบมีข้อจำกัดใดๆ ก็ตาม สามารถกำหนดให้อยู่ในกรอบที่เทียบเท่ากันได้ในรูปแบบของปัญหาการเขียนโปรแกรมเชิงกำลังสอง แม้แต่สำหรับ เมทริกซ์ Rที่ไม่ใช่เมทริกซ์จัตุรัสทั่วไปก็ตาม

เมื่อทำการหาค่าต่ำสุดของฟังก์ชันfในบริเวณใกล้เคียงจุดอ้างอิงx ₀ ใดๆ นั้นQจะถูกกำหนดให้เป็นเมทริกซ์เฮสเซียนH ( f ( x ₀ ))และcจะถูกกำหนดให้เป็นเกรเดียนต์∇ f ( x ₀ )ปัญหาการเขียนโปรแกรมที่เกี่ยวข้องอีกปัญหาหนึ่งคือการเขียนโปรแกรมเชิงกำลังสองที่มีข้อจำกัดแบบกำลังสองซึ่งสามารถกำหนดได้โดยการเพิ่มข้อจำกัดแบบกำลังสองให้กับตัวแปรต่างๆ

สำหรับปัญหาทั่วไป มักใช้วิธีการที่หลากหลาย ซึ่งรวมถึง

• จุดภายใน
• ชุดแอคทีฟ^{[ ​​3 ]}
• ^{ลาก ราง}เจียนเสริม [ ^{4 ]}
• การไล่ระดับแบบคอนจูเกต
• การ ฉายภาพแบบไล่ระดับ
• ส่วนขยายของอัลกอริทึมซิมเพล็กซ์^{[ 3 ]}

ในกรณีที่Qเป็นเมทริกซ์บวกแน่นอนปัญหาดังกล่าวเป็นกรณีพิเศษของสาขาการหาค่าเหมาะสมที่สุดแบบนูน (convex optimization ) ที่ทั่วไปกว่า

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

${\displaystyle {\text{Minimize}}\quad {\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x} }$

${\displaystyle {\text{subject to}}\quad E\mathbf {x} =\mathbf {d} }$

กำหนดโดยระบบเชิงเส้น

${\displaystyle {\begin{bmatrix}Q&E^{\top }\\E&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix}-\mathbf {c} \\\mathbf {d} \end{bmatrix}}}$

โดยที่λคือเซตของตัวคูณลากรางจ์ซึ่งได้มาจากคำตอบพร้อมกับ x

วิธีที่ง่ายที่สุดในการแก้ปัญหาระบบนี้คือการแก้ปัญหาโดยตรง (เช่นการแยกตัวประกอบ LU ) ซึ่งเป็นวิธีที่ใช้ได้จริงสำหรับปัญหาขนาดเล็ก สำหรับปัญหาขนาดใหญ่ ระบบนี้ก่อให้เกิดความยากลำบากที่ผิดปกติบางประการ โดยเฉพาะอย่างยิ่งคือปัญหาจะไม่เป็นเมทริกซ์บวกแน่นอน (แม้ว่าQจะเป็นก็ตาม) ทำให้การหาวิธีแก้ปัญหาเชิงตัวเลขที่ดีอาจทำได้ยากมาก และมีวิธีการให้เลือกมากมายขึ้นอยู่กับปัญหา

หากข้อจำกัดไม่ได้ผูกตัวแปรไว้แน่นเกินไป วิธีการที่ค่อนข้างง่ายคือการเปลี่ยนตัวแปรเพื่อให้ข้อจำกัดเป็นไปตามเงื่อนไขโดยไม่มีเงื่อนไข ตัวอย่างเช่น สมมติว่าd = 0 (การขยายไปสู่ค่าที่ไม่ใช่ศูนย์นั้นทำได้ง่าย) เมื่อพิจารณาสมการข้อจำกัด:

${\displaystyle E\mathbf {x} =0}$

แนะนำตัวแปรใหม่yซึ่งกำหนดโดย

${\displaystyle Z\mathbf {y} =\mathbf {x} }$

โดยที่yมีมิติเท่ากับxลบด้วยจำนวนข้อจำกัด จากนั้น

${\displaystyle EZ\mathbf {y} =\mathbf {0} }$

และถ้า เลือก ค่า Zให้EZ = 0สมการข้อจำกัดก็จะได้รับการตอบสนองเสมอ การหาค่าZ ดังกล่าว จำเป็นต้องหาปริภูมิว่างของEซึ่งจะง่ายหรือง่ายขึ้นอยู่กับโครงสร้างของEการแทนค่าลงในรูปแบบกำลังสองจะทำให้ได้ปัญหาการหาค่าต่ำสุดแบบไม่มีข้อจำกัด:

${\displaystyle {\tfrac {1}{2}}\mathbf {x} ^{\top }Q\mathbf {x} +\mathbf {c} ^{\top }\mathbf {x} \quad \implies \quad {\tfrac {1}{2}}\mathbf {y} ^{\top }Z^{\top }QZ\mathbf {y} +\left(Z^{\top }\mathbf {c} \right)^{\top }\mathbf {y} }$

ซึ่งคำตอบของสมการนี้คือ:

${\displaystyle Z^{\top }QZ\mathbf {y} =-Z^{\top }\mathbf {c} }$

ภายใต้เงื่อนไขบางประการเกี่ยวกับQเมทริกซ์ลดรูปZ ^T QZ จะเป็นเมทริกซ์บวก แน่นอนสามารถเขียนรูปแบบหนึ่งของวิธีการไล่ระดับคอนจูเกตซึ่งหลีกเลี่ยงการคำนวณZ อย่างชัดเจนได้ ^{[ 5 ]}

ปัญหาการเขียนโปรแกรมเชิงกำลัง สองที่มีฟังก์ชันคู่ลากรางจ์ก็เป็นปัญหาการเขียนโปรแกรมเชิงกำลังสองเช่นกัน เพื่อให้เห็นภาพนี้ เรามาพิจารณากรณีที่c = 0และQเป็นเมทริกซ์บวกแน่นอน เราเขียน ฟังก์ชัน ลากรางจ์ได้ดังนี้

${\displaystyle L(x,\lambda )={\tfrac {1}{2}}x^{\top }Qx+\lambda ^{\top }(Ax-b).}$

เมื่อกำหนดฟังก์ชันคู่ (ลากรางจ์) g (λ)เป็นเราจะพบค่าต่ำสุดของLโดยใช้และความเป็นบวกแน่นอนของQ : ${\displaystyle g(\lambda )=\inf _{x}L(x,\lambda )}$${\displaystyle \nabla _{x}L(x,\lambda )=0}$

${\displaystyle x^{*}=-Q^{-1}A^{\top }\lambda .}$

ดังนั้น หน้าที่สองประการคือ

${\displaystyle g(\lambda )=-{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b,}$

ดังนั้นคู่ลากรางจ์ของปัญหาการเขียนโปรแกรมเชิงกำลังสองคือ

${\displaystyle {\text{maximize}}_{\lambda \geq 0}\quad -{\tfrac {1}{2}}\lambda ^{\top }AQ^{-1}A^{\top }\lambda -\lambda ^{\top }b.}$

นอกจากทฤษฎีทวิภาวะของลากรางจ์แล้ว ยังมีการจับคู่ทวิภาวะอื่นๆ อีก (เช่น ทฤษฎีของวูล์ฟเป็นต้น)

สำหรับQ ที่เป็นบวกแน่นอน ปัญหาการลดค่าต่ำสุดจะเป็นแบบนูนดังนั้นวิธีวงรี จึง สามารถใช้แก้ปัญหาได้ในเวลาพหุนาม (แบบอ่อน) ซึ่งได้รับการแสดงอย่างชัดเจนในปี 1979 โดย Kozlov, Tarasov และ Khachiyan ^{[ 6 ]}

Ye และ Tse ^{[ 7 ]}นำเสนออัลกอริทึมเวลาพหุนาม ซึ่งขยายอัลกอริทึมของ Karmarkarจากการเขียนโปรแกรมเชิงเส้นไปสู่การเขียนโปรแกรมกำลังสองแบบนูน บนระบบที่มี ตัวแปร nตัวและ บิตอินพุต Lอัลกอริทึมของพวกเขาต้องการการวนซ้ำ O(L n) ครั้ง ซึ่งแต่ละครั้งสามารถทำได้โดยใช้การดำเนินการทางคณิตศาสตร์ O(L n ³ ) ครั้ง ทำให้ความซับซ้อนของเวลาการทำงานโดยรวมเป็น O( L ² n ⁴ )

Kapoor และ Vaidya ^{[ 8 ]}นำเสนออัลกอริทึมอีกตัวหนึ่งซึ่งต้องใช้การดำเนินการทางคณิตศาสตร์ O( L * log L * n ^3.67 * log n )

เมื่อQไม่ใช่เมทริกซ์บวกแน่นอน (ดังนั้นปัญหาจึงไม่นูน) การเขียนโปรแกรมกำลังสองจะเป็นปัญหาNP-hardวิธีหนึ่งที่จะพิสูจน์ได้คือการใช้ทฤษฎีบทMotzkin-Straus ^{[ 9 ]}ซึ่งระบุว่าสำหรับกราฟG ที่ไม่มีทิศทางใดๆ โปรแกรมกำลังสองบางอย่างที่เกี่ยวข้องกับGจะมีค่าสูงสุดที่เป็นฟังก์ชันของจำนวนคลิกของGการคำนวณจำนวนคลิกของกราฟเป็นปัญหา NP-hard ที่รู้จักกันดี ดังนั้นการแก้โปรแกรมกำลังสองจึงเป็น NP-hard เช่นกัน กรณีพิเศษที่สำคัญบางกรณีก็เป็น NP-hard เช่นกัน:

• Sahni ^{[ 10 ]}พิสูจน์ความยากแบบ NP สำหรับกรณีที่ Q เป็นเมทริกซ์บวกแน่นอน (มี ค่าไอเกนลบ nค่า)
• Pardalos และ Vavasis ^{[ 11 ]}พิสูจน์ความยากแบบ NP (อย่างแข็งแกร่ง) เมื่อใดก็ตามที่ Q มีค่าไอ เกนลบอย่างน้อยหนึ่งค่า พวกเขาทำเช่นนี้โดยแสดงการลดรูปจากปัญหา Cliqueไปเป็นโปรแกรมกำลังสองเฉพาะที่มีตัวแปรw ​​, x ₁ ... x _n , y _1,2 ... y _(n-1),n , zและฟังก์ชันวัตถุประสงค์z - w ²พวกเขาพิสูจน์ว่ากราฟอินพุตมี clique ขนาดkก็ต่อเมื่อโปรแกรมกำลังสองที่สอดคล้องกันมีคำตอบที่มีค่าเป็น 0

ยิ่งไปกว่านั้น การค้นหาจุด KKT ของโปรแกรมกำลังสองที่ไม่นูนนั้นยากแบบ CLS ^{[ 12 ]}

มีบางสถานการณ์ที่องค์ประกอบหนึ่งหรือมากกว่าของเวกเตอร์xจะต้องมี ค่า เป็นจำนวนเต็มซึ่งนำไปสู่การกำหนดปัญหาการเขียนโปรแกรมกำลังสองแบบผสมจำนวนเต็ม (MIQP) ^{[ 13 ]}การประยุกต์ใช้ MIQP ได้แก่ทรัพยากรน้ำ^{[ 14 ]}และการสร้างกองทุนดัชนี^{[ 15 ]}

การเพิ่มประสิทธิภาพพหุนาม^{[ 16 ]}เป็นกรอบการทำงานทั่วไปมากขึ้น ซึ่งข้อจำกัดสามารถเป็นฟังก์ชันพหุนามที่มีดีกรีใดก็ได้ ไม่ใช่แค่ 2 เท่านั้น

• การเขียนโปรแกรมกำลังสองแบบลำดับ
• การเขียนโปรแกรมเชิงเส้น
• วิธีเส้นวิกฤต

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). ปัญหาความสมบูรณ์แบบเชิงเส้น . วิทยาศาสตร์คอมพิวเตอร์และการคำนวณทางวิทยาศาสตร์. บอสตัน, แมสซาชูเซตส์: Academic Press, Inc. หน้า xxiv+762 หน้าISBN 978-0-12-192350-1MR 1150683​ ​
• Garey, Michael R. ; Johnson, David S. (1979). คอมพิวเตอร์และความยากลำบากในการแก้ปัญหา: คู่มือทฤษฎีความสมบูรณ์ของ NP . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP2, หน้า 245.
• Gould, Nicholas IM; Toint, Philippe L. (2000). "บรรณานุกรมการเขียนโปรแกรมเชิงควาดราติก" (PDF) . รายงานภายในกลุ่มวิเคราะห์เชิงตัวเลข RAL 2000-1. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2017-07-05.

• หน้าเว็บเกี่ยวกับการเขียนโปรแกรมเชิงกำลังสอง (Quadratic Programming) เก็บถาวรเมื่อวันที่ 7 มิถุนายน 2011 ที่Wayback Machine
• คู่มือการปรับปรุงประสิทธิภาพของ NEOS: การเขียนโปรแกรมเชิงกำลังสอง
• การเขียนโปรแกรมเชิงกำลังสอง (Quadratic Programming) ถูกเก็บถาวรเมื่อวันที่ 8 เมษายน 2023 ที่Wayback Machine
• การเขียนโปรแกรมแบบลูกบาศก์และอื่นๆ นอกเหนือจากนั้นใน Operations Research Stack Exchange