Quadratic Programming (QP)
แอปพลิเคชันนี้คำนวณหาคำตอบของ quadratic programming problem ภายใต้เงื่อนไข linear constraint และ bound constraint และปัญหานี้จะเขียนอยู่ในรูป \[ \begin{aligned} \min_{x\in\mathbf{R}^n} \quad & \frac{1}{2}x^TQx+c^Tx \\ \text{ภายใต้เงื่อนไข}\quad & Ax\leqslant b \\ & A_\mathrm{eq}x = b_\mathrm{eq} \\ & l\leqslant x\leqslant u \end{aligned} \] โดยที่เวกเตอร์ $x\in\mathbf{R}^n$ เป็นตัวแปรอิสระ ส่วนเวกเตอร์ $c\in\mathbf{R}^n$, $b\in\mathbf{R}^m$, $b_\mathrm{eq}\in\mathbf{R}^q$, $l\in\mathbf{R}^n$, $u\in\mathbf{R}^n$ และเมตริกซ์ $Q\in\mathbf{R}^{n\times n}$, $A\in\mathbf{R}^{m\times n}$, $A_\mathrm{eq}\in\mathbf{R}^{q\times n}$ เป็นข้อมูลที่ให้มา ในที่นี้ $Q$ เป็นเมตริกซ์สมมาตรทั่วไป ไม่จำเป็นต้องมีคุณสมบัติ positive semidefinite
ตัวอย่างของปัญหา quadratic programming เช่น เราต้องการหาค่าต่ำสุดของฟังก์ชัน \[f(x_1,x_2)=3x_1^2 +2x_1x_2+x_2^2+x_1+6x_2\] โดย $x_1,x_2$ จะต้องสอดคล้องกับเงื่อนไข $2x_1+3x_2\geqslant 4$
เพื่อที่จะหาคำตอบด้วยแอปพลิเคชันนี้ เราต้องเขียนปัญหาให้อยู่ในรูปข้างต้นก่อนดังนี้ จาก $f(x_1,x_2)$ เราจะได้ \[ Q=\left(\begin{array}{cc} 6 & 2 \\ 2 & 2 \end{array} \right) \quad\text{และ}\quad c = \left(\begin{array}{c} 1 \\ 6 \end{array} \right) \] ในส่วนของ $2x_1+3x_2\geqslant 4$ ต้องเปลี่ยนเป็น $-2x_1-3x_2\leqslant -4$ หรือในรูปของเมตริกซ์คือ \[ \left[ \begin{array}{cc} -2 & -3 \end{array} \right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array} \right] \leqslant \left[ \begin{array}{c} -4 \end{array} \right] \] ในปัญหาตัวอย่างนี้ไม่มีเงื่อนไขที่เป็นสมการและไม่มีขอบเขตล่างและขอบเขตบนของ $x$
ข้อมูลอินพุท
-
ในช่องข้อมูล Q และ c เราจะใส่ข้อมูลสำหรับเมตริกซ์ขนาด $n\times (n+1)$ โดยที่ $n$ คือจำนวนตัวแปร
ข้อมูลหลักที่ $n+1$ หรือหลักสุดท้ายคือข้อมูลของเวกเตอร์ $c$ ส่วนข้อมูล $n$ หลักแรกเป็นข้อมูลของเมตริกซ์ $Q$
และเนื่องจาก $Q$ เป็นเมตริกซ์สมมาตร สมาชิกตามแนวทะแยงมุมและเหนือแนวทะแยงมุมเท่านั้นที่จะนำมาใช้ในการคำนวณ
จาก $Q$ และ $c$ ในตัวอย่างข้างบน เราจะใส่ข้อมูลเป็น
6 2 1 2 2 6
- ในช่องข้อมูล A และ b กับ Aeq และ beq ก็ทำเช่นเดียวกับในช่องข้อมูล Q และ c ถ้าไม่มีเงื่อนไขเหล่านี้ก็ให้ว่างไว้
- ข้อมูล $l$ และ $u$ ใช้ข้อมูลอินพุทแบบเดียวกับที่ใช้ใน Constrained Optimization ถ้าไม่มีข้อมูลในช่องนี้ แอปพลิเคชันจะกำหนดให้ $l_i=-10$ และ $u_i=10$ โดย $i=1,\ldots, n$
- ค่าเริ่มต้น $x_0$ ใช้ข้อมูลอินพุทแบบเดียวกับที่ใช้ใน Constrained Optimization ถ้าไม่มีข้อมูลในช่องนี้ แอปพลิเคชันจะกำหนดให้ $x_{0i}=\text{random(0,1)}$ โดย $i=1,\ldots, n$