التحسين المحدب

يُعدّ التحسين المحدب فرعًا من فروع التحسين الرياضي ، ويتناول مسألة تصغير الدوال المحدبة على المجموعات المحدبة (أو، بصورة مكافئة، تعظيم الدوال المقعرة على المجموعات المحدبة). تُتيح العديد من فئات مسائل التحسين المحدب خوارزميات تعمل في زمن متعدد الحدود، ^{[ 1 ]} بينما يُصنّف التحسين الرياضي عمومًا ضمن المسائل الصعبة من نوع NP . ^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}

تعريف

الشكل المجرد

تُعرَّف مسألة التحسين المحدب بمكونين: ^{[ 5 ]}^{[ 6 ]}

دالة الهدف ، وهي دالة محدبة ذات قيم حقيقية لـ n متغيرًا، $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ ؛
المجموعة الممكنة ، وهي مجموعة جزئية محدبة $C\subseteq \mathbb {R} ^{n}$ .

الهدف من هذه المسألة هو إيجاد بعض $\mathbf {x^{\ast }} \in C$ تحقيق

\inf\{f(\mathbf {x} ):\mathbf {x} \in C\}

.

بشكل عام، هناك ثلاثة خيارات فيما يتعلق بوجود حل: ^{[ 7 ]}^{: الفصل 4}

إذا كانت هناك نقطة مثل x * ، فإنها تسمى نقطة أو حلًا مثاليًا ؛ وتسمى مجموعة جميع النقاط المثلى بالمجموعة المثلى ؛ وتسمى المشكلة قابلة للحل .
لو $f$ غير محدود من الأسفل إلى الأعلى $C$ أو إذا لم يتم الوصول إلى الحد الأدنى، فإن مسألة التحسين يقال إنها غير محدودة .
وإلا، إذا $C$ إذا كانت المجموعة فارغة، فإن المشكلة يقال إنها غير قابلة للحل .

النموذج القياسي

تكون مسألة التحسين المحدب في صورتها القياسية إذا كُتبت على النحو التالي:

{\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {x} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}

المكان: ^{[ 7 ]}^{: الفصل 4}

$\mathbf {x} \in \mathbb {R} ^{n}$ هو متجه متغيرات التحسين؛
دالة الهدف $f:{\mathcal {D}}\subseteq \mathbb {R} ^{n}\to \mathbb {R}$ هي دالة محدبة ؛
دوال قيد المتباينة $g_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ ، $i=1,\ldots ,m$ ، هي دوال محدبة؛
دوال قيد المساواة $h_{i}:\mathbb {R} ^{n}\to \mathbb {R}$ ، $i=1,\ldots ,p$ ، هي تحويلات خطية ، أي من الشكل التالي: $h_{i}(\mathbf {x} )=\mathbf {a_{i}} \cdot \mathbf {x} -b_{i}$ ، أين $\mathbf {a_{i}}$ هو متجه و $b_{i}$ هو كمية قياسية.

المجموعة الممكنة $C$ تتكون مسألة التحسين من جميع النقاط $\mathbf {x} \in {\mathcal {D}}$ تحقق هذه المجموعة قيود المتباينة والمساواة، وهي مجموعة محدبة لأن ${\mathcal {D}}$ إذا كانت محدبة، فإن مجموعات المستويات الفرعية للدوال المحدبة تكون محدبة، والمجموعات الأفينية تكون محدبة، وتقاطع المجموعات المحدبة يكون محدبًا. ^{[ 7 ]}^{: الفصل 2}

يمكن صياغة العديد من مسائل التحسين بشكل مكافئ في هذا الشكل القياسي. على سبيل المثال، مسألة تعظيم دالة مقعرة $f$ يمكن إعادة صياغة المسألة بشكل مكافئ على أنها مسألة تقليل الدالة المحدبة $-f$ تُعرف مسألة تعظيم دالة مقعرة على مجموعة محدبة باسم مسألة التحسين المحدب. ^{[ 8 ]}

شكل النقش (الشكل القياسي ذو الهدف الخطي)

في الصيغة القياسية، يمكن افتراض، دون فقدان للعمومية، أن دالة الهدف f هي دالة خطية . وذلك لأن أي برنامج ذي هدف عام يمكن تحويله إلى برنامج ذي هدف خطي بإضافة متغير واحد t وقيد واحد ، كما يلي: ^{[ 9 ]}^{: 1.4}

{\begin{aligned}&{\underset {\mathbf {x} ,t}{\operatorname {minimize} }}&&t\\&\operatorname {subject\ to} &&f(\mathbf {x} )-t\leq 0\\&&&g_{i}(\mathbf {x} )\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(\mathbf {x} )=0,\quad i=1,\dots ,p,\end{aligned}}

شكل مخروطي

يمكن تمثيل كل برنامج محدب في شكل مخروطي ، مما يعني تقليل دالة هدف خطية على تقاطع مستوى أفيني ومخروط محدب: ^{[ 9 ]}^{: 5.1}

{\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&c^{T}x\\&\operatorname {subject\ to} &&x\in (b+L)\cap K\end{aligned}}

حيث K مخروط محدب مغلق ذو رأس مدبب ، وL فضاء جزئي خطي من Rⁿ ^، وb متجه في Rⁿ ^. البرنامج الخطي في صورته القياسية هو الحالة الخاصة التي يكون فيها K هو الجزء غير السالب من ^Rⁿ .

إزالة قيود المساواة الخطية

من الممكن تحويل برنامج محدب في صورته القياسية إلى برنامج محدب بدون قيود مساواة. ^{[ 7 ]}^{: 132} لنرمز لقيد المساواة hᵢ ( x ) = 0 بالرمز _Ax = b ، حيث A لها n عمودًا. إذا كان Ax = b غير قابل للحل، فإن المسألة الأصلية غير قابلة للحل. وإلا، فلها حل x₀ _، ويمكن تمثيل مجموعة جميع الحلول بالصيغة: Fz + _x₀ ، حيث z ينتمي إلى Rᵏ ^، و k = n -rank( A )، و F مصفوفة من الرتبة n × k . بالتعويض عن x = Fz + x₀ في المسألة الأصلية، نحصل على _:

${\begin{aligned}&{\underset {\mathbf {x} }{\operatorname {minimize} }}&&f(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\\&\operatorname {subject\ to} &&g_{i}(\mathbf {F\mathbf {z} +\mathbf {x} _{0}} )\leq 0,\quad i=1,\dots ,m\\\end{aligned}}$

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

حالات خاصة

جميع فئات المسائل التالية هي مسائل تحسين محدبة، أو يمكن اختزالها إلى مسائل تحسين محدبة عبر تحويلات بسيطة: ^{[ 7 ]}^{: الفصل 4}^{[ 10 ]}

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

وتشمل الحالات الخاصة الأخرى ما يلي:

طريقة المربعات الصغرى
تصغير الدالة التربيعية مع قيود تربيعية محدبة
البرمجة الهندسية
تعظيم الإنتروبيا مع مراعاة القيود المناسبة.

ملكيات

فيما يلي بعض الخصائص المفيدة لمسائل التحسين المحدب: ^{[ 11 ]}^{[ 7 ]}^{: الفصل 4}

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

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

الخوارزميات

المسائل غير المقيدة والمسائل المقيدة بالمساواة

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

في فئة المسائل غير المقيدة (أو المقيدة بالمساواة)، أبسطها تلك التي يكون فيها الهدف تربيعيًا . بالنسبة لهذه المسائل، تكون شروط كاروش-كون-تاكر (اللازمة للأمثلية) خطية جميعها، لذا يمكن حلها تحليليًا. ^{[ 7 ]}^{: الفصل 11}

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

ومن الخوارزميات الفعالة الأخرى للتقليل غير المقيد خوارزمية التدرج الهبوطي (وهي حالة خاصة من خوارزمية الهبوط الأسرع ).

مشاكل عامة

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

يمكن أيضًا حل مسائل التحسين المحدب باستخدام الطرق المعاصرة التالية: ^{[ 12 ]}

طرق التجميع (وولف، ليمارشال، كيوييل)، و
طرق إسقاط التدرج الفرعي (بولياك)،
طرق النقطة الداخلية ، ^{[ 1 ]} التي تستخدم دوال الحاجز المتوافقة ذاتيًا ^{[ 13 ]} ودوال الحاجز المنتظمة ذاتيًا. ^{[ 14 ]}
أساليب القطع بالمسحاة
طريقة القطع الناقص
طريقة التدرج الفرعي
التدرجات الفرعية المزدوجة وطريقة الانجراف بالإضافة إلى العقوبة

تتميز طرق التدرج الفرعي بسهولة تطبيقها، ولذا فهي شائعة الاستخدام. ^{[ 15 ]} طرق التدرج الفرعي المزدوجة هي طرق تدرج فرعي تُطبق على مسألة مزدوجة . تشبه طريقة الانجراف مع العقوبة طريقة التدرج الفرعي المزدوجة، ولكنها تأخذ متوسطًا زمنيًا للمتغيرات الأولية.

مضاعفات لاغرانج

لنفترض مسألة تصغير محدبة معطاة في شكلها القياسي بواسطة دالة التكلفة $f(x)$ وقيود عدم المساواة $g_{i}(x)\leq 0$ ل $1\leq i\leq m$ ثم المجال ${\mathcal {X}}$ يكون:

{\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leq 0\right\}.

دالة لاغرانج للمسألة هي ^{[ 16 ]}

L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_{1}(x)+\cdots +\lambda _{m}g_{m}(x).

لكل نقطة $x$ في $X$ ذلك يقلل $f$ زيادة $X$ توجد أعداد حقيقية $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$ تُسمى هذه المضاعفات بمضاعفات لاغرانج ، والتي تحقق هذه الشروط في آن واحد:

$x$ يقلل $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ إجمالي $y\in X,$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geq 0,$ مع واحد على الأقل $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (تراخي تكميلي).

إذا وُجدت "نقطة ممكنة تمامًا"، أي نقطة $z$ مُرضٍ

g_{1}(z),\ldots ,g_{m}(z)<0,

عندئذٍ يمكن تعزيز البيان أعلاه ليشترط ما يلي: $\lambda _{0}=1$ .

وعلى العكس من ذلك، إذا كان بعض $x$ في $X$ يحقق (1)–(3) للكميات القياسية $\lambda _{0},\ldots ,\lambda _{m}$ مع $\lambda _{0}=1$ ثم $x$ من المؤكد أن ذلك سيقلل $f$ زيادة $X$ .

برمجة

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

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

فيما يلي جدولان. يعرض الأول أدوات النمذجة (مثل CVXPY و JuMP.jl)، بينما يعرض الثاني برامج الحل (مثل SCS و MOSEK). وهما ليسا شاملين بأي حال من الأحوال.


برنامج	لغة	وصف	FOSS ؟	المرجع.
CVX	MATLAB	تتكامل مع خوارزميات حل SeDuMi و SDPT3؛ مصممة للتعبير فقط عن مسائل التحسين المحدب.	نعم	^{[ 17 ]}
CVXPY	بايثون		نعم	^{[ 18 ]}
Convex.jl	جوليا	البرمجة المحدبة المنضبطة، تدعم العديد من الحلول.	نعم	^{[ 19 ]}
CVXR	R		نعم	^{[ 20 ]}
GAMS		نظام نمذجة لمسائل البرمجة الخطية وغير الخطية، والبرمجة الخطية/غير الخطية المختلطة، وبرمجة المخروط من الدرجة الثانية.	لا	^{[ 17 ]}
جلوبتي بولي	ماتلاب، أوكتاف	نظام نمذجة لتحسين متعدد الحدود.	نعم	^{[ 17 ]}
JuMP.jl	جوليا	يدعم العديد من خوارزميات الحل. كما يدعم التحسين الصحيح وغير الخطي، وبعض أنواع التحسين غير المحدب.	نعم	^{[ 21 ]}
روما		نظام نمذجة للتحسين القوي. يدعم التحسين القوي التوزيعي ومجموعات عدم اليقين .	نعم	^{[ 17 ]}
سوستول		نظام نمذجة لتحسين الدوال متعددة الحدود . يستخدم SDPT3 و SeDuMi. يتطلب Symbolic Computation Toolbox.	نعم	^{[ 17 ]}
SparsePOP		نظام نمذجة لتحسين متعدد الحدود. يستخدم حلول SDPA أو SeDuMi.	نعم	^{[ 17 ]}
يالميب	MATLAB، أوكتاف	يتكامل مع برامج حل CPLEX وGUROBI وMOSEK وSDPT3 وSEDUMI وCSDP وSDPA وPENNON؛ كما يدعم التحسين الصحيح وغير الخطي، وبعض أنواع التحسين غير المحدب. ويمكنه إجراء تحسين قوي مع وجود عدم يقين في قيود البرمجة الخطية/برمجة التربيعية المتدرجة/برمجة شبه محددة.	نعم	^{[ 17 ]}


برنامج	لغة	وصف	FOSS ؟	المرجع.
أهداف		يمكن إجراء تحسين قوي على البرمجة الخطية (باستخدام MOSEK لحل برمجة المخروط من الدرجة الثانية) والبرمجة الخطية المختلطة . حزمة نمذجة للبرمجة الخطية + البرمجة شبه المحددة، بالإضافة إلى إصدارات قوية.	لا	^{[ 17 ]}
مجمع		يدعم طرق البرمجة الخطية الأولية والثنائية، بالإضافة إلى البرمجة التربيعية المخروطية. يمكنه حل مسائل البرمجة الخطية، والبرمجة التربيعية، والبرمجة التربيعية المخروطية، ومسائل البرمجة الخطية المختلطة.	لا	^{[ 17 ]}
CSDP	ج	يدعم طرق البرمجة الخطية والبرمجة شبه المحددة (SDP) الأولية والثنائية. تتوفر واجهات برمجة تطبيقات لبرامج MATLAB و R وPython. يتوفر إصدار متوازي. حلّ SDP.	نعم	^{[ 17 ]}
CVXOPT	بايثون	يدعم طرق الثنائية الأولية لبرمجة الخطية + البرمجة التربيعية المخروطية + البرمجة شبه المحددة. يستخدم مقياس نيستروف-تود. يتكامل مع MOSEK وDSDP.	نعم	^{[ 17 ]}
موسك		يدعم طرق البرمجة الخطية + البرمجة التربيعية المخروطية.	لا	^{[ 17 ]}
سيدومي	MATLAB، Octave، المكسيك	يحلّ مسائل البرمجة الخطية + البرمجة التربيعية المتقاطعة + البرمجة شبه المحددة. يدعم طرق البرمجة الأولية الثنائية لمسائل البرمجة الخطية + البرمجة التربيعية المتقاطعة + البرمجة شبه المحددة.	نعم	^{[ 17 ]}
SDPA	لغة سي++	يحل مسائل البرمجة الخطية والبرمجة شبه المحددة. يدعم طرق البرمجة الخطية والبرمجة شبه المحددة الأولية. تتوفر إصدارات متوازية وإصدارات ذات دقة موسعة.	نعم	^{[ 17 ]}
SDPT3	MATLAB، Octave، المكسيك	يحلّ مسائل البرمجة الخطية + البرمجة التربيعية المتقاطعة + البرمجة شبه المحددة. يدعم طرق البرمجة الأولية الثنائية لمسائل البرمجة الخطية + البرمجة التربيعية المتقاطعة + البرمجة شبه المحددة.	نعم	^{[ 17 ]}
حزمة كونيك		يدعم هذا البرنامج أكوادًا عامة للبرمجة الخطية (LP) وبرمجة SOCP وبرمجة SDP. يستخدم أسلوب التجميع. كما يوفر دعمًا خاصًا لقيود SDP وSOCP.	نعم	^{[ 17 ]}
DSDP		يدعم رموز الأغراض العامة لـ LP + SDP. يستخدم طريقة النقطة الداخلية المزدوجة.	نعم	^{[ 17 ]}
لوكو		يدعم البرنامج رموزًا عامة الأغراض لـ SOCP، والتي يتعامل معها على أنها مشكلة برمجة غير خطية.	لا	^{[ 17 ]}
راية صغيرة		يدعم البرامج ذات الأغراض العامة. يستخدم طريقة لاغرانج المعززة، وخاصة للمسائل ذات قيود البرمجة شبه المحددة.	لا	^{[ 17 ]}
SDPLR		يدعم الرموز ذات الأغراض العامة. يستخدم تحليل الرتبة المنخفضة مع طريقة لاغرانج المعززة.	نعم	^{[ 17 ]}

التطبيقات

يمكن استخدام التحسين المحدب لنمذجة المشكلات في نطاق واسع من التخصصات، مثل أنظمة التحكم الآلي ، والتقدير ومعالجة الإشارات ، والاتصالات والشبكات، وتصميم الدوائر الإلكترونية ، ^{[ 7 ]}^{: 17} تحليل البيانات ونمذجتها، والتمويل ، والإحصاء ( التصميم التجريبي الأمثل )، ^{[ 22 ]} والتحسين الهيكلي ، حيث أثبت مفهوم التقريب كفاءته. ^{[ 7 ]}^{[ 23 ]} يمكن استخدام التحسين المحدب لنمذجة المشكلات في المجالات التالية:

تحسين المحفظة الاستثمارية . ^{[ 24 ]}
تحليل المخاطر في أسوأ الحالات. ^{[ 24 ]}
الإعلان الأمثل. ^{[ 24 ]}
تنوعات الانحدار الإحصائي (بما في ذلك التنظيم والانحدار الكمي ). ^{[ 24 ]}
ملاءمة النموذج ^{[ 24 ]} (وخاصة التصنيف متعدد الفئات ^{[ 25 ]} ).
تحسين توليد الكهرباء . ^{[ 25 ]}
التحسين التوافقي . ^{[ 25 ]}
النمذجة غير الاحتمالية للشك . ^{[ 26 ]}
تحديد الموقع باستخدام الإشارات اللاسلكية ^{[ 27 ]}

الإضافات

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

انظر أيضاً

ملحوظات

1 2 نيستيروف ونميروفسكي 1994
↑ مورتي، كاتا؛ كابادي، سانتوش (1987). "بعض مسائل NP-كاملة في البرمجة التربيعية وغير الخطية". البرمجة الرياضية . 39 (2): 117-129 . Bibcode : 1987MatPr..39..117M . doi : 10.1007/BF02592948 . hdl : 2027.42/6740 . S2CID 30500771 .
↑ Sahni, S. "المشاكل المتعلقة بالحسابات"، في مجلة SIAM للحوسبة، 3، 262-279، 1974.
↑ باردالوس، بانوس م.؛ فافاسيس، ستيفن أ. (1991). "البرمجة التربيعية ذات القيمة الذاتية السالبة هي مسألة صعبة من نوع NP" . مجلة التحسين العالمي . 1 : 15-22 . doi : 10.1007/BF00120662 .
^ هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1996). التحليل المحدب وخوارزميات التقليل: الأساسيات . سبرينغر. ص. 291. ردمك 9783540568506.
↑ بن تال، أهارون؛ نيميروفسكي، أركادي سيمينوفيتش (2001). محاضرات في التحسين المحدب الحديث: التحليل والخوارزميات والتطبيقات الهندسية . ص 335-336 . ISBN 9780898714913.
1 2 3 4 5 6 7 8 9 10 11 12 بويد، ستيفن؛ فاندنبيرغ، ليفين (2004). التحسين المحدب (ملف PDF) . مطبعة جامعة كامبريدج . ISBN 978-0-521-83378-3تم الاطلاع عليه بتاريخ 12 أبريل 2021 .
↑ "أنواع مسائل التحسين - التحسين المحدب" . 9 يناير 2011.
1 2 أركادي نيميروفسكي (2004). طرق الوقت متعدد الحدود للنقطة الداخلية في البرمجة المحدبة .
↑ أغراوال، أكشاي؛ فيرشويرين، روبن؛ دايموند، ستيفن؛ بويد، ستيفن (2018). "نظام إعادة كتابة لمسائل التحسين المحدب" (ملف PDF) . التحكم والقرار . 5 (1): 42-60 . arXiv : 1709.04494 . doi : 10.1080/23307706.2017.1397554 . S2CID 67856259 .
↑ روكافيلر، ر. تيريل (1993). "مضاعفات لاغرانج والأمثلية" (ملف PDF) . مجلة SIAM Review . 35 (2): 183-238 . Bibcode : 1993SIAMR..35..183R . CiteSeerX 10.1.1.161.7209 . doi : 10.1137/1035044 .
↑ للاطلاع على طرق تقليل المحدب، انظر المجلدات التي ألفها هيريارت-أوروتي وليمارشال (مجموعة) والكتب المدرسية التي ألفها روسزكزينسكي ، وبيرتسيكاس ، وبويد وفاندنبيرغ (نقطة داخلية).
↑ نيستيروف، يوري؛ أركادي، نيميروفسكي (1995). خوارزميات كثيرات الحدود ذات النقطة الداخلية في البرمجة المحدبة . جمعية الرياضيات الصناعية والتطبيقية. ISBN 978-0898715156.
↑ بينغ، جيمينغ؛ روس، كورنيليس؛ تيرلاكي، تاماس (2002). "الدوال ذاتية الانتظام واتجاهات بحث جديدة للتحسين الخطي وشبه المحدد". البرمجة الرياضية . 93 (1): 129-171 . doi : 10.1007/s101070200296 . ISSN 0025-5610 . S2CID 28882966 .
↑ "التحسين العددي" . سلسلة سبرينغر في بحوث العمليات والهندسة المالية . 2006. doi : 10.1007/978-0-387-40065-5 . ISBN 978-0-387-30303-1.
↑ بيفيس، برايان؛ دوبس، إيان م. (1990). "التحسين الساكن" . نظرية التحسين والاستقرار للتحليل الاقتصادي . نيويورك: مطبعة جامعة كامبريدج. ص 40. ISBN 0-521-33605-8.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 بورشرز ، برايان. "نظرة عامة على برامج التحسين المحدب" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 18 سبتمبر 2017. تم الاطلاع عليه بتاريخ 12 أبريل 2021 .
↑ "مرحباً بكم في CVXPY 1.1 — وثائق CVXPY 1.1.11" . www.cvxpy.org . تاريخ الاطلاع: 12 أبريل 2021 .
↑ أوديل، مادلين؛ موهان، كارانفير؛ زينغ، ديفيد؛ هونغ، جيني؛ دايموند، ستيفن؛ بويد، ستيفن (17-10-2014). "التحسين المحدب في جوليا". arXiv : 1410.4821 [ math.OC ].
↑ "التحسين المحدب المنضبط - CVXR" . www.cvxgrp.org . تم الاطلاع عليه بتاريخ 17-06-2021 .
↑ لوبين، مايلز؛ داوسون، أوسكار؛ دياس غارسيا، جواكيم؛ هوشيت، جوي؛ ليغات، بينوا؛ فيلما، خوان بابلو (2023). "JuMP 1.0: تحسينات حديثة على لغة نمذجة للتحسين الرياضي". الحوسبة والبرمجة الرياضية . 15 (3): 581-589 . arXiv : 2206.03866 . doi : 10.1007/s12532-023-00239-3 .
^ كريستنسن/كلاربرينغ، chpt. 4.
↑ شميت، إل إيه؛ فلوري، سي. 1980: التركيب الهيكلي من خلال الجمع بين مفاهيم التقريب والأساليب الثنائية . مجلة المعهد الأمريكي للملاحة الجوية والفضائية 18، 1252-1260
1 2 3 4 5 بويد، ستيفن؛ دايموند، ستيفن؛ تشانغ، جونزي؛ أغراوال، أكشاي. "تطبيقات التحسين المحدب" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 1 أكتوبر 2015. تم الاطلاع عليه بتاريخ 12 أبريل 2021 .
1 2 3 مالك، جيروم (28-09-2011). "التحسين المحدب: التطبيقات، والصيغ، والاسترخاء" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 12-04-2021 . تم الاطلاع عليه بتاريخ 12 أبريل 2021 .
↑ بن حاييم ي. وإليشاكوف إ.، النماذج المحدبة للشك في الميكانيكا التطبيقية، دار نشر إلسيفير للعلوم، أمستردام، 1990
↑ أحمد بازي ، وديرك تي إم سلوك، وليزا ميلهاك. "تقدير زاوية الوصول عبر الإنترنت في وجود اقتران متبادل". ورشة عمل معالجة الإشارات الإحصائية IEEE لعام 2016 (SSP). IEEE، 2016.

مراجع

بيرتسيكاس، ديمتري ب.؛ نيديتش، أنجيليا؛ أوزداغلار، أسومان (2003). التحليل المحدب والتحسين . بلمونت، ماساتشوستس: أثينا ساينتيفيك. ISBN 978-1-886529-45-8.
بيرتسيكاس، ديمتري ب. (2009). نظرية التحسين المحدب . بلمونت، ماساتشوستس: أثينا ساينتيفيك. ISBN 978-1-886529-31-1.
بيرتسيكاس، ديمتري ب. (2015). خوارزميات التحسين المحدب . بلمونت، ماساتشوستس: أثينا ساينتيفيك. ISBN 978-1-886529-28-1.
بورواين، جوناثان؛ لويس، أدريان (2000). التحليل المحدب والتحسين غير الخطي: النظرية والأمثلة، الطبعة الثانية (ملف PDF) . سبرينغر . تم الاطلاع عليه بتاريخ 12 أبريل 2021 .
كريستنسن، بيتر دبليو؛ أندرس كلاربرينغ (2008). مقدمة في التحسين الهيكلي . المجلد 153. سبرينغر ساينس آند بيزنس ميديا. ISBN 9781402086663.

هيريارت أوروتي، جان بابتيست، ولومارشال، كلود . (2004). أساسيات التحليل المحدب . برلين: سبرينغر.
هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1993). التحليل المحدب وخوارزميات التقليل، المجلد الأول: الأساسيات . Grundlehren der Mathematischen Wissenschaften [المبادئ الأساسية للعلوم الرياضية]. المجلد. 305. برلين: سبرينغر-فيرلاغ. ص الثامن عشر+417. رقم ISBN 978-3-540-56850-6MR 1261420 .
هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1993). التحليل المحدب وخوارزميات التقليل، المجلد الثاني: النظرية المتقدمة وطرق الحزمة . Grundlehren der Mathematischen Wissenschaften [المبادئ الأساسية للعلوم الرياضية]. المجلد. 306. برلين: سبرينغر-فيرلاغ. ص الثامن عشر+346. رقم ISBN 978-3-540-56852-0MR 1295240 .
كيوييل، كريستوف سي. (1985). طرق الانحدار للتحسين غير التفاضلي . سلسلة محاضرات في الرياضيات. نيويورك: سبرينغر-فيرلاغ. ISBN 978-3-540-15642-0.
ليمارشال، كلود (2001). "استرخاء لاغرانج". في مايكل جونغر ودينيس نادف (محرر). التحسين التوافقي الحسابي: أوراق من مدرسة الربيع التي عقدت في شلوس داغستوهل، 15-19 مايو 2000 . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 2241. برلين: سبرينغر-فيرلاغ. ص 112 – 156. دوى : 10.1007 / 3-540-45586-8_4 . رقم ISBN 978-3-540-42877-0MR 1900016 . S2CID 9048698 .
نيستيروف، يوري؛ نميروفسكي، أركادي (1994). طرق متعددة الحدود للنقطة الداخلية في البرمجة المحدبة . سيام.
نيستروف، يوري. (2004). محاضرات تمهيدية في التحسين المحدب ، دار نشر كلوير الأكاديمية
روكافيلر، آر تي (1970). التحليل المحدب . برينستون: مطبعة جامعة برينستون.

روسزينسكي، أندريه (2006). التحسين غير الخطي . مطبعة جامعة برينستون.
شميت، إل إيه؛ فلوري، سي. 1980: التركيب الهيكلي من خلال الجمع بين مفاهيم التقريب والأساليب الثنائية . مجلة المعهد الأمريكي للملاحة الجوية والفضائية 18، 1252-1260

روابط خارجية

EE364a: التحسين المحدب 1 و EE364b: التحسين المحدب 2 ، صفحات مقررات جامعة ستانفورد
6.253: التحليل المحدب والتحسين ، صفحة دورة MIT OCW الرئيسية
برايان بورشرز، نظرة عامة على برامج التحسين المحدب
كتاب التحسين المحدب من تأليف ليفين فاندنبيرغ وستيفن ب. بويد

[Nesterov_1994-1] 1 2 نيستيروف ونميروفسكي 1994

[2] مورتي، كاتا؛ كابادي، سانتوش (1987). "بعض مسائل NP-كاملة في البرمجة التربيعية وغير الخطية". البرمجة الرياضية . 39 (2): 117-129 . Bibcode : 1987MatPr..39..117M . doi : 10.1007/BF02592948 . hdl : 2027.42/6740 . S2CID 30500771 .

[3] Sahni, S. "المشاكل المتعلقة بالحسابات"، في مجلة SIAM للحوسبة، 3، 262-279، 1974.

[4] باردالوس، بانوس م.؛ فافاسيس، ستيفن أ. (1991). "البرمجة التربيعية ذات القيمة الذاتية السالبة هي مسألة صعبة من نوع NP" . مجلة التحسين العالمي . 1 : 15-22 . doi : 10.1007/BF00120662 .

[5] هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1996). التحليل المحدب وخوارزميات التقليل: الأساسيات . سبرينغر. ص. 291. ردمك 9783540568506.

[6] بن تال، أهارون؛ نيميروفسكي، أركادي سيمينوفيتش (2001). محاضرات في التحسين المحدب الحديث: التحليل والخوارزميات والتطبيقات الهندسية . ص 335-336 . ISBN 9780898714913.

[:2-7] 1 2 3 4 5 6 7 8 9 10 11 12 بويد، ستيفن؛ فاندنبيرغ، ليفين (2004). التحسين المحدب (ملف PDF) . مطبعة جامعة كامبريدج . ISBN 978-0-521-83378-3تم الاطلاع عليه بتاريخ 12 أبريل 2021 .

[8] "أنواع مسائل التحسين - التحسين المحدب" . 9 يناير 2011.

[:02-9] 1 2 أركادي نيميروفسكي (2004). طرق الوقت متعدد الحدود للنقطة الداخلية في البرمجة المحدبة .

[rewriting-10] أغراوال، أكشاي؛ فيرشويرين، روبن؛ دايموند، ستيفن؛ بويد، ستيفن (2018). "نظام إعادة كتابة لمسائل التحسين المحدب" (ملف PDF) . التحكم والقرار . 5 (1): 42-60 . arXiv : 1709.04494 . doi : 10.1080/23307706.2017.1397554 . S2CID 67856259 .

[rockafellar93-11] روكافيلر، ر. تيريل (1993). "مضاعفات لاغرانج والأمثلية" (ملف PDF) . مجلة SIAM Review . 35 (2): 183-238 . Bibcode : 1993SIAMR..35..183R . CiteSeerX 10.1.1.161.7209 . doi : 10.1137/1035044 .

[12] للاطلاع على طرق تقليل المحدب، انظر المجلدات التي ألفها هيريارت-أوروتي وليمارشال (مجموعة) والكتب المدرسية التي ألفها روسزكزينسكي ، وبيرتسيكاس ، وبويد وفاندنبيرغ (نقطة داخلية).

[13] نيستيروف، يوري؛ أركادي، نيميروفسكي (1995). خوارزميات كثيرات الحدود ذات النقطة الداخلية في البرمجة المحدبة . جمعية الرياضيات الصناعية والتطبيقية. ISBN 978-0898715156.

[PengRoos2002-14] بينغ، جيمينغ؛ روس، كورنيليس؛ تيرلاكي، تاماس (2002). "الدوال ذاتية الانتظام واتجاهات بحث جديدة للتحسين الخطي وشبه المحدد". البرمجة الرياضية . 93 (1): 129-171 . doi : 10.1007/s101070200296 . ISSN 0025-5610 . S2CID 28882966 .

[15] "التحسين العددي" . سلسلة سبرينغر في بحوث العمليات والهندسة المالية . 2006. doi : 10.1007/978-0-387-40065-5 . ISBN 978-0-387-30303-1.

[16] بيفيس، برايان؛ دوبس، إيان م. (1990). "التحسين الساكن" . نظرية التحسين والاستقرار للتحليل الاقتصادي . نيويورك: مطبعة جامعة كامبريدج. ص 40. ISBN 0-521-33605-8.

[:3-17] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 بورشرز ، برايان. "نظرة عامة على برامج التحسين المحدب" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 18 سبتمبر 2017. تم الاطلاع عليه بتاريخ 12 أبريل 2021 .

[18] "مرحباً بكم في CVXPY 1.1 — وثائق CVXPY 1.1.11" . www.cvxpy.org . تاريخ الاطلاع: 12 أبريل 2021 .

[19] أوديل، مادلين؛ موهان، كارانفير؛ زينغ، ديفيد؛ هونغ، جيني؛ دايموند، ستيفن؛ بويد، ستيفن (17-10-2014). "التحسين المحدب في جوليا". arXiv : 1410.4821 [ math.OC ].

[20] "التحسين المحدب المنضبط - CVXR" . www.cvxgrp.org . تم الاطلاع عليه بتاريخ 17-06-2021 .

[21] لوبين، مايلز؛ داوسون، أوسكار؛ دياس غارسيا، جواكيم؛ هوشيت، جوي؛ ليغات، بينوا؛ فيلما، خوان بابلو (2023). "JuMP 1.0: تحسينات حديثة على لغة نمذجة للتحسين الرياضي". الحوسبة والبرمجة الرياضية . 15 (3): 581-589 . arXiv : 2206.03866 . doi : 10.1007/s12532-023-00239-3 .

[22] كريستنسن/كلاربرينغ، chpt. 4.

[23] شميت، إل إيه؛ فلوري، سي. 1980: التركيب الهيكلي من خلال الجمع بين مفاهيم التقريب والأساليب الثنائية . مجلة المعهد الأمريكي للملاحة الجوية والفضائية 18، 1252-1260

[:0-24] 1 2 3 4 5 بويد، ستيفن؛ دايموند، ستيفن؛ تشانغ، جونزي؛ أغراوال، أكشاي. "تطبيقات التحسين المحدب" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 1 أكتوبر 2015. تم الاطلاع عليه بتاريخ 12 أبريل 2021 .

[:1-25] 1 2 3 مالك، جيروم (28-09-2011). "التحسين المحدب: التطبيقات، والصيغ، والاسترخاء" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 12-04-2021 . تم الاطلاع عليه بتاريخ 12 أبريل 2021 .

[26] بن حاييم ي. وإليشاكوف إ.، النماذج المحدبة للشك في الميكانيكا التطبيقية، دار نشر إلسيفير للعلوم، أمستردام، 1990

[27] أحمد بازي ، وديرك تي إم سلوك، وليزا ميلهاك. "تقدير زاوية الوصول عبر الإنترنت في وجود اقتران متبادل". ورشة عمل معالجة الإشارات الإحصائية IEEE لعام 2016 (SSP). IEEE، 2016.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 26 ]

[ 27 ]