طريقة النقطة الداخلية

مثال على البحث عن حل. الخطوط الزرقاء توضح القيود، والنقاط الحمراء توضح الحلول المتكررة.

تُعدّ طرق النقاط الداخلية (المعروفة أيضًا باسم طرق الحاجز أو IPMs ) خوارزميات لحل مسائل التحسين المحدب الخطية وغير الخطية . وتجمع طرق النقاط الداخلية بين ميزتين من الخوارزميات المعروفة سابقًا:

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

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

تاريخ

اكتشف عالم الرياضيات السوفيتي إيل ديكين طريقة النقطة الداخلية في عام 1967. ^{[ 1 ]} أُعيد ابتكار هذه الطريقة في الولايات المتحدة في منتصف الثمانينيات. في عام 1984، طور ناريندرا كارماركار طريقة للبرمجة الخطية تسمى خوارزمية كارماركار ، ^{[ 2 ]} والتي تعمل في وقت متعدد الحدود ( $O(n^{3.5}L)$ تُجري هذه الطريقة عمليات على أعداد مكونة من L بت، حيث n هو عدد المتغيرات والثوابت، وهي فعالة للغاية عمليًا. وقد أثارت ورقة كارماركار اهتمامًا كبيرًا بطرق النقطة الداخلية. وبعد عامين، ابتكر جيمس رينيغار أول طريقة لتتبع المسار باستخدام النقطة الداخلية، مع وقت تشغيل $O(n^{3}L)$ . تم توسيع هذه الطريقة لاحقًا من مسائل التحسين الخطي إلى مسائل التحسين المحدب، استنادًا إلى دالة حاجز متوافقة ذاتيًا تُستخدم لترميز المجموعة المحدبة . ^[³^]

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

ابتكر يوري نيستيروف وأركادي نيميروفسكي فئة خاصة من هذه الحواجز التي يمكن استخدامها لترميز أي مجموعة محدبة. ويضمنان أن عدد تكرارات الخوارزمية محدود بدالة متعددة الحدود في بُعد ودقة الحل. ^{[ 5 ]}^{[ 3 ]}

تُعتبر فئة طرق تتبع المسار الثنائي الأولي ذات النقطة الداخلية الأكثر نجاحًا. وتُشكل خوارزمية ميهروترا للتنبؤ والتصحيح الأساس لمعظم تطبيقات هذه الفئة من الطرق. ^{[ 6 ]}

التعريفات

لدينا برنامج محدب على الشكل التالي: ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{تقليل}}}\quad &f(x)\\{\text{بشرط}}\quad &x\in G.\end{aligned}}$ حيث f دالة محدبة وG مجموعة محدبة . وبدون فقدان للعمومية، يمكننا افتراض أن دالة الهدف f دالة خطية . عادةً، تُمثَّل المجموعة المحدبة G بمجموعة من المتباينات المحدبة والمعادلات الخطية؛ ويمكن حذف المعادلات الخطية باستخدام الجبر الخطي ، لذا، ولتبسيط الأمر، نفترض وجود متباينات محدبة فقط، ويمكن وصف البرنامج كما يلي، حيث gᵢ _دوال محدبة: ${\begin{aligned}{\underset {x\in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(x)\\{\text{subject to}}\quad &g_{i}(x)\leq 0{\text{ for }}i=1,\dots ,m.\\\end{aligned}}$ نفترض أن دوال القيد تنتمي إلى عائلة معينة (مثل الدوال التربيعية)، بحيث يمكن تمثيل البرنامج بمتجه معاملات محدود (مثل معاملات الدوال التربيعية). يُسمى بُعد متجه المعاملات هذا بحجم البرنامج . المُحلِّل العددي لعائلة معينة من البرامج هو خوارزمية تُولِّد، عند إعطائها متجه المعاملات، سلسلة من الحلول التقريبية x _t لـ t = 1, 2, ...، باستخدام عدد محدود من العمليات الحسابية. يُسمى المُحلِّل العددي متقاربًا إذا كان، لأي برنامج من العائلة وأي قيمة موجبة ε > 0، توجد قيمة T (التي قد تعتمد على البرنامج وعلى ε ) بحيث يكون الحل التقريبي x _t ، لأي t > T ، تقريبيًا من ε، أي: ${\begin{aligned}&f(x_{t})-f^{*}\leq \epsilon ,\\&g_{i}(x_{t})\leq \epsilon \quad {\text{for}}\quad i=1,\dots ,m,\\&x\in G,\end{aligned}}$ أين $f^{*}$ هو الحل الأمثل. يُطلق على برنامج الحل اسم متعدد الحدود إذا كان إجمالي عدد العمليات الحسابية في أول T خطوة على الأكثر

poly(problem-size) * log( V / ε ),

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

الأنواع

تشمل أنواع طرق النقاط الداخلية ما يلي:

طرق الاختزال المحتملة : كانت خوارزمية كارماركار هي الأولى.
أساليب تتبع المسار : كانت خوارزميات جيمس رينيغار ^{[ 7 ]} وكلوفيس غونزاغا ^{[ 8 ]} هي الأولى.
الأساليب الثنائية الأولية .

أساليب تتبع المسار

فكرة

بفرض وجود برنامج تحسين محدب (P) مع قيود، يمكننا تحويله إلى برنامج غير مقيد بإضافة دالة حاجز . تحديدًا، لنفترض أن b دالة محدبة سلسة، معرفة داخل المنطقة الممكنة G ، بحيث يكون لأي متتالية $\{x_{j}\in {\textbf {G}}\}$ التي تقع نهايتها على حدود G : $\lim _{j\to \infty }b(x_{j})=\infty$ نفترض أيضاً أن b غير منحل، أي: $b''(x)$ تكون موجبة تمامًا لجميع قيم x في داخل (G). الآن، لننظر إلى عائلة البرامج: $P_{t}=t\cdot f(x)+b(x)$

من الناحية التقنية، يُعتبر البرنامج مقيدًا، لأن b مُعرّفة فقط داخل G. ولكن عمليًا، يُمكن حله كبرنامج غير مقيد، لأن أي خوارزمية تحاول تقليل الدالة لن تقترب من الحد الذي تقترب فيه b من اللانهاية. لذلك، فإن ( P( _t )) له حل وحيد - نرمز له بـ x *( t ). الدالة x * دالة متصلة لـ t ، وتُسمى المسار المركزي . جميع نقاط النهاية لـ x *، عندما تقترب t من اللانهاية، هي حلول مثلى للبرنامج الأصلي (P).

طريقة تتبع المسار هي طريقة لتتبع الدالة x * على طول متتالية متزايدة معينة _t1 , t2 _, ...، أي: حساب تقريب جيد بما فيه الكفاية xᵢ للنقطة x*(tᵢ)، بحيث يقترب الفرق xᵢ - x * ( tᵢ ) _من الصفر عندما يقترب i _من اللانهاية ؛ _عندئذٍ_تقترب المتتالية xᵢ من _الحل الأمثل للمسألة (P). يتطلب هذا تحديد ثلاثة أمور:

دالة الحاجز b(x).
سياسة لتحديد معايير العقوبة t _i .
يُستخدم مُحلِّل التحسين غير المقيد لحل ( P _i ) وإيجاد x _i ، مثل طريقة نيوتن . لاحظ أنه يمكننا استخدام كل x _i كنقطة بداية لحل المسألة التالية ( P _i+1 ).

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

أثبت كل من رينيجار ^{[ 7 ]} وجونزاجا ^{[ 8 ]} أن حالة محددة من طريقة تتبع المسار هي متعددة الوقت:

القيود (والهدف) عبارة عن دوال خطية؛
دالة الحاجز لوغاريتمية : $b(x)=-\sum _{j=1}^{m}\log({-g_{j}(x)})$
يتم تحديث معامل الجزاء t هندسيًا، أي $t_{i+1}:=\mu \cdot t_{i}$ حيث μ ثابت (أخذوا $\mu =1+0.001\cdot {\sqrt {m}}$ (حيث m هو عدد قيود عدم المساواة)؛
تعتمد طريقة الحل على طريقة نيوتن، ويتم تنفيذ خطوة واحدة من طريقة نيوتن لكل خطوة في t .

لقد أثبتوا أنه في هذه الحالة ، يظل الفرق xᵢ _- x *( tᵢ ₎ على الأكثر 0.01، ويكون f( xᵢ ₎ - f* على الأكثر ${\frac {2m}{t_{j}}}$ وبالتالي، فإن دقة الحل تتناسب طرديًا مع ${\frac {1}{t_{j}}}$ لذا، لإضافة رقم دقة واحد، يكفي ضرب t _i في 2 (أو أي عامل ثابت آخر)، وهو ما يتطلب $O({\sqrt {m}})$ ^{خطوات نيوتن. بما أن كل خطوة من خطوات}^نيوتن تستغرق O( mn² ) عملية، فإن التعقيد الكلي هو O( m³ ^/ 2n² ) عملية لرقم الدقة.

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

تفاصيل

لدينا مسألة تحسين محدبة (P) في "الصيغة القياسية":

تقليل c ^Tx st x في G ،

حيث G محدبة ومغلقة. يمكننا أيضًا افتراض أن G محدودة (يمكننا بسهولة جعلها محدودة بإضافة قيد | x | ≤ R لبعض قيم R الكبيرة بما فيه الكفاية ). ^{[ 3 ]}^{: القسم 4}

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

لكل t > 0، نُعرّف دالة الهدف المُعاقَبة f ( _t ) := t c ^Tx + b( x ) . ونُعرّف مسار القيم المُصغِّرة كما يلي: x*(t) := arg min f ₍ t) _. ونُقرِّب هذا المسار على طول متتالية متزايدة tᵢ . تُهيَّأ المتتالية بإجراء تهيئة ثنائي المراحل غير بديهي. ثم تُحدَّث وفقًا للقاعدة التالية: $t_{i+1}:=\mu \cdot t_{i}$ .

لكل قيمة _tᵢ ، نجد قيمة دنيا تقريبية للدالة fᵢ _، ونرمز لها بـ xᵢ _. يتم اختيار القيمة الدنيا التقريبية بحيث تحقق "شرط التقارب" التالي (حيث L هو مدى تحمل المسار ):

${\sqrt {[\nabla _{x}f_{t}(x_{i})]^{T}[\nabla _{x}^{2}f_{t}(x_{i})]^{-1}[\nabla _{x}f_{t}(x_{i})]}}\leq L$ .

لإيجاد xᵢ₊₁ _، نبدأ بـ xᵢ _ونطبق طريقة نيوتن المُخمدة . نُطبق عدة خطوات من هذه الطريقة حتى تتحقق ^"_{علاقة التقارب" المذكورة أعلاه. يُرمز إلى} أول نقطة تُحقق هذه العلاقة بـ xᵢ₊₁ _.^[³^] : ^القسم₄

التقارب والتعقيد

يُعطى معدل تقارب الطريقة بالصيغة التالية، لكل i : ^{[ 3 ]}^{: Prop.4.4.1}

$c^{T}x_{i}-c^{*}\leq {\frac {2M}{t_{0}}}\mu ^{-i}$

أخذ $\mu =\left(1+r/{\sqrt {M}}\right)$ عدد خطوات نيوتن اللازمة للانتقال من _xᵢ إلى xᵢ + ₁_هو عدد ثابت على الأكثر، يعتمد فقط على r و L. وبالتحديد، ^فإن العدد الإجمالي لخطوات نيوتن اللازمة لإيجاد حل تقريبي من النوع ε (أي إيجاد x في G بحيث يكون cᵀx - c* ≤ ε ) هو على الأكثر: ^[³^]^:^{نظرية 4.4.1}

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{t_{0}\varepsilon }}+1\right)$

حيث يعتمد العامل الثابت O(1) فقط على r و L. عدد خطوات نيوتن المطلوبة لإجراء التهيئة ذي الخطوتين هو على الأكثر: ^{[ 3 ]}^{: نظرية 4.5.1}

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M}{1-\pi _{x_{f}^{*}}({\bar {x}})}}+1\right)+O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {M{\text{Var}}_{G}(c)}{\epsilon }}+1\right)$

حيث يعتمد العامل الثابت O(1) فقط على r و L ، و ${\text{Var}}_{G}(c):=\max _{x\in G}c^{T}x-\min _{x\in G}c^{T}x$ ، و ${\bar {x}}$ تقع نقطة ما داخل G. إجمالاً، فإن التعقيد النيوتني الإجمالي لإيجاد حل تقريبي من نوع ε هو على الأكثر

$O(1)\cdot {\sqrt {M}}\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)$ ، حيث V ثابت يعتمد على المسألة: $V={\frac {{\text{Var}}_{G}(c)}{1-\pi _{x_{f}^{*}({\bar {x}})}}}$ .

^{تستغرق كل خطوة من} خطوات نيوتن O( n³ ) من العمليات الحسابية.

التهيئة: أساليب المرحلة الأولى

لتهيئة طرق تتبع المسار، نحتاج إلى نقطة في الجزء الداخلي النسبي للمنطقة الممكنة G. بعبارة أخرى: إذا كانت G مُعرَّفة بالمتباينات g _i ( x ) ≤ 0، فنحن بحاجة إلى قيمة x تحقق g _i ( x ) < 0 لجميع قيم i في 1، ...، m . إذا لم تتوفر لدينا مثل هذه النقطة، فنحن بحاجة إلى إيجادها باستخدام ما يُسمى بطريقة المرحلة الأولى . ^{[ 4 ]}^{: 11.4} تتمثل إحدى طرق المرحلة الأولى البسيطة في حل البرنامج المحدب التالي: ${\begin{aligned}{\text{تقليل}}\quad &s\\{\text{رهناً بـ}}\quad &g_{i}(x)\leq s{\text{ لـ }}i=1,\dots ,m\end{aligned}}$ لنرمز إلى الحل الأمثل بـ x*، s *.

إذا كان s *<0، فإننا نعلم أن x* هي نقطة داخلية للمشكلة الأصلية ويمكننا الانتقال إلى "المرحلة الثانية"، وهي حل المشكلة الأصلية.
إذا كانت s *>0، فإننا نعلم أن البرنامج الأصلي غير قابل للتنفيذ - المنطقة الممكنة فارغة.
إذا كانت s *=0 وتم الوصول إليها بواسطة حل ما x*، فإن المشكلة قابلة للحل ولكن ليس لها نقطة داخلية؛ إذا لم يتم الوصول إليها، فإن المشكلة غير قابلة للحل.

_{في هذا البرنامج ،} من السهل إيجاد نقطة داخلية: يمكننا اختيار x = 0 بشكل عشوائي، واختيار s أي عدد أكبر من max( f1 (0), ..., fm (0)). بالتالي _، يمكن حله باستخدام طرق النقطة الداخلية. مع ذلك، يتناسب زمن التشغيل طرديًا مع log(1/ s *). كلما اقتربت قيمة s* من الصفر، يصبح إيجاد حل دقيق لمسألة المرحلة الأولى أكثر صعوبة، وبالتالي يصبح من الصعب تحديد ما إذا كانت المسألة الأصلية قابلة للحل.

الاعتبارات العملية

تفترض الضمانات النظرية أن معامل الجزاء يزداد بمعدل $\mu =\left(1+r/{\sqrt {M}}\right)$ وبالتالي، فإن أسوأ عدد من خطوات نيوتن المطلوبة هو $O({\sqrt {M}})$ نظريًا، إذا كانت قيمة μ أكبر (مثلًا 2 أو أكثر)، فإن أسوأ عدد من خطوات نيوتن المطلوبة يكون في $O(M)$ مع ذلك، عمليًا، تؤدي قيمة μ الأكبر إلى تقارب أسرع بكثير. تُسمى هذه الطرق بطرق الخطوات الطويلة . ^{[ 3 ]}^{: القسم 4.6.} عمليًا، إذا كانت قيمة μ بين 3 و100، فإن البرنامج يتقارب خلال 20-40 خطوة نيوتن، بغض النظر عن عدد القيود (مع العلم أن زمن تشغيل كل خطوة نيوتن يزداد مع ازدياد عدد القيود). القيمة الدقيقة لـ μ ضمن هذا النطاق ليس لها تأثير يُذكر على الأداء. ^{[ 4 ]}^{: الفصل 11}

طرق تقليل الجهد

بالنسبة لطرق تقليل الجهد، تُعرض المسألة في شكل مخروطي : ^{[ 3 ]}^{: القسم 5}

تقليل c ^Tx st x في {b+L} ∩ K ،

حيث b متجه في Rⁿ ^، وL فضاء جزئي خطي في ^Rⁿ (وبالتالي b + L مستوى أفيني )، و K مخروط محدب مغلق ذو رأس مدبب وداخل غير فارغ. يمكن تحويل أي برنامج محدب إلى الشكل المخروطي. لاستخدام طريقة اختزال الجهد (وتحديدًا، امتداد خوارزمية كارماركار للبرمجة المحدبة)، نحتاج إلى الافتراضات التالية: ^{[ 3 ]}^{: القسم 6}

أ . المجموعة الممكنة {b+L} ∩ K محدودة، وتتقاطع مع الجزء الداخلي من المخروط K.
ب . لدينا مسبقًا حل ممكن تمامًا x ^، أي حل ممكن في داخل K.
ج. نحن نعرف مسبقًا القيمة المثلى للهدف، c*، للمسألة.
د . لدينا حاجز متجانس ذاتيًا متجانس لوغاريتميًا M F للمخروط K.

تُعدّ الافتراضات أ، ب، د ضرورية في معظم طرق النقطة الداخلية. أما الافتراض ج فهو خاص بمنهج كارماركار، ويمكن التخفيف منه باستخدام "قيمة هدف منزلقة". ومن الممكن تبسيط البرنامج أكثر ليصبح بصيغة كارماركار .

تقليل s ^Tx st x في M ∩ K و e ^Tx = 1

حيث M هي فضاء جزئي خطي من في R ⁿ ، وقيمة الهدف الأمثل هي 0. تعتمد الطريقة على دالة الجهد القياسي التالية :

v ( x ) = F ( x ) + ^Mln ( sTx )

حيث F هو حاجز التوافق الذاتي M للمخروط الممكن. من الممكن إثبات أنه عندما يكون x ممكنًا تمامًا ويكون v ( x ) صغيرًا جدًا (سالبًا جدًا)، فإن x يكون مثاليًا تقريبًا. تتمثل فكرة طريقة تقليل الجهد في تعديل x بحيث ينخفض الجهد في كل تكرار بمقدار ثابت X على الأقل (وتحديدًا، X = 1/3 - ln(4/3)). هذا يعني أنه بعد i تكرار، يكون الفرق بين قيمة الهدف وقيمة الهدف المثلى على الأكثر V * exp( -iX / M )، حيث V ثابت يعتمد على البيانات. لذلك، فإن عدد خطوات نيوتن المطلوبة لحل تقريبي ε هو على الأكثر $O(1)\cdot M\cdot \ln \left({\frac {V}{\varepsilon }}+1\right)+1$ .

لاحظ أن التعبير في طرق تتبع المسار هو ${\sqrt {M}}$ بدلاً من M ، وهو الأفضل نظرياً. لكن عملياً، تسمح طريقة كارماركار باتخاذ خطوات أكبر بكثير نحو الهدف، لذا قد تتقارب أسرع بكثير من الضمانات النظرية.

الأساليب الأولية الثنائية

يسهل إثبات فكرة طريقة الثنائية الأولية في مسائل التحسين غير الخطي المقيد . ^{[ 9 ]}^{[ 10 ]} ولتبسيط الأمر، لنفترض مسألة التحسين غير الخطي التالية ذات القيود المتباينة:

${\begin{aligned}\operatorname {minimize} \quad &f(x)\\{\text{subject to}}\quad &x\in \mathbb {R} ^{n},\\&c_{i}(x)\geq 0{\text{ for }}i=1,\ldots ,m,\\{\text{where}}\quad &f:\mathbb {R} ^{n}\to \mathbb {R} ,\ c_{i}:\mathbb {R} ^{n}\to \mathbb {R} .\end{aligned}}\quad (1)$

تُحل مسألة التحسين هذه المقيدة بالمتباينات عن طريق تحويلها إلى دالة هدف غير مقيدة، والتي نأمل في إيجاد قيمتها الدنيا بكفاءة. وبالتحديد، فإن دالة الحاجز اللوغاريتمية المرتبطة بالمعادلة (1) هي $B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)$

هنا $\mu$ هو عدد قياسي موجب صغير، يُطلق عليه أحيانًا اسم "معامل الحاجز". $\mu$ يتقارب إلى الصفر الحد الأدنى لـ $B(x,\mu )$ ينبغي أن تتقارب إلى حل للمعادلة (1).

تدرج دالة قابلة للتفاضل $h:\mathbb {R} ^{n}\to \mathbb {R}$ يُشار إليه بـ $\nabla h$ تدرج دالة الحاجز هو $\nabla B(x,\mu )=\nabla f(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x).\quad (3)$

بالإضافة إلى المتغير الأصلي ("الأولي") $x$ نقدم متغيرًا ثنائيًا مستوحى من مضاعف لاغرانج $\lambda \in \mathbb {R} ^{m}$ $c_{i}(x)\lambda _{i}=\mu ,\quad \forall i=1,\ldots ,m.\quad (4)$

تُسمى المعادلة (4) أحيانًا شرط "التكامل المضطرب"، نظرًا لتشابهها مع "الركود التكميلي" في شروط KKT .

نحاول العثور على هؤلاء $(x_{\mu },\lambda _{\mu })$ والتي يكون تدرج دالة الحاجز عندها صفراً.

الاستبدال $1/c_{i}(x)=\lambda _{i}/\mu$ من (4) إلى (3)، نحصل على معادلة للتدرج: $\nabla B(x_{\mu },\lambda _{\mu })=\nabla f(x_{\mu })-J(x_{\mu })^{T}\lambda _{\mu }=0,\quad (5)$ حيث المصفوفة $J$ هو جاكوبيان القيود $c(x)$ .

يكمن الحدس وراء (5) في أن تدرج $f(x)$ ينبغي أن تقع في الفضاء الفرعي الذي تمتد عليه تدرجات القيود. "التكامل المضطرب" مع صغير $\mu$ (4) يمكن فهمه على أنه الشرط الذي ينص على أن الحل يجب أن يقع بالقرب من الحدود $c_{i}(x)=0$ أو أن إسقاط التدرج $\nabla f$ على عنصر القيد $c_{i}(x)$ يجب أن تكون القيمة الطبيعية قريبة من الصفر.

يترك $(p_{x},p_{\lambda })$ كن اتجاه البحث للتحديث المتكرر $(x,\lambda )$ بتطبيق طريقة نيوتن على المعادلتين (4) و(5)، نحصل على معادلة لـ $(p_{x},p_{\lambda })$ : ${\begin{pmatrix}H(x,\lambda )&-J(x)^{T}\\\operatorname {diag} (\lambda )J(x)&\operatorname {diag} (c(x))\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-\nabla f(x)+J(x)^{T}\lambda \\\mu 1-\operatorname {diag} (c(x))\lambda \end{pmatrix}},$

أين $H$ هي مصفوفة هيسيان لـ $B(x,\mu )$ ، $\operatorname {diag} (\lambda )$ هي مصفوفة قطرية من $\lambda$ ، و $\operatorname {diag} (c(x))$ هي المصفوفة القطرية لـ $c(x)$ .

بسبب (1)، (4) الشرط

\lambda \geq 0

ينبغي تطبيق ذلك في كل خطوة. ويمكن تحقيق ذلك عن طريق اختيار ما هو مناسب. $\alpha$ :

(x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).

مسار تكرارات x باستخدام طريقة النقطة الداخلية.

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

فيما يلي بعض الحالات الخاصة للبرامج المحدبة التي يمكن حلها بكفاءة باستخدام طرق النقطة الداخلية. ^{[ 3 ]}^{: القسم 10}

البرامج الخطية

لنفترض برنامجًا خطيًا على الشكل التالي: ${\begin{aligned}\operatorname {minimize} \quad &c^{\top }x\\{\text{subject to}}\quad &Ax\leq b.\end{aligned}}.$ يمكننا تطبيق أساليب تتبع المسار باستخدام الحاجز $b(x):=-\sum _{j=1}^{m}\ln(b_{j}-a_{j}^{T}x).$ الوظيفة $b$ يتوافق هذا مع المعامل M = m (عدد القيود). لذلك، فإن عدد خطوات نيوتن المطلوبة لطريقة تتبع المسار هو O( mn² ⁾ ، وتعقيد وقت التشغيل الكلي هو O( m³ ^/2n² ⁾ .

البرامج التربيعية المقيدة تربيعيًا

بالنظر إلى برنامج تربيعي مقيد تربيعيًا على الشكل التالي: ${\begin{aligned}\operatorname {minimize} \quad &d^{\top }x\\{\text{subject to}}\quad &f_{j}(x):=x^{\top }A_{j}x+b_{j}^{\top }x+c_{j}\leq 0\quad {\text{ for all }}j=1,\dots ,m,\end{aligned}}$ حيث تكون جميع المصفوفات A _j مصفوفات شبه موجبة . يمكننا تطبيق طرق تتبع المسار مع الحاجز $b(x):=-\sum _{j=1}^{m}\ln(-f_{j}(x)).$ الوظيفة $b$ هو حاجز متوافق ذاتيًا بمعامل M = m . تعقيد نيوتن هو O( (m+n)n ² )، وتعقيد وقت التشغيل الكلي هو O( m ^1/2 (m+n) n ² ).

تقريب معيار L _p

لنفترض مسألة من الشكل التالي ${\begin{aligned}\operatorname {minimize} \quad &\sum _{j}|v_{j}-u_{j}^{\top }x|_{p}\end{aligned}},$ حيث كل $u_{j}$ هو متجه، كل $v_{j}$ هو كمية قياسية، و $|\cdot |_{p}$ هو معيار L _p مع $1<p<\infty .$ بعد التحويل إلى الشكل القياسي، يمكننا تطبيق طرق تتبع المسار مع حاجز متوافق ذاتيًا بمعامل M = 4m . تعقيد نيوتن هو O( (m+n)n² ⁾ ، وتعقيد وقت التشغيل الكلي هو O( m¹ ^/² (m+n) n² ⁾ .

برامج هندسية

لننظر في المشكلة

${\begin{aligned}\operatorname {minimize} \quad &f_{0}(x):=\sum _{i=1}^{k}c_{i0}\exp(a_{i}^{\top }x)\\{\text{subject to}}\quad &f_{j}(x):=\sum _{i=1}^{k}c_{ij}\exp(a_{i}^{\top }x)\leq d_{j}\quad {\text{ for all }}j=1,\dots ,m.\end{aligned}}$

يوجد حاجز متوافق ذاتيًا بمعامل 2k + m . تتميز طريقة تتبع المسار بتعقيد نيوتن O( mk² + ^k³ + ^n³ ) وتعقيد إجمالي O(( ^k+ m ) ¹ ^/²^[ mk² + k³ ⁺ n³ ] ⁾ .

برامج شبه محددة

يمكن استخدام طرق النقطة الداخلية لحل البرامج شبه المحددة. ^{[ 3 ]}^{: القسم 11}

انظر أيضاً

مراجع

↑ ديكين، الثاني (1967). "الحل التكراري لمسائل البرمجة الخطية والتربيعية" . دوكل. أكاد. ناوك إس إس إس آر . 174 (1): 747– 748. Zbl 0189.19504 .
↑ كارماركار، ن. (1984). "خوارزمية جديدة متعددة الحدود للبرمجة الخطية" (ملف PDF) . وقائع الندوة السنوية السادسة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '84 . ص 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 28 ديسمبر 2013.
1 2 3 4 5 6 7 8 9 10 11 12 13 أركادي نيميروفسكي (2004). طرق الوقت متعدد الحدود للنقطة الداخلية في البرمجة المحدبة .
1 2 3 بويد، ستيفن؛ فاندنبيرغ، ليفين (2004). التحسين المحدب . كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-83378-3MR 2061575 .
↑ رايت، مارغريت هـ. (2004). "ثورة النقطة الداخلية في التحسين: التاريخ، والتطورات الحديثة، والنتائج الدائمة" . نشرة الجمعية الرياضية الأمريكية . 42 : 39-57 . doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .
↑ بوترا، فلوريان أ.؛ ستيفن ج. رايت (2000). "طرق النقطة الداخلية" . مجلة الرياضيات الحسابية والتطبيقية . 124 ( 1-2 ): 281-302 . Bibcode : 2000JCoAM.124..281P . doi : 10.1016/S0377-0427(00)00433-7 .
1 2 رينيغار، جيمس (1 يناير 1988). "خوارزمية زمنية متعددة الحدود، تعتمد على طريقة نيوتن، للبرمجة الخطية" . البرمجة الرياضية . 40 (1): 59-93 . doi : 10.1007/BF01580724 . ISSN 1436-4646 .
1 2 غونزاغا، كلوفيس سي. (1989)، "خوارزمية لحل مسائل البرمجة الخطية في O(n³L) عملية" ، في ميغيدو، نمرود (محرر)، التقدم في البرمجة الرياضية: طرق النقطة الداخلية والطرق ذات الصلة ، نيويورك، نيويورك: سبرينغر، ص 1-28 ، doi : 10.1007/978-1-4613-9617-8_1 ، ISBN 978-1-4613-9617-8تم الاطلاع عليه بتاريخ 22 نوفمبر 2023
↑ ميهروترا، سانجاي (1992). "حول تطبيق طريقة النقطة الداخلية الأولية-الثنائية". مجلة SIAM للتحسين . 2 (4): 575-601 . doi : 10.1137/0802028 .
↑ رايت، ستيفن (1997). طرق النقطة الداخلية الأولية-الثنائية . فيلادلفيا، بنسلفانيا: SIAM. ISBN 978-0-89871-382-4.

بونان، ج. فريدريك؛ جيلبرت، ج. تشارلز؛ ليمارشال، كلود ؛ ساغاستيزابال، كلوديا أ. (2006). التحسين العددي: الجوانب النظرية والعملية . Universitext (الطبعة الثانية المنقحة من ترجمة الطبعة الفرنسية لعام 1997). برلين: Springer-Verlag. الصفحات: xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 978-3-540-35445-1MR 2265882 .
نوسيدال، خورخي؛ ستيفن رايت (1999). التحسين العددي . نيويورك، نيويورك: سبرينغر. ISBN 978-0-387-98793-4.
بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "القسم 10.11. البرمجة الخطية: طرق النقطة الداخلية" . وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8أُرشف من المصدر الأصلي بتاريخ 11 أغسطس 2011. تم الاطلاع عليه بتاريخ 12 أغسطس 2011 .

[1] ديكين، الثاني (1967). "الحل التكراري لمسائل البرمجة الخطية والتربيعية" . دوكل. أكاد. ناوك إس إس إس آر . 174 (1): 747– 748. Zbl 0189.19504 .

[2] كارماركار، ن. (1984). "خوارزمية جديدة متعددة الحدود للبرمجة الخطية" (ملف PDF) . وقائع الندوة السنوية السادسة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '84 . ص 302. doi : 10.1145/800057.808695 . ISBN 0-89791-133-4تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 28 ديسمبر 2013.

[:0-3] 1 2 3 4 5 6 7 8 9 10 11 12 13 أركادي نيميروفسكي (2004). طرق الوقت متعدد الحدود للنقطة الداخلية في البرمجة المحدبة .

[:3-4] 1 2 3 بويد، ستيفن؛ فاندنبيرغ، ليفين (2004). التحسين المحدب . كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-83378-3MR 2061575 .

[5] رايت، مارغريت هـ. (2004). "ثورة النقطة الداخلية في التحسين: التاريخ، والتطورات الحديثة، والنتائج الدائمة" . نشرة الجمعية الرياضية الأمريكية . 42 : 39-57 . doi : 10.1090/S0273-0979-04-01040-7 . MR 2115066 .

[6] بوترا، فلوريان أ.؛ ستيفن ج. رايت (2000). "طرق النقطة الداخلية" . مجلة الرياضيات الحسابية والتطبيقية . 124 ( 1-2 ): 281-302 . Bibcode : 2000JCoAM.124..281P . doi : 10.1016/S0377-0427(00)00433-7 .

[:1-7] 1 2 رينيغار، جيمس (1 يناير 1988). "خوارزمية زمنية متعددة الحدود، تعتمد على طريقة نيوتن، للبرمجة الخطية" . البرمجة الرياضية . 40 (1): 59-93 . doi : 10.1007/BF01580724 . ISSN 1436-4646 .

[:2-8] 1 2 غونزاغا، كلوفيس سي. (1989)، "خوارزمية لحل مسائل البرمجة الخطية في O(n³L) عملية" ، في ميغيدو، نمرود (محرر)، التقدم في البرمجة الرياضية: طرق النقطة الداخلية والطرق ذات الصلة ، نيويورك، نيويورك: سبرينغر، ص 1-28 ، doi : 10.1007/978-1-4613-9617-8_1 ، ISBN 978-1-4613-9617-8تم الاطلاع عليه بتاريخ 22 نوفمبر 2023

[9] ميهروترا، سانجاي (1992). "حول تطبيق طريقة النقطة الداخلية الأولية-الثنائية". مجلة SIAM للتحسين . 2 (4): 575-601 . doi : 10.1137/0802028 .

[10] رايت، ستيفن (1997). طرق النقطة الداخلية الأولية-الثنائية . فيلادلفيا، بنسلفانيا: SIAM. ISBN 978-0-89871-382-4.

[ 1 ]

[ 2 ]

[ 5 ]

[ 6 ]

[ 9 ]

[ 10 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗