التحسين المقيّد وشروط KKT

التحسين تحت قواعد

تخضع المحافظ الحقيقية لقواعد: مجموع الأوزان واحد، ولا بيع على المكشوف، وسقف للدوران. والمسألة المقيّدة هي $\min f(\mathbf w)$ بشرط المساواتين $h(\mathbf w)=0$ والمتباينات $g(\mathbf w)\le0$. ومع مساواة واحدة تكون أفضل نقطة ممكنة حيث يخترق $\nabla f$ سطح القيد عموديًا، لأن أي مركبة جانبية يمكن استعمالها لتحسين $f$ دون مغادرة السطح. وهذا شرط لاغرانج $\nabla f+\lambda\nabla h=0$، والعدد $\lambda$ هو مضروب لاغرانج. وجمع كل شيء في لاغرانجيان $L=f+\lambda h+\mu g$ يحوّل المسألة المقيدة إلى البحث عن نقطة ساكنة لـ $L$.

في المتباينات تتكون المجموعة الكاملة من الشروط، المسماة نسبة إلى كاروش وكون وتاكر، من أربعة أجزاء: سكون لاغرانجيان، والإمكان الأولي (تتحقق القيود)، والإمكان الثنائي ($\mu\ge0$)، والارتخاء التكاملي ($\mu g=0$). ويعني الارتخاء التكاملي أن كل متباينة إما غير فعالة بـ $g<0$ و$\mu=0$ فلا تؤثر، وإما فعالة بـ $g=0$ و$\mu>0$ فتعمل كمساواة. وفي المسألة المحدبة تكون هذه الشروط لازمة وكافية للأمثل العام. والمضروب سعر أيضًا: هو المعدل الذي تتحسن به أفضل قيمة لـ $f$ حين يُرخى القيد بوحدة واحدة.

محفظة التباين الأدنى هي الحالة النموذجية: صغّر $\mathbf w^{T}\Sigma\mathbf w$ بشرط $\mathbf 1^{T}\mathbf w=1$. يعطي شرط لاغرانج $2\Sigma\mathbf w+\lambda\mathbf 1=0$ النتيجة $\mathbf w\propto\Sigma^{-1}\mathbf 1$. ولأصلين غير مترابطين بتباينين $0.04$ و$0.09$ تتناسب الأوزان مع $1/0.04=25$ و$1/0.09=11.1$ فيكون $w_1=0.692$ و$w_2=0.308$ وتباين المحفظة $1/(25+11.1)=0.0277$. والمضروب يساوي $-2$ مرة هذا التباين الأدنى. وفي محفظة حقيقية يكون لقاعدة الشراء فقط أو لسقف الدوران مضروبها الخاص، ويدل $\mu$ الكبير على أن تلك القاعدة تكلفك كثيرًا.

• قيد مساواة: $\nabla f+\lambda\nabla h=0$ مع $h=0$.
• متباينة: $\mu\ge0$ و$\mu g=0$؛ فعّال يعني $g=0$ وغير فعّال يعني $\mu=0$.
• السعر: المضروب هو حساسية أفضل قيمة لإرخاء قيده.

المختبر: ما الذي يُقيَّم

• المضروب10 نقطة
• النقطة المثلى10 نقطة
• إرخاء القيد10 نقطة
• وزن أدنى تباين لأصلين15 نقطة
• التباين الأدنى15 نقطة
• شروط KKT الأربعة15 نقطة
• قيد فعّال10 نقطة
• ماذا يخبرك المضروب15 نقطة