تحليل مُنعّم

تُعدّ خوارزمية السمبلكس خوارزمية فعّالة للغاية عمليًا، وهي من الخوارزميات السائدة في البرمجة الخطية . في المسائل العملية، يتناسب عدد خطوات الخوارزمية طرديًا مع عدد المتغيرات والقيود. ^{[ 3 ] [ 4 ]} مع ذلك، في أسوأ الحالات النظرية، تتطلب الخوارزمية عددًا هائلاً من الخطوات لتحليل معظم قواعد المحور بنجاح. وكان هذا أحد الدوافع الرئيسية لتطوير التحليل المُبسّط. ^{[ 5 ]}

بالنسبة لنموذج الاضطراب، نفترض أن بيانات الإدخال مشوّهة بضوضاء من توزيع غاوسي . ولأغراض التطبيع، نفترض أن البيانات غير مشوّهة.${\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}}$يرضي$\displaystyle \|(\bar {\mathbf {a} }}_{i},\bar {b}}_{i})\|_{2}\leq 1}$لجميع الصفوف${\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}$من المصفوفة${\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).}$الضوضاء${\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}$تحتوي على مدخلات مستقلة مأخوذة من توزيع غاوسي بمتوسط${\displaystyle 0}$والانحراف المعياري${\displaystyle \sigma }$لقد حددنا${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}}$تتكون بيانات الإدخال المُنعّمة من البرنامج الخطي

أقصى

${\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }$

رهناً بـ

${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$.

إذا كان وقت تشغيل خوارزميتنا على البيانات${\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }$يُعطى بواسطة${\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}$ثم يكون التعقيد المُعدَّل لطريقة سيمبلكس هو ^{[ 6 ]}

${\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar) {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).}$

ينطبق هذا الحد على قاعدة محورية محددة تُسمى قاعدة رأس الظل. تُعدّ قاعدة رأس الظل أبطأ من القواعد المحورية الأكثر شيوعًا، مثل قاعدة دانتزيغ أو قاعدة الحافة الأكثر انحدارًا ^{[ 7 ]،} ولكنها تتمتع بخصائص تجعلها مناسبة جدًا للتحليل الاحتمالي. ^{[ 8 ]}

تتميز العديد من خوارزميات البحث المحلي بأوقات تشغيل سيئة في أسوأ الحالات، لكنها تؤدي أداءً جيدًا في الممارسة العملية. ^{[ 9 ]}

من الأمثلة على ذلك خوارزمية 2-opt لحل مسألة البائع المتجول . قد تستغرق هذه الخوارزمية عددًا هائلاً من التكرارات حتى تجد حلاً أمثل محليًا، مع أن وقت التشغيل عمليًا أقل من تربيعي بالنسبة لعدد الرؤوس. ^{[ 10 ]} نسبة التقريب ، وهي النسبة بين طول مخرجات الخوارزمية وطول الحل الأمثل، تميل إلى أن تكون جيدة عمليًا، ولكنها قد تكون سيئة في أسوأ الحالات النظرية.

يمكن تمثيل أحد أنواع مسائل البحث من خلال${\displaystyle n}$النقاط في المربع${\displaystyle [0,1]^{d}}$حيث تُستمد المسافات بين أزواجها من معيار . حتى في بُعدين، قد تتطلب طريقة 2-opt عددًا هائلاً من التكرارات حتى إيجاد الحل الأمثل المحلي . في هذا السياق، يمكن تحليل نموذج الاضطراب حيث تكون الرؤوس${\displaystyle v_{1},\dots ,v_{n}}$يتم أخذ عينات مستقلة وفقًا لتوزيعات احتمالية ذات دالة كثافة احتمالية${\displaystyle f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]}$. ل${\displaystyle \theta =1}$تكون النقاط موزعة بشكل منتظم. عندما${\displaystyle \theta >1}$كلما كان حجم المشكلة كبيرًا، زادت قدرة الخصم على زيادة احتمالية ظهور حالات المشكلة الصعبة. في نموذج الاضطراب هذا، يكون العدد المتوقع لتكرارات الخوارزمية الاستدلالية 2-opt، بالإضافة إلى نسب تقريب المخرجات الناتجة، محدودًا بدوال متعددة الحدود لـ${\displaystyle n}$و${\displaystyle \theta }$[ ^{10 ]​}

ومن خوارزميات البحث المحلي الأخرى التي نجح فيها التحليل المُنعّم طريقة k-means .${\displaystyle n}$النقاط في${\displaystyle [0,1]^{d}}$يُعدّ إيجاد تقسيم جيد إلى مجموعات بمسافات زوجية صغيرة بين النقاط في المجموعة نفسها مسألة صعبة من نوع NP-hard . تُستخدم خوارزمية لويد على نطاق واسع وهي سريعة جدًا في التطبيق العملي، على الرغم من أنها قد تستغرق وقتًا أطول.${\displaystyle e^{\أوميغا (n)}}$تُستخدم التكرارات في أسوأ الحالات لإيجاد حل أمثل محليًا. ومع ذلك، بافتراض أن النقاط لها توزيعات غاوسية مستقلة ، لكل منها قيمة متوقعة في${\displaystyle [0,1]^{d}}$والانحراف المعياري${\displaystyle \sigma }$، يكون العدد المتوقع لتكرارات الخوارزمية محدودًا بواسطة متعددة حدود في${\displaystyle n}$،${\displaystyle d}$و${\displaystyle \sigma }$[ ^{11 ]​}