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

${\displaystyle {\begin{aligned}&{\text{minimize}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{subject to}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{for }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}}$

โดยที่P ₀ , ..., P _mเป็น เมทริกซ์ ขนาดn x nและx ∈ R ⁿคือตัวแปรการปรับให้เหมาะสมที่สุด

ถ้าP ₀ , ..., P _mเป็นเมทริกซ์บวกกึ่งกำหนด (positive semidefinite) ทั้งหมด ปัญหาจะเป็นแบบนูน (convex ) ถ้าเมทริกซ์เหล่านี้ไม่ใช่ทั้งเมทริกซ์บวกกึ่งกำหนดและเมทริกซ์ลบกึ่งกำหนด ปัญหาจะเป็นแบบไม่นูน (non-convex) ถ้าP ₁ , ... , P _mเป็นศูนย์ทั้งหมด ข้อจำกัดจะเป็นเชิงเส้นและปัญหาจะเป็นโปรแกรมกำลังสอง (quadratic program )

ปัญหา QCQP แบบนูนสามารถแก้ไขได้อย่างมีประสิทธิภาพโดยใช้วิธีจุดภายใน (ในเวลาพหุนาม) โดยทั่วไปแล้วต้องใช้การวนซ้ำประมาณ 30-60 ครั้งจึงจะลู่เข้า การแก้ปัญหากรณีทั่วไปที่ไม่นูนนั้นเป็นปัญหา NP-hard

เพื่อให้เข้าใจเรื่องนี้ โปรดสังเกตว่าข้อจำกัดสองข้อx ₁ ( x ₁ − 1) ≤ 0 และx ₁ ( x ₁ − 1) ≥ 0 นั้นเทียบเท่ากับข้อจำกัดx ₁ ( x ₁ − 1) = 0 ซึ่งเทียบเท่ากับข้อจำกัดx ₁ ∈ {0, 1} ดังนั้นโปรแกรมจำนวนเต็ม 0–1 ใดๆ (ซึ่งตัวแปรทั้งหมดต้องเป็น 0 หรือ 1 เท่านั้น) สามารถกำหนดเป็นโปรแกรมกำลังสองที่มีข้อจำกัดแบบกำลังสองได้ เนื่องจากโดยทั่วไปแล้ว การเขียนโปรแกรมจำนวนเต็ม 0–1 เป็นปัญหา NP-hard ดังนั้น QCQP จึงเป็นปัญหา NP-hard เช่นกัน

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

การผ่อนคลาย QCQP หลักๆ มีสองวิธี ได้แก่ การใช้การเขียนโปรแกรมแบบกึ่งกำหนด (SDP) และการใช้เทคนิคการปรับรูปแบบใหม่-การทำให้เป็นเชิงเส้น (RLT) สำหรับปัญหา QCQP บางประเภท (โดยเฉพาะ QCQP ที่มีองค์ประกอบแนวทแยงเป็นศูนย์ในเมทริกซ์ข้อมูล) การผ่อนคลาย การเขียนโปรแกรมแบบกรวยลำดับที่สอง (SOCP) และการเขียนโปรแกรมเชิงเส้น (LP) จะให้ค่าวัตถุประสงค์เดียวกันกับการผ่อนคลาย SDP ^{[ 1 ]}

QCQP ที่ไม่นูนซึ่งมีองค์ประกอบนอกแนวทแยงที่ไม่เป็นบวกสามารถแก้ไขได้อย่างแม่นยำโดยการผ่อนคลาย SDP หรือ SOCP ^{[ 2 ]}และมีเงื่อนไขเพียงพอที่ตรวจสอบได้ในเวลาพหุนามสำหรับการผ่อนคลาย SDP ของ QCQP ทั่วไปให้แม่นยำ^{[ 3 ]}ยิ่งไปกว่านั้น แสดงให้เห็นว่าคลาสของ QCQP ทั่วไปแบบสุ่มมีการผ่อนคลายแบบกึ่งกำหนดที่แน่นอนด้วยความน่าจะเป็นสูงตราบใดที่จำนวนข้อจำกัดเติบโตไม่เร็วกว่าพหุนามคงที่ในจำนวนตัวแปร^{[ 3 ]}

เมื่อP ₀ , ..., P _mเป็นเมทริกซ์บวกกำหนด ทั้งหมด ปัญหาจะเป็นแบบนูนและสามารถแก้ไขได้ง่ายโดยใช้วิธีจุดภายในเช่นเดียวกับการเขียนโปรแกรมแบบกึ่งกำหนด

• Max Cutเป็นปัญหาในทฤษฎีกราฟ ซึ่งเป็นปัญหา NP-hard โดยกำหนดกราฟมาให้ ปัญหาคือการแบ่งจุดยอดออกเป็นสองเซต โดยให้มีเส้นเชื่อมจากเซตหนึ่งไปยังอีกเซตหนึ่งมากที่สุดเท่าที่จะเป็นไปได้ Max Cut สามารถกำหนดได้ในรูปของ QCQP และการผ่อนคลาย SDP ของปัญหาคู่ขนานนี้ให้ขอบเขตล่างที่ดี
• QCQP ใช้สำหรับปรับแต่งการตั้งค่าเครื่องจักรอย่างละเอียดในงานที่มีความแม่นยำสูง เช่นการพิมพ์ภาพด้วยแสง (photolithography )

• Albers CJ, Critchley F., Gower, JC (2011). "ปัญหาการลดค่ากำลังสองในทางสถิติ" (PDF)วารสารการวิเคราะห์หลายตัวแปร 102 ( 3): 698– 713. doi : 10.1016/j.jmva.2009.12.018 . hdl : 11370/6295bde7-4de1-48c2-a30b-055eff924f3e .{{cite journal}}: CS1 maint: multiple names: authors list ( link )

• คู่มือการปรับปรุงประสิทธิภาพของ NEOS: การเขียนโปรแกรมเชิงกำลังสองแบบมีข้อจำกัด ( เก็บถาวรเมื่อ 2 เมษายน 2556 ที่Wayback Machine)