البرمجة الهندسية

البرنامج الهندسي ( GP ) هو مسألة تحسين من الشكل التالي:

${\displaystyle {\begin{array}{ll}{\mbox{minimize}}&f_{0}(x)\\{\mbox{subject to}}&f_{i}(x)\leq 1,\quad i=1,\ldots ,m\\&g_{i}(x)=1,\quad i=1,\ldots ,p,\end{array}}}$

أين${\displaystyle f_{0},\dots ,f_{m}}$هي أسماء متعددة و${\displaystyle g_{1},\dots ,g_{p}}$هي أحاديات الحد. في سياق البرمجة الهندسية (على عكس الرياضيات القياسية)، أحاديات الحد هي دالة من${\displaystyle \mathbb {R} _{++}^{n}}$ل${\displaystyle \mathbb {R} }$يُعرَّف بأنه

${\displaystyle x\mapsto cx_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{n}^{a_{n}}}$

أين${\displaystyle c>0\ }$و${\displaystyle a_{i}\in \mathbb {R} }$المضاعف الإيجابي هو أي مجموع من أحاديات الحدود. ^{[ 1 ] [ 2 ]}

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

لا تُعدّ البرامج الهندسية عمومًا مسائل تحسين محدبة، ولكن يمكن تحويلها إلى مسائل محدبة عن طريق تغيير المتغيرات وتحويل دالتي الهدف والقيود. على وجه الخصوص، بعد إجراء تغيير المتغيرات${\displaystyle y_{i}=\log(x_{i})}$وبأخذ اللوغاريتم الطبيعي لدالة الهدف ودالة القيود، تصبح الدوال${\displaystyle f_{i}}$أي أن الدوال ذات الحدود الموجبة تُحوّل إلى دوال لوغاريتمية مجموعية أسية ، وهي دوال محدبة، والدوال${\displaystyle g_{i}}$أي أن أحاديات الحدود تصبح خطية . وبالتالي، يحوّل هذا التحويل كل برنامج هندسي إلى برنامج محدب مكافئ. ^{[ 2 ]} في الواقع، يمكن استخدام هذا التحويل اللوغاريتمي-اللوغاريتمي لتحويل فئة أكبر من المسائل، تُعرف باسم البرمجة المحدبة اللوغاريتمية-اللوغاريتمية (LLCP)، إلى شكل محدب مكافئ. ^{[ 7 ]}

توجد العديد من حزم البرامج للمساعدة في صياغة وحل البرامج الهندسية.

• MOSEK هو برنامج تجاري قادر على حل البرامج الهندسية بالإضافة إلى مشاكل التحسين غير الخطية الأخرى.
• CVXOPT هو برنامج مفتوح المصدر لحل مسائل التحسين المحدب.
• GPkit هي حزمة بايثون تُستخدم لتعريف نماذج البرمجة الهندسية ومعالجتها بسهولة. تجد هنا عددًا من نماذج البرمجة الهندسية النموذجية المكتوبة باستخدام هذه الحزمة .
• GGPLAB عبارة عن مجموعة أدوات MATLAB لتحديد وحل البرامج الهندسية (GPs) والبرامج الهندسية المعممة (GGPs).
• CVXPY هي لغة نمذجة مضمنة في بايثون لتحديد وحل مسائل التحسين المحدب، بما في ذلك GPs وGGPs وLLCPs. ^{[ 7 ]}

• إشارة
• كلارنس زينر