طريقة القطع الناقص

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

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

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

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

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

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

تتكون مسألة التصغير المحدب من المكونات التالية.

• دالة محدبة${\displaystyle f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R} }$يتم تقليلها على المتجه${\displaystyle x}$(تحتوي على n متغيرات)؛
• قيود المتباينات المحدبة من الشكل${\displaystyle f_{i}(x)\leqslant 0}$، حيث الدوال${\displaystyle f_{i}}$محدبة؛ تحدد هذه القيود مجموعة محدبة${\displaystyle Q}$.
• قيود المساواة الخطية من الشكل${\displaystyle h_{i}(x)=0}$.

كما تم تزويدنا بقطع ناقص أولي${\displaystyle {\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}}$يُعرَّف بأنه

${\displaystyle {\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\$ :\ (z-x_{0})^{T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}}

يحتوي على مُصغِّر${\displaystyle x^{*}}$، أين${\displaystyle P_{(0)}\succ 0}$و${\displaystyle x_{0}}$هو مركز${\displaystyle {\mathcal {E}}}$.

وأخيرًا، نحن نشترط وجود وسيط فصل للمجموعة المحدبة${\displaystyle Q}$. بالنظر إلى نقطة${\displaystyle x\in \mathbb {R} ^{n}}$، يجب أن تُرجع العرافة إحدى الإجابتين التاليتين: ^{[ 5 ]}

• "النقطة"${\displaystyle x}$هو في${\displaystyle Q}$"، أو -
• "النقطة"${\displaystyle x}$ليس في${\displaystyle Q}$وعلاوة على ذلك، يوجد هنا مستوى فائق يفصل${\displaystyle x}$من${\displaystyle Q}$أي متجه${\displaystyle c}$بحيث${\displaystyle c\cdot x<c\cdot y}$للجميع${\displaystyle y\in Q}$.

تكون مخرجات طريقة القطع الناقص إما:

• أي نقطة في متعدد السطوح${\displaystyle Q}$(أي أي نقطة ممكنة)، أو -
• دليل على ذلك${\displaystyle Q}$فارغ.

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

في التكرار رقم k من الخوارزمية، لدينا نقطة${\displaystyle x^{(k)}}$في مركز شكل بيضاوي

${\displaystyle {\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\$ :\ \left(xx^{(k)}\right)^{T}P_{(k)}^{-1}\left(xx^{(k)}\right)\leqslant 1\right\}.}

نستعلم من وسيط مستوى القطع للحصول على متجه${\displaystyle g^{(k+1)}\in \mathbb {R} ^{n}}$بحيث

${\displaystyle g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.}$

وعليه نستنتج أن

${\displaystyle x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\$ :\ g^{(k+1)T}\left(zx^{(k)}\right)\leqslant 0\right\}.}

لقد حددنا${\displaystyle {\mathcal {E}}^{(k+1)}}$أن يكون الشكل الإهليلجي ذو الحجم الأدنى الذي يحتوي على نصف الشكل الإهليلجي الموصوف أعلاه، ثم احسب${\displaystyle x^{(k+1)}}$يتم تقديم التحديث بواسطة

${\displaystyle {\begin{aligned}x^{(k+1)}&=x^{(k)}-{\frac {1}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}\\P_{(k+1)}&={\frac {n^{2}}{n^{2}-1}}\left(P_{(k)}-{\frac {2}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}{\tilde {g}}^{(k+1)T}P_{(k)}\right)\end{aligned}}}$

أين

${\displaystyle {\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}.}$

يُحدد معيار التوقف بالخاصية التي

${\displaystyle {\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .}$

في التكرار رقم k من خوارزمية التصغير المقيد، لدينا نقطة${\displaystyle x^{(k)}}$في مركز شكل بيضاوي${\displaystyle {\mathcal {E}}^{(k)}}$كما في السابق. يجب علينا أيضاً الاحتفاظ بقائمة من القيم.${\displaystyle f_{\rm {best}}^{(k)}}$تسجيل أصغر قيمة هدفية للتكرارات الممكنة حتى الآن. اعتمادًا على ما إذا كانت النقطة${\displaystyle x^{(k)}}$إذا كان ذلك ممكناً، فإننا نقوم بأحد المهمتين التاليتين:

• لو${\displaystyle x^{(k)}}$إذا كان ذلك ممكناً، فقم بإجراء نفس التحديث تقريباً كما في الحالة غير المقيدة، عن طريق اختيار تدرج فرعي${\displaystyle g_{0}}$ذلك يرضي

${\displaystyle g_{0}^{T}(x^{*}-x^{(k)})+f_{0}(x^{(k)})-f_{\rm {best}}^{(k)}\leqslant 0}$

• لو${\displaystyle x^{(k)}}$إذا كان الحل غير ممكن ويخالف القيد رقم j ، فقم بتحديث القطع الناقص باستخدام قطع قابل للتطبيق. قد يكون قطعنا القابل للتطبيق عبارة عن تدرج فرعي.${\displaystyle g_{j}}$ل${\displaystyle f_{j}}$والذي يجب أن يفي

${\displaystyle g_{j}^{T}(z-x^{(k)})+f_{j}(x^{(k)})\leqslant 0}$

لجميع قيم z الممكنة .

طبّق ليونيد خاشيان طريقة القطع الناقص على حالة خاصة من البرمجة الخطية : تصغير c ^T x st Ax ≤ b ، حيث جميع المعاملات في A وb وc أعداد نسبية. وقد أثبت أن البرامج الخطية يمكن حلها في وقت متعدد الحدود. فيما يلي ملخص لنظرية خاشيان. ^{[ 7 ] : القسم 8.4.2}

الخطوة الأولى: اختزال التحسين إلى بحث . تنص نظرية ازدواجية البرمجة الخطية على أنه يمكننا اختزال مسألة التصغير المذكورة أعلاه إلى مسألة بحث: إيجاد x و y بحيث يكون Ax ≤ b  ؛ و ^Aᵀy = c  ؛ و y ≤ 0  ؛ و ^cᵀx = bᵀy ^. المسألة الأولى قابلة للحل إذا وفقط إذا كانت المسألة الثانية قابلة للحل؛ وفي حالة كون المسألة الثانية قابلة للحل، فإن مركبات x لحل المسألة الثانية تمثل حلاً أمثل للمسألة الأولى. لذلك، من الآن فصاعدًا، يمكننا افتراض أننا بحاجة إلى حل المسألة التالية: إيجاد z ≥ 0 بحيث يكون Rz ≤ r . بضرب جميع المعاملات النسبية في المقام المشترك، يمكننا افتراض أن جميع المعاملات أعداد صحيحة.

الخطوة الثانية: اختزال البحث إلى التحقق من الجدوى . يمكن اختزال مسألة إيجاد z ≥ 0 بحيث يكون Rz ≤ r إلى مسألة القرار الثنائي: " هل يوجد z ≥ 0 بحيث يكون Rz ≤ r ؟ ". يمكن القيام بذلك كما يلي: إذا كانت إجابة مسألة القرار "لا"، فإن إجابة مسألة البحث هي "لا يوجد"، وبذلك نكون قد انتهينا. وإلا، نأخذ قيد المتباينة الأول R ₁ z ≤ r ₁ ؛ ونستبدله بمساواة R ₁ z = r ₁ ؛ ونطبق مسألة القرار مرة أخرى. إذا كانت الإجابة "نعم"، نبقي على المساواة؛ أما إذا كانت الإجابة "لا"، فهذا يعني أن المتباينة زائدة، ويمكننا حذفها. ثم ننتقل إلى قيد المتباينة التالي. لكل قيد، إما أن نحوله إلى مساواة أو نحذفه. وأخيراً، لدينا فقط قيود المساواة، والتي يمكن حلها بأي طريقة لحل نظام المعادلات الخطية.

الخطوة 3 : يمكن اختزال مسألة القرار إلى مسألة تحسين مختلفة. نُعرّف دالة الباقي f(z)  := max[(Rz) ₁ -r ₁ , (Rz) ₂ -r ₂ , (Rz) ₃ -r ₃ ,...]. من الواضح أن f ( z ) ≤ 0 إذا وفقط إذا كان Rz ≤ r . لذلك، لحل مسألة القرار، يكفي حل مسألة التصغير: min _z f ( z ). الدالة f محدبة (وهي قيمة عظمى للدوال الخطية). نرمز إلى القيمة الصغرى بـ f *. إذن، تكون إجابة مسألة القرار "نعم" إذا وفقط إذا كان f* ≤ 0.

الخطوة 4 : في مسألة التحسين min _z f ( z )، يمكننا افتراض أن z يقع ضمن صندوق طول ضلعه 2L ^، حيث L هو طول بتات بيانات المسألة. وبالتالي، لدينا برنامج محدب محدود، يمكن حله بدقة تصل إلى ε باستخدام طريقة القطع الناقص، في زمن متعدد الحدود بالنسبة إلى L.

الخطوة 5 : يمكن إثبات أنه إذا كانت f*>0، فإن f*>2 ^-poly(L) لبعض كثيرات الحدود. لذلك، يمكننا اختيار الدقة ε=2 ^-poly(L) . عندئذٍ، سيكون الحل التقريبي ε الذي تم إيجاده بطريقة القطع الناقص موجبًا، إذا وفقط إذا كانت f*>0، وإذا وفقط إذا كانت مسألة القرار غير قابلة للحل.

تتضمن طريقة القطع الناقص عدة أشكال، وذلك بحسب القطع المستخدمة تحديدًا في كل خطوة. ^{[ 1 ] : القسم 3}

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

• ديميتريس أليفراس ومانفريد دبليو بادبيرج، التحسين الخطي والامتدادات: المشكلات والامتدادات ، Universitext، Springer-Verlag، 2001. (مشكلات من بادبيرج مع الحلول.)
• V. Chandru و MRRao، البرمجة الخطية، الفصل 31 في كتيب الخوارزميات ونظرية الحوسبة ، حرره MJAtallah، CRC Press 1999، 31-1 إلى 31-37.
• V. Chandru و MRRao، البرمجة العددية، الفصل 32 في كتيب الخوارزميات ونظرية الحوسبة ، حرره MJAtallah، CRC Press 1999، 32-1 إلى 32-45.
• جورج ب. دانتزيج وموكوند ن. ثابا. 1997. البرمجة الخطية 1: مقدمة . سبرينغر-فيرلاغ.
• جورج ب. دانتزيج وموكوند ن. ثابا. 2003. البرمجة الخطية 2: النظرية والتوسعات . سبرينغر-فيرلاغ.
• ل. لوفاس : نظرية خوارزمية للأعداد والرسوم البيانية والتحدب ، سلسلة مؤتمرات CBMS-NSF الإقليمية في الرياضيات التطبيقية 50، SIAM، فيلادلفيا، بنسلفانيا، 1986
• كاتا جي. مورتي، البرمجة الخطية ، وايلي، 1983.
• م. بادبيرج ، التحسين الخطي والامتدادات ، الطبعة الثانية، سبرينغر-فيرلاغ، 1999.
• كريستوس هـ. باباديميتريو وكينيث ستيغليتز، التحسين التوافقي: الخوارزميات والتعقيد ، إعادة نشر مصححة مع مقدمة جديدة، دوفر.
• ألكسندر شريفر , نظرية البرمجة الخطية والأعداد الصحيحة . جون وايلي وأولاده، 1998، ISBN 0-471-98232-6

• EE364b ، الصفحة الرئيسية لدورة ستانفورد