باید تابع هدف خطی روی اشتراک صفحه آفینی و مخروط K ، مینیمم سازی کنیم . این اشتراک محدب است پسP یک مسئله محدب است .
مسئله به شکل مخروطی مشابه مسئله برنامه ریزی خطی به شکل استاندارد است ؛ مسئلهP شکل جهانی مسئله برنامهریزی محدب است . در واقع ، کافی است نشان دهیم مسئله به شکل استاندارد S را میتوان به شکل مخروطیP بازنویسی کر د.
دامنه ی G محدب و بسته است ، کافی است نشان دهیمG اشتراک یک مخروط محدب بسته با یک صفحه آفینی است ، بنابراین ابرصفحه آفینی را در نظر میگیریم و
که و پوسته مخروطی است . به راحتی میتوان دید که معادل است و مسئله دوم مخروطی است (یعنی K ، یک مخروط محدب و بسته و گوشه دار با درون ناتهی است) ، وG دامنه بسته و محدب است که شامل هیچ خطی نمیباشد . بنابراین Pشکل جهانی مسئله محدب است .
دوگانگی مخروطی:
شباهت میان مسئله مخروطی P و مسئله برنامهریزی خطی وقتی مسئله دوگانگی باشد ، واضح است . این دوگانگی برای توسعه روشهای کاهش پتانسیل مهم است .
دوگان فنچل مسئله مخروطیP را بیان میکنیم . بدین منظور قرار میدهیم :
این توابع محدب ، بسته و سرهاند و P مسئله مینیمم سازی روی است . برای نوشتن دوگان فنچل باید توابع را به دست آوریم بنابراین :
که ، مکمل متعامد L است .
که ، دوگان مخروط است .
دوگان فنچل P به صورت زیر است :
میتوانیم معادل دو گان فنچل P را ایجاد کنیم :
که در آن تحت این محدودیتها تابع هدف در دوگان فنچل برابر است و .
توجه کنید که تابع هدف واقعی در دوگان فنچل است که در D جمله ثابت حذف شده است (زیرا این جمله در مجموعه بهینه تاثیری ندارد، حتی اگر مقادیر بهینه تغییر کنند) . مسئله D دوگان مخروطی نسبت به مسئله اولیه مخروطی P نامیده میشود . هم چنین فرض کردیم K مخروطی بسته ، محدب و گوشهدار با درون ناتهی است بنابراین مخروط دوگان بسته ، محدب و گوشهدار با درون ناتهی است . پس مسئله دوگان نیز مخروطی است و داریم و این نشان دهنده آن است که دوگانگی کاملا متقارن است .
حال چند تذکر درباره دوگانگی مخروطی بیان میکنیم ؛ که مشابه آن چه درباره دوگانگی LP میدانستیم میباشد :
-
- اگر (x,s) جفت شدنی اولیه- دوگان باشند ، یعنی جفتی که شامل جوابهای شدنی D و P باشند ، آنگاه :
سمت چپ رابطه ، فاصله دوگانگی[۳۸] نامیده می شود و که برابر با است و همواره نامنفی است .
-
- فرض کنیم به ترتیب مقادیر بهینه مسئله اولیه – دوگان باشند (مقدار بهینه است اگر مسئله نشدنی باشد و است اگر مسئله از پایین بیکران باشد) ، آن گاه
و جواب شدنی اولیه x و جواب شدنی دوگان s در رابطه زیر صدق میکند:
-
- اگر مسئله دوگان شدنی باشد آن گاه مسئله اولیه از پایین کراندار است . اگر مسئله اولیه شدنی باشد آن گاه دوگان از پایین کراندار است.
-
- قضیه دوگانگی مخروط: اگر یکی از مسائل اولیه- دوگان P و D اکیدا شدنی (یعنی دارای جوابهای شدنی از داخل مخروط باشد) و از پایین کراندار باشد ، آن گاه مسئله دوم حل پذیر است و مقادیر بهینه مسئلهها متناهی است . فاصله دوگانگی صفر است . اگر هر دو مسئله اکیدا شدنی باشند ، آن گاه هر دو آن ها حل پذیر و جفت جوابهای شدنی مسئله است و جوابهای بهینهاند اگر و تنها اگر فاصله دوگانگی صفر باشد اگر و تنها اگر در رابطه مکمل و زائد صدق کنند .
توجه کنید که قضیه دوگانگی مخروط اگر چه بسیار شبیه قضیه دوگانگی LP است ، اما کمی ضعیفتر است ، در LP شدنی و از پایین کرانداری است اما در مخروطها اکیدا شدنی و از پایین کرانداری از مفروضات است .
نتیجه که از این بخش میگیریم این است که دوگانگی مخروطی برای توسعه روشهای نقطه درونی کاهش پتانسیل مفید است .
۴-۳-۲ موانع لگاریتمی همگن[۳۹] :
برای توسعه روشهای کاهش پتانسیل ، به فرمولهای مخروطی مسائل محدب نیاز داریم. روشهای نقطه درونی مسائل مخروطی با ارتباط خاص مانعهای ϑ-خود هماهنگ برای مخروط ها بیان میشود که به اصطلاح شرایط همگن لگاریتمی مینامند.
تعریف ۴-۳-۱ : فرض کنیم یک مخروط محدب ، بسته و گوشهدار با درون ناتهی باشد و حقیقی است . تابع ، مانع ϑ- خود هماهنگ همگن لگاریتمی برای K نامیده میشود، اگر روی خود هماهنگ باشد و در رابطه زیر صدق کند :
(۴-۳۴)
حال این سوال پیش می آید که “آیا مانع خود هماهنگ لگاریتمی” برای یک مخروط ، مانع خود هماهنگ برای آن هست یا خیر؟ پاسخ این سوال در گزاره زیر آمده است :
گزاره ۴-۳-۱ : یک مانع ϑ-خود هماهنگ همگن لگاریتمی(F) برای K یک مانع ϑ- خود هماهنگ ناتباهیده برای K است . هم چنینF در روابط زیر صدق میکند:
(۴-۳۵)
(۴-۳۶)
(۴-۳۷)
برهان : با توجه به فرض ، چون K شامل هیچ خطی نیست ، F ناتباهیده است (فصل ۲- قسمت ۳) حال رابطههای (۴-۳۵) تا (۴-۳۷) را اثبات میکنیم .
(۴-۳۸)
از رابطه فوق نسبت به x مشتق میگیریم :
رابطه (۴-۳۵) به دست میآید .
با مشتق گیری از (۴-۳۵) نسبت به t و قرار دادن رابطه (۴-۳۶) به دست میآید .
با مشتق گیری از (۴-۳۸) نسبت به t و قرار دادن میرسیم به :