بهینه سازی غیرخطی Nonlinear Optimization
اسلاید 1: بهینهسازی غیرخطی
اسلاید 2: فهرستساختار کلی مسائل بهینهسازیروشهای حل مسائل بهینهسازیروش نیوتن (Newton) در حالت تکمتغیرهروش خط قاطع ( secant) در حالت تکمتغیرهروش نیوتن برای کمینهکردن در حالت تکمتغیرهروش نیوتن در حالت چندمتغیرهبهینهسازی نامقیدروشهای تکراری شبه نیوتن ( quasi-Newton)بهینهسازی مقید با قیود تساویبهینهسازی مقید با قیود نامساوی
اسلاید 3: فهرستبرنامهریزی درجه دوم ( Quadratic Programming)توابع شایستگی ( Merit Functions) جستجوی خط ( Line Search)فیلترها Filters)ناحیه اطمینان ( Trust Region)برنامهریزی درجه دوم متوالی (( Sequential Quadratic Programming)برنامهریزی درجه دوم متوالی ( SQP)نقطه درونی ( Interior point)برخی اشکالات در تعریف مسائل بهینهسازی
اسلاید 4: ساختار کلی مسائل بهینهسازیاجزای تشکیلدهنده مسائل بهینهسازیـ متغیرهای بهینهسازی (Optimization Variables)ـ تابع هدف اسکالر (Objective Function)ـ قیود تساوی و نامساوی (Equality and Inequality Constraints)ـ محدودیتها (Bounds)
اسلاید 5: ساختار کلی مسائل بهینهسازینکاتی درخصوص مسائل بهینهسازیـ توابع هدف و قیود مسائل بهینهسازی، عبارات جبری میباشند که بسته به خطی یا غیرخطی بودن آنها، خطی یا غیرخطی بودن کلیت مسئله مشخص میشود.ـ با توجه به مسئله بهینهسازی تعریف شده، متغیرهای بهینهسازی میتوانند در حوزه خاصی از اعداد (حقیقی، صحیح و غیره) تعریف شوند.ـ خروجی تابع هدف، یک عدد (اسکالر) میباشد. برای بهینهسازی چندهدفی، باید اهداف مختلف با بهرهگیری از ضرایب وزنی متفاوت در قالب یک تابع اسکالر تعریف گردند:ـ متغیرهای بهینهسازی بسته به مسئله، میتوانند دارا یا فاقد محدودیت از بالا و پایین باشند. ـ محدودیتها همانند قیود نامساوی عمل میکنند.
اسلاید 6: ساختار کلی مسائل بهینهسازیمثالمتغیرهای بهینهسازیتابع هدفمحدودیتهاقید نامساوی
اسلاید 7: روشهای حل مسائل بهینهسازیروشهای حل مسائل بهینهسازی به دو دسته اصلی تقسیم میشوند:ـ روشهای مبتنی بر شیب (Gradient Methods)ـ روشهای جمعیتی (Population Methods)روشهای مبتنی بر شیبـ با بهره‌گيري از مشتقات متغيرها به حل بهينه دست مي‌يابند. ـ داراي ساختاري پيچيده به منظور بهره‌گيري از مشتقات متغيرها مي‌باشند.ـ به سرعت قادر به همگرايي و دستيابي به حل دقيق بهينه هستند. ـ مشكل عمده اين روش‌ها، توقف در نقاط كمينه محلي مي‌باشد. ـ با بهرهگیری از برخی روش‌ها، میتوان از توقف در کمینههای محلی اجتناب نمود.
اسلاید 8: روشهای جمعیتی (ابتکاری ـ مکاشفهای)ـ بدون بهره‌گيري از مشتقات و صرفاً با روابط جبري ساده به حل بهينه دست مي‌يابند. ـ به دليل عدم استفاده از مشتقات، ساختار ساده‌تري دارند و پياده‌سازي آنها آسان‌تر است.ـ فرآیند حل در آنها به شدت زمان‌بَر بوده و منجر به پاسخ‌هاي گوناگوني مي‌شود.ـ از قابليت‌هاي قابل‌توجه اين روش‌ها، امكان تعيين نقاط كمينه سراسري مي‌باشد. ـ عموماً از طبيعت الهام گرفته شده‌اند و از رويکرد‌هاي جالب‌توجهي بهره مي‌برند. روشهای حل مسائل بهینهسازیروشهای حل مسائل بهینهسازی به دو دسته اصلی تقسیم میشوند:ـ روشهای مبتنی بر شیب (Gradient Methods)ـ روشهای جمعیتی (Population Methods)
اسلاید 9: روشهای مبتنی بر شیبـ برنامه‌ريزي خطيـ برنامه‌ريزي غيرخطي ـ برنامه‌ريزي صحيح ـ برنامه‌ريزي درجه‌دو ـ برنامه‌ريزي تصادفي ـ برنامه‌ريزي مقاومـ ...روشهای حل مسائل بهینهسازیروشهای جمعیتیـ الگوريتم ژنتيک ـ تبرید شبيه‌سازي‌شده ـ ازدحام ذرات ـ جستجوي ممنوعهـ لانه‌يابي مورچهـ لانهیابی زنبور عسلـ ...
اسلاید 10: روشهای حل مسائل بهینهسازیبرنامهریزی غیرخطی (Non-Linear Programming)ـ به مجموعهای از روشهای مبتنی بر شیب که برای حل مسائل بهینهسازی غیرخطی مورد استفاده قرار میگیرند، برنامهریزی غیرخطی (NLP) میگویند.ـ برنامه‌ريزي غيرخطي در لغت برابر با بهينه‌سازي غيرخطي مي‌باشد. عبارت «برنامه‌ريزي» به معناي «برنامه‌نويسي رايانه‌اي» نمي‌باشد، بلكه به معناي «رويه‌هاي طرح‌‌ريزي و اجرا» است.ـ اساس و مبنای تمام روشهای برنامهریزی غیرخطی، روش نیوتن میباشد.
اسلاید 11: روش نیوتن (Newton) در حالت تکمتغیرهبا استفاده از روش نیوتن، میتوان ریشه یک معادله غیرخطی را تعیین نمود:مبنای روش نیوتن برای تعیین ریشه، تقریب معادله غیرخطی c(x) با دو عبارت اول سری تیلور حول مقدار کنونی x میباشد:اگر بخواهد ریشه معادله غیرخطی c(x) باشد، باید باشد: مقدار جدیدی است که با حرکت از مقدار x در راستای شیب معادله بدست میآید.
اسلاید 12: روش نیوتن (Newton) در حالت تکمتغیرهچون معادلـه c(x) غیرخطی است، نمیتوان انتظار داشت که با یکبـار حرکت در راستـای شیب، بتوان به ریشه معادله رسید. اما میتوان انتظار داشت که مقدار نسبت به مقدار به ریشه واقعی معادله ( ) نزدیکتر باشد: برایناساس، میتوان با بهرهگیری از رابطه نیوتن در قالب یک فرآیند تکراری، گام به گام به ریشه واقعی معادله غیرخطی نزدیکتر شد:این فرآیند تا جایی ادامه مییابد که تا حد مطلوب به صفر نزدیک گردد.
اسلاید 13: روش نیوتن (Newton) در حالت تکمتغیرهx(0)x(1)x(2)xc(x)اگر معادله غیرخطی چند ریشه داشته باشد، بسته به مقدار اولیه انتخابی، روش نیوتن به یکی از ریشهها همگرا خواهد شد.
اسلاید 14: مثالروش نیوتن (Newton) در حالت تکمتغیرهIterc(x)x1 0.75258256189040.52-0.93282017950411.112141637097303-0.13875403935060.909672693736814-0.00539399804130.867263818208825-9.3331063520941e-0060.865477135298266-2.8106184046806e-0110.865474033110967 1.1102230246252e-0160.86547403310161
اسلاید 15: مثالروش نیوتن (Newton) در حالت تکمتغیره
اسلاید 16: روش خط قاطع (secant) در حالت تکمتغیرهدر این روش، بجای محاسبه مشتق معادله غیرخطی، از تقریب خطی آن استفاده میشود:ـ فرآیند حل در این روش، با دو مقدار اولیه شروع میشود.ـ این روش، برای حل معادلاتی توصیه میشود که محاسبه مشتق آنها دشوار باشد.
اسلاید 17: x(0)x(1)x(2)xc(x)روش خط قاطع (secant) در حالت تکمتغیرهx(3)اگر معادله غیرخطی چند ریشه داشته باشد، بسته به مقادیر اولیه انتخابی، روش خط قاطع به یکی از ریشهها همگرا خواهد شد.
اسلاید 18: مثالIterc(x)x(k-1)x(k)1 0.75258256189040.40.52-1.47395023633930.51.220323368826903 0.32516375166071.220323368826900.743473981938324 0.10404876115860.743473981938320.829657590454505-0.01432151866350.829657590454500.870212496650256 0.00050607320350.870212496650250.865305793321917 2.321132476335e-0060.865305793321910.865473261586098-3.791308378354e-0100.865473261586090.865474033227639 4.440892098501e-0160.865474033227630.86547403310161روش خط قاطع (secant) در حالت تکمتغیره
اسلاید 19: روش نیوتن برای کمینهکردن در حالت تکمتغیرهبا استفاده از روش نیوتن، میتوان مقدار کمینه یک معادله غیرخطی را نیز تعیین نمود.برای این کار لازم است تا تقریب معادله غیرخطی F(x) با سه عبارت اول سری تیلور حول مقدار کنونی x در نظرگرفته شود:در یافتن ریشه، دو عبارت اول سری تیلور درنظرگرفته شد، چون تقریب خطی برای یافتن ریشه کفایت میکرد. اما برای کمینهکردن، تقریب خطی کفایت نمیکند، چون یک خط، مقدار کمینه ندارد.
اسلاید 20: روش نیوتن برای کمینهکردن در حالت تکمتغیرهاگر بخواهد کمینه معادله غیرخطی F(x) باشد، باید شرط زیر برقرار گردد:همانگونه که از معادلات فوق قابل مشاهده است، کمینه کردن با روش نیوتن، همان یافتن ریشههای مشتق معادله غیرخطی با روش نیوتن میباشد.باید توجه داشت که ریشه مشتق یک معادله میتواند مقدار کمینه، بیشینه یا عطف باشد. بسته به تقعر منحنی (مشتق دوم) در مقدار ریشه، میتوان نوع آن را تشخیص داد.
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.