آن گاه s متناسب با ضریب مثبتی از است . بدین منظور مجموعه را در نظر بگیرید :

تحدید به ناحیه داخلی برابر تحدید F است ، پس خود هماهنگ است . چون کراندار است (و ) ، Fو در نتیجه به مینیمم مقدارش روی ناحیه داخلی می‌رسد و چونF ناتباهیده است ، این مینیمم مقدار منحصر به فرد است و آن را y در نظر می‌گیریم و داریم :

و است . با توجه به رابطه فوق داریم :

حال (۴-۴۵) نشان می‌دهد که . بنابراین با توجه به ساختار و y مینیمم مقدار منحصر به فرد است . نتیجه می‌گیریم بنابراین و اثبات کامل می‌شود .□

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

حال فرض کنیم می‌خواهیم دوگان- اولیه مسئله مخروطی را حل کنیم :
(۴-۴۶)
که سطرهای A مستقل خطی‌اند و هر دو مسئله دارای جواب های به طور اکید شدنی اند (یعنی وجود دارند) . همچنین فرض کنیم F یک مانع ϑ- خود هماهنگ همگن لگاریتمی برای K با تبدیلات لژاندار باشد ، که یک مانع ϑ- خود هماهنگ همگن لگاریتمی برای است. مسئله P را می توان به شکل زیر در نظر گرفت .
(۴-۴۷)
که مجموعه آفینی نقش مجموعه ی مرجع و نقش X را ایفا می کند . تحدید F به یک مانع ϑ-خود هماهنگ برای مسئله (۴-۴۷) ایجاد می کند . (با توجه به گزاره ۳-۱-۱- قسمت الف).
در نتیجه می توان مسیر مرکزی اولیه را تعریف کنیم که شامل جواب های به طور اکید شدنیP است و همگرا به مجموعه جواب بهینه مسئله اولیه است وقتی که .
به طور مشابه، قرار می دهیم ، مسئله دوگان را می توان به صورت (۴-۴۷) بازنویسی کرد ؛ یعنی :

دامنهY این مسئله نیز به یک مانع ϑ- خود هماهنگ مجهز می شود یعنی . هم چنین مجموعه های تراز مسئله کراندارند. پس می توان مسیر مرکزی را تعریف کرد.
این مسیر مرکزی شامل است ؛ یعنی مسیر مرکزی شامل نقاط درونی است . در نهایت به مسیر مرکزی اولیه- دوگان در داخل ناحیه می رسیم و به راحتی می توان دید که برای هر ، نقطه با محدودیت های زیر روی مولفه ی s,x تعریف می شود .
(جواب های به طور اکید شدنی اولیه)
(جواب های به طور اکید شدنی دوگان)
(با بهره گرفتن از مکمل و زائد)
توجه کنید که هر یک از معادلات مکمل و زائد بر دیگری دلالت دارد و می توان با حذف یکی از آن ها، هر دو تقارن اولیه- دوگان را حفظ کنیم .
روش های نقطه درونی اولیه- دوگان مسیر تعقیب به طور همزمان مسیرهای مرکزی اولیه و دوگان را می یابد و این به نظر می رسد که مسیر تعقیب با هم به صرفه تر از مسیر تعقیب به تنهایی (یا یکی از آن ها) است .
این روش ها دارای مزیت های خوبی است . راه های زیبایی برای مقداردهی اولیه به مسیر ردیابی حتی در زمانی که هیچ جواب شدنی برایD وP در دسترس نباشد وجود دارد .( )
در قسمت بعدی ، خانواده دیگری از روش های نقطه درونی اولیه- دوگان که اساس آن روی کاهش پتانسیل است را بیان می کنیم .
۴-۴ روش کارمارکار :
اولین روش نقطه درونی چند جمله ای زمان مسائل خطی توسط کارمارکار (۱۹۸۴) کشف شد تعمیم مخروطی الگوریتم را بیان می کنیم.
۴-۴-۱ قرارداد و فرض های مسئله :
یک مسئله محدب به شکل مخروطی به صورت زیر است:
(۴-۴۸)
که:

• • K یک مخروط محدب، بسته و گوشه دار با درون ناتهی در است.

• • L یک زیر فضای خطی در است

• • c,b بردارهای -n بعدی داده شده است .

فرضیات :
الف) مجموعه شدنی مسئله کراندار است و ناحیه درونی اشتراک مخروط K است.
ب) جواب به طور اکید شدنی مسئله داده شده است یعنی جواب شدنی که به درون K تعلق دارد .
پ) مقدار بهینه، ، مسئله مشخص است.
ت)مانع ϑ- خود هماهنگ همگن لگاریتمیF برای مخروط K داده شده است . توجه شود F داده شده به گونه ای است که به ازای هر می توانیم مقادیر (F(x) )، گرادیان ( ) و هسین مانع ( ) را محاسبه کنیم .
فرض الف و ب کم و بیش برای روش نقطه درونی است و فرض پ مخصوص روش کارمارکار است .
۴-۴-۲ شکل همگن مسئله :