قليلا عن الازدواجية المخروطية

عند دراسة الدورات النظرية في التعلم الآلي (الرياضيات ، الاقتصاد ، التحسين ، التمويل ، إلخ) ، غالبًا ما يتم العثور على مفهوم "المشكلة المزدوجة".

غالبًا ما تستخدم المهام المزدوجة للحصول على تقديرات أقل (أو أعلى) للهدف الوظيفي في مشكلات التحسين. بالإضافة إلى ذلك ، بالنسبة إلى أي بيان تقريبًا عن مشكلة التحسين ، فإن المشكلة المزدوجة لها تفسير ذو معنى. وهذا هو ، إذا كنت تواجه مشكلة تحسين مهمة ، فمن المحتمل أن تكون المشكلة المزدوجة هي الأكثر أهمية.

في هذه المقالة سأتحدث عن الازدواجية المخروطية. في رأيي ، هذه الطريقة لبناء المهام المزدوجة محرومة من الاهتمام ...

ماتان المقبل ...

كيف يتم بناء المهام المزدوجة عادة؟

دع بعض مشاكل التحسين تعطى:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ f_i (x) \ leq 0، \ quad 1 \ leq i \ leq k \\ h_i (x) = 0، 1 \ leq i \ leq m$$

يتم إنشاء المهمة المزدوجة وفقًا للمخطط التالي:

• بناء لاغرانج

$$

$$L (x، \ lambda، \ mu) = f (x) + \ sum_ {i = 1} ^ k \ lambda_i f_i (x) + \ sum_ {i = 1} ^ m \ mu_i h_i (x)$$

• بناء وظيفة مزدوجة

$$

$$g (\ lambda، \ mu) = \ inf_x L (x، \ lambda، \ mu)$$

• الحصول على مهمة مزدوجة

$$

$$\ max _ {\ lambda، \ mu} g (\ lambda، \ mu) \\ \ lambda \ geq 0$$

الصعوبة الرئيسية في هذا المخطط هي سلكية في خطوة البحث $$$\ inf_x L (x، \ lambda، \ mu)$ .

إذا لم تكن المشكلة محدبة ، فهذه نعش - في الحالة العامة ، لا يمكن حلها في وقت متعدد الحدود (إذا $$$P \ neq NP$ ) وهذه المشكلات في هذه المقالة لن نتطرق إليها في المستقبل.

نفترض أن المشكلة هي محدبة ، ثم ماذا؟

إذا كانت المشكلة سلسة ، فيمكننا استخدام شرط الأمثلية من الدرجة الأولى $$$\ nabla_x L (x، \ lambda، \ mu) = 0$ . من هذه الحالة ، إذا كان كل شيء على ما يرام ، فإنه يتحول إلى استنتاج أو $$$x (\ lambda، \ mu) = \ arg \ min_x L (x، \ lambda، \ mu)$ و $$$g (\ lambda، \ mu) = L (x (\ lambda، \ mu)، \ lambda، \ mu)$ أو وظيفة مباشرة $$$g (\ lambda، \ mu)$ .

إذا لم تكن المشكلة سلسة ، فيمكننا استخدام تناظرية لحالة من الدرجة الأولى $$$0 \ in \ part_x L (x، \ lambda، \ mu)$ (هنا $$$\ الجزئي L (x ، \ lambda ، \ mu)$ يدل على التفضيل الفرعي للدالة $$$L (x، \ lambda، \ mu)$ ) ، ومع ذلك ، عادة ما يكون هذا الإجراء أكثر تعقيدًا.

في بعض الأحيان توجد مشكلة تحسين "سلسة" مكافئة ويمكن للمرء إنشاء مشكلة مزدوجة لها. ولكن لتحسين الهيكل (من غير السلس إلى السلس) ، كقاعدة عامة ، عليك دائمًا دفع زيادة في البعد.

الازدواجية المخروطية

هناك عدد غير قليل من مهام التحسين (الأمثلة أدناه) التي تعترف بالتمثيل التالي:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx \\ Ax + b \ in K$$

اين $$$دولا$ - المصفوفة $$$ب$ - ناقل $$$K$ - مخروط محدب غير متحلل.

في هذه الحالة ، يمكن إنشاء المهمة المزدوجة وفقًا للمخطط التالي:

يتم إنشاء المهمة المزدوجة وفقًا للمخطط التالي:

• بناء لاغرانج

$$

$$L (x، \ lambda) = c ^ Tx + \ lambda ^ T (Ax + b)$$

• بناء وظيفة مزدوجة

$$

$$g (\ lambda) = \ inf_x L (x، \ lambda) = \ start {cases} \ lambda ^ T b، \ quad c + A ^ T \ lambda = 0 \\ - \ infty، \ quad c + A ^ T \ lambda \ neq 0 \ end {cases}$$

• الحصول على مهمة مزدوجة

$$

$$\ max _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ in K ^ *$$

أين هو المخروط المتقارن $$$K ^ *$ للمخروط $$$K$ كما هو محدد $$$K ^ * = \ left \ {y \ in R ^ k | z ^ T y \ geq 0، \ quad \ forall z \ in K \ right \}$ .

كما نرى ، تم نقل التعقيد الكامل لبناء المشكلة المزدوجة إلى بناء المخروط المزدوج. لكن الفرح هو أن هناك حساب التفاضل والتكامل الجيد لبناء المخاريط المزدوجة وغالبا ما يمكن كتابة مخروط مزدوج على الفور.

مثال

لنفترض أننا بحاجة إلى إنشاء مشكلة أمثلية للمشكلة:

$$

$$\ min_ {x \ in R ^ n} \ | x \ | _2 + \ | x \ | _1 \\ Ax \ geq b$$

هنا $$$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ ، $$$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$

أول شيء يمكن أن تلاحظه: يمكن دائمًا جعل الوظيفة الموضوعية خطية!

بدلاً من ذلك ، هناك دائمًا مشكلة مكافئة مع دالة موضوعية خطية:

$$

$$\ min_ {x \ in R ^ n ، y \ in R ، z \ in R} y + z \\ \ | x \ | _2 \ leq y \\ \ | x \ | _1 \ leq z \\ Axe \ geq ب$$

أنت الآن بحاجة إلى استخدام القليل من المعرفة السرية: كثير

$$

$$K_1 = \ {(x، t) \ in R ^ n \ times R | \ quad \ | x \ | _1 \ leq t \}$$

و

$$

هي مخروط محدب.

وبالتالي ، وصلنا إلى التدوين المعادل للمشكلة:

$$

$$\ min_ {x \ in R ^ n ، y \ in R ، z \ in R} y + z \\ I_ {n + 1} \ تبدأ {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ in K_2 \\ I_ {n + 1} \ start {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ in K_1 \\ Ax-b \ in R _ + ^ k$$

الآن يمكننا على الفور كتابة مشكلة مزدوجة:

$$

$$\ max _ {\ lambda، \ mu، \ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0، \ quad 1 \ leq i \ leq n \\ \ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\ - \ lambda \ في K_2 ^ * (= K_2) \\ - \ mu \ in K_1 ^ * (= K _ {\ infty}) \\ - \ nu \ in R ^ k _ +$$

أو ، لتبسيط قليلا ،

$$

$$\ max _ {\ lambda، \ mu، \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ in R ^ k _ +$$

اين $$$\ | \ mu \ | _ {\ infty} = \ max_ {i} | \ mu_i |$ .

روابط لمزيد من الدراسة:

• S. Boyd & L. Vanderberghe، Convex Optimization، 2.6 (p. 51)
• A. Ben-Tall & L. El Ghaoui & A. Nemirovski، Robust Optimization، App. أ