البرمجة غير الخطية
- قدّمه
- Jorge Nocedal & Stephen Wright
- السنة
- 2006
- النوع
- Continuous mathematical optimization
- العائلة
- Mathematical programming
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البرمجة غير الخطية (NLP) هي فرع من فروع التحسين الرياضي يهتم بالمشكلات التي تكون فيها الدالة الهدف أو على الأقل أحد القيود غير خطي. تم تقنين البرمجة غير الخطية بشكل شامل من قبل خورخي نوسيدال وستيفن رايت في نصهم الأساسي لعام 2006، وتشمل البرمجة غير الخطية خوارزميات تعتمد على التدرج — بما في ذلك البرمجة التربيعية المتسلسلة (SQP)، وطرق النقطة الداخلية، ومقاربات نيوتن شبه — لإيجاد حلول مثلى محلية أو عالمية لمشكلات القرار المستمرة الناشئة في الهندسة والاقتصاد والعلوم الفيزيائية.
الفكرة الحدسية وراء الطريقة
تخيل نزول منظر طبيعي جبلي مغطى بالضباب مع البقاء داخل منطقة مسورة. لا يمكنك رؤية التضاريس بأكملها، لذا تشعر بالمنحدر تحت قدميك (التدرج)، وتعدل اتجاه خطوتك للنزول، وتتحقق عند كل خطوة من أنك لم تعبر السياج (القيود). إذا انحنى السياج أو تداخلت التلال، فلن تنجح المسارات المستقيمة البسيطة — يجب عليك تقويس مسارك. البرمجة غير الخطية تقنن هذه العملية بالضبط، مستبدلة المشي البديهي على التلال بقواعد رياضية صارمة لحجم الخطوة والاتجاه.
التاريخ
تعود الأسس النظرية للبرمجة غير الخطية إلى شروط KKT التي اشتقها كاروش (1939) وكوهن وتاكر (1951). تسارعت الخوارزميات العملية خلال الستينيات إلى الثمانينيات مع تطوير طرق SQP، ومقاربات اللاغرانجي المعززة، وتحديثات نيوتن شبه بما في ذلك BFGS (1970). أصبح كتاب نوسيدال ورايت الثاني لعام 2006 بعنوان "التحسين العددي" مرجعًا نهائيًا، حيث قام بتجميع نظرية التقارب، وأطر البحث الخطي ومناطق الثقة، وطرق النقطة الداخلية في معالجة حديثة متماسكة.
متى تُستخدم
استخدم البرمجة غير الخطية عندما لا يمكن خطيّة الدالة الهدف أو القيود دون خسارة مادية للدقة وتكون متغيرات القرار مستمرة. تشمل الإعدادات النموذجية تصميم الهندسة مع قيود القانون الفيزيائي، وتحسين المحفظة مع مقاييس مخاطر غير خطية، والانحدار مع نماذج غير خطية. الافتراضات الرئيسية هي أن f و c قابلة للتفاضل بشكل مستمر مرتين على الأقل (للمحللات المعتمدة على التدرج) وأن مؤهلات القيود سارية. عندما تكون المتغيرات ذات قيم صحيحة، تنطبق امتدادات البرمجة غير الخطية المختلطة الصحيحة (MINLP). بالنسبة للمشكلات المحدبة، تضمن طرق النقطة الداخلية الأمثلية العالمية؛ بالنسبة للمشكلات غير المحدبة، توجد ضمانات محلية فقط.
الحدود والاعتبارات
- المشكلات غير المحدبة تقدم ضمانات أمثلية محلية فقط؛ الحلول العالمية تتطلب استراتيجيات بحث عالمية إضافية.
- تتطلب أن تكون الدالة الهدف والقيود سلسة (قابلة للتفاضل على الأقل)؛ المشكلات غير السلسة تحتاج إلى طرق تفاضلية فرعية متخصصة.
- تزداد التكلفة الحسابية بشكل كبير مع حجم المشكلة عندما يكون تقييم الهيسية الدقيق مطلوبًا.
- قد تفشل مؤهلات القيود (على سبيل المثال، عند النقاط الممكنة المنحلة)، مما يتسبب في فقدان شروط KKT لأساسها النظري.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- تتعامل مع فئة واسعة من مشكلات العالم الحقيقي حيث تكون التقريبات الخطية أو التربيعية غير كافية.
- نظرية خوارزمية ناضجة مع ضمانات تقارب مدروسة جيدًا للحالات المحدبة.
- محللات فعالة تعتمد على التدرج (SQP، النقطة الداخلية) تتوسع إلى آلاف المتغيرات عمليًا.
- إطار لاغرانجي موحد يستوعب القيود المختلطة للمساواة وعدم المساواة بشكل طبيعي.
التطبيقات
- الهندسة الإنشائية والطيران: تقليل الوزن مع مراعاة قيود الإجهاد والانحراف.
- إدارة المحافظ: تعظيم العائد المتوقع مع مراعاة ميزانية تباين (مخاطر) غير خطية.
- تصميم العمليات الكيميائية: تحسين إنتاجية المفاعل مع مراعاة القيود الديناميكية الحرارية والسلامة.
- تعلم الآلة: تدريب الشبكات العصبية ونماذج النواة عبر محللات البرمجة غير الخطية غير المقيدة أو المقيدة.
- أنظمة الطاقة: مشكلات تدفق الطاقة المثلى في إرسال شبكة الكهرباء مع قيود فيزيائية غير خطية.
كيف يعمل
كيف يعمل
يحدد المحلل دالة هدف قياسية f(x) لتقليلها أو تعظيمها على متغيرات القرار x في R^n، جنبًا إلى جنب مع قيود المساواة c_i(x) = 0 وقيود عدم المساواة c_j(x) >= 0. تحديد القيود النشطة عند حل مرشح وما إذا كانت شروط الانتظام (مؤهلات القيود) سارية هو أمر بالغ الأهمية في هذه المرحلة ويحدد نظرية الأمثل التي تنطبق.
الصيغة
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}توفر شروط كاروش-كون-تاكر (KKT) شروطًا ضرورية من الدرجة الأولى للأمثل المحلي. تتطلب هذه الشروط استقرارية اللاغرانجي، والامتثال التكميلي لمضاعفات عدم المساواة (lambda_j c_j = 0)، والجدوى المزدوجة (lambda_j >= 0)، والجدوى الأولية. تقوم الخوارزميات بشكل متكرر ببناء تكرارات تلبي هذه الشروط بشكل متزايد، مع تأكيد شروط الكفاية من الدرجة الثانية أن نقطة الاستقرار هي بالفعل حد أدنى محلي.
الصيغة
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}في كل تكرار k، تحسب الخوارزمية اتجاه بحث p_k — عادةً عبر تقريب نيوتن شبه B_k للمصفوفة الهيسية (على سبيل المثال، BFGS) أو نظام مشتقة ثانية دقيق — وطول خطوة alpha_k الذي يلبي شروط وولف أو أرميجو. تحل طرق SQP مشكلة فرعية تربيعية لـ p_k، بينما تضيف طرق النقطة الداخلية حدودًا حاجزية للتعامل مع قيود عدم المساواة ودفع التكرارات نحو الداخل الممكن.
الصيغة
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)يحدث الإنهاء عندما تنخفض كل من معيار تدرج اللاغرانجي والانتهاك الأقصى للقيود عن الحدود المحددة مسبقًا (epsilon و delta). نظرًا لأن البرمجة غير الخطية غير محدبة بشكل عام، فقد تتقارب الخوارزميات إلى أمثل محلية؛ يوصى بإعادة التشغيل المتعدد من نقاط بداية مختلفة أو استراتيجيات البحث العالمية (التفرع والحد، إعادة التشغيل المتعدد) عندما تكون الأمثلية العالمية مطلوبة.
الصيغة
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaالأخطاء الشائعة
- تجاهل مؤهلات القيود وتطبيق شروط KKT بشكل أعمى عند النقاط المنحلة أو غير الممكنة يؤدي إلى حلول زائفة.
- استخدام متغيرات ذات مقياس سيء يسبب تقريبات هيسية سيئة التكييف وتقاربًا بطيئًا أو فاشلاً.
- قبول الحد الأدنى المحلي الأول الذي تم العثور عليه دون إعادة تشغيل متعددة في الإعدادات غير المحدبة قد يفوت الأمثل العالمي بشكل كبير.
- تقريبات التدرج بالفرق المحدود تُدخل خطأ عدديًا؛ يُفضل بشدة التفاضل التحليلي أو التلقائي.
الأسئلة الشائعة
هل كل برنامج خطي هو أيضًا برنامج غير خطي؟
نعم. البرمجة الخطية هي حالة خاصة من البرمجة غير الخطية حيث تكون كل من الدالة الهدف وجميع القيود خطية تآلفية. ومع ذلك، تسمح البرمجة الخطية بخوارزميات السيمبلكس والنقطة الداخلية التي تستغل الخطية وهي أكثر كفاءة بكثير من محللات البرمجة غير الخطية العامة؛ استخدام محلل برمجة غير خطية عام لبرنامج خطي هو إهدار ولكنه صحيح رياضيًا.
متى يمكنني الوثوق بأن نقطة KKT هي حد أدنى عالمي؟
عندما تكون البرمجة غير الخطية محدبة — مما يعني أن f محدبة ومجموعة الحلول الممكنة هي مجموعة محدبة — فإن أي نقطة KKT هي حد أدنى عالمي. بالنسبة للمشكلات غير المحدبة، لا ينطبق هذا الضمان، ونقطة KKT هي مجرد حد أدنى محلي (تحت شروط الكفاية من الدرجة الثانية). بخلاف ذلك، هناك حاجة إلى طرق التحسين العالمي مثل التفرع والحد أو الاسترخاء المحدب.
ما الفرق بين طرق SQP وطرق النقطة الداخلية؟
تحل طريقة SQP بشكل متكرر مشكلات فرعية تربيعية تقرب البرمجة غير الخطية محليًا وغالبًا ما تُفضل للمشكلات الصغيرة إلى المتوسطة مع العديد من القيود النشطة. تميل طرق النقطة الداخلية (الحاجز) إلى البقاء داخل المنطقة الممكنة تمامًا وتميل إلى التوسع بشكل أفضل للمشكلات الكبيرة المتفرقة. كلاهما يتقارب بشكل أسرع من خطي تحت شروط الانتظام المناسبة.
طرق ذات صلة
المصادر
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ردمك: 978-0-387-30303-1تم النسخ.