همگرایی چندجمله ای الگوریتم پیشگو-اصلاحگر نوع مهروترا برای مسایل مکمل خطی P*(K) روی مخروط متقارن

دراین مقاله یک الگوریتم نقطه درونی نشدنی پیشگو-اصلاحگر نوع مهروترا، با یک طرح به روز رسانی پارامتر مرکزی برای مسایل مکمل خطی P*(K) روی مخروط های متقارن با استفاده از جبرهای جردن اقلیدسی ارایه می شود. همچنین با اصلاح طول گام ماکزیمم در گام پیشگو و دستگاه نیوتون در گام اصلاحگر، کران پیچیدگی تکرار این الگوریتم برای تمام رده ی جهت های جابجایی پذیر، برابر با (فرمول در متن اصلی مقاله) است که در آن r برابر با رتبه مخروط K، k امتیاز مساله cond (G) شرط عددی ماتریس G و 0 > ε دقت موردنیاز برای مساله است. تمام بررسی های ارایه شده بر پایه این فرض که مجموعه ی جواب های شدنی درونی برای مسلایل مکمل خطی ناتهی هستند، صورت گرفته است.

کلیدواژه ها:

مساله ی مکمل خطی ، جبر جردن اقلیدسی ، روش های نقطه درونی ، پیچیدگی چند جمله ای ، ویژگی دکارتی P*(K)