التحسين الرياضي

التحسين الرياضي (أو التحسين المكتوب بشكل بديل ) أو البرمجة الرياضية هو اختيار أفضل عنصر، فيما يتعلق ببعض المعايير، من مجموعة من البدائل المتاحة. ^{[1] [2]} وينقسم عمومًا إلى مجالين فرعيين: التحسين المنفصل والتحسين المستمر . تنشأ مشاكل التحسين في جميع التخصصات الكمية من علوم الكمبيوتر والهندسة ^[3] إلى بحوث العمليات والاقتصاد ، وكان تطوير طرق الحل محل اهتمام الرياضيات لعدة قرون. [ ^{4] [5]}

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

يمكن تقسيم مشاكل التحسين إلى فئتين، اعتمادًا على ما إذا كانت المتغيرات متصلة أو منفصلة :

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

يمكن تمثيل مشكلة التحسين بالطريقة التالية:

معطى: دالة f  : A → من مجموعة A إلى الأعداد الحقيقية${\displaystyle \mathbb {R} }$

المطلوب: عنصر x ₀ ∈ A بحيث f ( x ₀ ) ≤ f ( x ) لجميع x ∈ A ("التقليل") أو بحيث f ( x ₀ ) ≥ f ( x ) لجميع x ∈ A ("التعظيم").

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

حيث أن ما يلي صحيح

${\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} )،}$

يكفي حل مشاكل التقليل فقط. ومع ذلك، فإن المنظور المعاكس المتمثل في النظر فقط في مشاكل التعظيم سيكون صحيحًا أيضًا.

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

عادةً، يكون A عبارة عن مجموعة فرعية من الفضاء الإقليدي ، وغالبًا ما يتم تحديدها من خلال مجموعة من القيود أو المساواة أو عدم المساواة التي يجب أن تلبيها عناصر A. يُطلق على المجال A من f اسم مساحة البحث أو مجموعة الاختيار ، بينما تُسمى عناصر A حلولاً مرشحة أو حلولاً ممكنة . ${\displaystyle \mathbb {R} ^{n}}$

تُسمى الدالة f بشكل مختلف دالة الهدف ، أو دالة المعيار ، أو دالة الخسارة ، أو دالة التكلفة (التقليل إلى الحد الأدنى)، ^{[8] أو} دالة المنفعة ، أو دالة اللياقة البدنية (التعظيم)، أو في مجالات معينة، دالة الطاقة أو دالة الطاقة . يُطلق على الحل القابل للتطبيق الذي يقلل (أو يزيد) من دالة الهدف اسم الحل الأمثل .

في الرياضيات، عادة ما يتم صياغة مشاكل التحسين التقليدية من حيث التقليل.

يتم تعريف الحد الأدنى المحلي x * على أنه عنصر يوجد به بعض δ > 0 بحيث

${\displaystyle \forall \mathbf {x} \in A\;{\text{حيث}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,}$

العبارة f ( x *) ≤ f ( x ) صحيحة؛

وهذا يعني أنه في بعض المناطق حول x * تكون جميع قيم الدالة أكبر من أو تساوي القيمة عند هذا العنصر. يتم تعريف القيم القصوى المحلية على نحو مماثل.

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

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

غالبًا ما يتم التعبير عن مشكلات التحسين باستخدام تدوين خاص. وفيما يلي بعض الأمثلة:

خذ بعين الاعتبار الترميز التالي:

${\displaystyle \min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)}$

يشير هذا إلى القيمة الدنيا لدالة الهدف x ² + 1 ، عند اختيار x من مجموعة الأعداد الحقيقية . القيمة الدنيا في هذه الحالة هي 1، تحدث عند x = 0 . ${\displaystyle \mathbb {R} }$

وبالمثل، فإن التدوين

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

يطلب إيجاد القيمة القصوى لدالة الهدف 2 x ، حيث يمكن أن يكون x أي عدد حقيقي. في هذه الحالة، لا يوجد حد أقصى لأن دالة الهدف غير محدودة، لذا فإن الإجابة هي " لا نهاية " أو " غير محددة ".

خذ بعين الاعتبار الترميز التالي:

${\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,}$

أو ما يعادله

${\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].}$

يمثل هذا قيمة (أو قيم) الوسيطة x في الفاصل ( −∞,−1] التي تقلل (أو تقلل) من دالة الهدف x ² + 1 (القيمة الدنيا الفعلية لهذه الدالة ليست ما تطلبه المشكلة). في هذه الحالة، تكون الإجابة x = −1 ، نظرًا لأن x = 0 غير قابلة للتنفيذ، أي أنها لا تنتمي إلى المجموعة الممكنة .

بصورة مماثلة،

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,}$

أو ما يعادله

${\displaystyle {\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

يمثل الزوج (أو الأزواج) { x , y } الذي يزيد (أو يزيد) قيمة دالة الهدف x cos y ، مع القيد الإضافي بأن x تقع في الفاصل الزمني [−5,5] (مرة أخرى، لا تهم القيمة القصوى الفعلية للتعبير). في هذه الحالة، تكون الحلول هي الأزواج من النموذج {5, 2 k π } و {−5, (2 k + 1) π } ، حيث يتراوح k على جميع الأعداد الصحيحة .

المشغلان arg min و arg max يُكتبان أحيانًا أيضًا على هيئة argmin و argmax ، ويمثلان وسيطة الحد الأدنى ووسيطة الحد الأقصى .

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

يعود مصطلح " البرمجة الخطية " لبعض حالات التحسين إلى جورج ب. دانتزيج ، على الرغم من أن ليونيد كانتوروفيتش كان قد قدم الكثير من النظرية في عام 1939. ( لا تشير البرمجة في هذا السياق إلى برمجة الكمبيوتر ، ولكنها تأتي من استخدام البرنامج من قبل الجيش الأمريكي للإشارة إلى جداول التدريب واللوجستيات المقترحة ، والتي كانت المشاكل التي درسها دانتزيج في ذلك الوقت.) نشر دانتزيج خوارزمية سيمبليكس في عام 1947، كما عمل جون فون نيومان وباحثون آخرون على الجوانب النظرية للبرمجة الخطية (مثل نظرية الثنائية ) في نفس الوقت تقريبًا. ^[9]

ومن بين الباحثين الآخرين البارزين في مجال التحسين الرياضي ما يلي:

• تدرس البرمجة المحدبة الحالة التي تكون فيها دالة الهدف محدبة (تقليل القيمة) أو مقعرة (تعظيم القيمة) وتكون مجموعة القيود محدبة . ويمكن اعتبار ذلك حالة خاصة من البرمجة غير الخطية أو تعميمًا للبرمجة التربيعية الخطية أو المحدبة.
  • البرمجة الخطية (LP)، وهي نوع من البرمجة المحدبة، تدرس الحالة التي تكون فيها دالة الهدف f خطية ويتم تحديد القيود باستخدام المساواة الخطية وعدم المساواة الخطية فقط. تسمى مجموعة القيود هذه متعدد السطوح أو متعدد السطوح إذا كانت محدودة .
  • برمجة المخروط من الدرجة الثانية (SOCP) عبارة عن برنامج محدب، ويتضمن أنواعًا معينة من البرامج التربيعية.
  • البرمجة شبه المحددة (SDP) هي مجال فرعي من التحسين المحدب حيث تكون المتغيرات الأساسية عبارة عن مصفوفات شبه محددة . وهي تعميم للبرمجة التربيعية الخطية والمحدبة.
  • البرمجة المخروطية هي شكل عام من أشكال البرمجة المحدبة. يمكن اعتبار LP وSOCP وSDP جميعها برامج مخروطية مع النوع المناسب من المخروط.
  • البرمجة الهندسية هي تقنية يمكن من خلالها تحويل القيود الموضوعية واللامساواة المعبر عنها كحدود موجبة وقيود المساواة كحدود أحادية إلى برنامج محدب.
• تدرس البرمجة الصحيحة البرامج الخطية التي يتم فيها تقييد بعض المتغيرات أو كلها لتأخذ قيمًا صحيحة . وهذا ليس محدبًا، وبشكل عام يكون أكثر صعوبة من البرمجة الخطية العادية.
• تسمح البرمجة التربيعية للدالة الهدفية بأن يكون لها حدود تربيعية، بينما يجب تحديد المجموعة الممكنة باستخدام مساوات خطية وعدم مساوات. بالنسبة للأشكال المحددة للحدود التربيعية، يعد هذا نوعًا من البرمجة المحدبة.
• تدرس البرمجة الكسرية تحسين نسب دالتين غير خطيتين. يمكن تحويل الفئة الخاصة من البرامج الكسرية المقعرة إلى مشكلة تحسين محدبة.
• تدرس البرمجة غير الخطية الحالة العامة التي تحتوي فيها الدالة الهدف أو القيود أو كليهما على أجزاء غير خطية. وقد يكون هذا برنامجًا محدبًا أو لا يكون كذلك. وبشكل عام، يؤثر كون البرنامج محدبًا على صعوبة حله.
• تدرس البرمجة العشوائية الحالة التي تعتمد فيها بعض القيود أو المعلمات على متغيرات عشوائية .
• التحسين القوي هو، مثل البرمجة العشوائية، محاولة لالتقاط عدم اليقين في البيانات التي تشكل أساس مشكلة التحسين. يهدف التحسين القوي إلى إيجاد حلول صالحة في ظل جميع الإدراكات الممكنة لعدم اليقين التي تحددها مجموعة عدم اليقين.
• يهتم التحسين التوافقي بالمشاكل التي تكون فيها مجموعة الحلول الممكنة منفصلة أو يمكن اختزالها إلى حل منفصل .
• يتم استخدام التحسين العشوائي مع قياسات الوظائف العشوائية (المزعجة) أو المدخلات العشوائية في عملية البحث.
• تدرس دراسات التحسين ذات الأبعاد اللانهائية الحالة التي تكون فيها مجموعة الحلول الممكنة عبارة عن مجموعة فرعية من مساحة ذات أبعاد لا نهائية ، مثل مساحة الوظائف.
• إن الطرق التجريبية والطرق الفوقية لا تضع سوى افتراضات قليلة أو معدومة حول المشكلة التي يتم تحسينها. وعادةً لا تضمن الطرق التجريبية ضرورة إيجاد أي حل مثالي. ومن ناحية أخرى، تُستخدم الطرق التجريبية لإيجاد حلول تقريبية للعديد من مشاكل التحسين المعقدة.
• تدرس دراسة إرضاء القيود الحالة التي تكون فيها دالة الهدف f ثابتة (يتم استخدام هذا في الذكاء الاصطناعي ، وخاصة في التفكير الآلي ).
  • برمجة القيود هي نموذج برمجة يتم فيه تحديد العلاقات بين المتغيرات في شكل قيود.
• تُستخدم البرمجة المنفصلة عندما يتعين تلبية قيد واحد على الأقل ولكن ليس جميع القيود. وهي مفيدة بشكل خاص في الجدولة.
• رسم الخرائط الفضائية هو مفهوم لنمذجة وتحسين نظام هندسي لتحقيق دقة نموذجية عالية (دقيقة) من خلال استغلال نموذج خشن أو بديل مناسب وذو معنى فيزيائيًا .

في عدد من المجالات الفرعية، تم تصميم التقنيات في المقام الأول لتحسين السياقات الديناميكية (أي اتخاذ القرار بمرور الوقت):

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

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

يتم الحكم على التصميم بأنه "أمثل باريتو" (أو ما يعادله، "فعال باريتو" أو في مجموعة باريتو) إذا لم يهيمن عليه أي تصميم آخر: إذا كان أسوأ من تصميم آخر في بعض النواحي وليس أفضل في أي ناحية، فإنه مهيمن عليه وليس مثاليًا باريتو.

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

تم تعميم مشاكل التحسين متعددة الأهداف إلى مشاكل تحسين المتجهات حيث لم يعد الترتيب (الجزئي) معطى بواسطة ترتيب باريتو.

غالبًا ما تكون مشكلات التحسين متعددة الوسائط؛ أي أنها تمتلك حلولاً جيدة متعددة. وقد تكون جميعها جيدة عالميًا (نفس قيمة دالة التكلفة) أو قد يكون هناك مزيج من الحلول الجيدة عالميًا والجيدة محليًا. إن الحصول على جميع الحلول المتعددة (أو على الأقل بعضها) هو هدف المحسن متعدد الوسائط.

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

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

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

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

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

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

يمكن إيجاد أفضل الحلول للمشكلات المقيدة بالمساواة باستخدام طريقة مضاعف لاغرانج . ويمكن إيجاد أفضل الحلول للمشكلات المقيدة بالمساواة و/أو عدم المساواة باستخدام " شروط كاروش-كوهن-توكر ".

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

تصف نظرية المغلف كيف تتغير قيمة الحل الأمثل عندما يتغير أحد المعاملات الأساسية . وتسمى عملية حساب هذا التغيير بالإحصائيات المقارنة .

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

بالنسبة للمشكلات غير المقيدة مع الدوال القابلة للاشتقاق مرتين، يمكن إيجاد بعض النقاط الحرجة من خلال إيجاد النقاط التي يكون فيها منحدر دالة الهدف صفرًا (أي النقاط الثابتة). وبشكل عام، فإن منحدر فرعي صفري يشهد على إيجاد حد أدنى محلي لمشاكل التقليل مع الدوال المحدبة ووظائف ليبشيتز المحلية الأخرى ، والتي تلتقي في تقليل دالة الخسارة للشبكة العصبية. يسمح تقدير الزخم الإيجابي-السلبي بتجنب الحد الأدنى المحلي ويتقارب عند الحد الأدنى العالمي لدالة الهدف. ^[10]

علاوة على ذلك، يمكن تصنيف النقاط الحرجة باستخدام دقة مصفوفة هيسان : إذا كانت مصفوفة هيسان موجبة محددة عند نقطة حرجة، فإن النقطة تكون حدًا أدنى محليًا؛ إذا كانت مصفوفة هيسان سالبة محددة، فإن النقطة تكون حدًا أقصى محليًا؛ وأخيرًا، إذا كانت غير محددة، فإن النقطة تكون نوعًا من نقاط السرج .

يمكن غالبًا تحويل المشكلات المقيدة إلى مشكلات غير مقيدة بمساعدة مضاعفات لاغرانج . كما يمكن أن يوفر استرخاء لاغرانج حلولاً تقريبية للمشكلات المقيدة الصعبة.

عندما تكون دالة الهدف دالة محدبة ، فإن أي حد أدنى محلي سيكون أيضًا حدًا أدنى عالميًا. توجد تقنيات عددية فعّالة لتقليل الدوال المحدبة، مثل طرق النقطة الداخلية .

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

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

• خوارزمية سيمبلكس لجورج دانتزيج ، مصممة للبرمجة الخطية
• امتدادات خوارزمية السيمبلكس المصممة للبرمجة التربيعية والبرمجة الخطية الكسرية
• متغيرات خوارزمية السمبلكس المناسبة بشكل خاص لتحسين الشبكة
• الخوارزميات التوليفية
• خوارزميات التحسين الكمي

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

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

• طرق تقييم الهسيانيين (أو الهسيانيين التقريبيين، باستخدام الفروق المحدودة ):
  • طريقة نيوتن
  • البرمجة التربيعية المتسلسلة : طريقة تعتمد على نيوتن لحل المشكلات المقيدة على نطاق صغير إلى متوسط . يمكن لبعض الإصدارات التعامل مع المشكلات ذات الأبعاد الكبيرة.
  • طرق النقطة الداخلية : هذه فئة كبيرة من الطرق للتحسين المقيد، بعضها يستخدم فقط معلومات التدرج (الفرعية) والبعض الآخر يتطلب تقييم الهسيانيين.
• الأساليب التي تقوم بتقييم التدرجات، أو تقريب التدرجات بطريقة ما (أو حتى التدرجات الفرعية):
  • طرق نزول الإحداثيات : الخوارزميات التي تقوم بتحديث إحداثيات واحدة في كل تكرار
  • طرق التدرج المترافق : طرق تكرارية للمشكلات الكبيرة. (من الناحية النظرية، تنتهي هذه الطرق بعدد محدود من الخطوات باستخدام وظائف الهدف التربيعية، ولكن هذه النهاية المحدودة لا يتم ملاحظتها عمليًا على أجهزة الكمبيوتر ذات الدقة المحدودة.)
  • النزول التدريجي (أو "الانحدار الأكثر انحدارًا" أو "الصعود الأكثر انحدارًا"): طريقة (بطيئة) ذات أهمية تاريخية ونظرية، وقد وجدت اهتمامًا متجددًا لإيجاد حلول تقريبية لمشاكل هائلة.
  • طرق التدرج الفرعي : طريقة تكرارية لوظائف Lipschitz المحلية الكبيرة باستخدام التدرجات المعممة . وفقًا لبوريس تي. بولياك، فإن طرق إسقاط التدرج الفرعي تشبه طرق التدرج المترافق.
  • طريقة حزمة النزول: طريقة تكرارية للمشاكل الصغيرة والمتوسطة الحجم مع وظائف Lipschitz المحلية، وخاصة لمشاكل التقليل المحدب (على غرار طرق التدرج المترافق).
  • طريقة القطع الناقص : طريقة تكرارية للمسائل الصغيرة ذات الدوال الهدفية شبه المحدبة ، وهي ذات أهمية نظرية كبيرة، وخاصة في تحديد تعقيد الوقت متعدد الحدود لبعض مسائل التحسين التوافقي. وهي تشبه طرق شبه نيوتن.
  • طريقة التدرج الشرطي (فرانك-وولف) لتقليل المشاكل ذات البنية الخاصة ذات القيود الخطية تقريبًا ، وخاصة مع شبكات المرور. بالنسبة للمشاكل العامة غير المقيدة، يتم تقليص هذه الطريقة إلى طريقة التدرج، والتي تعتبر قديمة (بالنسبة لجميع المشاكل تقريبًا).
  • طرق شبه نيوتن : طرق تكرارية للمشكلات المتوسطة والكبيرة (على سبيل المثال N<1000).
  • طريقة التقريب العشوائي للاضطراب المتزامن (SPSA) للتحسين العشوائي؛ تستخدم تقريب التدرج العشوائي (الفعال).
• الأساليب التي تقوم بتقييم قيم الدالة فقط: إذا كانت المشكلة قابلة للاشتقاق بشكل مستمر، فيمكن تقريب التدرجات باستخدام الفروق المحدودة، وفي هذه الحالة يمكن استخدام طريقة تعتمد على التدرج.
  • طرق الاستيفاء
  • طرق البحث عن الأنماط ، والتي لها خصائص تقارب أفضل من طريقة نيلدر-ميد (مع التبسيطات) ، والتي يتم سردها أدناه.
  • نزول المرآة

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

تتطلب المشكلات في ديناميكيات الأجسام الصلبة (وخاصة ديناميكيات الأجسام الصلبة المفصلية) غالبًا تقنيات برمجة رياضية، حيث يمكنك النظر إلى ديناميكيات الأجسام الصلبة على أنها محاولة لحل معادلة تفاضلية عادية على متعدد القيد؛ ^[11] القيود هي قيود هندسية غير خطية مختلفة مثل "يجب أن تتطابق هاتان النقطتان دائمًا"، "يجب ألا يخترق هذا السطح أي سطح آخر"، أو "يجب أن تقع هذه النقطة دائمًا في مكان ما على هذا المنحنى". أيضًا، يمكن حل مشكلة حساب قوى التلامس عن طريق حل مشكلة التكامل الخطي ، والتي يمكن أيضًا اعتبارها مشكلة برمجة تربيعية (QP).

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

يمكن تطبيق هذا النهج في علم الكون والفيزياء الفلكية. ^[12]

يرتبط الاقتصاد ارتباطًا وثيقًا بتحسين العوامل لدرجة أن التعريف المؤثر يصف الاقتصاد باعتباره علمًا بأنه "دراسة السلوك البشري كعلاقة بين الغايات والوسائل النادرة " مع استخدامات بديلة. ^[13] تتضمن نظرية التحسين الحديثة نظرية التحسين التقليدية ولكنها تتداخل أيضًا مع نظرية الألعاب ودراسة التوازنات الاقتصادية . تصنف أكواد مجلة الأدب الاقتصادي البرمجة الرياضية وتقنيات التحسين والموضوعات ذات الصلة تحت JEL: C61-C63 .

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

منذ سبعينيات القرن العشرين، قام خبراء الاقتصاد بوضع نماذج للقرارات الديناميكية على مر الزمن باستخدام نظرية التحكم . ^[14] على سبيل المثال، تُستخدم نماذج البحث الديناميكي لدراسة سلوك سوق العمل . ^[15] هناك تمييز حاسم بين النماذج الحتمية والعشوائية. ^[16] يبني خبراء الاقتصاد الكلي نماذج التوازن العام العشوائي الديناميكي (DSGE) التي تصف ديناميكيات الاقتصاد ككل كنتيجة لقرارات التحسين المترابطة للعمال والمستهلكين والمستثمرين والحكومات ^[17] . ^{[18] [19]}

تتضمن بعض التطبيقات الشائعة لتقنيات التحسين في الهندسة الكهربائية تصميم المرشح النشط ، ^[20] وتقليل المجال الضال في أنظمة تخزين الطاقة المغناطيسية الفائقة التوصيل، وتصميم رسم خرائط الفضاء لهياكل الموجات الدقيقة ، ^[21] وهوائيات الهاتف، ^{[22] [23] [24]} والتصميم القائم على الكهرومغناطيسية. وقد استخدم تحسين التصميم المعتمد كهرومغناطيسيًا لمكونات وهوائيات الموجات الدقيقة على نطاق واسع نموذجًا بديلًا قائمًا على الفيزياء أو تجريبيًا ومنهجيات رسم الخرائط الفضائية منذ اكتشاف رسم الخرائط الفضائية في عام 1993. ^{[25] [26]} تُستخدم تقنيات التحسين أيضًا في تحليل تدفق الطاقة . ^[27]

تم استخدام التحسين على نطاق واسع في الهندسة المدنية. تعد إدارة البناء وهندسة النقل من بين الفروع الرئيسية للهندسة المدنية التي تعتمد بشكل كبير على التحسين. أكثر مشاكل الهندسة المدنية شيوعًا التي يتم حلها عن طريق التحسين هي قطع الطرق وردمها، وتحليل دورة حياة الهياكل والبنية التحتية، ^[28] وتسوية الموارد ، ^{[29] [30]} وتخصيص موارد المياه ، وإدارة المرور ^[31] وتحسين الجدول الزمني.

مجال آخر يستخدم تقنيات التحسين على نطاق واسع هو بحوث العمليات . ^[32] يستخدم بحوث العمليات أيضًا النمذجة العشوائية والمحاكاة لدعم اتخاذ القرار المحسن. على نحو متزايد، يستخدم بحوث العمليات البرمجة العشوائية لنمذجة القرارات الديناميكية التي تتكيف مع الأحداث؛ يمكن حل مثل هذه المشكلات من خلال التحسين واسع النطاق وطرق التحسين العشوائية .

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

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

تُستخدم طرق التحسين غير الخطية على نطاق واسع في التحليل التكويني .

تُستخدم تقنيات التحسين في العديد من جوانب علم الأحياء للأنظمة الحاسوبية مثل بناء النماذج والتصميم التجريبي الأمثل والهندسة الأيضية والبيولوجيا الاصطناعية. ^{[33] وقد تم تطبيق} البرمجة الخطية لحساب أقصى إنتاج ممكن لمنتجات التخمير، ^[33] واستنتاج شبكات تنظيم الجينات من مجموعات بيانات متعددة من المصفوفات الدقيقة ^[34] بالإضافة إلى شبكات تنظيم النسخ من البيانات عالية الإنتاجية. ^{[35] وقد تم استخدام} البرمجة غير الخطية لتحليل عملية التمثيل الغذائي للطاقة ^[36] وتم تطبيقها على الهندسة الأيضية وتقدير المعلمات في المسارات الكيميائية الحيوية. ^[37]

• بويد، ستيفن ب .؛ فاندنبرغ، ليفين (2004). التحسين المحدب. كامبريدج: مطبعة جامعة كامبريدج. رقم ISBN 0-521-83378-7.
• جيل، بي إي؛ موراي، دبليو؛ رايت، إم إتش (1982). التحسين العملي . لندن: أكاديميك بريس. رقم ISBN 0-12-283952-8.
• لي، جون (2004). دورة أولى في التحسين التوافقي . مطبعة جامعة كامبريدج. رقم ISBN 0-521-01012-8.
• نوسيدال، جورج ؛ رايت، ستيفن جيه. (2006). التحسين العددي (الطبعة الثانية). برلين: سبرينغر. رقم ISBN 0-387-30303-0.

• "شجرة القرار لتحسين البرمجيات".روابط لمصادر أكواد التحسين
• "التحسين العالمي".
• "EE364a: Convex Optimization I" دورة من جامعة ستانفورد .
• فاروكو، جايل. "التحسين الرياضي: إيجاد الحد الأدنى للوظائف".