۷) هندسه بیضی‌های دیکن: برای

که نیم نرمh مرتبط با تقارنG درx است یعنی نرم با گوی واحد:

و داریم :
(۳-۱۵)
برهان: نامساوی اول در (۳-۱۵) بدیهی است زیرا بیضی واحد و بسته دیکنF به مرکز x درونG است ( زیراF خود هماهنگ وG بسته است ، فصل ۲- قسمت ۲ ) به عبارت دیگر G شامل گوی واحد  به مرکز x است ، با توجه به تعریف گوی واحد  به مرکز x بزرگ‌ترین تقارن نسبت به x زیر مجموعه G است پس شامل  است که معادل با نامساوی چپ (۳-۱۵) است . برای اثبات نامساوی سمت راست ، نشان می‌دهیم اگر  آن‌گاه  یا با توجه بهP، حداقل یکی از دو بردار  به درون G تعلق ندارد . بدون آنکه از کلیت مسئله کاسته شود ، فرض می‌کنیم  (در غیر این صورت،-h را جایگزین h می‌کنیم) . جفت x و h در فرض لم ۳-۲-۱ صدق می‌کند پس بردار  به درون G تعلق ندارد .□
۸) سازگاری هسین‌ها^[۲۸]: فرض کنیم  . آن‌گاه به ازای هر  داریم:
(۳-۱۶)
برهان: با توجه به تعریف تابع مینکوفسکی،  وجود دارد به طوری که

حال اگر  باشد آن‌گاه  (چون بیضی واحد و بسته دیکن F به مرکز x متعلق به G است) ، بنابراین نقطه زیر به G تعلق دارد :

در نتیجه y مرکز  گوی به شعاع  در Gاست ، بنابراین بزرگ‌ترین تقارن نسبت بهx ، زیر مجموعه G وجود دارد و داریم :

ترکیب این نامساوی با (۳-۱۵) ، رابطه (۳-۱۶) را نتیجه می دهد .□
۹) وجود مانع خود هماهنگ دامنه داده شده: فرض کنیم G دامنه محدب و بسته در  باشد. آن‌گاه مانع ϑ-خود هماهنگ برای G وجود دارد با  که  یک ثابت مطلق مناسب است. اگر G شامل هیچ خطی نباشد ، آن‌گاه مانع فوق به صورت زیر خواهد بود :

کهVol ، حجم n-بعدی است .

قضیه فوق را ثابت نمی کنیم ؛ چون از آن استفاده نمی کنیم.تاکید می کنیم که به کار بردن تئوری برای ساخت یک مانع خودهماهنگ برای دامنه شدنی مسأله محدب لازم است اما کافی نیست. این قضیه بیان می کند که همواره مانع وجود دارد ، اما مانعی که ایجاد می کند معمولا پیچیدگی محاسباتی بالایی دارد زیرا انتگرال های چند گانه را درگیر می کند که سخت هستند. پس باید از روشی استفاده کنیم که موانع خود هماهنگ “محاسبه پذیر” بدست آوریم. در این صورت موانع مناسبی برای دامنه های شدنی مسایل محدب بدست می آوریم .
در اینجا “محاسبه پذیر” بدین معنی است که F(x) ، گرادیان F’(x) ، و هسین مانع F’’(x) به راحتی قابل محاسبه باشد.
فصل ۴
روش های نقطه درونی
جالب ترین روشی که در دهه ی ۱۹۸۰ برای حل مسایل برنامه ریزی خطی ابداع شد روشی بود به نام روش نقطه درونی که توسط ریاضی دان جوانی به نام کارمارکار معرفی شد . اگرچه این روش در ابتدا در مقایسه با روش سیمپلکس تو جه ها را به خود جلب ننمود اما اصول و مفاهیم کلیدی به کار رفته در آن نشان می دهد که این روش خاص پتاسیل حل مسایل برنامه ریزی خطی بسیار بزرگ را به گونه ای دارد که روش سیمپلکس به سختی آ ن ها را حل می کند . محققان زیادی جهت اصلاح و بهبود این الگوریتم کار کردند و به همین دلیل الگوریتم های قدرتمندی براساس روش نقطه درونی ابداع و معرفی نمودند . امروزه اغلب نرم افزار های قدرتمند طراحی شده جهت حل مسایل بزرگ برنامه ریزی خطی حداقل یکی از الگوریتم های ابداع شده براساس روش نقطه درونی را در کنار روش سیمپلکس دارند .
تفاوت بین روش سیمپلکس و نقطه درونی در اصل در حل مسایل با اندازه های مختلف مشخص می شود . عملکرد روش سیمپلکس و روش نقطه درونی اساسا با هم متفاوت است اما نقاط مشترکی نیز بین آن ها وجود دارد . یکی از این شباهت ها آن است که هر دو جز الگوریتم های تکراری محسوب می شوند . روش نقطه درونی از یک جواب اولیه موجه آغاز می شود و در هر تکرار از نقطه حاضر به یک نقطه جواب موجه بهتر حرکت می کند . این فرایند تا زمانی ادامه می یابد که به جواب بهینه برسیم .
تفاوت اصلی در ماهیت جواب هاست . در روش سیمپلکس جواب های بدست آمده از هر تکرار ، نقاط گوشه ای موجه بودند ، بنابراین مسیری که روش سیمپلکس برای بهبود جواب ها طی می کند بر مرزهای ناحیه شدنی مسئله است . اما در روش نقطه درونی جواب ها ، نقطه های داخلی هستند ، یعنی نقاطی هستند که درون ناحیه شدنی قرار دارند . به همین دلیل به الگوریتم کارمارکار و روش های توسعه یافته آن الگوریتم های نقطه درونی می گویند .
در این فصل روش های نقطه درونی برای حل مسائل بهینه سازی محدب را بیان می کنیم.
۴-۱ روش های نقطه درونی
مسئله زیر را در نظر بگیرید :
(۴-۱)
که  محدب و بطور پیوسته مشتق پذیر از مرتبه دوم می باشند . فرض کنیم مسئله حل پذیر باشد یعنی ، یک جواب بهینه  وجود داشته باشد . مقدار بهینه  را با  نشان می دهیم.
همچنین فرض می کنیم مسئله اکیداً شدنی است ؛ یعنی، x در ناحیه شدنی مسئله وجود دارد که در شرایط اسلاتر صدق می کند . بنابراین شرط دوگان قوی برقرار است .
روش های نقطه درونی مسئله (۴-۱) را با پیاده سازی روش میرا شده نیوتن حل می کنند . که در این فصل چند الگوریتم خاص این روش را بیان می کنیم و به مقایسه آن ها می پردازیم .
قبل از بیان روش ها ، به ذکر چند مطلب می پردازیم.
۴-۱-۱ تابع مانع لگاریتمی و مسیر مرکزی
هدف ما تبدیل مسائل با محدودیت نامساوی (۴-۱) به مسائل نامقید است . قدم اول بازنویسی مسئله (۴-۱) با بهره گرفتن از روش قرار دادن محدودیت های نامساوی در تابع هدف است:
(۴-۲)
که  تابع شاخص برای مقادیر حقیقی نامنفی است:

مسئله (۴-۲) محدودیت نامساوی ندارد، اما تابع هدف آن (در حالت کلی) مشتق پذیر نمی باشد . پس از روش میرا شده نیوتن نمی توان آن را حل کرد.
ایده اصلی روش با تابع شاخص با بهره گرفتن از تابع زیر، نزدیک است.

که  ، پارامتری به منظور درستی تقریب است . تابع  محدب و غیر نزولی است و برای  ، مقدار آن  است . همچنین، برخلاف  ، تابع  مشتق پذیر و بسته است .
با جایگذاری  به جای  در (۴-۲) تقریب زیر بدست می آید:
(۴-۳)
که در اینجا تابع هدف محدب و مشتق پذیر است.
تابع:
(۴-۴)
با  ، مانع لگاریتمی برای مسئله (۴-۱) نامیده می شود. این دامنه مجموعه ای از نقاطی است که محدودیت های نامساوی (۴-۱) را ایجاد می کند .
مسئله (۴-۳) تنها یک تقریب مسئله اصلی (۴-۲) است ، بنابراین یک سوال مطرح می شود که چگونه یک جواب (۴-۳) یک تقریب خوبی از جواب مسئله (۴-۲) است . نشان خواهیم داد که وقتی پارامتر t رشد می کند تقریب ها بهبود می یابند .
حال برای بررسی بیشتر جزئیات مسئله (۴-۳) نمادگذاری را ساده تر می کنیم . یعنی تابع هدف را در t ضرب می کنیم و مسئله هم ارز زیر را در نظر می گیریم:
(۴-۵)
فرض کنیم مسئله (۴-۵) با روش میرا شده نیوتن قابل حل است ، همچنین دارای جواب منحصر به فرد برای هر  است ؛ که برای  ،  را به عنوان جواب (۴-۵) تعریف می کنیم . مسیر مرکزی^[۲۹] در رابطه با مسئله (۴-۵) به عنوان مجموعه ای از نقاط  ،  ، تعریف می شود که نقاط مرکزی می نامیم که این نقاط باید بطور اکید شدنی باشند یعنی در شرایط اسلاتر صدق کنند .
۴-۲ روش مسیر تعقیب^[۳۰]
از نتایج توابع و موانع خود هماهنگ می‌توان اولین طرح نقطه درونی چند جمله‌ای زمان را بیان کنیم.