مشكلة التكامل الخطي

الموسوعة الحرة

في نظرية التحسين الرياضي ، تظهر مسألة التكامل الخطي (LCP) بشكل متكرر في الميكانيكا الحسابية ، وتشمل البرمجة التربيعية المعروفة كحالة خاصة. وقد اقترحها كوتل ودانتزيج في  عام 1968. [ 1 ] [ 2 ] [ 3 ]

التركيبة

بالنظر إلى مصفوفة حقيقية M ومتجه q ، فإن مسألة التكامل الخطي LCP( q , M ) تبحث عن المتجهين z و w اللذين يحققان القيود التالية:

  • w،z⩾0،{\displaystyle w,z\geqslant 0,}(أي أن كل مكون من مكونات هذين المتجهين غير سالب )
  • zتيw=0{\displaystyle z^{T}w=0}أو ما يعادل ذلك∑أناwأناzأنا=0.{\displaystyle \sum \nolimits _{i}w_{i}z_{i}=0.}هذا هو شرط التكامل ، لأنه يعني أنه، بالنسبة لجميعأنا{\displaystyle i}، على الأكثر واحد منwأنا{\displaystyle w_{i}}وzأنا{\displaystyle z_{i}}قد يكون إيجابياً.
  • w=مz+q{\displaystyle w=Mz+q}

الشرط الكافي لوجود حل فريد لهذه المسألة هو أن تكون المصفوفة M متناظرة وموجبة التحديد . إذا كانت M بحيث يكون للمسألة LCP( q , M ) حل لكل قيمة q ، فإن M تكون مصفوفة Q. وإذا كانت M بحيث يكون للمسألة LCP( q , M ) حل وحيد لكل قيمة q ، فإن M تكون مصفوفة P. كلا هذين الشرطين كافيان وضروريان. [ 4 ]

المتجه w هو متغير فائض ، [ 5 ] ولذلك يتم تجاهله عمومًا بعد إيجاد z . وبناءً على ذلك، يمكن صياغة المسألة أيضًا على النحو التالي:

  • مz+q⩾0{\displaystyle Mz+q\geqslant 0}
  • z⩾0{\displaystyle z\geqslant 0}
  • zتي(مz+q)=0{\displaystyle z^{\mathrm {T} }(Mz+q)=0}(شرط التكامل)

تصغير الدالة التربيعية المحدبة: الشروط الدنيا

يرتبط إيجاد حل لمسألة التكامل الخطي بتقليل الدالة التربيعية

و(z)=zتي(مz+q){\displaystyle f(z)=z^{T}(Mz+q)}

رهناً بالقيود

مz+q⩾0{\displaystyle {Mz}+q\geqslant 0}
z⩾0{\displaystyle z\geqslant 0}

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

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

كذلك، تُصاغ مسألة البرمجة التربيعية على النحو التالي: تقليلو(x)=جتيx+12xتيسؤالx{\displaystyle f(x)=c^{T}x+{\tfrac {1}{2}}x^{T}Qx}رهناً بـأx⩾ب{\displaystyle Ax\geqslant b}إلى جانبx⩾0{\displaystyle x\geqslant 0}مع Q متناظر

وهو ما يعادل حل مسألة البرمجة الخطية باستخدام

q=[ج-ب]،م=[سؤال-أتيأ0]{\displaystyle q={\begin{bmatrix}c\\-b\end{bmatrix}},\qquad M={\begin{bmatrix}Q&-A^{T}\\A&0\end{bmatrix}}}

وذلك لأن شروط كاروش-كون-تاكر لمسألة البرمجة التربيعية يمكن كتابتها على النحو التالي:

{v=سؤالx-أتيλ+جs=أx-بx،λ،v،s⩾0xتيv+λتيs=0{\displaystyle {\begin{cases}v=Qx-A^{T}{\lambda }+c\\s=Ax-b\\x,{\lambda },v,s\geqslant 0\\x^{T}v+{\lambda }^{T}s=0\end{cases}}}

حيث تمثل v معاملات لاغرانج لقيود عدم السلبية، وλ معاملات قيود المتباينة، و s متغيرات الركود لقيود المتباينة. وينشأ الشرط الرابع من تكامل كل مجموعة من المتغيرات ( x , s ) مع مجموعة متجهات KKT الخاصة بها (معاملات لاغرانج المثلى) وهي ( v , λ ) . في هذه الحالة،

z=[xλ]،w=[vs]{\displaystyle z={\begin{bmatrix}x\\\lambda \end{bmatrix}},\qquad w={\begin{bmatrix}v\\s\end{bmatrix}}}

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

سؤالx=أتيλ-ج{\displaystyle Qx=A^{T}{\lambda }-c}

أو:

x=سؤال-1(أتيλ-ج){\displaystyle x=Q^{-1}(A^{T}{\lambda }-c)}

بضرب طرفي المعادلة في A من اليسار وطرح b نحصل على:

أx-ب=أسؤال-1(أتيλ-ج)-ب{\displaystyle Ax-b=AQ^{-1}(A^{T}{\lambda }-c)-b\,}

الجانب الأيسر، بسبب شرط كاروش-كون-تاكر الثاني، هو s . بالتعويض وإعادة الترتيب:

s=(أسؤال-1أتي)λ+(-أسؤال-1ج-ب){\displaystyle s=(AQ^{-1}A^{T}){\lambda }+(-AQ^{-1}c-b)\,}

اتصل الآن

م:=(أسؤال-1أتي)q:=(-أسؤال-1ج-ب){\displaystyle {\begin{aligned}M&:=(AQ^{-1}A^{T})\\q&:=(-AQ^{-1}c-b)\end{aligned}}}

لدينا مسألة تكامل خطي (LCP) بسبب علاقة التكامل بين متغيرات الركود s ومعاملات لاغرانج الخاصة بها λ . بمجرد حلها، يمكننا الحصول على قيمة x من λ من خلال شرط كاروش-كون-تاكر الأول.

وأخيرًا، من الممكن أيضًا التعامل مع قيود المساواة الإضافية:

أهـqx=بهـq{\displaystyle A_{eq}x=b_{eq}}

يُدخل هذا متجهًا من مُضاعفات لاغرانج μ ، بنفس بُعدبهـq{\displaystyle b_{eq}}.

من السهل التحقق من أن قيمتي M و Q لنظام LCPs=مλ+سؤال{\displaystyle s=M{\lambda }+Q}يتم التعبير عنها الآن على النحو التالي:

م:=[أ0][سؤالأهـqتي-أهـq0]-1[أتي0]q:=-[أ0][سؤالأهـqتي-أهـq0]-1[جبهـq]-ب{\displaystyle {\begin{aligned}M&:={\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\\0\end{bmatrix}}\\q&:=-{\begin{bmatrix}A&0\end{bmatrix}}{\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}c\\b_{eq}\end{bmatrix}}-b\end{aligned}}}

من λ يمكننا الآن استعادة قيم كل من x ومضاعف لاغرانج للمعادلات μ :

[xμ]=[سؤالأهـqتي-أهـq0]-1[أتيλ-ج-بهـq]{\displaystyle {\begin{bmatrix}x\\\mu \end{bmatrix}}={\begin{bmatrix}Q&A_{eq}^{T}\\-A_{eq}&0\end{bmatrix}}^{-1}{\begin{bmatrix}A^{T}\lambda -c\\-b_{eq}\end{bmatrix}}}

في الواقع، تعتمد معظم برامج حل مسائل البرمجة التربيعية على صياغة مسألة التكامل الخطي، بما في ذلك طريقة النقطة الداخلية ، وطريقة التمحور الرئيسي/التكاملي، وطرق المجموعة الفعالة . [ 1 ] [ 2 ] يمكن أيضًا حل مسائل التكامل الخطي باستخدام خوارزمية التقاطع ، [ 6 ] [ 7 ] [ 8 ] [ 9 ] وعلى العكس، بالنسبة لمسائل التكامل الخطي، تتوقف خوارزمية التقاطع بشكل نهائي فقط إذا كانت المصفوفة مصفوفة كافية. [ 8 ] [ 9 ] المصفوفة الكافية هي تعميم لكل من المصفوفة الموجبة المحددة ومصفوفة P ، حيث تكون المحددات الرئيسية لكل منها موجبة. [ 8 ] [ 9 ] [ 10 ] يمكن حل مسائل التكامل الخطي هذه عند صياغتها بشكل مجرد باستخدام نظرية المصفوفات الموجهة . [ 11 ] [ 12 ] [ 13 ]

انظر أيضاً

ملحوظات

مراجع

للمزيد من القراءة

  • LCPSolve — إجراء بسيط في GAUSS لحل مسألة التكامل الخطي
  • Siconos /Numerics تطبيق مفتوح المصدر مرخص بموجب رخصة GPL بلغة C لخوارزمية ليمكي وطرق أخرى لحل مسائل LCP وMLCP.