وظيفة الحاجز

الموسوعة الحرة

في مجال التحسين المقيد ، وهو فرع من فروع الرياضيات ، تُعرَّف دالة الحاجز بأنها دالة متصلة تتزايد قيمتها إلى ما لا نهاية كلما اقترب متغيرها من حدود المنطقة الممكنة لمسألة التحسين. [ 1 ] [ 2 ] تُستخدم هذه الدوال لاستبدال قيود المتباينات بحد جزائي في دالة الهدف، مما يُسهِّل التعامل معها. تُسمى دالة الحاجز أيضًا بدالة الجزاء الداخلي ، لأنها دالة جزاء تُجبر الحل على البقاء داخل المنطقة الممكنة.

أكثر أنواع دوال الحاجز شيوعًا هما دوال الحاجز العكسية ودوال الحاجز اللوغاريتمية . وقد حفز الاهتمام المتجدد بدوال الحاجز اللوغاريتمية ارتباطها بطرق النقاط الداخلية الأولية-الثنائية .

تحفيز

ضع في اعتبارك مسألة التحسين المقيد التالية:

تقليل f ( x )
بشرط أن يكون x ≤ b

حيث b ثابت ما. إذا رغبنا في إزالة قيد المتباينة، فيمكن إعادة صياغة المسألة على النحو التالي:

تقليل f ( x ) + c ( x ) ،
حيث c ( x ) = ∞ إذا كان x > b ، وصفر خلاف ذلك.

هذه المسألة مكافئة للمسألة الأولى. فهي تتخلص من المتباينة، لكنها تُدخل مشكلة أن دالة الجزاء c ، وبالتالي دالة الهدف f ( x ) + c ( x ) ، غير متصلة ، مما يمنع استخدام حساب التفاضل والتكامل لحلها.

دالة الحاجز، الآن، هي تقريب مستمر g للدالة c يؤول إلى اللانهاية عندما تقترب x من b من الأسفل. باستخدام هذه الدالة، تتم صياغة مسألة تحسين جديدة، وهي:

تقليل f ( x ) + μ g ( x )

حيث μ > 0 هو مُعامل حر. هذه المسألة ليست مُكافئة للمسألة الأصلية، ولكن كلما اقتربت قيمة μ من الصفر، أصبحت تقريبًا أفضل. [ 3 ]

دالة الحاجز اللوغاريتمي

بالنسبة لدوال الحاجز اللوغاريتمية،ز(x،ب){\displaystyle g(x,b)}يُعرَّف بأنه-سجل⁡(ب-x){\displaystyle -\!\log(bx)}متىx<ب{\displaystyle x<b}و∞{\displaystyle \infty }وإلا (في بُعد واحد؛ انظر أدناه للتعريف في الأبعاد الأعلى). ويعتمد هذا أساسًا على حقيقة أنسجل⁡ت{\displaystyle \log t}يؤول إلى سالب ما لا نهاية عندمات{\displaystyle t}يميل إلى الصفر.

يُدخل هذا تدرجًا إلى الدالة التي يتم تحسينها، مما يُفضل القيم الأقل تطرفًا لـx{\displaystyle x}(في هذه الحالة، القيم أقل منب{\displaystyle b})، مع تأثير منخفض نسبياً على الوظيفة بعيداً عن هذه الحالات المتطرفة.

قد يتم تفضيل دوال الحاجز اللوغاريتمية على دوال الحاجز العكسية الأقل تكلفة حسابية اعتمادًا على الدالة التي يتم تحسينها.

أبعاد أعلى

يُعدّ التوسع إلى أبعاد أعلى أمرًا بسيطًا، شريطة أن يكون كل بُعد مستقلًا. لكل متغيرxأنا{\displaystyle x_{i}}والتي ينبغي أن تكون أقل بكثير منبأنا{\displaystyle b_{i}}، يضيف-سجل⁡(بأنا-xأنا){\displaystyle -\!\log(b_{i}-x_{i})}.

التعريف الرسمي

التقليلجتيx{\displaystyle \mathbf {c} ^{T}x}رهناً بـأأناتيx≤بأنا،أنا=1،...،م{\displaystyle \mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m}

بافتراض أن الأمر ممكن تماماً:{x|أx<ب}≠∅{\displaystyle \{\mathbf {x} \mid Ax<b\}\neq \emptyset }

تعريف الحاجز اللوغاريتميز(x)={∑أنا=1م-سجل⁡(بأنا-أأناتيx)ل أx<ب+∞خلاف ذلك{\displaystyle g(x)={\begin{cases}\sum _{i=1}^{m}-\!\log(b_{i}-a_{i}^{T}x)&{\text{لـ }}Ax<b\\+\infty &{\text{فيما عدا ذلك}}\end{cases}}}

انظر أيضاً

مراجع

  1. ↑ نيستيروف، يوري (2018). محاضرات في التحسين المحدب (  الطبعة الثانية). تشام، سويسرا: سبرينغر. ص  56. ISBN 978-3-319-91577-7.
  2. ↑ نوسيدال، خورخي؛ رايت، ستيفن (2006). التحسين العددي ( الطبعة الثانية). نيويورك، نيويورك: سبرينغر. ص 566. ISBN   0-387-30303-0.
  3. ↑ فاندرباي، روبرت ج. (2001). البرمجة الخطية: الأسس والتوسعات . كلوير. ص 277-279 .