مقدمة لتحسين قوي [... وقائمة تسوق صغيرة نسيت ...]

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

في هذا المنشور ، سننظر في مشاكل التحسين مع عدم اليقين في البيانات وتقريبها من خلال مشكلات محدبة حتمية. هذه واحدة من الحيل الرئيسية في التحسين القوي - وهي تقنية تتيح لك التعامل مع مهام التحسين الحساسة للغاية للتغيرات في بيانات الإدخال.

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

ونعم ، هذا مثال على منشور ينمو فيه التعقيد أضعافا مضاعفة (القمامة بالفعل) ...

ماذا يعني "حل" مشكلة التحسين؟

لنبدأ بتذكير موجز.

تبدو مهمة التحسين بشكل عام كما يلي:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ s.t. \\ x \ in X$$

هنا $$$f (x)$ تسمى وظيفة الهدف ، و $$$X$ - مجموعة صالحة.

عن طريق حل مشكلة التحسين نعني هذه النقطة $$$x ^ * \ في X$ الذي تم تنفيذه من أجله:

$$

$$f (x) - f (x ^ *) \ geq 0 ، \ quad \ forall x \ in X$$

هذا هو المفهوم القياسي لحل مشكلة التحسين دون شك.

ما هي مشكلة التحسين مع عدم اليقين؟

حان الوقت لنتساءل عن أصل الوظيفة $$$f (x)$ والقيود $$$X$ .

مفيد جدا للمشاركة

• المنطق الهيكلي للمشكلة (وبعبارة أخرى ، ما هي الوظائف المستخدمة) ،
• القيود الفنية (مستقلة عن المنطق البشري أو البيانات) ،
• المعلمات التي يتم تقييمها من البيانات.

على سبيل المثال ، جاء إلينا رجل أعمال وأظهر مشكلة البرمجة الخطية:

$$

$$\ min_ {x \ in R ^ 2} 2.16 x_1 + 3.7 x_2 \\ s.t. \\ 0.973 x_1 + 2.619 x_2 \ leq 3.32 \\ x_1 \ geq 0، x_2 \ geq 0$$

ترى هذه المهمة لأول مرة. رجل أيضا (ربما لا ، ولكن في السترات الزرقاء كل شيء مجردة جدا!). أنت لا تعرف معنى المتغيرات. ولكن حتى الآن ، مع قدر كبير من الثقة ، يمكننا أن نقول ما يلي:

1. على الأرجح المهمة خطية ، لأن شخصًا ما قرر ذلك. الخطية هي البنية التي اختارها الشخص.
2. القيود $$$x_1 \ geq 0 ، x_2 \ geq 0$ هي التقنية. أي أنها جاءت من "فيزياء" وليست من بيانات (على سبيل المثال ، المبيعات لا يمكن أن تكون سلبية).
3. معاملات محددة $$$\ {0.973، 2.619، 3.32 \}$ في الحد $$$0.973 x_1 + 2.619 x_2 \ leq 3.32 دولا$ في مثالنا تم تقييمها من البيانات. وهذا هو ، في البداية قال أحدهم أن المتغير $$$x_1$ المرتبطة متغير $$$x_2 دولا$ ، ثم قيل أن العلاقة خطية ، وأخيراً ، تم تقدير المعاملات في معادلة الاقتران من البيانات. وينطبق الشيء نفسه على الاحتمالات. $$$\ {2.16، 3.7 \}$ في وظيفة الهدف.

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

العودة إلى قصتنا. لدينا مشكلة خطية ، شخص يقدر المعاملات في ذلك بطريقة أو بأخرى. إذا كنا على صواب بشأن طبيعة المعاملات في الوظيفة ، فعندئذ في الواقع طُلب منا حل المشكلة لسيناريو واحد من تطور الأحداث (مثال محدد للمشكلة).

هذا في بعض الأحيان يكفي لنا ، ونحن نحلها فقط.

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

ماذا تفعل في هذه الحالة ، وكيف نمذجة حالة عدم اليقين في البيانات؟

أولاً ، لاحظ أنه يمكن دائمًا نقل عدم اليقين في البيانات من الوظيفة الهدف إلى القيود أو العكس. كيفية القيام بذلك ، انظر تحت القطع.

مؤشر ستوكاستيك ، عبر الإنترنت ، تحسين قوي وقائمة المنتجات

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

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

سنقوم بتصميم هذا الموقف: لقد جئنا إلى أوشان مع ورقة في أيدينا للتسوق.

الاهتمام ، والسؤال الأول: كيفية نموذج؟

الإدخال: معلومات حول المنتجات المراد شراؤها والكمية المطلوبة.

للراحة ، يمكننا أن نفكر في النشرة باعتبارها ناقلات عدد صحيح غير سالب $$$y \ in Z _ + ^ n$ .

كمتغيرات ، نأخذ ، على التوالي ، ناقل عدد صحيح غير سالب $$$x \ في Z _ + ^ n$ - كم وما هي المنتجات التي سنشتريها في النهاية (حلنا).

النقطة صغيرة - خذ نوعًا من الوظيفة الموضوعية $$$f (x، y)$ ، والتي تقول كم ارتكبنا خطأ في اختيار المنتجات.

اعتمادًا على السياق ، قد يتغير نوع الوظيفة ، ولكن هناك بعض المتطلبات الأساسية لذلك:

• وظيفة $$$f (x، y)$ يجب أن يكون الحد الأدنى $$$x ^ * = \ arg \ min_ {x \ in R ^ n} f (x، y) = y$ (وهذا هو ، على النحو الأمثل سنشتري بالضبط ما هو مكتوب في النشرة)
• وظيفة $$$f (x، y)$ يجب أن يكون محدب في $$$x$ (ويفضل السلس) - أن تكون قادرة على حساب فعال $$$دقيقة$ .

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

$$

$$min_ {x \ in R ^ n} f (x، y)$$

تخيل الآن أن الورقة ظلت في المنزل ...

لذلك ، مع ملاحظة واحدة ، وصلنا إلى عالم المهام مع عدم اليقين.

فماذا تفعل إذا في هذه المهمة $$$min_ {x \ in R ^ n} f (x، y)$ غير معروف لنا $$$ذ$ ؟

الجواب ، مرة أخرى ، يعتمد على السياق.

الاستوكاستك الأمثل

يتضمن الاستوكاستك الأمثل (عادة)

• حالة عدم اليقين في البيانات ذات طبيعة عشوائية. معرفة كاملة للتوزيع الاحتمالي لقيم المعلمة غير القطعية
• القيود بما في ذلك عدم اليقين لينة

في مثالنا ، إذا قمنا بتصميمها باستخدام التحسين العشوائي ، فسنقول

• حسنًا ، لا أعرف ما هو مكتوب في المنشور ، لكنني أمشي مع المنشورات منذ 8 سنوات ، ولدي معرفة جيدة بما يكفي حول توزيع المتجه. $$$ذ$
• حتى لو ارتكبت خطأ في الاختيار (على سبيل المثال ، مع $$$x$ ) ، والعودة إلى المنزل ، وأنا أجد الحقيقي $$$ذ$ وإذا كنت سأكون آمنًا تمامًا ، فسوف أذهب إلى Pyaterochka وأشتريها ، وإن كان أكثر تكلفة.
• الآن سأختار واحدة $$$x$ ، والتي سوف تقلل إلى حد ما من نوع ما من وظيفة الهدف الأصلي و "الغرامات" المحتملة للخطأ.

هذا سيقودنا إلى هذه المهمة:

$$

$$\ min_ {x \ in R ^ n} E_y [f (x، y) + \ psi (y، z)] \\ s.t. \\ x + z \ geq y$$

لاحظ أنه في هذه المهمة ، نتخذ قرارات فعلية مرتين: أولاً ، القرار الرئيسي للشراء في أوشان ، الذي نتحمل المسؤولية عنه $$$x$ ، ثم "تصحيح الخطأ" مع $$$z$ .

المشاكل الرئيسية في هذا النهج هي:

• غالبًا لا توجد معلومات حول توزيع المعلمات.
• قد تكون القيود شديدة (بالنسبة للمهام ذات الخطورة العالية - الموت ، الخراب ، نهاية العالم النووي أو الزومبي ، إلخ)
• ليس من الممكن دائمًا "تصحيح الأخطاء" (يتم اتخاذ القرار مرة واحدة) أو العكس ، يتم اتخاذ القرارات غالبًا (في هذه الحالة ، ستظهر العديد من التكاملات المتداخلة ، وسيكون من الصعب للغاية حسابها).

التحسين عبر الإنترنت

التحسين عبر الإنترنت هو إطار يستكشف اتخاذ القرارات بشكل متسق. واحدة من النهج القياسية لنمذجة في هذا الإطار هي اللصوص متعددة الأسلحة ، والتي سبق أن كتبت عن هابري عدة مرات.

في سياق مثال لعبة لدينا ، فإننا:

• لا يوجد (ولم تستخدم من قبل) النشرة
  
• وفي المنزل ، سيتم الإشادة / التوبيخ لتلك المنتجات التي اشتريناها (في الوقت نفسه ، يمكننا تخمين المجموعة المطلوبة فقط)
• ستكون المهمة هي أن تتعلم في أسرع وقت ممكن شراء الطعام وكذلك أميرها السابق الوهمي ، أو أفضل صديق لأبناء والدتها.

تحسين قوي

التحسين القوي هو امتداد منطقي لفكرة حل minimax.

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

علاوة على ذلك ، أريد أن يتم دفع اللغز إلى محلل منتظم - وهم لا يفهمون القيود "لأي تنفيذ لمتغير عشوائي" (إذا لم يكن هناك عدد محدد من هذه التطبيقات).

في مشكلة المنشور ، يجب اتخاذ القرار هنا والآن وتبقى سارية تحت أي ظرف من الظروف:

$$

$$\ min_ {x \ in R ^ n ، t \ in R} t \\ s.t. \\ f (x، y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

من الواضح أنه حتى في مثال اللعب هذا ، إذا كنت لا تحتاج إلى شيء منه $$$ذ$ ، ثم لا يوجد حل له معنى.

إذا كيف يمكنك التعامل مع هذه المهام؟

بناء نسخة قوية من المهمة باستخدام مثال مهمة LP

النظر في مشكلة التحسين الخطي مع عدم اليقين:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

المعلمات $$$\ تبدأ {pmatrix} c ^ T ، d \\ A ، b \ end {pmatrix}$ كانت مستمدة من البيانات وتشمل عدم اليقين.

الافتراض 1: العديد من القيم (التطبيقات) $$$\ تبدأ {pmatrix} c ^ T ، d \\ A ، b \ end {pmatrix}$ يمكن أن تكون معلمة ، أي هناك مثل هذا $$$\ تبدأ {pmatrix} c_0 ^ T ، d_0 \\ A_0 ، b_0 \ end {pmatrix} ، \ start {pmatrix} c_1 ^ T ، d_1 \\ A_1 ، b_1 \ end {pmatrix} ، \ dots ، \ start {pmatrix } c_k ^ T ، d_k \\ A_k ، b_k \ end {pmatrix}$ أن أي تنفيذ البيانات $$$\ تبدأ {pmatrix} c ^ T ، d \\ A ، b \ end {pmatrix}$ يكمن في المجموعة:

$$

$$\ تبدأ {pmatrix} c ^ T ، d \\ A ، b \ end {pmatrix} \ in U = \ left \ {\ تبدأ {pmatrix} c_0 ^ T ، d_0 \\ A_0 ، b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ تبدأ {pmatrix} c_i ^ T ، d_i \\ A_i ، b_i \ end {pmatrix} | \ quad \ zeta \ في Q \ subset R ^ k \ right \}$$

هنا $$$\ تبدأ {pmatrix} c ^ T_0 ، d_0 \\ A_0 ، b_0 \ end {pmatrix}$ تسمى البيانات "الاسمية" ، و $$$\ تبدأ {pmatrix} c ^ T_i ، d_i \\ A_i ، b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "التحولات".



نحن نعلم بالفعل أنه يمكن إزالة جميع حالات عدم اليقين في المشكلة في الحدود. دعونا نفعل ذلك.

نحن نواجه المشكلة

$$

$$\ min_ {x \ in R ^ n ، t \ in R} t \\ st \\ c ^ Tx + d \ leq t ، \ quad \ forall \ تبدأ {pmatrix} c ^ T ، d \ end {pmatrix} \ in U \\ Ax \ leq b، \ quad \ forall \ تبدأ {pmatrix} A ، b \ end {pmatrix} \ in U \\ $$

نسخة قوية من المهمة

لقد حان الوقت لواحدة من أروع الحيل في التحسين القوي - كيفية الانتقال من عدد لا حصر له من القيود إلى مجموعة محدودة من القيود الجيدة.

لتبدأ ، والنظر في مثال بسيط عندما

$$

$$Q = \ {\ zeta \ in R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

جميع القيود في النظام

$$

$$c ^ Tx + d \ leq t ، \ quad \ forall \ تبدأ {pmatrix} c ^ T ، d \ end {pmatrix} \ in U \\ Ax \ leq b، \ quad \ forall \ تبدأ {pmatrix} A ، b \ end {pmatrix} \ in U \\ $$

نفس النوع - انها مجرد عدم المساواة الخطية. تعلم كيفية العمل مع واحد - تعلم كيفية العمل مع الجميع.

لذلك ، فإننا نعتبر تقييدًا واحدًا لنوع عدم المساواة:

$$

$$a ^ Tx \ leq b \ quad \ forall (a، b) \ in U = \ {(a_0، b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i، b_i) | \ quad \ zeta \ في Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ in Q \\ \ max _ {\ zeta \ في Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

اسمحوا لي أن أشرح ما حدث.

أولاً ، نقلنا جميع الأجزاء مع عدم اليقين إلى الجانب الأيسر من عدم المساواة. $$$\ زيتا$ .
بعد ذلك ، نظرنا إلى أسوأ الحالات (لكل منها) $$$x$ هو له).
نتيجة لذلك ، حصلنا على السجل التالي:

$$

$$g (x) = max _ {\ zeta \ in Q} f (x، \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

والخطوة التالية هي لكتابة وظيفة واضحة $$$g (x)$ . للقيام بذلك ، يكفي حل مشكلة التحسين بواسطة $$$\ زيتا$ واستبدل الأمثل $$$\ زيتا *$ :

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

مما يؤدي إلى عدم المساواة:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

لاحظ أن عدم المساواة الناتج هو محدب وأي $$$x$ إرضائه يرضي الأصلي $$$a ^ Tx \ leq b$ لأي تنفيذ $$$(a، b) \ in U$ ...

القيد $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ دعا نسخة قوية من القيد $$$a ^ Tx \ leq b \ quad \ forall (a، b) \ in U$ .

هذا هو واحد من workhorses الرئيسية في التحسين القوي - تقريب قيود الاحتمال من قبل مجموعة محدودة من القيود المحدبة.

ماذا تفعل مع القيود (غير الخطية) المعقدة؟

بناء إصدارات قوية من القيود باستخدام الازدواجية المخروطية

يمكن تمثيل الكثير من القيود غير الخطية القياسية في شكل مخروطي (أي في النموذج $$ اين $$$K$ هو بعض مخروط محدب مغلق):

• غير سلبية $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ in R ^ n _ +$
• القيود المعيارية $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ تبدأ {pmatrix} x \\ p \ end {pmatrix} \ in K_p ^ n = \ left \ {(x، t) \ in R ^ n \ الأوقات R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• القيود على الدقة الايجابية للمصفوفة $$$x_1F_1 + \ dots x_nF_n + G \ succeq 0$

العودة إلى قيود قوية.

نفترض أن مشكلة التحسين فيما يتعلق $$$\ زيتا$ تمكنت من أن تخفض إلى شكل مخروطي

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ in K$$

نحن نبني المزدوج لهذه المشكلة.

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

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ start {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ in K ^ *$$

الآن الأمر متروك للشيء الصغير - نظرية الازدواجية الضعيفة:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ in K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ in G} \ lambda ^ Td \\ حيث \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ start {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k؛ \ quad \ lambda \ in K ^ * \ right \}$$

لذلك ، كتقريب قوي من القيد الأولي $$$a ^ Tx \ leq b ، \ quad (a، b) \ in U$ تقييد يمكن استخدامها

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ left \ {\ lambda | \ quad C ^ T \ lambda + \ start {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k؛ \ quad \ lambda \ in K ^ * \ right \}$$

اين $$$\ lambda$ نفس المتغير $$$x$ .

لذلك قمنا ببناء قيد قوي لعدم المساواة الأصلي.

الخاتمة

درسنا تقنية تقريب القيود (العشوائية) السيئة من قبل مجموعة من تلك محدبة جيدة. قد يكون ذلك مفيدًا ، على سبيل المثال ، إذا:

• لا تريد أن تكتب خوارزميات بنفسك ، لكن المعالج الذي تستخدمه لا يعرف كيفية التعامل مع قيود الاحتمالات.
• هناك مشكلة في المعلمات العشوائية ، في حين أن الأمثل هو حساس للغاية للتقلبات في البيانات.
• وبالطبع ، المهام مع عدم اليقين ، حيث تكون جميع القيود صارمة (سعر الخطأ مرتفع للغاية)