تحقیقات انجام شده در مورد روش های نقطه درونی برای بهینه سازی۹۲- فایل ۸ |
نمونههای اولیه از موانع خود هماهنگ را بیان میکنیم.
مثال۳-۱-۱: تابع ثابت، مانع خود هماهنگ برای با پارامتر صفر است. میتوان ثابت کرد تابع ثابت تنها مانع خود هماهنگ برای همه فضاهاست، و تنها مانع خود هماهنگ با مقدار پارامتر کمتر از ۱ است.
توجه کنید تابع خطی و درجه دوم محدب که تابع خود هماهنگ روی همه فضاهاست لزوما یک مانع خود هماهنگ نمیباشد.
مثال ۳-۱-۲: تابع یک مانع خود هماهنگ با پارامتر ۱ روی محور نامنفی هاست. تعداد مثالها را با بهره گرفتن از قواعد ترکیبی و ساده زیر میتوان افزایش داد (مشابه توابع خود هماهنگ):
گزاره۳-۱-۱. الف) (ثبات نسبت به تعویض آفینی آرگومان) فرض کنیمF ، مانع ϑ-خود هماهنگ برای باشد آنگاه تابع نیز یک مانع ϑ- خود هماهنگ است.
ب) (ثبات نسبت به جمع و ضرب با مقادیر حقیقی ) اگر ها، موانع ϑ-خود هماهنگ برای دامنههای محدب و بسته باشد و حقیقی باشد ، . فرض کنیم که فضای درونی ناتهی دارد . آنگاه تابع
مانع - خود هماهنگ برایG است.
ج) (ثبات نسبت به جمع مستقیم) اگر موانع - خود هماهنگ برای دامنههای محدب و بسته باشند ، آنگاه تابع
مانع - خود هماهنگ برایG است.
برهان: به راحتی از تعریف قابل اثبات است. به عنوان مثال (ب) را ثابت میکنیم با توجه به گزاره ۲-۱-۱- (ب) میدانیم که F روی خود هماهنگ است و
( چون ها موانع -خود هماهنگاند )
( با بهره گرفتن از نامساوی کوشی )
□.
یک نتیجه که از قواعد ترکیبی میتوان گرفت در زیر آمده است :
نتیجه ۳-۱-۱ : اگر یک چند وجهی محدب که توسط نامساویهای خطی که در شرایط اسلاتر صدق میکنند، تعریف شده باشد:
مانع لگاریتمی استاندارد G به صورت زیر، مانعm-خود هماهنگ برایG است.
برهان: تابع ، مانع ۱-خود هماهنگ روی محور مثبتها میباشد (مثال ۳-۱-۲) بنابراین هر تابع مانع ۱-خودهماهنگ برای نیم فضای بسته است (قسمت الف- گزاره ۳-۱-۱)، بنابراین ، مانعm -خود هماهنگ روی اشتراک این نیم فضاهاست (قسمت (ب) گزاره ۳-۱-۱) .□
این نتیجه، مسئول ۱۰۰% چند جملهای زمان برنامه ریزی خطی است.
حال به بررسی خواص مانع خود هماهنگ میپردازیم.
۳-۲. خواص موانع خود هماهنگ
فرض کنیم G دامنه ی محدب و بسته در باشد، وF مانع ϑ-خود هماهنگ G باشد.
تعریف۳-۲-۱ : تابع مینکوفسکی یک دامنه محدب:
یک نقطه درونی ازG مانند x داده شده است، تابع مینکوفسکی G به صورت زیر تعریف میشود:
به عبارت دیگر، برای یافتن ، شعاع را در نظر بگیرید می بینیم که این پرتوهای متقاطع مرز G هستند، اگر از این تقاطعها وجود داشته باشد، آنگاه طول پاره خط است که توسط طول پاره خط تقسیم شده است. اگر شعاع درون G باشد آنگاه . توجه کنید تابع مینکوفکسی محدب، پیوسته و همگن مثبت است:
هم چنین درx ، صفر است، درون G کوچکتر مساوی ۱ است ؛ روی مرزG ، برابر ۱ و خارج G بزرگتر از ۱ است . این تابع در حقیقت برای عبارتهای آفینی تعریف شده است .
۱) فرض کنیم و y به گونهای باشد که ، آنگاه
(۳-۲)
پس نقطه یک نقطه درونی G نمیباشد.
برهان: فرض کنیم
که بزرگترین نیم فاصله از شعاع است به طوری که هرگاه . توجه کنید تابع Φ به طور پیوسته مشتق پذیر از مرتبه ۳ روی Δ است و
(۳-۳)
(از تعریف تابع مینکوفسکی و در اینجا )
چون F ، مانع ϑ-خود هماهنگ G است (از گزاره ۳-۱-۱- قسمت الف) داریم:
یا
(۳-۴)
که . توجه کنید که مثبت است و با توجه فرض، Ψ غیرنزولی است (به عنوان مشتق یک تابع محدب) ، بنابراین روی ∆ مثبت است و از (۳-۴) و رابطه داریم . با بهره گرفتن از رابطه دوم میتوان رابطه (۳-۴) را بازنویسی کرد:
که
(۳-۵)
سمت چپ رابطه فوق روی هر پاره خط کراندارست ، و داریم:
که و در نهایت به (۳-۲) میرسیم .□
۲) نیمه کرانداری : به ازای هر و داریم :
(۳-۶)
۳)کران بالایی: اگر باشد آنگاه
فرم در حال بارگذاری ...
[شنبه 1400-08-22] [ 03:14:00 ب.ظ ]
|