البرمجة غير الخطية

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

ليكن n و m و p أعدادًا صحيحة موجبة. ليكن X مجموعة جزئية من R ⁿ (عادةً ما تكون مقيدة بصندوق)، وليكن f و g _i و h _j دوال ذات قيمة حقيقية على X لكل i في { 1 و..., m } ولكل j في { 1 و..., p }، بحيث يكون أحد f و g _i و h _j على الأقل غير خطي.

مشكلة البرمجة غير الخطية هي مشكلة تحسين من النموذج

${\displaystyle {\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}}$

اعتمادًا على مجموعة القيود، هناك عدة احتمالات:

• المشكلة الممكنة هي المشكلة التي يوجد فيها على الأقل مجموعة واحدة من القيم للمتغيرات الاختيارية التي تلبي جميع القيود.
• المشكلة غير القابلة للحل هي المشكلة التي لا تلبي فيها أي مجموعة من القيم للمتغيرات المختارة جميع القيود. أي أن القيود متناقضة مع بعضها البعض، ولا يوجد حل؛ المجموعة القابلة للحل هي المجموعة الفارغة .
• المشكلة غير المحدودة هي مشكلة قابلة للتنفيذ حيث يمكن جعل دالة الهدف أفضل من أي قيمة محدودة معينة. وبالتالي لا يوجد حل مثالي، لأنه يوجد دائمًا حل قابل للتنفيذ يعطي قيمة دالة هدف أفضل من أي حل مقترح معين.

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

بعض الحالات الخاصة من البرمجة غير الخطية لها طرق حل متخصصة:

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

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

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

في ظل مؤهلات التفاضل والقيود ، توفر شروط كاروش-كون-تاكر (KKT) الشروط الضرورية ليكون الحل مثاليًا. إذا كانت بعض الوظائف غير قابلة للتفاضل، تتوفر إصدارات فرعية من شروط كاروش-كون-تاكر (KKT) . ^[1]

في ظل التقوس، تكون شروط KKT كافية لتحقيق أفضلية عالمية . وبدون التقوس، تكون هذه الشروط كافية فقط لتحقيق أفضلية محلية . في بعض الحالات، يكون عدد الأمثلية المحلية صغيرًا، ويمكن للمرء أن يجدها جميعًا تحليليًا ويجد تلك التي تكون القيمة الموضوعية لها أصغر. ^[2]

في أغلب الحالات الواقعية، من الصعب جدًا حل شروط KKT تحليليًا، لذا يتم حل المشكلات باستخدام الطرق العددية . هذه الطرق تكرارية: تبدأ بنقطة أولية، ثم تنتقل إلى نقاط من المفترض أن تكون أقرب إلى النقطة المثلى، باستخدام بعض قواعد التحديث. هناك ثلاثة أنواع من قواعد التحديث: ^{[2] : 5.1.2}

• روتينات الترتيب الصفري - تستخدم فقط قيم دالة الهدف ووظائف القيد في النقطة الحالية؛
• روتينات الدرجة الأولى - استخدم أيضًا قيم تدرجات هذه الوظائف؛
• روتينات الدرجة الثانية - استخدم أيضًا قيم هيسيانز لهذه الوظائف.

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

تتضمن طريقة أخرى استخدام تقنيات التفرع والحد ، حيث يتم تقسيم البرنامج إلى فئات فرعية لحلها باستخدام تقريبات محدبة (مشكلة تقليل) أو خطية تشكل حدًا أدنى للتكلفة الإجمالية داخل التقسيم الفرعي. مع التقسيمات اللاحقة، في مرحلة ما، سيتم الحصول على حل فعلي تكون تكلفته مساوية لأفضل حد أدنى تم الحصول عليه لأي من الحلول التقريبية. هذا الحل مثالي، على الرغم من أنه ربما لا يكون فريدًا. يمكن أيضًا إيقاف الخوارزمية مبكرًا، مع التأكد من أن أفضل حل ممكن يقع ضمن التسامح من أفضل نقطة تم العثور عليها؛ تسمى هذه النقاط ε-optimal. عادةً ما يكون الإنهاء إلى نقاط ε-optimal ضروريًا لضمان الإنهاء المحدود. هذا مفيد بشكل خاص للمشاكل الكبيرة والصعبة والمشاكل ذات التكاليف أو القيم غير المؤكدة حيث يمكن تقدير عدم اليقين بتقدير موثوقية مناسب.

توجد العديد من حلول البرمجة غير الخطية، بما في ذلك مفتوحة المصدر:

• ينفذ ALGLIB (C++، C#، Java، Python API) العديد من حلول البرمجة غير الخطية من الدرجة الأولى والخالية من المشتقات
• NLopt (تنفيذ C/C++، مع العديد من الواجهات بما في ذلك Julia وPython وR وMATLAB/Octave)، يتضمن العديد من حلول البرمجة غير الخطية
• يحتوي SciPy (المعيار الفعلي للغة Python العلمية) على scipy.optimize solver، والذي يتضمن العديد من خوارزميات البرمجة غير الخطية (الترتيب الصفري، والترتيب الأول، والترتيب الثاني).
• IPOPT (تنفيذ C++، مع العديد من الواجهات بما في ذلك C وFortran وJava وAMPL وR وPython وما إلى ذلك) هو مُحلِّل لطريقة النقطة الداخلية (الترتيب الصفري، واختياريًا المشتقات من الدرجة الأولى والثانية).

يمكن تعريف مشكلة بسيطة (كما هو موضح في الرسم التخطيطي) من خلال القيود باستخدام دالة الهدف المراد تعظيمها حيث x = ( x ₁ ، x ₂ ) . $${\displaystyle {\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\x_{1}^{2}+x_{2}^{2}&\geq 1\\x_{1}^{2}+x_{2}^{2}&\leq 2\end{aligned}}}$$$${\displaystyle f(\mathbf {x} )=x_{1}+x_{2}}$$

يمكن تعريف مشكلة بسيطة أخرى (انظر الرسم البياني) من خلال القيود باستخدام دالة الهدف المراد تعظيمها حيث x = ( x ₁ ، x ₂ ، x ₃ ) . $${\displaystyle {\begin{aligned}x_{1}^{2}-x_{2}^{2}+x_{3}^{2}&\leq 2\\x_{1}^{2}+x_{2}^{2}+x_{3}^{2}&\leq 10\end{aligned}}}$$$${\displaystyle f(\mathbf {x} )=x_{1}x_{2}+x_{2}x_{3}}$$

• تركيب المنحنى
• التقليل باستخدام المربعات الصغرى
• البرمجة الخطية
• nl (تنسيق)
• المربعات الصغرى غير الخطية
• قائمة برامج التحسين
• البرمجة التربيعية المقيدة تربيعيًا
• فيرنر فينشيل ، الذي وضع الأساس للبرمجة غير الخطية

• أفريل، مردخاي (2003). البرمجة غير الخطية: التحليل والأساليب. دار دوفر للنشر. ISBN 0-486-43227-0 . 
• بازاره، مختار س. وشيتي، سي إم (1979). البرمجة غير الخطية. النظرية والخوارزميات. جون وايلي وأولاده. ISBN 0-471-78610-1 . 
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). التحسين العددي: الجوانب النظرية والعملية. Universitext (الطبعة الثانية المنقحة من ترجمة الطبعة الفرنسية لعام 1997). برلين: Springer-Verlag. ص. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. السيد  2265882.
• Luenberger, David G .; Ye, Yinyu (2008). البرمجة الخطية وغير الخطية . السلسلة الدولية في بحوث العمليات وعلوم الإدارة. المجلد 116 (الطبعة الثالثة). نيويورك: Springer. ص. xiv+546. ISBN 978-0-387-74502-2. السيد  2423726.
• نوسيدال، جورج ورايت، ستيفن جيه. (1999). التحسين العددي. سبرينغر. ISBN 0-387-98793-2 . 
• يان برينكويس وفلاديمير تيخوميروف، التحسين: الأفكار والتطبيقات ، 2005، مطبعة جامعة برينستون

• مسرد البرمجة الرياضية