باید تابع هدف خطی  روی اشتراک صفحه آفینی  و مخروط K ، مینیمم سازی کنیم . این اشتراک محدب است پسP یک مسئله محدب است .
مسئله به شکل مخروطی مشابه مسئله برنامه ریزی خطی به شکل استاندارد است ؛ مسئلهP شکل جهانی مسئله برنامه‌ریزی محدب است . در واقع ، کافی است نشان دهیم مسئله به شکل استاندارد S را می‌توان به شکل مخروطیP بازنویسی کر د.

دامنه ی G محدب و بسته است ، کافی است نشان دهیمG اشتراک یک مخروط محدب بسته با یک صفحه آفینی است ، بنابراین ابرصفحه آفینی  را در نظر می‌گیریم و

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

که  و  پوسته مخروطی است . به راحتی می‌توان دید که  معادل  است و مسئله دوم مخروطی است (یعنی K ، یک مخروط محدب و بسته و گوشه دار با درون ناتهی است) ، وG دامنه بسته و محدب است که شامل هیچ خطی نمی‌باشد . بنابراین Pشکل جهانی مسئله محدب است .
دوگانگی مخروطی:
شباهت میان مسئله مخروطی P و مسئله برنامه‌ریزی خطی وقتی مسئله دوگانگی باشد ، واضح است . این دوگانگی برای توسعه روش‌های کاهش پتانسیل مهم است .
دوگان فنچل مسئله مخروطیP را بیان می‌کنیم . بدین منظور قرار می‌دهیم :

این توابع محدب ، بسته و سره‌اند و P مسئله مینیمم سازی  روی  است . برای نوشتن دوگان فنچل باید توابع  را به دست آوریم بنابراین :

که  ، مکمل متعامد L است .

که ، دوگان مخروط است .
دوگان فنچل P به صورت زیر است :

می‌توانیم معادل دو گان فنچل P را ایجاد کنیم :

که در آن  تحت این محدودیت‌ها تابع هدف در دوگان فنچل برابر  است و  .
توجه کنید که تابع هدف واقعی در دوگان فنچل  است که در D جمله ثابت  حذف شده است (زیرا این جمله در مجموعه بهینه تاثیری ندارد، حتی اگر مقادیر بهینه تغییر کنند) . مسئله D دوگان مخروطی نسبت به مسئله اولیه مخروطی P نامیده می‌شود . هم چنین فرض کردیم K مخروطی بسته ، محدب و گوشه‌دار با درون ناتهی است بنابراین مخروط دوگان بسته ، محدب و گوشه‌دار با درون ناتهی است . پس مسئله دوگان نیز مخروطی است و داریم  و این نشان دهنده آن است که دوگانگی کاملا متقارن است .
حال چند تذکر درباره دوگانگی مخروطی بیان می‌کنیم ؛ که مشابه آن چه درباره دوگانگی LP می‌دانستیم می‌باشد :

1. 1. اگر (x,s) جفت شدنی اولیه- دوگان باشند ، یعنی جفتی که شامل جواب‌های شدنی D و P باشند ، آنگاه :

سمت چپ رابطه ، فاصله دوگانگی^[۳۸] نامیده می شود و که برابر با  است و همواره نامنفی است .

1. 1. فرض کنیم به ترتیب مقادیر بهینه مسئله اولیه – دوگان باشند (مقدار بهینه است اگر مسئله نشدنی باشد و است اگر مسئله از پایین بی‌کران باشد) ، آن گاه

و جواب شدنی اولیه x و جواب شدنی دوگان s در رابطه زیر صدق می‌کند:

1. 1. اگر مسئله دوگان شدنی باشد آن گاه مسئله اولیه از پایین کراندار است . اگر مسئله اولیه شدنی باشد آن گاه دوگان از پایین کراندار است.

1. 1. قضیه دوگانگی مخروط: اگر یکی از مسائل اولیه- دوگان P و D اکیدا شدنی (یعنی دارای جواب‌های شدنی از داخل مخروط باشد) و از پایین کراندار باشد ، آن گاه مسئله دوم حل پذیر است و مقادیر بهینه مسئله‌ها متناهی است . فاصله دوگانگی  صفر است . اگر هر دو مسئله اکیدا شدنی باشند ، آن گاه هر دو آن ها حل پذیر و جفت جواب‌های شدنی مسئله است و جواب‌های بهینه‌اند اگر و تنها اگر فاصله دوگانگی  صفر باشد اگر و تنها اگر در رابطه مکمل و زائد  صدق کنند .

توجه کنید که قضیه دوگانگی مخروط اگر چه بسیار شبیه قضیه دوگانگی LP است ، اما کمی ضعیف‌تر است ، در LP شدنی و از پایین کرانداری است اما در مخروط‌ها اکیدا شدنی و از پایین کرانداری از مفروضات است .
نتیجه که از این بخش می‌گیریم این است که دوگانگی مخروطی برای توسعه روش‌های نقطه درونی کاهش پتانسیل مفید است .
۴-۳-۲ موانع لگاریتمی همگن^[۳۹] :
برای توسعه روش‌های کاهش پتانسیل ، به فرمول‌های مخروطی مسائل محدب نیاز داریم. روش‌های نقطه درونی مسائل مخروطی با ارتباط خاص مانع‌های ϑ-خود هماهنگ برای مخروط ها بیان می‌شود که به اصطلاح شرایط همگن لگاریتمی می‌نامند.
تعریف ۴-۳-۱ : فرض کنیم  یک مخروط محدب ، بسته و گوشه‌دار با درون ناتهی باشد و  حقیقی است . تابع  ، مانع ϑ- خود هماهنگ همگن لگاریتمی برای K نامیده می‌شود، ‌اگر روی  خود هماهنگ باشد و در رابطه زیر صدق کند :
(۴-۳۴)
حال این سوال پیش می آید که “آیا مانع خود هماهنگ لگاریتمی” برای یک مخروط ، مانع خود هماهنگ برای آن هست یا خیر؟ پاسخ این سوال در گزاره زیر آمده است :
گزاره ۴-۳-۱ : یک مانع ϑ-خود هماهنگ همگن لگاریتمی(F) برای K یک مانع ϑ- خود هماهنگ ناتباهیده برای K است . هم چنینF در روابط زیر صدق می‌کند:
(۴-۳۵)
(۴-۳۶)
(۴-۳۷)
برهان : با توجه به فرض ، چون K شامل هیچ خطی نیست ، F ناتباهیده است (فصل ۲- قسمت ۳) حال رابطه‌های (۴-۳۵) تا (۴-۳۷) را اثبات می‌کنیم .
(۴-۳۸)
از رابطه فوق نسبت به x مشتق می‌گیریم :

رابطه (۴-۳۵) به دست می‌آید .
با مشتق گیری از (۴-۳۵) نسبت به t و قرار دادن  رابطه (۴-۳۶) به دست می‌آید .
با مشتق گیری از (۴-۳۸) نسبت به t و قرار دادن  می‌رسیم به :