بنابراین پوسته مخروطی کوچکترین مخروط محدب شامل C است.

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

تعریف ۱-۱-۱۳: تابع نرم نامیده می شود ، هر گاه در شرایط زیر صدق کند :

و نیم نرم نامیده می شود اگر به ازای بردارهای غیر صفر ، صفر باشند .
تعریف ۱-۱-۱۳ : ماتریس مربعی حقیقی از مرتبه n را معین مثبت گوییم هرگاه :
الف) ماتریس A متقارن باشد .
ب) به ازای هر

همین طور ماتریس A را نیمه معین مثبت می نامیم هرگاه A متقارن باشد و

قضیه ۱-۱-۳ : فرض کنید معین مثبت باشد آن گاه A نامنفرد (معکوس پذیر) است [۵].
فصل ۲
توابع خود هماهنگ
در این فصل مفهوم تابع خود هماهنگ را بیان می‌کنیم. هدف، تعریف خانواده‌ای از توابع محدب و هموار مناسب جهت مینیمم سازی روش نیوتن است. برای یادآوری، یک گام روش نیوتن برای مسئله مینیمم سازی نامقید تابع محدب و هموار f را بیان می‌کنیم:
جهت یافتن تکرار نیوتن یک نقطه x، بسط تیلور مرتبه دوم f در x را محاسبه می‌کنیم، مینیمم مقدار (یعنی) را از این بسط را یافته و یک گام از x در راستای جهت اجرا می‌کنیم.
دو کاستی عمده در تجزیه و تحلیل همگرایی روش کلاسیک نیوتن وجود دارد. اولین کاستی از لحاظ عملی است ، برآورد پیچیدگی به عدد حالت هسین f و ثابت لیپ شیتز هسین آن وابسته است و در این صورت نمی توان تعداد گام های مورد نیاز را بدست آورد ؛ زیرا این ثابت ها به طور کلی ناشناخته اند.
دومین نقطه ضعف این است که در حالی که روش نیوتن مستقل آفینی است اما تجزیه و تحلیل کلاسیک روش نیوتن بسیار وابسته به مختصات استفاده شده درسیستم می باشد و با تغییر مختصات ، گرادیان وهسین نسبت به تبدیلات ثابت باقی نمی مانند ( ثابت لیپ شیتز و عدد حالت ماتریس هسین ) . در واقع توصیف کلاسیک روش تنها به تابع هدف وابسته نیست ، بلکه به انتخاب ساختار اقلیدسی استفاده شده بستگی دارد و متضاد با مستقل آفینی روش است.
بنابراین باید به دنبال تجزیه و تحلیل روش نیوتنی باشیم که مشابه روش خودش ، مستقل آفینی از تغییرات مختصات باشد. برای حل این مشکل ، توجه کنید که تابع هدف در هر نقطه x ساختار اقلیدسی را ایجاد می کند . برای تعریف این ساختار ، مشتقات مرتبه دوم f در x و در راستای جهت های g, h به عنوان ضرب داخلی بردار های g,h استفاده می کنیم :

چونf محدب است، ضرب داخلی همه خواص مورد نیاز را دارد. البته ساختار اقلیدسی محلی وابسته به x است. توجه کنید که ماتریس هسین f درx نسبت به ساختار اقلیدسی خوب است، یعنی ماتریس واحد است و عدد حالت آن یک است. نتایج کلاسیک روش نیوتن می‌گوید آنچه برای ما مهم است علاوه بر عدد حالت، ثابت لیپ شیتز ماتریس هسینf یا اندازه مشتقات مرتبه سومf است. حال چه اتفاقی می‌افتد اگر مقدار دوم را به ساختار اقلیدسی محلی که توسطf تعریف می‌شود وابسته کنیم؟ این کلید مفهوم خود هماهنگ است که توسط نستروف و نمیروسکی کشف شد.
۲-۱ تابع خودهماهنگ
قبل از تعریف توابع خود هماهنگ ، چند دلیل اهمیت آن ها را بیان می کنیم:

• • آن ها شامل توابع مانع لگاریتمی هستند که نقش مهمی در روش نقطه درونی برای حل مسایل بهینه سازی محدب دارند .

• • تجزیه و تحلیل روش نیوتن توابع خود هماهنگ به ثابت های ذکر شده وابسته نیست .

• • خود هماهنگی خاصیت مستقل آفینی را دارد، یعنی اگر یک تبدیل خطی از متغیر های تابع خود هماهنگ را در نظر بگیریم یک تابع خود هماهنگ بدست می آوریم. بنابراین برآورد پیچیدگی برای روش نیوتن به وسیله تابع خود هماهنگ ، مستقل از تغییرات آفینی مختصات است .

تعریف۲- ۱ -۱ : اگر Q مجموعه‌ای محدب، باز و ناتهی در باشد وF یک تابع محدب و هموار از مرتبه سوم که روی Q تعریف می‌شود .تابع F خود هماهنگ^[۱۸] روی Q نامیده می‌شود اگر دارای ۲ خاصیت زیر باشد:
خاصیت مانع: در راستای هر دنباله که همگرا به نقاط مرزی Q است.

نامساوی دیفرانسیلی خود هماهنگ: F در رابطه زیر صدق کند.
(۲-۱)
به ازای هر و . [۲]
یادآوری : مشتق k ‌ام F درx در راستای جهت‌های به صورت زیر است .

ممکن است سوال کنید چرا ثابت ۲ را در نظر می‌گیرید (چه جادویی در ۲ است)؟
جواب: در واقع این ثابت برای راحتی انتخاب شده است، به عبارت دیگر برای ساده کردن فرمول های بعد از آن است و هر ثابت مثبت دیگری می توان به جای آن استفاده کرد. به عنوان مثال ، فرض کنیم تابع F که در رابطه زیر صدق کند:

با ثابت مثبت . می‌توانید ضریب را در نظر بگیرید و ببینید که در رابطه (۲-۱) صدق می‌کند پس انتخاب ضریب در (۲-۱) هیچ اهمیتی ندارد. این انتخاب نشان می‌دهد که انگیزه‌ای برای ساخت تابع است که نقش مهمی برای برآورد کردن رابطه (۲-۱) بدون هیچ مقیاسی دارد.
مثال۲-۱-۱: یک تابع محدب و مرتبه دوم به شکل روی (به خصوص شکل خطی روی ) خود هماهنگ است.
واضح است زیرا طرف چپ رابطه (۲-۱) همواره صفر است (مشتق سوم برابر صفر است) .
مثال ۲-۱-۲ : تابع روی خود هماهنگ است

۲-۲ ترکیب قواعد اولیه
تعداد مثال‌ها را می‌توان به راحتی با بهره گرفتن از قوانین ترکیبی ساده زیر افزایش داد:
گزاره ۲-۲-۱. الف) ]ثبات نسبت به تعویض آفینی آرگومان[
اگر Fروی خود هماهنگ باشد و آن‌گاه نیز خود هماهنگ است.
ب) ]ثبات نسبت به ضرب و جمع[ اگر ‌ها توابع خود هماهنگ روی دامنه‌های محدب باشند و حقیقی فرض کنیم ناتهی است . آن‌گاه تابع

خود هماهنگ است.
ج) ]ثبات نسبت به جمع مستقیم[ اگر ‌‌ها روی دامنه‌های محدب و باز خود هماهنگ باشند ، آن‌گاه تابع

خود هماهنگ است.
برهان: با بهره گرفتن از تعریف ثابت می‌شود. برای نمونه، قسمت (ب) را ثابت می‌کنیم. چون ‌ها دامنه محدب و باز با اشتراک غیرتهی Q است پس، Qیک دامنه محدب و باز است. علاوه بر اینF روی Q، محدب و هموار است، برای اثبات خاصیت مانع ، چون ‌ ها محدب هستند ، از پایین روی هر زیر مجموعه کراندارQ ، کراندارند. این نشان می‌دهد که اگر دنباله همگرا به نقاط مرزی Q باشد آن‌گاه همه دنباله های از پایین کراندار است و حداقل یکی از آن‌ها واگراست (چونx به مرز یکی از مجموعه‌های متعلق است) پس .
برای اثبات (۲-۱) نامساوی‌های زیر را اضافه می‌کنیم: