مضاعف لاغرانج
في مجال التحسين الرياضي ، تُعدّ طريقة مُضاعِفات لاغرانج استراتيجيةً لإيجاد القيم العظمى والصغرى المحلية لدالة تخضع لقيود المعادلات ( أي، تخضع لشرط أن تُحقّق قيم المتغيرات المختارة معادلةً واحدةً أو أكثر بدقة ). [ 1 ] سُمّيت هذه الطريقة نسبةً إلى عالم الرياضيات جوزيف لويس لاغرانج .
ملخص وتبرير
تتمثل الفكرة الأساسية في تحويل مسألة مقيدة إلى صيغة تسمح بتطبيق اختبار المشتقة الخاص بمسألة غير مقيدة. وتؤدي العلاقة بين تدرج الدالة وتدرجات القيود بشكل طبيعي إلى إعادة صياغة المسألة الأصلية، والمعروفة بدالة لاغرانج أو دالة لاغرانج. [ 2 ] في الحالة العامة، تُعرَّف دالة لاغرانج على النحو التالي:
للوظائف؛ التدوينيشير إلى الضرب الداخلي . القيمةيُطلق عليه اسم مُضاعِف لاغرانج .
في الحالات البسيطة، حيث يُعرَّف الضرب الداخلي بأنه الضرب النقطي ، يكون لاغرانجيان
يمكن تلخيص الطريقة على النحو التالي: لإيجاد القيمة العظمى أو الصغرى لدالة مامع مراعاة شرط المساواةأوجد النقاط الثابتة لـباعتبارها دالة لـومضاعف لاغرانجوهذا يعني أن جميع المشتقات الجزئية يجب أن تساوي صفرًا، بما في ذلك المشتقة الجزئية بالنسبة إلى[ 3 ]
أو ما يعادل ذلك
إن الحل المقابل للتحسين المقيد الأصلي هو دائمًا نقطة سرجية لدالة لاغرانج، [ 4 ] [ 5 ] والتي يمكن تحديدها من بين النقاط الثابتة من خلال تحديد مصفوفة هيسيان ذات الحدود . [ 6 ]
تتمثل الميزة الكبرى لهذه الطريقة في أنها تسمح بحل مسائل التحسين دون الحاجة إلى تحديد المعاملات بشكل صريح بدلالة القيود. ونتيجة لذلك، تُستخدم طريقة مُضاعِفات لاغرانج على نطاق واسع لحل مسائل التحسين المقيدة المعقدة. علاوة على ذلك، تُعمَّم طريقة مُضاعِفات لاغرانج باستخدام شروط كاروش-كون-تاكر ، التي يمكنها أيضًا مراعاة قيود المتباينات من الشكل التالي:لثابت معين.
إفادة
ما يلي يُعرف باسم نظرية مضاعف لاغرانج. [ 7 ]
يتركلتكن دالة الهدف ولتكنلتكن دالة القيود، وكلاهما ينتمي إلى(أي أن تكون مشتقاتها الأولى متصلة). لننظر في مسألة التحسين المقيد التالية:
يتركليكن حلاً أمثل لمسألة التحسين المذكورة أعلاه بحيث يكون، بالنسبة لمصفوفة المشتقات الجزئية،إذن، يوجد مُضاعِف لاغرانج فريدبحيث(في هذه المعادلة،هو متجه عمودي، لذا فإن منقولههو متجه صف. بدلاً من ذلك، يمكننا إعادة تعريف مُضاعِف لاغرانج مباشرةً كمتجه صف، وبالتالي تجنب عملية النقل.
تنص نظرية مُضاعِفات لاغرانج على أنه عند أي قيمة عظمى (أو صغرى) محلية للدالة المحسوبة في ظل قيود المساواة، إذا انطبق شرط القيد (الموضح أدناه)، فإن تدرج الدالة (عند تلك النقطة) يُمكن التعبير عنه كمزيج خطي من تدرجات القيود (عند تلك النقطة)، حيث تعمل مُضاعِفات لاغرانج كمعاملات . [ 8 ] وهذا يُكافئ القول بأن أي اتجاه عمودي على جميع تدرجات القيود يكون أيضًا عموديًا على تدرج الدالة. أو بعبارة أخرى، أن المشتقة الاتجاهية للدالة تساوي صفرًا في كل اتجاه ممكن.
قيد واحد

في حالة وجود قيد واحد فقط ومتغيرين للاختيار فقط (كما هو موضح في الشكل 1)، ضع في اعتبارك مسألة التحسين (أحيانًا يتم عرض الثابت الإضافي بشكل منفصل بدلاً من تضمينه فيوفي هذه الحالة، يُكتب القيدكما هو موضح في الشكل 1.) نفترض أن كليهماولدينا مشتقات جزئية أولى متصلة . نقدم متغيرًا جديدًا () يُسمى مُضاعِف لاغرانج (أو مُضاعِف لاغرانج غير المُحدَّد ) ودراسة دالة لاغرانج (أو لاغرانجيان أو تعبير لاغرانجيان ) المُعرَّفة بواسطة حيثيمكن إضافة المصطلح أو طرحه. إذاالحد الأقصى هوبالنسبة للمسألة المقيدة الأصلية وثم يوجدبحيث () هي نقطة ثابتة لدالة لاغرانج (النقاط الثابتة هي تلك النقاط التي تكون عندها المشتقات الجزئية الأولى لـ(صفر). الافتراضيُطلق على هذه العملية اسم "تأهيل القيد". مع ذلك، لا تُؤدي جميع النقاط الثابتة إلى حل للمسألة الأصلية، إذ تُقدّم طريقة مُضاعفات لاغرانج شرطًا ضروريًا فقط للأمثلية في المسائل المُقيدة. [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] توجد أيضًا شروط كافية للحد الأدنى أو الأقصى ، ولكن إذا استوفى حل مُرشّح مُعيّن الشروط الكافية، فإنه يُضمن فقط أن هذا الحل هو الأفضل محليًا - أي أنه أفضل من أي نقاط مجاورة مسموح بها. يُمكن إيجاد الحل الأمثل العالمي بمقارنة قيم دالة الهدف الأصلية عند النقاط التي تُحقق الشروط الضرورية والشروط الكافية محليًا.
تعتمد طريقة مُضاعِفات لاغرانج على الحدس القائل بأنه عند القيمة العظمى، لا يمكن أن تكون الدالة f ( x , y ) متزايدة في اتجاه أي نقطة مجاورة لها أيضًا g = 0. فلو كانت كذلك، لأمكننا التحرك على طول g = 0 للوصول إلى قيمة أعلى، مما يعني أن نقطة البداية لم تكن في الواقع القيمة العظمى. من هذا المنظور، تُشابه هذه الطريقة تمامًا اختبار ما إذا كانت مشتقة دالة غير مقيدة تساوي صفرًا ، أي أننا نتحقق من أن المشتقة الاتجاهية تساوي صفرًا في أي اتجاه ذي صلة (ممكن).
يمكننا تصور خطوط الكفاف لـ f المعطاة بواسطة f ( x , y ) = d لقيم مختلفة من d ، وخطوط الكفاف لـ g المعطاة بواسطة g ( x , y ) = c .
لنفترض أننا نسير على طول خط الكفاف حيث g = c . نحن مهتمون بإيجاد النقاط التي لا تتغير فيها f تقريبًا أثناء سيرنا، لأن هذه النقاط قد تكون نقاطًا عظمى.
هناك طريقتان يمكن أن يحدث بهما هذا:
- يمكننا لمس خط كفاف الدالة f ، لأن f ، بحسب التعريف ، لا تتغير أثناء سيرنا على طول خطوط كفافها. وهذا يعني أن المماسات لخطوط كفاف الدالتين f و g متوازية هنا.
- لقد وصلنا إلى جزء "مستوي" من f ، مما يعني أن f لا تتغير في أي اتجاه.
للتحقق من الاحتمال الأول (حيث نلامس خطًا كفافيًا للدالة f )، لاحظ أنه بما أن تدرج الدالة عمودي على الخطوط الكفافية، فإن المماسات للخطوط الكفافية للدالتين f و g تكون متوازية إذا وفقط إذا كان تدرج الدالتين f و g متوازيًا. وبالتالي، نريد النقاط ( x , y ) حيث g ( x , y ) = c و بالنسبة للبعضأين هي التدرجات المعنية. الثابتهذا ضروري لأنه على الرغم من أن متجهي التدرج متوازيان، إلا أن مقداريهما لا يكونان متساويين عمومًا. يُسمى هذا الثابت مُضاعِف لاغرانج. (في بعض الاصطلاحات)(يسبقها علامة ناقص).
لاحظ أن هذه الطريقة تحل أيضًا الاحتمال الثاني، وهو أن تكون الدالة f مستوية: إذا كانت f مستوية، فإن ميلها يساوي صفرًا، وبالتالي فإنهو حل بغض النظر عن.
ولدمج هذه الشروط في معادلة واحدة، نقدم دالة مساعدة وحل لاحظ أن هذا يعني حل ثلاث معادلات بثلاثة مجاهيل. هذه هي طريقة معاملات لاغرانج.
لاحظ أنيشير إلىكمشتق جزئي لـبالنسبة إلىيكون
باختصار يمكن تعميم هذه الطريقة بسهولة على الدوال الموجودة علىالمتغيرات وهو ما يعادل حل n + 1 معادلة في n + 1 مجهول.
تمثل القيم القصوى المقيدة للدالة f نقاطًا حرجة في دالة لاغرانج.لكنها ليست بالضرورة قيمًا قصوى محلية لـ(انظر المثال 2 أدناه).
يمكن إعادة صياغة دالة لاغرانج كدالة هاميلتونية ، وفي هذه الحالة تكون الحلول عبارة عن نقاط دنيا محلية للدالة الهاميلتونية. ويتم ذلك في نظرية التحكم الأمثل ، في صورة مبدأ بونترياغين الأقصى .
إن حقيقة أن حلول طريقة معاملات لاغرانج ليست بالضرورة نقاطًا قصوى لدالة لاغرانج، تُشكل أيضًا صعوبات في التحسين العددي. ويمكن معالجة هذه الصعوبة بتقليل قيمة تدرج دالة لاغرانج، حيث أن هذه القيم الدنيا هي نفسها أصفار القيمة القصوى، كما هو موضح في المثال 5: التحسين العددي .
قيود متعددة


يمكن توسيع طريقة مُضاعِفات لاغرانج لحل مسائل ذات قيود متعددة باستخدام حجة مماثلة. لنفترض وجود قطع مكافئ يخضع لقيود خطية تتقاطع في نقطة واحدة. وباعتبارها الحل الوحيد الممكن، فإن هذه النقطة تُعدّ قيمة قصوى مقيدة. ومع ذلك، فإن مجموعة المستوى لـمن الواضح أن الخط ليس موازيًا لأي من القيدين عند نقطة التقاطع (انظر الشكل 3)؛ بل هو توليفة خطية من تدرجات القيدين. في حالة وجود قيود متعددة، سيكون هذا ما نبحث عنه بشكل عام: تبحث طريقة لاغرانج عن نقاط لا يكون عندها تدرج الخط موازيًا لأي من القيدين.هو بالضرورة مضاعف لتدرج أي قيد منفرد، ولكنه في هذه الحالة يكون مزيجًا خطيًا من تدرجات جميع القيود.
على وجه التحديد، لنفترض أن لديناالقيود ويسيرون على طول مجموعة النقاط التي تحققكل نقطةعلى محيط دالة قيد معينةيحتوي على فضاء من الاتجاهات المسموح بها: فضاء المتجهات العمودية علىوبالتالي، فإن مجموعة الاتجاهات المسموح بها وفقًا لجميع القيود هي فضاء الاتجاهات العمودية على تدرجات جميع القيود. نرمز إلى فضاء الحركات المسموح بها هذا بـونرمز إلى مدى تدرجات القيود بـثمفضاء المتجهات العمودية على كل عنصر من
ما زلنا مهتمين بإيجاد نقاط حيثلا يتغير أثناء سيرنا، لأن هذه النقاط قد تكون نقاطًا قصوى (مقيدة). لذلك نسعى إلىبحيث يكون أي اتجاه مسموح به للحركة بعيدًا عنعمودي على(وإلا فقد نزيدعن طريق التحرك في ذلك الاتجاه المسموح به). بعبارة أخرى،وبالتالي توجد كميات قياسيةبحيث
هذه الكميات القياسية هي معاملات لاغرانج. لدينا الآنواحد منهم، واحد لكل قيد.
كما في السابق، نقدم دالة مساعدة وحل وهو ما يعادل حلالمعادلات فيمجهول.
الافتراض المتعلق بتأهيل القيود عند وجود قيود متعددة هو أن تدرجات القيود عند النقطة ذات الصلة مستقلة خطيًا.
صياغة حديثة عبر مشعبات قابلة للتفاضل
يمكن تعميم مشكلة إيجاد القيم العظمى والصغرى المحلية الخاضعة للقيود لتشمل إيجاد القيم العظمى والصغرى المحلية على مشعب قابل للتفاضل[ 14 ] فيما يلي، ليس من الضروري أنقد يكون فضاءً إقليديًا، أو حتى متعدد الشعب الريماني . جميع مظاهر التدرج(الذي يعتمد على اختيار المقياس الريماني) يمكن استبداله بالمشتق الخارجي.
قيد واحد
يتركليكن متعدد الأبعاد أملسًالنفترض أننا نرغب في إيجاد النقاط الثابتةدالة سلسةعندما يقتصر على الشعبة الفرعيةمحدد بواسطةأينهي دالة سلسة يكون فيها الصفر قيمة منتظمة .
يتركوتكون المشتقات الخارجية لـو. استقرار القيدفيوسائلوبعبارة أخرى، النواةيتضمنبعبارة أخرى،وهي أشكال تناسبية من الدرجة الأولى. ولذلك، من الضروري والكافي أن يكون النظام التالي منالمعادلة صحيحة: أينيشير إلى المنتج الخارجي . النقاط الثابتةهي حلول نظام المعادلات المذكور أعلاه بالإضافة إلى القيدلاحظ أنالمعادلات ليست مستقلة، لأن الطرف الأيسر من المعادلة ينتمي إلى مجموعة فرعية منيتكون من عناصر قابلة للتحلل .
في هذه الصيغة، ليس من الضروري إيجاد مُضاعِف لاغرانج صراحةً، وهو عددبحيث
قيود متعددة
يتركويكون الأمر كما هو موضح في القسم أعلاه فيما يتعلق بحالة القيد الواحد. بدلاً من الدالةكما هو موضح هناك، لنفترض الآن دالة سلسةمع وظائف المكوناتوالتيهي قيمة منتظمة . ليكنليكن التشعب الفرعي لـمحدد بواسطة
هي نقطة ثابتة لـإذا وفقط إذايتضمنللتسهيل، دعناوأينيشير إلى خريطة المماس أو جاكوبيان(يمكن تحديدها بشكل أساسي بـ). الفضاء الجزئيأبعاده أصغر من أبعاد، أيوينتمي إلىإذا وفقط إذاينتمي إلى صورةمن الناحية الحسابية، الشرط هو أنينتمي إلى فضاء الصفوف لمصفوفةأو ما يعادله، فضاء أعمدة مصفوفة(المنقول). إذايرمز إلى الضرب الخارجي لأعمدة مصفوفةالشرط الثابت لـفييصبح ومرة أخرى، في هذه الصيغة ليس من الضروري إيجاد معاملات لاغرانج بشكل صريح، الأرقامبحيث
تفسير معاملات لاغرانج
في هذا القسم، نقوم بتعديل معادلات القيد من الشكل التالي:إلى النموذجحيثهي m ثوابت حقيقية تُعتبر وسائط إضافية للتعبير اللاغرانجي.
غالبًا ما تُفسَّر معاملات لاغرانج على أنها كمية معينة ذات أهمية. على سبيل المثال، من خلال تحديد خط الكفاف للقيد، أي إذا كان تعبير لاغرانج هو ;\lambda _{1},\lambda _{2},\ldots ;c_{1},c_{2},\ldots )\\[4pt]={}&f(x_{1},x_{2},\ldots )+\lambda _{1}(c_{1}-g_{1}(x_{1},x_{2},\ldots ))+\lambda _{2}(c_{2}-g_{2}(x_{1},x_{2},\dots ))+\cdots \end{aligned}}} ثم
إذن، λk هو معدل تغير الكمية المراد تحسينها كدالة لمعامل القيد. على سبيل المثال، في ميكانيكا لاغرانج، تُشتق معادلات الحركة بإيجاد النقاط الثابتة للفعل ، وهو التكامل الزمني للفرق بين الطاقة الحركية والطاقة الكامنة. وبالتالي، يمكن تفسير القوة المؤثرة على جسيم نتيجة جهد قياسي، F = −∇V ، على أنها مُضاعِف لاغرانج يُحدد التغير في الفعل (انتقال الطاقة الكامنة إلى الطاقة الحركية) تبعًا لتغير في مسار الجسيم المُقيد. في نظرية التحكم، يُصاغ هذا بدلاً من ذلك كمعادلات الحالة المرافقة .
علاوة على ذلك، وبحسب نظرية الغلاف، فإن القيمة المثلى لمضاعف لاغرانج تُفسَّر على أنها التأثير الهامشي لثابت القيد المقابل على القيمة المثلى الممكنة لدالة الهدف الأصلية: إذا رمزنا للقيم عند القيمة المثلى بعلامة النجمة ()، عندئذٍ يمكن إثبات أن
على سبيل المثال، في علم الاقتصاد، يتم حساب الربح الأمثل للاعب في ظل مجموعة محدودة من الإجراءات، حيث يمثل مُضاعِف لاغرانج التغير في القيمة المثلى لدالة الهدف (الربح) نتيجة لتخفيف قيد معين (مثلاً من خلال تغيير في الدخل)؛ في مثل هذا السياقيمثل التكلفة الحدية للقيد، ويشار إليه باسم السعر الظلي . [ 15 ]
شروط كافية
يمكن تحديد الشروط الكافية لوجود قيمة عظمى أو صغرى محلية مقيدة بدلالة سلسلة من المحددات الرئيسية (محددات المصفوفات الفرعية المحاذية للأعلى الأيسر) لمصفوفة هيسيان ذات الحدود للمشتقات الثانية للتعبير اللاغرانجي. [ 6 ] [ 16 ]
أمثلة
المثال 1

لنفترض أننا نرغب في تحقيق أقصى قدر منرهناً بالقيودمجموعة الحلول الممكنة هي دائرة الوحدة، ومجموعات مستوى الدالة f هي خطوط قطرية (بميل -1)، لذا يمكننا أن نرى بيانيًا أن القيمة القصوى تحدث عندوأن الحد الأدنى يحدث عند
بالنسبة لطريقة معاملات لاغرانج، فإن القيد هو ومن ثم دالة لاغرانج، هي دالة مكافئة لـمتىتم ضبطه على 0 .
والآن يمكننا حساب التدرج: وبالتالي:
لاحظ أن المعادلة الأخيرة هي القيد الأصلي.
المعادلتان الأوليان تعطيان بالتعويض في المعادلة الأخيرة نحصل على: لذا مما يعني أن النقاط الثابتة لـنكون
تقييم دالة الهدف f عند هذه النقاط ينتج عنه
وبالتالي فإن الحد الأقصى المقيد هووالحد الأدنى المقيد هو.
المثال 2

الآن نعدل دالة الهدف في المثال 1 بحيث نخفض بدلاً منمرة أخرى على طول الدائرةالآن مجموعات المستويات منلا تزال هذه الخطوط ذات ميل -1، والنقاط على الدائرة المماسية لهذه المستويات هي مرة أخرىوتمثل نقاط التماس هذه القيم القصوى لـ
من ناحية أخرى، تحدث القيم الدنيا على مجموعة المستويات لـ(منذ بنائها)لا يمكن أن تأخذ قيمًا سالبة عندوحيث منحنيات المستوى لـلا تكون مماسية للقيد. الشرط هو أنيُحدد البرنامج جميع النقاط الأربع بشكل صحيح على أنها نقاط قصوى؛ وتتميز النقاط الدنيا بـوالقيم القصوى بواسطة
المثال 3

يتناول هذا المثال حسابات أكثر تعقيدًا، ولكنه لا يزال مشكلة ذات قيد واحد.
لنفترض أن المرء يريد إيجاد القيم القصوى لـ بشرط أن- وتقع الإحداثيات على الدائرة المحيطة بنقطة الأصل بنصف قطرأي، رهناً بالقيد
بما أن هناك قيدًا واحدًا فقط، فهناك مُضاعِف واحد، على سبيل المثال
القيديساوي الصفر تمامًا على الدائرة التي نصف قطرهاأي مضاعف لـيمكن إضافته إلىمغادرةدون تغيير في المنطقة محل الاهتمام (على الدائرة حيث يتم استيفاء القيد الأصلي).
يؤدي تطبيق طريقة مضاعف لاغرانج العادية إلى ومنها يمكن حساب التدرج: وبالتالي: (iii) هو القيد الأصلي فقط. (i) يستلزمأولوثمبواسطة (ثالثاً) وبالتالي من (ii). إذاوباستبدال هذا في (ii) ينتجبتعويض هذا في (iii) وحل المعادلة لإيجادأعطِوبالتالي، توجد ست نقاط حرجة :}
بتقييم الهدف عند هذه النقاط، يجد المرء أن
وبالتالي، تصل دالة الهدف إلى القيمة القصوى العالمية (مع مراعاة القيود) عندوالحد الأدنى العالمي عندالنقطةهو الحد الأدنى المحلي لـوهي قيمة عظمى محلية لـكما يمكن تحديده من خلال النظر في مصفوفة هيسيان لـ
لاحظ أنه بينماتُعد نقطة حاسمة منإنها ليست حالة قصوى محلية لـلدينا
بالنظر إلى أي حي منيمكن للمرء أن يختار جانبًا إيجابيًا صغيرًاوصغيرمن أي من العلامتين للحصول علىالقيم الأكبر والأصغر منويمكن ملاحظة ذلك أيضًا من خلال مصفوفة هيسيان الخاصة بـيتم تقييمها عند هذه النقطة (أو في الواقع عند أي من النقاط الحرجة) وهي مصفوفة غير محددة . كل نقطة من النقاط الحرجة لـهي نقطة سرجية[ 4 ]
المثال 4 - الإنتروبيا
لنفترض أننا نرغب في إيجاد التوزيع الاحتمالي المنفصل على النقاطمع أقصى إنتروبيا معلوماتية . وهذا يعني أننا نرغب في إيجاد أقل توزيع احتمالي منظم على النقاطبمعنى آخر، نرغب في تعظيم معادلة إنتروبيا شانون :
لكي يكون هذا توزيعًا احتماليًا، يجب أن يكون مجموع الاحتمالاتعند كل نقطةيجب أن يساوي 1، لذا فإن قيدنا هو:
نستخدم معاملات لاغرانج لإيجاد نقطة أقصى إنتروبيا،عبر جميع التوزيعات الاحتمالية المنفصلةعلىنحن نشترط ما يلي: مما ينتج عنه نظام من n معادلة،بحيث:
بإجراء عملية التفاضل لهذه المعادلات n ، نحصل على
هذا يدل على أن كلمتساويتان (لأنهما تعتمدان على λ فقط). باستخدام القيد نجد
وبالتالي، فإن التوزيع المنتظم هو التوزيع ذو أكبر إنتروبيا، من بين التوزيعات على n نقطة.
المثال 5 - التحسين العددي


تقع النقاط الحرجة لدوال لاغرانج عند نقاط السرج ، وليس عند القيم العظمى (أو الصغرى) المحلية. [ 4 ] [ 17 ] لسوء الحظ، صُممت العديد من تقنيات التحسين العددي، مثل تسلق التلال ، وانحدار التدرج ، وبعض طرق شبه نيوتن ، وغيرها، لإيجاد القيم العظمى (أو الصغرى) المحلية وليس نقاط السرج. لهذا السبب، يجب إما تعديل الصيغة لضمان أنها مسألة تصغير (على سبيل المثال، عن طريق إيجاد القيمة القصوى لمربع تدرج دالة لاغرانج كما هو موضح أدناه)، أو استخدام تقنية تحسين تجد النقاط الثابتة (مثل طريقة نيوتن بدون بحث خطي عن القيم القصوى ) وليس بالضرورة القيم القصوى.
كمثال بسيط، لننظر في مشكلة إيجاد قيمة x التي تقلل منمقيدة بحيث(هذه المشكلة غير نمطية إلى حد ما لأنه لا يوجد سوى قيمتين تحققان هذا القيد، لكنها مفيدة لأغراض التوضيح لأنه يمكن تصور الدالة غير المقيدة المقابلة في ثلاثة أبعاد.)
باستخدام معاملات لاغرانج، يمكن تحويل هذه المشكلة إلى مشكلة تحسين غير مقيدة:
تحدث النقطتان الحرجتان عند نقاط السرج حيث x = 1 و x = −1 .
لحل هذه المشكلة باستخدام تقنية التحسين العددي، يجب أولاً تحويلها بحيث تقع النقاط الحرجة عند القيم الدنيا المحلية. ويتم ذلك بحساب مقدار تدرج مسألة التحسين غير المقيدة.
أولاً، نقوم بحساب المشتقة الجزئية للمسألة غير المقيدة بالنسبة لكل متغير:
إذا لم تكن الدالة المستهدفة قابلة للتفاضل بسهولة، فيمكن تقريب التفاضل بالنسبة لكل متغير على النحو التالي: أينقيمة صغيرة.
بعد ذلك، نحسب مقدار التدرج، وهو الجذر التربيعي لمجموع مربعات المشتقات الجزئية:
(بما أن المقدار دائمًا غير سالب، فإن التحسين على أساس مربع المقدار يكافئ التحسين على أساس المقدار. وبالتالي، يمكن حذف "الجذر التربيعي" من هذه المعادلات دون أي فرق متوقع في نتائج التحسين.)
تحدث النقاط الحرجة للدالة h عند x = 1 و x = −1 ، تمامًا كما فيبخلاف النقاط الحرجة فيومع ذلك، فإن النقاط الحرجة في h تحدث عند الحد الأدنى المحلي، لذلك يمكن استخدام تقنيات التحسين العددي لإيجادها.
التطبيقات
ميكانيكا لاغرانج
في ميكانيكا لاغرانج ، يمكن إضافة مُضاعِفات لاغرانج إلى معادلات أويلر-لاغرانج كوسيلة لفرض قيود فيزيائية على الأنظمة. [ 18 ] هذه الطريقة ليست ضرورية بشكل عام، لأن هناك طريقة بديلة تتمثل في اختيار مجموعة من الإحداثيات المعممة المستقلة خطيًا بحيث تُفرض القيود ضمنيًا.
عند استخدام معاملات لاغرانج، يجب حل معادلات القيد بالتزامن مع معادلات أويلر-لاغرانج. وبالتالي، تصبح المعادلات نظامًا من المعادلات التفاضلية الجبرية (بدلاً من نظام المعادلات التفاضلية العادية ). [ 19 ]
تُعدّ طريقة مُضاعِفات لاغرانج مفيدةً عندما يصعب كتابة دالة لاغرانج بدلالة مجموعة من الإحداثيات المعممة المستقلة خطيًا. على سبيل المثال، تُستخدم في خوارزميات نمذجة الأنظمة الديناميكية البرمجية، أو في نمذجة الأنظمة ذات السلاسل الحركية المغلقة. [ 20 ] كما أنها مفيدة لفرض قيود غير هولونومية. [ 18 ] [ 20 ]
بالنظر إلى مجموعة من معادلات القيود الهولونوميةويمكن كتابة معادلات أويلر-لاغرانج مع مضاعفات لاغرانج على النحو التالي [ 18 ] [ 19 ]
معنىيمكن تفسير ذلك بنقله إلى الجانب الآخر من المعادلة ودمجه في حد القوة المعممةفي هذا التفسير، يمتلك النظامعدد من درجات الحرية الإضافية، ولا توجد قيود مفروضة إضافية، ولكن قوى القيدتصادف أن تكون لها القيم المناسبة بحيث تتحقق القيود. [ 18 ] [ 19 ]
نظرية التحكم
في نظرية التحكم الأمثل ، يتم تفسير مضاعفات لاغرانج على أنها متغيرات الحالة المرافقة ، ويتم إعادة صياغة مضاعفات لاغرانج على أنها تقليل الهاميلتوني ، في مبدأ بونترياجين الأقصى .
البرمجة غير الخطية
تتضمن طريقة مُضاعِف لاغرانج عدة تعميمات. في البرمجة غير الخطية، توجد عدة قواعد للمُضاعِف، مثل قاعدة كاراثيودوري-جون للمُضاعِف وقاعدة المُضاعِف المحدب، لقيود المتباينات. [ 21 ]
الاقتصاد
في العديد من نماذج الاقتصاد الرياضي ، مثل نماذج التوازن العام ، يُعبَّر عن سلوك المستهلك بتعظيم المنفعة ، وعن سلوك الشركة بتعظيم الربح ، مع خضوع كلا الكيانين لقيود مثل قيود الميزانية وقيود الإنتاج . ويتم عادةً تحديد الحل الأمثل من خلال تعظيم دالة معينة، حيث تُفرض القيود باستخدام مُضاعِفات لاغرانج. [ 22 ] [ 23 ] [ 24 ] [ 25 ]
أنظمة الطاقة
تُستخدم الطرق القائمة على مضاعفات لاغرانج في أنظمة الطاقة ، على سبيل المثال في تحديد مواقع موارد الطاقة الموزعة (DER) وتخفيف الأحمال. [ 26 ]
التعلم الآمن المعزز
تُطبَّق طريقة مُضاعِفات لاغرانج على عمليات اتخاذ القرار ماركوف المقيدة . [ 27 ] وهي تُنتج بشكل طبيعي خوارزميات ثنائية أولية قائمة على التدرج في التعلم المعزز الآمن. [ 28 ]
بالنظر إلى مسائل المعادلات التفاضلية الجزئية ذات القيود، أي دراسة خصائص الحلول المعيارية، فإن مضاعفات لاغرانج تلعب دورًا مهمًا.
انظر أيضاً
- تعديل الملاحظات
- الازدواجية
- فهرس جيتينز
- شروط كاروش-كون-تاكر : تعميم لطريقة مضاعفات لاغرانج
- مضاعفات لاغرانج على فضاءات باناخ : تعميم آخر لطريقة مضاعفات لاغرانج
- اختبار مضاعف لاغرانج في تقدير الاحتمال الأقصى
- استرخاء لاغرانجي
مراجع
- ↑ هوفمان، لورانس د.؛ برادلي، جيرالد ل. (2004). حساب التفاضل والتكامل للأعمال والاقتصاد والعلوم الاجتماعية والحياتية ( الطبعة الثامنة). ماكجرو هيل للتعليم العالي. الصفحات 575-588 . ISBN 0-07-242432-X.
- ↑ بيفيس، برايان؛ دوبس، إيان م. (1990). "التحسين الساكن" . نظرية التحسين والاستقرار للتحليل الاقتصادي . نيويورك: مطبعة جامعة كامبريدج. ص 40. ISBN 0-521-33605-8.
- ↑ بروتر، موراي هـ .؛ موري، تشارلز ب. الابن (1985). حساب التفاضل والتكامل المتوسط ( الطبعة الثانية). نيويورك، نيويورك: سبرينغر. ص 267. ISBN 0-387-96058-9.
- 1 2 3 والش، جي آر (1975). "خاصية نقطة السرج لدالة لاغرانج" . طرق التحسين . نيويورك، نيويورك: جون وايلي وأولاده. ص 39-44 . ISBN 0-471-91922-5.
- ↑ كالمان، دان (2009). " التسوية باستخدام لاغرانج: منظور بديل للتحسين المقيد". مجلة الرياضيات . 82 (3): 186-196 . doi : 10.1080/0025570X.2009.11953617 . JSTOR 27765899. S2CID 121070192 .
- 1 2 سيلبربرغ، يوجين؛ سوين، وينغ (2001). بنية الاقتصاد: تحليل رياضي ( الطبعة الثالثة). بوسطن: إيروين ماكجرو هيل. ص 134-141 . ISBN 0-07-234352-4.
- ↑ دي لا فوينتي ، أنجيل (2000). الأساليب والنماذج الرياضية للاقتصاديين . كامبريدج: مطبعة جامعة كامبريدج. ص 285. doi : 10.1017/CBO9780511810756 . ISBN 978-0-521-58512-5.
- ↑ لونبرغر، ديفيد ج. (1969). التحسين باستخدام طرق الفضاء المتجهي . نيويورك: جون وايلي وأولاده. ص 188-189 .
- ↑ بيرتسيكاس، ديمتري ب. (1999). البرمجة غير الخطية ( الطبعة الثانية). كامبريدج، ماساتشوستس: أثينا ساينتيفيك. ISBN 1-886529-00-0.
- ↑ فابنيارسكي، آي بي (2001) [1994]، "مضاعفات لاغرانج" ، موسوعة الرياضيات ، دار نشر إي إم إس.
- ↑ لاسدون، ليون س. (2002) [1970]. نظرية التحسين للأنظمة الكبيرة (طبعة مُعاد طباعتها). مينولا، نيويورك، نيويورك: دوفر. ISBN 0-486-41999-1MR 1888251 .
- ^ هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1993). “الفصل الثاني عشر: الازدواجية المجردة للممارسين”. التحليل المحدب وخوارزميات التقليل . Grundlehren der Mathematischen Wissenschaften [المبادئ الأساسية للعلوم الرياضية]. المجلد. 306. برلين، DE: Springer-Verlag. ص 136 – 193 (والتعليقات الببليوغرافية ص 334 – 335). رقم ISBN 3-540-56852-2MR 1295240. المجلد الثاني : النظرية المتقدمة وطرق الحزم.
- ^ ليمارشال، كلود (15-19 مايو 2000). "استرخاء لاغرانج". في جونجر، مايكل؛ نادف، دينيس (محرران). التحسين التوافقي الحسابي: أوراق من مدرسة الربيع التي عقدت في شلوس داغستوهل . أقيمت مدرسة الربيع في شلوس داغستوهل في الفترة من 15 إلى 19 مايو 2000 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2241. برلين، DE: Springer-Verlag (نشرت عام 2001). ص 112 – 156. دوى : 10.1007 / 3-540-45586-8_4 . رقم ISBN 3-540-42877-1MR 1900016 . S2CID 9048698 .
- ↑ لافونتين، جاك (2015). مقدمة في المشعبات التفاضلية . سبرينغر. ص 70. ISBN 978-3-319-20735-3.
- ↑ ديكسيت، أفيناش ك. (1990). "أسعار الظل" . الأمثلية في النظرية الاقتصادية ( الطبعة الثانية). نيويورك: مطبعة جامعة أكسفورد. ص 40-54 . ISBN 0-19-877210-6.
- ↑ تشيانغ ، ألفا سي. (1984). الأساليب الأساسية للاقتصاد الرياضي ( الطبعة الثالثة). ماكجرو هيل. ص 386. ISBN 0-07-010813-7.
- ↑ هيث، مايكل ت. (2005). الحوسبة العلمية: دراسة تمهيدية . ماكجرو هيل. ص 203. ISBN 978-0-07-124489-3.
- 1 2 3 4 غولدشتاين، هربرت ؛ بول، تشارلز ب. الابن ؛ سافكو، جون ل. (2002). الميكانيكا الكلاسيكية ( الطبعة الثالثة). سان فرانسيسكو، كاليفورنيا: أديسون ويسلي. الصفحات 45-51 . ISBN 0-201-65702-3.
- 1 2 3 برينان، ك. إي.؛ كامبل، س. ل.؛ بيتزولد، ل. ر. (1995). الحل العددي لمسائل القيمة الابتدائية في المعادلات التفاضلية الجبرية . جمعية الرياضيات الصناعية والتطبيقية. ص 4-5 . doi : 10.1137/1.9781611971224 .
- 1 2 روي، فيذرستون (2008). خوارزميات ديناميكيات الأجسام الصلبة . سبرينغر نيويورك. ص 42-45 ، 141-143 . doi : 10.1007/978-1-4899-7560-7 .
- ↑ بوركيو، بروس هـ. (1980). "قواعد المضاعف الحديثة" . المجلة الرياضية الأمريكية الشهرية . 87 (6): 433-452 . doi : 10.2307/2320250 . JSTOR 2320250 .
- ↑ كامين، إم آي ؛ شوارتز، إن إل (1991). التحسين الديناميكي: حساب التفاضل والتكامل والتحكم الأمثل في الاقتصاد والإدارة ( الطبعة الثانية). نيويورك: إلسيفير. ISBN 0-444-01609-0.
- ↑ غلوتزل، إرهارد؛ غلوتزل، فلورنتين؛ ريخترز، أوليفر (2019). "من التحسين المقيد إلى الديناميكيات المقيدة: توسيع أوجه التشابه بين الاقتصاد والميكانيكا". مجلة التفاعل والتنسيق الاقتصادي . 14 (3): 623-642 . doi : 10.1007/s11403-019-00252-7 . hdl : 10419/171974 .
- ↑ باكسلي، جون ف.؛ مورهاوس، جون س. (1984). "مسائل مضاعف لاغرانج في الاقتصاد". المجلة الرياضية الأمريكية الشهرية . 91 (7): 404-412 . doi : 10.1080/00029890.1984.11971446 ..
- ↑ جانوفا، جيتكا (2011). "تطبيقات منهجية الميكانيكا المقيدة في الاقتصاد". المجلة الأوروبية للفيزياء . 32 (6): 1443-1463 . arXiv : 1106.3455 . Bibcode : 2011EJPh...32.1443J . doi : 10.1088/0143-0807/32/6/001 .
- ↑ غوتام، موكيش؛ بهوسال، نارايان؛ بنيدريس، محمد (2020). منهج قائم على الحساسية لتخفيف الأحمال التكيفي عند انخفاض التردد . مؤتمر IEEE تكساس للطاقة والكهرباء 2020 (TPEC). معهد مهندسي الإلكترونيات والكهرباء . الصفحات 1-5 . doi : 10.1109/TPEC48276.2020.9042569 .
- ↑ ألتمان، إيتان (2021). عمليات اتخاذ القرار ماركوف المقيدة . روتليدج .
- ↑ دينغ، دونغشنغ؛ تشانغ، كايتشينغ؛ يوفانوفيتش، ميهايلو؛ باسار، تامر (2020). طريقة التدرج الطبيعي للسياسة الأولية-الثنائية لعمليات اتخاذ القرار ماركوف المقيدة . التطورات في أنظمة معالجة المعلومات العصبية.
للمزيد من القراءة
- بيفيس، برايان؛ دوبس، إيان م. (1990). "التحسين الساكن" . نظرية التحسين والاستقرار للتحليل الاقتصادي . نيويورك، نيويورك: مطبعة جامعة كامبريدج. ص 32-72 . ISBN 0-521-33605-8.
- بيرتسيكاس، ديمتري ب. (1982). التحسين المقيد وطرق مضاعف لاغرانج . نيويورك، نيويورك: أكاديميك برس. ISBN 0-12-093480-9.
- بيفريدج، جوردون إس جي؛ شيشتر، روبرت إس. (1970). "المضاعفات اللاغرانجية" . التحسين: النظرية والتطبيق . نيويورك، نيويورك: ماكجرو هيل. ص 244-259 . ISBN 0-07-005128-3.
- بينجر، برايان ر.؛ هوفمان، إليزابيث (1998). "التحسين المقيد". الاقتصاد الجزئي مع حساب التفاضل والتكامل ( الطبعة الثانية). ريدينغ: أديسون-ويسلي. ص 56-91 . ISBN 0-321-01225-9.
- كارتر، مايكل (2001). "قيود المساواة" . أسس الاقتصاد الرياضي . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ص 516-549 . ISBN 0-262-53192-5.
- هيستينز، ماغنوس ر. (1966). "القيم الصغرى للدوال الخاضعة لقيود المساواة". حساب التفاضل والتكامل ونظرية التحكم الأمثل . نيويورك، نيويورك: وايلي. ص 29-34 .
- وايلي، سي. راي؛ باريت، لويس سي. (1995). "القيم القصوى للتكاملات تحت القيود". الرياضيات الهندسية المتقدمة ( الطبعة السادسة). نيويورك، نيويورك: ماكجرو هيل. الصفحات 1096-1103 . ISBN 0-07-072206-4.
روابط خارجية
معرض
- ستيوارد. "مقدمة مفاهيمية" . slimy.com .— بالإضافة إلى مناقشة موجزة لمعاملات لاغرانج في حساب التفاضل والتكامل كما هو مستخدم في الفيزياء.
- كاربنتر، كينيث هـ. "معاملات لاغرانج للأشكال التربيعية ذات القيود الخطية" (ملف PDF) . جامعة ولاية كانساس .
نصوص إضافية وتطبيقات تفاعلية
- ريسنيك. "شرح مبسط مع مثال على استخدام الحكومات للضرائب كمضاعفات لاغرانج" . umiacs.umd.edu . جامعة ميريلاند . مؤرشف من الأصل في 4 سبتمبر 2015. تم الاطلاع عليه في 28 فبراير 2007 .
- كلاين، دان. "مضاعفات لاغرانج بدون ندوب دائمة : شرح مع التركيز على الحدس" (ملف PDF) . nlp.cs.berkeley.edu . جامعة كاليفورنيا، بيركلي .
- ساتيانارايانا، شاشي. "التمثيل الهندسي لطريقة مُضاعِفات لاغرانج" . wolfram.com ( عرض توضيحي لبرنامج Mathematica ). شركة Wolfram Research .
يتطلب متصفح إنترنت إكسبلورر / فايرفوكس / سفاري.
— يقدم رؤية مقنعة في بعدين مفادها أنه عند نقطة التصغير، يجب أن يكون اتجاه الانحدار الأشد عموديًا على مماس منحنى القيد عند تلك النقطة. - "معاملات لاغرانج - متغيران" . برنامج MIT التعليمي المفتوح (ocw.mit.edu) (تطبيق صغير). معهد ماساتشوستس للتكنولوجيا .
- "مضاعفات لاغرانج" . موقع MIT Open Courseware (ocw.mit.edu) (محاضرة فيديو). الرياضيات 18-02: حساب التفاضل والتكامل متعدد المتغيرات. معهد ماساتشوستس للتكنولوجيا . خريف 2007.
- بيرتسيكاس. "تفاصيل حول مُضاعِفات لاغرانج" (ملف PDF) . athenasc.com (شرائح العرض / محاضرة الدورة). البرمجة غير الخطية.— شرائح العرض التقديمي المصاحبة للنص المتعلق بالتحسين غير الخطي
- وايت، جون (7 أبريل 2004) [19 نوفمبر 2002]. "مضاعفات ليجرانج، والتحسين المقيد، ومبدأ أقصى إنتروبيا" (ملف PDF) . www-mtl.mit.edu . الهندسة الكهربائية وعلوم الحاسوب / الهندسة الميكانيكية 6.050 - المعلومات، والإنتروبيا، والحوسبة.— الفكرة الهندسية وراء مضاعفات لاغرانج
- "استخدام مُضاعِفات لاغرانج في التحسين" . matlab.cheme.cmu.edu (مثال MATLAB). بيتسبرغ، بنسلفانيا: جامعة كارنيجي ميلون. 24 ديسمبر 2011.
- حساب التفاضل والتكامل متعدد المتغيرات
- التحسين الرياضي
- الأساليب الرياضية والكمية (الاقتصاد)
