بخشی از مقاله
چکیده
در این مقاله یک روش برنامهریزی درجه دوم متوالی بر اساس ناحیه اعتماد را بررسی می کنیم که از معیار فیلتر به عنوان شرطی برای پذیرش یا ردکردن گام آزمایشی استفاده می کند. این روش از دو فیلتر استفاده می کند که یکی فیلتر استاندارد، برای همگرایی سراسری و دیگری فیلتر غیر یکنواخت موضعی که امکان سریع بودن همگرایی موضعی را مهیا می سازد. خاصیت ویژه این روش، نیاز نداشتن آن به گام های اصلاحی مرتبه دوم است. همچنین، این روش را با تکنیک تصویر گرادیان ترکیب کرده و برای حل مسایل برنامه ریزی غیر خطی به کار می گیریم. فواید این ترکیب را با مثال های عددی ارائه شده نشان می دهیم.
واژه های کلیدیْ بهینه سازی غیر خطی، فیلترSQP، فیلتر غیر یکنواخت، همگرایی سراسری، همگرایی موضعی.
-1 مقدمه
بهینه سازی یکی از اساسی ترین شاخه های ریاضیات به شمار می رود. مسایل بهینه سازی در زندگی روزمره فراوان یافت می شوند. بنابراین، تلاش برای حل این مسایل از دغدغه های اصلی دانشمندان به شمار می رود و روش های زیادی برای مسایل بهینه سازی معرفی شده اند. از آنجاییکه یافتن جوابهای دقیق برای چنین مسایلی بهطور کلی امکانپذیر نمیباشد، روشهای عددی برای یافتن جوابهای تقریبی متدوال است. مسایل بهینهسازی غیر خطی مقید در مقایسه با مسایل بهینه سازی نامقید از پیچیدگی بیشتری برخوردار میباشند. روشهای مختلفی برای حل این مسایل وجود دارد، از جمله این روش ها می توان به روشهای جستجوی خطی و ناحیه اعتماد اشاره کرد.
در این مقاله یک الگوریتم مبتنی بر فیلتر غیر یکنواخت بر اساس ناحیه اعتماد برای حل مسایل مقید غیر خطی که توسط فلچر، لیفر و شن1 ارایه شده است، را مورد بررسی قرار می دهیم. این الگوریتم از دو فیلتر استاندارد و موضعی برای همگرایی سراسری و موضعی سریع استفاده می کند. روش تصویر گرادیان را با این الگوریتم ترکیب میکنیم و برای حل مجموعهای از مسایل آزمون مقید به کار میگیریم.یکی از کاراترین روشها برای بهینه سازی غیر خطی تولید گامها با حل زیر مسالههای درجه دوم است. روش برنامهریزی درجه دوم متوالی2 SQP میتواند در هر دو شکل ناحیه اعتماد و جستجوی خطی بکار برده شود، همچنین این روش برای مسالههای کوچک و بزرگ مناسب میباشد.
وقتی روشهای SQP برای حل مسائلی که محدودیتهای غیرخطی قابل توجهی دارند بکار گرفته میشوند، کاراییشان مشخص میشود. در راستای این روشها، فلچر و لیفر روش برنامهریزی درجه دوم متوالی بر اساس ناحیه اعتماد را ارایه دادند که در آن، تکنیک فیلتر بهعنوان شرط پذیرش گامهای آزمایشی، بهجای تابع جریمه مورد استفاده قرار گرفت. تکنیکهای فیلتر به دلیل سختی تخمین پارامتر جریمه در روشهای تابع جریمه، در دهههای اخیر مورد استقبال قرار گرفتند. گنزاگا3 روش مبتنی بر فیلتری ارائه داد که در آن هر تکرار در دو فاز بهینگی و بازگرداندن شدنی محاسبه میشد 18]،14،.[1
-2 برنامهریزی غیرخطی بدون تابع جریمه
فلچر و لیفر در [12] یکی از اولین کارهای مربوط به استفاده از فیلتر را ارائه نمودند. الگوریتم برنامهریزی درجه دوم متوالی برای حل مسایل برنامهریزی غیرخطی در نظر گرفته شده است. هدف، ارائه روشی است که همگرایی سراسری را بدون استفاده از تابع جریمه بهدست میآورد. با استفاده از مفهوم »فیلتر« گامهایی که هر دو تابع هدف و تابع خطای محدودیت را کاهش میدهند، پذیرفته میشوند. بدون از دست دادن کلیت مساله، فرض کنید مساله برنامهریزی غیرخطی بهصورت زیر باشد.که در آن f : n و c : n m بهطور پیوسته دوبار مشتقپذیر هستند. هدف این روش رهایی از تابع پنالتی است.
مشروط به اینکه، یک الگوریتمی ارایه شود که نیازمند انتخاب سخت مانند انتخاب پارامتر جریمه نباشد. از آنجاییکه مشتق دوم قابل محاسبه هست، انتظار میرود که تحت بعضی فرضیات، همگرایی مرتبه دوم در نزدیکی جواب موضعی بهدست آید . به منظور بهدست آوردن همگرایی مرتبه دوم، یک تکرار نیوتن لازم است و در رابطه با برنامهریزی غیرخطی، روش برنامهریزی درجه دوم متوالی به عنوان یک روش تکراری پایه، جالبترین گزینه میباشد. اگر نقطه شروع دور از جواب انتخاب شود، ممکن است این روش به جواب موضعیP همگرا نشود.به همین دلیل، اکثر روشها برای بهدست آوردن همگرایی، از تابع جریمه که ترکیب خطی از تابع هدف و بعضی از اندازه خطای قیود میباشد، استفاده میکنند. فیلتر میتواند بهصورت شکل زیر نمایش داده شود که هر نقطه در آن، بلوکی از نقطههای غیر قابل قبول تولید میکند و اجتماع این بلوکها مجموعه نقاط غیر قابل قبول برای فیلتر میباشد.
-3 خاصیتهای الگوریتمی
- 1- 3 کران بالای تابع تخطی محدودیت ها
یک شرط لازم اضافی برای پذیرش گام آزمایشی تولید شده به صورت u h - c - x - - که در آن u یک کران بالا برای تابع تخطی محدودیتها میباشد، در نظر گرفته میشود. این شرط با وارد کردن زوج - ,u - به فیلتر اعمال میشود. با این کار از پذیرش دنبالهای ازنقطههایی که دارای - f - x k 1 - f - x k و - h - x k h - x k 1 - با h - x k - میباشند جلوگیری به عمل میآید. یکی دیگر از دلایل استفاده از شرط کران بالای تابع تخطی محدودیت ها، حل مشکل غیر قبول بودن نقطه بهدست آمده توسط فاز بازگرداندن برای فیلتر میباشد.
-2-3 فاز باز گرداندن شدنی
یک اثر ناخوشایند به کارگیری شیوههایی بر اساس این حالت ممکن است محدودیتهای خطیسازی شده، برای این کار تقریب خطی از محدودیتهای غیرخطی - ناحیه اعتماد، امکان نشدنی شدن مساله QP با کاهش شعاع ناحیه اعتماد میباشد که در خودشان نشدنی باشند. در مواجه با این وضعیت، فاز بازگرداندن شدنی به کار گرفته میشود. c - x را بهدست آورده و دنبالهای از زیر مسالههای برنامهریزی خطی LP حل میشود.بههنگام استفاده از این استراتژی، دو مشکل اساسی وجود دارد. برای جلوگیری از مجبور بودن به استفاده از حل کننده خاص LP ، فاز اول را برای حل این زیرمسالههای LP به کار گرفته میشود که این امر در بعضی مواقع بسیار ناکارآمد میباشد.
یکی دیگر از این مشکلات این است که به دلیلنداشتن مشتق مرتبه دوم، عمدتاً این فرآیند با همگرایی کندی صورت میگیرد. فرض، در طول روش SQP در تکرار kاُم زیر مساله QP نشدنی باشد. در اینصورت، فاز بازگرداندن شدنی مساله زیر را برای بهدست آوردن نقطه شدنی حل میکند.که در آن محدودیتها به دو مجموعه اندیس تقسیم شدهاند. مجموعه شامل اندیسهای محدودیتهای نشدنی کردن مجموع محدودیتهای c و مجموعه J c 1, 2, ..., m J اندیسهای محدودیتهای شدنی میباشد. هدف مساله - LP1 - کمینه نشدنی میباشد در حالیکه محدودیتهای دیگر همچنان شدنی باقی بمانند.
-4 حذف ورودیهای مسدود کننده از فیلتر
یکی از پیشامدهای ناخوشایند این است که وقتی مسالهP دارای جواب سراسری ** x و جواب موضعی بدتر4 x باشد آنگاه گرچه به اندازه کافی به x ** نزدیک میباشد ولی دنباله تکرارهای x k به x * همگرا میشوند. در این حالت اگر f * f 0 آنگاه ورودی فیلتر - - f 0 , h0 ازهمگرایی تکرار SQP به x جلوگیری میکند. به این ورودی فیلتر - - f 0 , h0 ، »ورودی مسدود کننده« گفته میشود که در شکل 2 نشان داده - x ورودیهای مسدود کننده را از فیلتر حذف میکنند. ممکن است حذف این ورودیها شده است. برای برطرف کردن این مشکل - همگرایی به باعث ایجاد دور شود - یعنی الگوریتم دوباره به x 0 برگردد - برای این کار، کران بالای u را به - max - hk u کاهش داده که در آن تخطی محدودیتها در نقطه جدیدی که وارد فیلتر شده است، میباشد. کاهش کران بالای محدودیت، مانند یک ورودی فیلتر با کرده و شرط کاهش کافی را تحمیل میکند. به همین دلیل از ایجاد دور، جلوگیری میشود.
