Primal และ Dual Solution ไม่เหมือนกัน

Question

สมมติว่าเรามีปัญหาการเพิ่มประสิทธิภาพนูนต่อไปนี้: $$\ \min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0 $$ เราสามารถเขียนปัญหาเบื้องต้นเป็น: $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) $$ และปัญหาคู่เป็น: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) $$ เอาเป็นว่า $(\bar x, \bar \lambda)$ เป็นวิธีแก้ปัญหาเบื้องต้นและ $(x^*, \lambda^*)$วิธีแก้ปัญหาคู่ สมมติ$\psi$ และ $\phi$ ไม่นูนอย่างเคร่งครัดวิธีแก้ปัญหาเบื้องต้นไม่จำเป็นต้องเหมือนกับโซลูชันคู่เช่น $x^* \neq \bar x$ และ $\lambda^* \neq \bar\lambda$. อย่างไรก็ตามความเป็นคู่ที่แข็งแกร่งบอกเราว่า$\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. คุณช่วยชี้ให้ฉันเห็นตัวอย่างที่น่าสนใจสำหรับสิ่งเดียวกันหรือให้สัญชาตญาณได้ไหม ฉันเข้าใจว่าปัญหานี้ไม่มีจุดอานที่ไม่ซ้ำกันและด้วยเหตุนี้ปัญหานี้ ฉันยังคงมีข้อสงสัยเกี่ยวกับแนวคิดจะ$(x^*, \lambda^*)$ ไม่เป็นไปตามเงื่อนไข KKT สำหรับปัญหาการเพิ่มประสิทธิภาพที่มีข้อ จำกัด เดิม?

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

Answer 1

เงื่อนไข KKT ของปริมาลและปัญหาคู่นั้นเหมือนกันหากบรรลุวิธีแก้ปัญหาเบื้องต้น ปัญหาเบื้องต้นคือ:$$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ เงื่อนไขของจขกท. คือ $\phi(x) \leq 0$ (ความเป็นไปได้เบื้องต้น), $\lambda\geq 0$ (ความเป็นไปได้คู่) $\psi'(x) + \lambda \phi'(x)=0$ (stationarity) และ $\lambda \phi(x)=0$ (complementarity).

ปัญหาคู่คือ: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ ซึ่งเทียบเท่ากับ: $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ สภาพการหยุดนิ่งคือ $\phi(x) + y = 0$ (กล่าวคือ $\phi(x)\leq 0$). เงื่อนไขความเป็นไปได้เบื้องต้นคือ$\lambda \geq 0$ (เป็นอย่างอื่นค่าของ $\min_{y\geq 0}$ คือ $-\infty$) และ $\min_x \psi(x) + \lambda \phi(x)>-\infty$. อย่างหลังถ้าบรรลุขั้นต่ำ (เช่นปัญหาเบื้องต้นสามารถแก้ไขได้) คุณมี$\psi'(x) + \lambda \phi'(x)=0$. เงื่อนไขเสริมคือ$\lambda y = 0$ (ซึ่งหมายความว่า $\lambda \phi(x)=0$ ผ่านสภาพนิ่ง)