การเพิ่มรูปแบบกำลังสองกึ่งไม่มีที่สิ้นสุดที่เป็นบวกให้ได้มากที่สุดบนซิมเพล็กซ์มาตรฐาน

Aug 20 2020

ฉันกำลังพยายามที่จะเพิ่มรูปแบบกำลังสองกึ่งไม่มีที่สิ้นสุดที่เป็นบวกให้ได้มากที่สุดบนซิมเพล็กซ์มาตรฐาน

กำหนดเมทริกซ์เซมิเดอร์ฟินิท (เฮสเซียน) บวกแบบสมมาตร $A \in \Bbb R^{d \times d}$ และเมทริกซ์ $W \in \Bbb R^{d \times n}$,

$$\begin{array}{ll} \underset{z \in \Bbb R^n}{\text{maximize}} & z^\top W^\top A W z\\ \text{subject to} & \Bbb 1_n^\top z = 1\\ & z \geq \Bbb 0_n\end{array}$$

ที่ไหน $z_i \in [0,1]$ คือค่าความน่าจะเป็นที่ใช้ในการถ่วงน้ำหนักแต่ละคอลัมน์ตามสัดส่วน $W$.

ฉันพยายามแก้ปัญหานี้โดยใช้ความจริงที่ว่ามีข้อ จำกัด $z^\top z = 1$, $z$ ที่เพิ่มสูงสุด $z^\top W^\top A W z$ เป็นเวกเตอร์ลักษณะเฉพาะแรกของเมทริกซ์ $A$. แต่ฉันไม่แน่ใจว่าเป็นวิธีที่ถูกต้องหรือไม่

ขอขอบคุณ.

คำตอบ

2 user7530 Aug 21 2020 at 01:48

โดยทั่วไปปัญหาของคุณคือ QP ที่ไม่นูนซึ่งอาจมีค่าสูงสุดในท้องถิ่นจำนวนมาก (พิจารณาตัวอย่างเช่นในกรณีที่ง่ายที่สุด $W^TAW = I$ทุกมุมที่ไม่สำคัญของซิมเพล็กซ์คือค่าสูงสุดในท้องถิ่น)

ถ้า $n$ มีขนาดเล็กเพียงพอทดสอบทั้งหมด $2^n$ชุดที่ใช้งานจะได้ผลแน่นอน ฉันไม่ทราบวิธีการวิเคราะห์สำหรับข้อ จำกัด เฉพาะของคุณ เทคนิคสาขาและขอบเขตอาจสามารถแก้ปัญหาได้ในทางปฏิบัติ