مقاله رایگان با موضوع تعریف خانواده و پیچیدگی

دانلود پایان نامه

تابع محدب، سره و بسته f روی داده شده است که مقادیرش روی محور حقیقی قرار گرفته است (سره مربوط به دامنه تابع f (dom f) می شود یعنی مجموعه ای ناتهی که در آن f متناهی است. بسته یعنی اپی گراف تابع f بسته است) . مزدوج آن به صورت زیر تعریف می شود (تبدیل لژاندر):
که تابعی بسته، محدب و سره است و .
فرض کنیم توابعی محدب، بسته و سره روی باشند بطوری که فضای درونی دامنه تابع یک نقطه مشترک داشته باشند (درونی نسبت به پوسته های آفین دامنه هاست). قضیه دوگانگی فنچل بیان می کند که اگر تابع از پایین کراندار باشد، آنگاه:
(1-5) مسئله زیر را دوگان فنچل برای مسئله می نامیم:
تعریف 1-1-11: مجموعه ای از همه ترکیبات آفین از نقاط مجموعه ی پوسته آفین از C نامیده می شود و با affC نمایش می دهیم:
پوسته ی آفین کوچکترین مجموعه آفین شامل C می باشد ، به این معنی که اگر S مجموعه ای آفین باشد که پس .
تعریف 1-1-12: پوسته مخروطی مجموعه C، مجموعه ای از تمام ترکیبات مخروطی نقاط واقع در C است. یعنی:
بنابراین پوسته مخروطی کوچکترین مخروط محدب شامل C است.
تعریف 1-1-13: تابع نرم نامیده می شود ، هر گاه در شرایط زیر صدق کند :
و نیم نرم نامیده می شود اگر به ازای بردارهای غیر صفر ، صفر باشند .
تعریف 1-1-13 : ماتریس مربعی حقیقی از مرتبه n را معین مثبت گوییم هرگاه :
الف) ماتریس A متقارن باشد .
ب) به ازای هر
همین طور ماتریس A را نیمه معین مثبت می نامیم هرگاه A متقارن باشد و

این مطلب مشابه را هم بخوانید :   پایان نامه درباره مشکلات اجتماعی و دفاع از مظلوم

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