در نتیجه
(۴-۲۵)
چون خود هماهنگ است و داریم :

(فصل ۲-رابطه (۲-۱۶)) بنابراین :

(۴-۲۶)
از (۴-۱۳) داریم :

که از ترکیب این نامساوی و (۴-۲۵) و (۴-۲۴) به رابطه (۴-۱۹) می‌رسیم . □
حال می‌توانیم اثبات گزاره ۴-۲-۲ را کامل کنیم با بهره گرفتن از رابطه (۴-۹) که می رسیم به :

سمت چپ نامساوی از بالا در که به وسیله تابعی معین وابسته به κ و γ کراندار است . □
قضیه زیر به عنوان یک نتیجه از گزاره‌های ۴-۲-۱ و ۴-۲-۲ است.
قضیه ۴-۲-۱ : فرض کنیم P مسئله با دامنه محدب و بسته باشد به روش مسیر تعقیب با مانع ϑ-خود هماهنگ حل می‌شود به ترتیب معیار مجاز مسیر و پارامتر جریمه در مسیر می‌باشند و جفت شروع کننده هستند که در میزان نزدیکی صدق می‌کند. آن گاه خطای مطلق از تقریب جواب‌های تولیده شده روش نشان می‌دهد که از بالا کراندار است:
(۴-۲۷)
و پیچیدگی نیوتن هر تکرار روش از ثابت معین N ی که به κو γ وابسته است، تجاوز نمی‌کند. پیچیدگی نیوتن (مجموع تعداد گام‌های نیوتن) یافتن یک ε-جواب مسئله، یعنی یافتن به طوری که از بالا توسط عبارت زیر کراندار است:

با فاکتور ثابت که به κ و γ وابسته است .
۴-۲-۴ مقداردهی اولیه و روش دوفازی مسیر تعقیب
توضیحات فوق از روش کامل نیست . هدف یافتن مسیر و نزدیک شدن به آن در گام اول است. اما هنوز نمی‌دانیم چگونه برای شروع ردیابی باید به مسیر نزدیک شویم. چندین راه برای مشکل مقداردهی اولیه وجود دارد . ساده‌ترین راه به شرح زیر است :
می‌دانیم که مسیر هدف است، که وقتی همه نقطه‌های مسیر به مجموعه بهینه مسئله تعلق دارد. شروع مسیر جایی است که .

مسیر فوق وقتی به مرکزG نسبت به F میل می‌کند، یعنی مینیمم مقدار F ( ) روی G است(چون G کراندار است و از قسمت ۶ ، فصل ۳ می‌دانیم که مینیمم مقدار وجود دارد و منحصر به فرد است) . بنابراین همه مسیرهای F-تولید مرتبط با هدف های متفاوت c ، در همان نقطه شروع می‌شود. از مرکزG وقتی به سمت هر مجموعه بهینه مرتبط با تابع هدف حرکت می‌کند . به عبارت دیگر، مرکزG به همه مسیرهای F-تولید نزدیک است . بنابراین یک موقعیت خوب برای شروع مسیر مورد نظر است . حال چگونه به این موقعیت برسیم؟
یک ایده بدین شرح است . مسیرهای مرتبط با هدف‌های متفاوت ، همه نقاط درونی G را می‌پوشانند اگر یک نقطه درونی G باشد آن گاه مسیر گذرنده از x توسط هر هدف به شکل زیر است:

مثبت است . مقداردهی اولیه به صورت زیر است :
نقطه شروع داده شده است ، مسیر ساخته شده زیر را در معکوس زمان دنبال می‌کنیم :

یعنی کاهش پارامتر جریمهτ بهتر از افزایش آن است، این مسیر از نقطه می‌گذرد:

می‌توانیم ردیابی آن را با جفت آغاز کنیم که دقیقا در مسیر است وقتی این گونه به مسیر تعقیب می‌پردازیم، در زمان متوسط نزدیک مرکزG می‌شویم، در نتیجه مسیر ، مسیر مورد نظر است.
روش دو فازی مسیر تعقیب :
ورودی : نقطه شروع ، معیار مجاز مسیر و نرخ جریمه .
فاز یک : ]تقریب مرکز[ با شروع می‌کنیم. دنباله ی تولید می‌شود و به روزرسانی به به صورت زیر است :

    • قرارمی دهیم :
    • رسیدن به با بهره گرفتن از تابع

روش میراشده نیوتن را با شروع می‌کنیم

روش متوقف می‌شود وقتی که در گزاره زیر صدق می‌کند :
(۴-۲۸)
آن گاه قرار می‌دهیم:

    • بعد از اینکه تشکیل شد، نامساوی زیر را بررسی می‌کنیم:

(۴-۲۹)
در این صورت، فاز یک به پایان می‌رسد و نتیجه فاز است ، در غیر این صورت به گام بعدی فاز یک می‌رویم .
مقدار دهی اولیه فاز دو : نتیجه فاز یک داده شده است ، قرار می‌دهیم :
(۴-۳۰)

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...