بهینه سازی غیرخطی Nonlinear Optimization

صفحه 1:
IEE, 

صفحه 2:
* ساختار کلی مسائل بهینهسازی * روشهای حل مسائل بهینهسازی * روش نیوتن (6۷۷0۲۱!) در حالت تکمتغفیره ۰ روش خط قاطع ‎(secant)‏ در حالت تکمتغیره * روش نیوتن برای کمینهکردن در حالت تکمتفیره روش نیوتن در حالت چندمتفیره * بهینهسازی نامقید * _روشهای تکراری شبه نیوتن ( 017 لالاع0١!-أ35لا|0)‏ * بهینهسازی مقید با قیود تساوی * بهینهسازی مقید با فیود نامساوی 

صفحه 3:
* برنامهریزی درجه دوم ( ۳۲۳۵9۲3۲۳۳0369 ‎(Quadratic‏ (Merit Functions ) St als * (Line Search ) b+ ‏*؟ جستجوى‎ (Filters ‏فيلترها‎ * * ناحیه اطمینان ( 86910۳ کلا۳۲آ) * برنامهریزی درجه دوم متوالی (( 0030۲216 اومعنبا0ع5 ‎(Programming‏ برنامهریزی درجه دوم متوالی ( 500۳) (Interior point) ‏نقطه درونى‎ * *_برخی اشکالات در تعريف مسائل بهينهسازى 

صفحه 4:
Optimization) ‏متغیرهای بهینهسازی‎ a (Variables minimize F(x) Objective) JS! ‏تابع هدف‎ - Equality and Inequality) ¢<¢ slut ‏ناور‎ ci) aia ‏ماه‎ ‎exy=| 2 |=0 ex=| : [20 €m(X) >) -محدودیتها (06ا0ظ) ۷۸ > ۷ > ,۲ 

صفحه 5:
- توابع هدف و قیود مسائل بهینهسازی عبارات جبری میباشند که بسته به خطی یا غیرخطی بودن آنهاء خطی یا غیرخطی بودن کلیت مسئله مشخص میشود. با توجه به مسئله بهینهسازی تعریف شده. متغیرهای بهینهسازی میتوانند در حوزه خاصی از اعداد (حقیقی؛ صحیح و غیره) تعر یف شوند. خروجی تابع هدف. یک عدد (اسکالر) میباشد. برای بهینهسازی چندهدفی, بايد اهداف مختلف با بهرهگیری از ضرایب وزنی متفاوت در قالب یک تابع اسکالر تعریف گردند: ...+ ور + هکره + ‎Fx) = wR)‏ -متغیرهای بهینهسازی بسته به مسئله میتوانند دارا یا فاقد محدودیت از بالا و پایین باشند. - محدودیتها همانند قیود نامساوی عمل میکنند. 

صفحه 6:
را مثال 9 5 %|_ متغیرهای و« بهینهسازی تابع مدق ود + و محدودیتها قید ناساوی 320 :39+ 

صفحه 7:
‎aca abmeane seal Ce aa‏ تا ‏0000 ‏روشهاى حل مسائل بهينهسازى به دو دسته اصلى تقسيم ميشوند: - روشهاى مبتنى بر شيب (1/1611005 07803614) ‎ ‏روشهاى جمعيتى (1/16112005 907111361011) ‎ ‏- با بهرهكيرى از مشتقات متغيرها به حل بهينه دست مى يابند. دارای ساختاری پیچیده به منظور بهره گیری از -به سرعت قادر به همگرایی و دستیابی به حل دقیق بهینه هستند. - مشکل عمده این روش‌هاء توقف در نقاط کمینه محلی می‌باشد. با بهرهگیری از برخی روشهاء میتوان از توقف در کمینههای محلی اجتناب نمود. ‎ ‏ات متغیرها می‌باشند. 

صفحه 8:
‎aca abmeane seal Ce aa‏ تا ‏0000 ‏روشهاى حل مسائل بهينهسازى به دو دسته اصلى تقسيم ميشوند: - روشهاى مبتنى بر شيب (1/1611005 07803614) ‎ ‏روشهاى جمعيتى (1/16112005 907111361011) ‎ ‏- بدون بهرهكيرى از مشتقات و صرفاً با روابط جبرى ساده به حل بهينه دست مى يابند. - به دليل عدم استفاده از مشتقات؛ ساختار ساده‌تری دارند و پیاده‌سازی آنها آسان‌تر است. ‎ ‏-فرآیند حل در آنها به شدت زمانیر بوده و منجر به پاسخ‌های گوناگونی می‌شود. - از قابلیت‌های قابل توجه این روش‌هاء امکان تعیین نقاط کمینه سراسری می‌باشد. -عموماً از طبیعت الهام گرفته شده‌اند و از رویکردهای جالب توجهی بهره می‌برند. 

صفحه 9:
روشیای حل مسائل بپینسازی -برنامه‌ریزی خطی الگوریتم ژنت -برنامه‌ریزی غیرخطی - تبرید شبیه‌سازی‌شده -برنامه‌ریزی صحیح ازدحام ذرات -برنامه‌ریزی درجه‌دو - جستجوی ممنوعه -برنامه‌ریزی تصادفی لانهيابى مورجه -برنامه‌ریزی مقاوم - لانهيابى زنبور عسل 

صفحه 10:
روشیای حل مسائل بپینسازی -به مجموعهای از روشهای مبتنی بر شیب که برای حل مسائل بهینهسازی غیرخطی مورد استفاده قرار میگیرنده برنامهریزی غیر خطی (101.۳) میگویند. -برنامه‌ریزی غیرخطی در لغت برابر با بهینه‌سازی غیرخطی می‌باشد. عبارت «برنامه‌ریزی» به معنای «برنامه‌نویسی رایانه‌ای» نمی‌باشده بلکه به معنای «رویه‌های طرح‌ریزی و اجرا؛ است. -اساس و مبنای تمام روشهای برنامهریزی غیرخطی؛ روش نیوتن میباشد. 

صفحه 11:
ce) =0 با استفاده از روش نيوتن» ميتوان ريشه یک معادله غیرخطی را تعیین نمود: مبنای روش نیوتن برای تعبین ريشه» تقريب معادله غيرخطى (6)3 با دو عبارت اول سری تيلور حول مقدار كنونى 36 ميباشد: c(&) = c(x) +e'(x)(F — x) ex) =de/dx ‏#مقدار جدیدی است که با حر کت از مقدار ۲ در راستای شیب معادله بدست میآید.‎ ‏باید 0 < (0 باشد:‎ ab Ox) ‏بخواهد ريشه معادله غیرخطی‎ رگا‎ ۱( عم معدم !الم مدع 

صفحه 12:
‎9s (Newton)‏ حالت 0000 ‏چون معادله 6620 غیرخطی است. نمیتوان انتظار داشت که با یکبار حرکت در راستای ‎ ‏شیب بتوان به ريشه معادله رسید. اما میتوان انتظار داشت که مقدار آسبت به مقدار "یه * ریشه واقعی معادله ( *) نزدیکتر باشد: الجاع > اهما اد ندز ک | | برايناساسء ميتوان با بهرهكيرى از رابطه نيوتن در قالب يكك فرآيند تکراری» كام به كام به ريشه واقعى معادله غيرخطى نزديكتر شد: ‎GHD 7 ‎ ‏اين فرآيند تا جابى ادامه مبيايد كه (6)5 حد مطلوب به صفر نزديكك كردد. 

صفحه 13:
ن (16۷/0۲) در حالت اگر معادله غیرخطی چند ریشه داشته باشد؛ بسته به مقدار اوليه انتخابى» روش نيوتن به یکی از ریشهها همگرا خواهد شد. 

صفحه 14:
روش نيوتن (011/الا©10) در حالت تكمتغيره مثال ‎c(X =- sinx- 3x‏ قر حوم»- و)ه ‎Iter (x) aE‏ 0.5 0.7525825618904 1 1.1121416370973 0.9328201795041- 2 0 0.9096726937368 0.1387540393506- 3 1 0.8672638182088 0.0053939980413- 4 .2 ‎-9.3331063520941e- 0.8654771352982‏ 5 6 006 ‎-2.8106184046806e- 0.8654740331109‏ 6 ‎O11‏ 

صفحه 15:
5 6 00 0 1 3 73 2 | 

صفحه 16:
در اين روش؛ بجای محاسبه مشتق معادله غیرخطی, از تقریب خطی آن استفاده میشود: عد ومسي حك بد الوا و 2( -فرآیند حل در اين روش با دو مقدار اولیه شروع ميشود. -اين روش برای حل معادلاتی توصیه میشود که محاسبه مشتق آنها دشوار باشد. 

صفحه 17:
اش خط قاطع (56638101) در حالت (x) x8) x2) XD) اگر معادله غیرخطی چند ریشه داشته باشده بسته به مقادیر اولیه انتخابی؛ روش خط قاطع به یکی از ریشهها همگرا خواهد شد. 

صفحه 18:
‎lot) 9S 1c eat)‏ رس رت ‎ ‎x) =cosx- ¥ ‏مثال‎ ‎Iter (x) xen) x 1 0.7525825618904 0.4 05 2 | -1.4739502363393 05 1.2203233688269 0 ‎3 0.3251637516607 1.2203233688269 | 0.7434739819383 0 2 ‎4 0.1040487611586 0.7434739819383 | 0.8296575904545 2 0 ‎5 -0.0143215186635 0.8296575904545 | 0.8702124966502 0 5 ‎6 0.0005060732035 0.8702124966502 0.8653057933219 5 1 ‎ ‎ ‎ ‎ ‎ ‎Ts 2.321132476335e- 0.8653057933219 | 0.8654732615860 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 19:
با استفاده از روش نیوتن؛ میتوان مقدار کمینه یک معادله غیرخطی را نیز تعیین نمود. براى اين كار لازم است تا تقریب معادله غیر خطی (7)8 با سه عبارت اول سری تیلور حول مقدار کنونی 26 در نظ رگرفته شود: 1 ‎—x)F"(x\(F—x)‏ 2 +( ۲۵۲ +( )7 در یافتن ریشه دو عبارت اول سری تیلور درنظ رگرفته شد. چون تقریب خطی برای یافتن ريشه کفایت میکرد. اما برای کمینهکردن تقریب خطی کفایت نمیکند. چون یک خط مقدار کمینه ندارد. 

صفحه 20:
اگر ۲- بخواهد کمینه معادله غیر خطی (0" باشد بايد شرط زیر برقرار گردد: ae = P(X) =0= F(x) + Fy —x) ۵ !رم ”ما مدع همانكونه كه از معادلات فوق قابل مشاهده استء كمينه كردن با روش نيوتن؛ همان يافتن ريشههاى مشتق معادله غيرخطى با روش نيوتن ميباشد. بايد توجه داشت كه ريشه مشتق يكك معادله ميتولند مقدار ‎caine‏ بيشينه يا عطف باشد. بسته به تقعر منحنی (مشتق دوم) در مقدار ريشه, میتوان نوع آن را تشخیص داد. 

صفحه 21:
۳۷۵20 F'(x*) =0 ۲۷۵۷0 ۳۳) > 0 F'(x*)=0 F'(x*)>0 

صفحه 22:
F(¥ =2cosx+ 2co2x F(x) =- 2sinx- 4sin2x 1 | 1 ۱ | ”م 

صفحه 23:
روش نيوتن براى كمينيكردن در حالت تكمتغيره 1.047198 x 3.141593 x 5.235988 FO) -5.320132 -5.196152 F(x) 0.835422 1.003052e- BG. 4.093933 5.196152 F(X) 0.248311 -6.661338e- 75 -0.059644 -8.881784e- 718 -1.110819 5.551115e- FOO) 2.592239 2.598076 FX) 0.002825 6.617445e- 22 -2.461870 2.598076 

صفحه 24:
روش نيوتن در حالت جند متغيره با استفاده از روش نبوتن؛ میتوان پاسخهای یک دستگاه معادلات غیرخطی را تعیین نمود: ‎r(x)‏ ‎e(x) = ۱ =0 e(X) = e(x) + G(X—x)‏ لحان در رابطه فوق» 63 ماتریس ژاکوبین میباشد و به صورت زير بدست ميآيد: Bey Bex ‏نوه‎ ‎Oi‏ وق ‎den Hep 92 ۳9 ‏نج و‎ 5. io fa te ‏تعداد متغيرها‎ ‎G=—= ‎ax ‏تعداد معادلات‎ 10 - Bem — Dein Ben axy ‏وده‎ Bn 

صفحه 25:
اگر * بخواهد ریشههای دستگاه معادلات غیرخطی (:069 باشد ‎٩1*( = OLY‏ باشد: Fle X=x+p | ود + - تور +تپو 1 3 -ا ‎ont oa‏ 

صفحه 26:
3 2 ax =| ,* ** | =0 G@ =) 3% 1 | ‏و + هر‎ - 1 2x 2x; Iter norm(c) x ‏ود‎ ‎1 4,12310562562 1 2 1 1 1 0.162579326341 0.875 0.625, 0.00795143452627 0.829036348267 0.564349112426 2.42438353879e-005 0.826040108171 0.563619773503 2.1257525896e-010 0.826031357732 0.563624162132 1,.11022302463e-016 0.826031357654 0.563624162161 NY] a] apa} ofr 

صفحه 27:
با استفاده از روش تن میتوان مقدار کمینه یک تابع هدف اسکالر را تعیین نمود. برای این کار لازم است تا تقریب تابع هدف (72 با سه عبارت اول سری تیلور حول مقدار کنونی در نظ ركرفته شود: م ما 5 (- ۱۱۱00۲ 0ج + لس ی +(۶ < هام ‎OPE 02‏ ‎Tryin‏ 2 5 ‎we ae‏ 0 ماو 2 5 . > 11-۲-۳1 : |= ‎or ۳ ۳‏ ادن سای 7 ‎ep er er‏ ری 2 27 ۶ 2101 دواع بردار كراديان 

صفحه 28:
اگر ۶ بخواهد کمینههای تابع ‎Fx) ous‏ باشد باید0 < ‎BOX)‏ باشد» در نتیجه داریم: ‎p=-H'g xX=x+p‏ برایناساس» شرط کمینگی پاسخها به صورت زیر خواهد بود: ‎gi(x*)‏ ‏ماتریس هسیان (مثبت معین) ‏ 0 > ‎BX") = : =0 PHP‏ ‎Bn(X*)‏ ‏برای اطمینان از حرکت نزولی به سمت کمینههاء شرط نزول به صورت زیر تعریف میشود: ماتریس هسیان (میت معین) . لاع عاتتراء دمع 0> ماع 

صفحه 29:


صفحه 30:
5 4 پ تصعتعايير - جر زر ‎xe‏ که ورپهرر 6 a= -2 ‏دیدج‎ ‏ود‎ + 10 (Ax- 2x(- Axio 4 t-Bu ‏یه‎ ‎H= ‎C2y+4x?m)e"™ ) ‏لماو رتيربيه + برد‎ or 

صفحه 31:
1 & 0.25 -0.1924186406284 0.17915688200603 -0.01437869676853 3.4989606482556e- 005 2.5586626305923e- 010 1 -0.34017839817954 -0.75956851173729 -0.65776704494957 -0.6690197082945 -0.669071820759 -0.669071B291499G | 4.9855933277373e- (x) =| 0205 ‏نقطه‎ ‎۱ 4 ۹ -0.29246575257697 -0.28435395624279 -0.38265590453357 -0.40501642919638 -0.40523686710184 -0.40523687026669 ع تسیب ۱۶ 1 مادم إن اص اصن a 

صفحه 32:
a x 1 & 0.39871575257697 1 0.25 0.35745422382392 0.44329664510881 | -0.23335769443513 0.44085350236007 0.8021194093804 | 0.18772652331808 0.45522475853404 0.7428592326557 2 0.02133405258601 7 0.45546686638565 0.75242096990985 # 1.0259587685284e- 005 0.48 946687374075 | 1 38 - =| 0 x10 ‏ممم‎ - eo ۳0 028600124296- 0002 0 0۳548 oto= 0.45546687374075 0.75251988181478 - 3.7623025447086e- (kK) م ادح أت إحر eS 019 7 

صفحه 33:


صفحه 34:
si-Newton) در بسیاری از مسائل بدستآوردن ماتریس هسیان, فرآیندی دشوار میباشد. در اینگو: مسائل میتوان از روشهای شبه نیوتن به منظور تخمین ماتریس هسیان در قالب یک فرآیند تکراری استفاده نمود. برخی از اين روشها عبارتند از: الف) روش 3701716۳ ‎B=H‏ حاو لوح یم 5 ۳" Ag—BAx)(Ax)" ‏او و ود‎ B=B ‏رفظ وه‎ ‏ا و ع دع‎ Broyden, Fletcher, Goldfarb, and Shanno ‏ب) روش‎ BFGS Ag(Ag)’ BAx(Ax)'B 1 1 ‎ (Ax)BAx‏ ده آرییه) ‎ ‎ ‎ ‎ ‎B=B+ 

صفحه 35:
Symmetric Rank-one ‏ج) روش‎ (SRI Bap ‏دا‎ BAx)! 5 )۸۵۵- ۸ ۸ Davidon, Fletcher, and ۳07611 ‏د) روش (1۳۴ظ)‎ ‎BAx)(Ag)' + AgiAg—BAx)!‏ شا بو-و ‎(Ag) Ax - ‏وه اوه‎ ‎_ (Ag—Bax)'Ax ‏آوه)‎ 

صفحه 36:
روشیای تکراری شبه نیوتن (0۷851-1167/]0) Foe) +e ( + ‏مثال *(ود -ر)‎ ‏(ود - )2 +( تلو‎ 0 H, 1 0 &™) - 205 - %) ‏و"‎ 01 Ite Method F(x) acy ee = 6 | Newton | 1.79738868235 | 0.79611164529 | 1.20388835470 07 776 22 13| Broyden | 1.79738868235 | 0.79611164529 | 1.20388835470 07 776 22 11| 3808 | 1:79738868235 | 0.79611164529 | 0 07 776 22 

صفحه 37:
روشباى تكرارى شبه نيوتن ‎(quasi-Newton)‏ 

صفحه 38:
‎Nee _‏ اگر بخواهيم یک معادله غیرخطی را در حضور چندین قیود تساوی کمینه کنیم» باز هم میتوانیم از روش نیوتن استفاده کنیم. برای اين منظور لازم است تا تابع هدف جدیدی ‏تعریف نماییم که درب رگیرنده تبع هدف اصلی و قیود تساوی باشد: ‏مسئله بهینهسازی: کمینهکردن تابع هدف اسکالر(1) 7 در حضور قیود تساوی 0 < ‎CK)‏ ‏عزج — ‎L(x.) = Fox) — Mex) = FOR)‏ ‎i=l‏ ‏به تابع فوق» لا گرانژین (1۵01۵1001810) و به متغیرهای :2 ؛ ضرایب لاگرانژ گفته میشود. با تعریف تابع لاگرانژین و ضرایب لا گرانژ میتوان مسئله بهینهسازی مقید را نامقید نمود. 

صفحه 39:
شرایط لازم برای کمینهشدن لاگرانژین به صورت زیر میباشند: Vr L(x", 0) = 0 Vib=g-@X=VF- rave i=l VLA) =0 VAL =—e(x) ‏این شرایط همانند بهینهسازی نامقید. تمایزی میان نقاط کمینه؛ بيشينه يا عطف قائل نميشوند.‎ ‏به منظور شناسایی نوع نقاطء باید به تقعر تابع لا گرانژین در آن نقاط دقت نمود:‎ m Hy,= V},b= ۲ ‏ار کی‎ isl 

صفحه 40:
با اعمال روش نیوتن بر معادله لاگرانژین. معادلات زیر بدست میآید: ((-0 6-۱-6 ,6+1 -ع 0 ‎0=—c-—G(x—x)‏ اگر معادلات فوق را به صورت ماتریسی در آوریم. معادله زیر حاصل میگردد: م + < 35 . متفیرهای بهینهسازی جدید م- 611 ۲۷ ۳ FL ‏ریت‎ 7 به معادله فوق؛ شرط ‎gigs aa Karush-Kuhn-Tucker‏ با درنظرگرفتن مقادیر اولیه برای متفیرهای بهینهسازی و بهرهگیری از معادله فوق در یک ف رآیند تکراری میتوان به پاسخهای بهینه مطلوب دست يافت. 

صفحه 41:
ل ات۱ Fax +x, ‏-لاعه‎ 2۳) 3-4 ju, G=|8x- 2) 202 - 3( ‏ود) + *(2 - 240 - ود + برع رز‎ - 32-4 4 1 86 3د رده ‎oo]‏ 

صفحه 42:
ببينبيسازى مقيد با قيود تساوى x 4 1 2 1 1 2 7.5555555555556 | 0.66666666666667 | 2.6666666666667 3 2.0919299053876 1.0749354005168 | 0.96770025839793 4 3.4034044528578 1.4864251120825 1.0926778294759 5 3.8331615529634 1.4855440150564 1.2752727285932 6 3.85725969162 1.4943581597326 1.2744227642586 Ve 3.8574896890392 1.4942935475336 1.2745887504755 8 3.8574897217276 1.4942935630189 1.274588745144 01332004, ۳ 79097 0 ‎V, L=1.776410 | 0 url‏ ی ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 43:
3۳-4 - و) +2۳ =A(x - | 

صفحه 44:
ببينسازى مقيد با قيود نامساوى در این بخش, ميخواهيم يكك معادله غيرخطى را در حضور جندين قيود نامساوى با روش نيوقن كمينه كنيم: مسئله بهينهسازى: كمينهكردن تابع هدف اسكالر (3)/ در حضور قيود نامساوى 0 < (5)© - تعداد قیود نامساوی (17)) برخلاف تعداد قيود تساوى ميتواند بيش از تعداد متغيرهاى بهینهسازی («) باشد. به نقطهای که تمام قیود را ارضاء نمایده نقطه شدنی (1625[016) و به مجموعه نقاط شدنی؛ ناحیه شدنی میگویند. -نقاطی که در ناحیه نشدنی واقعانده یک یا چند قید را نقض میکنند. 

صفحه 45:
ببينسازى مقيد با قيود نامساوى در اين مسائل» قيود نامساوى در نقاط بهينه ميتوانند دو حالت داشته باشند: الف) برخى از قيود به صورت مرزى (همانند قيود تساوى) ارضاء ميشوند كه به آنها قيود فعال (۵01176) میگویند: ‎cG(x*)=0 for ied‏ ب) برخی از قیود به طورقطع ارضاء میشوند ‎(inactive) Sui pb 955 GET 4 S‏ میگویند: ‎c(x*)>0 for ied’‏ - قبود فعال را میتوان همانند قیود تساوی بر مسئله اعمال نمود. قیود غیرفعال نیز که خود ارضاء شدهاند. بنابراین» مهمترین کان تشخیص فعال یا غیرفعال بودن قیود است. 

صفحه 46:
با قيود نامساوى ‎ee‏ ‏برای مسائل بهینهسازی با قیود نامساوی شرط لازم ديكرى نيز درنظركرفته ميشود كه اين شرط لازم» كمكك بسيارى در تشخيص فعال يا غيرفعال بودن قيود ميكند: ‎for ieA‏ 0 < ز ‎FO) =x7 +3 (x) = 2-2) -19 20 ‎cf] cna my xd ‏در نقطه شروع؛ قید نامساوی مسئله؛ فعال میباشد. بنابراین؛ در گام اول؛ اين قيد را به صورت ‏یک قید تساوی بر مسئله اعمال مینماییم. 

صفحه 47:
ببينسازى مقيد با قيود نامساوى شرط بهينكى اين مسئله در كام اول به صورت زير بدست میآید: ] یه یعنی؛ مقدار ضریب لاگرانژباید 0 ۳ 2- > خباشد تا شرط برقرار باشد. بانوجه به منفى بودن ضريب لا گرانژ بايد قيد نامساوی را از مجموعه قیود فعال حذف کرد. با حذف قید مذ کون در گام بعدی» یک مسئله بهینهسازی نامقید خواهیم داشت که با روشهای بيانشده قبلی قابل حل میباشد. با حل مسئله بهینهسازی نامقید حاصلهه پاسخ بهینه به صورت زیر بدست میآید: ‎x7 =(0,0)‏ 

صفحه 48:
نامیریزی درجه دوم (۳۲۵9۲۵۲۱۲۳۳۱۱۲۱9 یکی از انواع بسیار مهم مسائل بهینهسازی» مسائل برنامهریزی درجه دوم میباشند: ‎Ax=a‏ ‎Bx>b‏ مسئله بهینهسازی: تابع هدف درجه دوم ما بر ‎de 345 FW)‏ برای حل مسائل 0۳ از روش مجموعه فعال (561 20176) استفاده میشود. برای بيادهسازى اين روش؛ فرضميکنيم که یک مجموعه آن اولیه ‎ (‏ ) و يكك نقطه شرلاع شدنی ‎ (‏ ) دراختیار میباشد. برایناساس الگوریتم 2۳ به صورت زیر بیان میشود: گام اول - کمینه تابع هدف را براساس قیود فعال درنظرگرفته شده بدست ميآوريم. در اين حالت؛ قیود فعال رابه صورت قیود تساوی برمسئله اعمالميکنيم و معادلات 1617 مربوطه را حل مینماییم. 

صفحه 49:
نامیریزی درجه دوم (۳۲۵9۲۵۲۱۲۳۳۱۱۲۱9 گام دوم - بیشترین گام ممکن را در راستای 19 برميداريم » بگونهای که هیچ نقض قیدی در قیود نامساوی غیرفعال رخ ندهد: xX=x+ap O<a<l ‏در معادله فوق؛ طول گام میباشد و باید بگونهای انتخاب شود که مقادیر جدید متفیرهای‎ ‏بهینهسازی در ناحیه شدنی باقی بمانند:‎ كات ‎piv.‏ 1۰ for ied’ a=min ci گام سوم -اگر طول گام محدود گردید (۱ ۳ ), قید نامساوی محدود کننده رابه مجموعه قیود فعال اضافه ميکنيم و به گام اول باز میگردیم. ‎RF‏ دادهب 

صفحه 50:
(Quadratic Program اكر طول كام كامل بود (! > #»علامت ضرايب لاكرائز را بررسى ميكنيم: -اكر تمامى قيود نامساوى داراى ضرايب لاكرانز مثبت بودندء از الككوريتم خارج ميشويم. - در غیراینصورت. قید نامساوی با منفيترين ضريب لاكرانز را از مجموعه قيود فعال حذف ميكنيم و به كام اول باز ميكرديم. گام اول - حل معادله ‎KKT‏ ‏گام دوم - تعیین طول گام گام سوم - حذف و اضافه قیود نامساوی 

صفحه 51:
مثال: مطلوب است کمینهکردن تابع هدف دادهشده در حضور قیود نامساوی زیر: be A )( ‏رد ع‎ + -2 0 F(x) =a} +33 2 x} = (4.0) e(x) =4-41 — gee 0 _| 2% _| 1 1 ۵ ِ 2 ‏ده اه‎ ud How Vt iin 2 0 ,j0 Oj 0 0 [2 0 H, = - - = fo 2-0 #0 d-lo 2 

صفحه 52:
تکرار صفرم: قید غیرفعال 2=220 -4+0= ‎G‏ اد 2 ‎AP = {eo}‏ قيدفال ‏ 2)0-0 4 -4- و 0 تکرار اول: 1.2308 = 1 8 زور و و 2+72 رو 0 | -| 2/3 -. 2 0 !5538-= یر ۵ ۱۱:1 0 1-23- 2.769 :1.230 - 4 ‎G =2.61540‏ هد = = ‎x=‏ ‎heal 4‏ يل ۳ یت با طول كام کامل» قید نامساوی غیرفعال نقض نمیگردد. پس: 1 < 6 چون ضریب لاگرانژ قید دوم منفی است پس از مجموعه فعال حذف میگردد: Al = {9} 

صفحه 53:
62 --2 رم 3092 52506 1 -- ور سد ‎al‏ : : ّ -D, gaxeapa| 27698, ‏انم‎ 0 G=-2<0 ‏م‎ 846 - 18462 70 o =+420 6 > 1 ‏با طول گام کامل قيد غیرفعال اول نقض میگردد. پس:‎ ‎goog gp,‏ 26154 -_ 2709218462 کم ‎Ah= fer}‏ ی مدمه ‎“PvE |- 2.7692 - 18468 ‎1 269 - 27692 12 4-60 ‏مج‎ gg (05607), each lca 0 2-2660 

صفحه 54:
تکرار سوم: 2-2 7 4 (م ]1 0 2 2+2 رز 246 ام -1 2 0 ‎Gav‏ ۰ 02۱ 11 1 02 ]ی 12 233320=¢ .— }|= 0+ 2 وه بو ‎“of oa ۱‏ وم با طول كام کامل» قید نامساوی غیرفعال نقض نمیگردد. پس: 1 < 6 ضریب لاگرانژ قید اول مثبت و ضریب لاگرانژ قيد دوم صفر است. پسء شرط خروج از الگوریتم برنامهریزی درجه دوم برقرار است: aa (11) d* = (2,0) AY = {ei} 

صفحه 55:
نامبریزی درجه دوم ‎(Quadratic Programming)‏ FQ) $17 4.53 ei (x) =x +42-220 c2(x) =4—x1 — fn 20 

صفحه 56:
مثال: مطلوب است کمینهکردن تابع هدف دادهشده در حضور قیود نامساوی زیر: 0< 2+ 2 - برع 6 25۴ - ود) + *(1 - بر)< جر 6<0 +216 - با -< 6 ‎ae i)‏ 9 0< 2+2 +4 -< و (23 - و2 20 = @ 1۵ 2 2 0 ‎G=%20‏ 

صفحه 57:
نامبریزی درجه دوم ‎(Quadratic Programming)‏ =a] با طول كام كامل» هيجكدام از قيود نامساوى غيرفعال نقض نميكردند. بس: 1 - © قيد سوم داراى منفيترين ضريب لا گرانژ است» بس از مجموعه فعال حذف ميكردد: 

صفحه 58:
نامبریزی درجه دوم ‎(Quadratic Programming)‏ )هصغ تكرار دوم: با طول كام كامل» هيجكدام از قيود نامساوى غيرفعال نقض نميكردند. بس: 1 - © ‎a‏ للك قید پنجم دارای ضریب ‎al alte BEV‏ پس از مجموعه فعال حذف میگرده: ‎EB‏ 

صفحه 59:
نامبریزی درجه دوم ‎(Quadratic Programming)‏ 2 ها 69218 5 ام 5-] اه 2۱ 0 وید ۷ 0 | دم مدع با طول گام کامل؛ قید نامساوی اول نقض میگردد. پس: 0.6 < 6 را 2 ام اب ثم قید محدود کننده اول به مجموعه فعال اضافه میگردد: ‎FUG)‏ 

صفحه 60:
نامبریزی درجه دوم ‎(Quadratic Programming)‏ سس سس ااام تکرار چهارم: 042 ‎Al‏ ۰۵ 11-۱ 0 2 2 دام 2-- ام ‎١‏ 2- 2 ه ۵8 |2 و واه 1-2 4 04] ی 11 |= 1 = = ‎Bextra ۳ +0 Fe‏ با طول كام كامل» هیچکدام از قیود نامساوی غیرفعال نقض نمیگردند. پس: 1 < 6 ضريب لاكرائز قيد فعال» مثبت است. پسء شرط خروج از الگوریتم برنامهریزی درجه دوم برقرار است: 14 17 - 

صفحه 61:
F=(x- 1)? +(x- 2.5)” % 0< 2+ 2 - با 6 6 <- ‏با‎ - 216+ 6<0 G ‏ور -< و‎ + 2 +2 <0 20 با ه G=% 20 ۳ 

صفحه 62:
در طول فرآیند حل مسائل بهینهسازی» لازم است تا به طریقی از همگرایی و پیشرفت حل اطمینان حاصل کنیم. متداولترین راه برای اندازهگیری پیشرفت اختصاص یک تابع شایستگی (/۸) به هر تکرار و اصرار بر برقراری شرط زیر میباشد: Mo) < Max) هدف از تعریف تابع شایستگی؛ بیان پیشرفت حل در قالب یک عدد است. - برای مسائل بهینهسازی نامقید. بهترین تابع شایستگی, تابع هدف میباشد: > 0 ‎F(x)‏ براك مسائل باقن ربشههاى جستن يبرع شایستگی به صورت زیراست: 

صفحه 63:
از پُرمهای دیگر نیز میتوان به عنوان تابع شایستگی استفاده نمود: m M(x) = [lel = leil isl ۲ 3 M(x) = [lell2 2 iz] M(x) = [leloo = mtx ci] -برای مسائل بهینهسازی مقید. یافتن تابع شایستگی مناسب قدری دشوار میباشد. چون باید در هرتکران هم کمینهشدن تابع هدف مدنظر باشد و هم ارضای قیود مورد توجه قرا رگیرد. 

صفحه 64:
(Merit Functions) su. Nee _ ‏یکی از انتخابهای متعارف برای تابع شایستگی, تابع جریمه درجه دوم میباشد:‎ وجو أ + وم - زميهم در معادله فوق» 6 وزن جریمه یا پارامتر جریمه نامیده ميشود. برای مقادیر بزرگ پارامتر جریمه میتوان ثابت نمود که کمینهکننده نامقید تبدیل به کمینهکننده مقید ميشود. اما درنظ رگرفتن مقادیر بز رگ برای پارامتر جریمه؛ از لحاظ حل عددی مطلوب نیست. برای رفع این مشکل, از تابع لاگرانژین افزوده استفاده میشود: منم ام جو رم وم ام + ‎POR A.p) = LOA)‏ M(x,2.p) = P(x.d.p) MM) AED, 9) < Mx, 2, p) 

صفحه 65:
کاهش تابع شایستگی در هرتکرار پیشرفت و همگرایی حل درآن تکرار را نشان میدهد. اگر تابع شایستگی در یک تکراره کاهش نیافت: باید به دنبال راهکاری بود تا این کاهش صورت گیرد. برای این منظور؛ میتوان با تغییر طول گام جستجو در معادله زیر نقاط جدیدی را یافت که در شرط کاهش تابع شایستگی صدق نمایند: ‎O<a<l‏ ممع دع یعنی؛ بجای برداشتن یک گام کامل در راستای جستجی گامی کوتاهتر برداشته ميشود تا شرط کاهش تابع شایستگی حفظ شود. ‏به الگوریتمهای تعیین طول گام برای کاهش تابع شایستگی؛ جستجوی خط میگویند. 

صفحه 66:
در هر تکران با بهرهگیری از روش نیوتن؛ راستای جستجو () مشخص میگردد که به کمک آن میتوان مقادیر جدید متفیرهای بهینهسازی را یافت. با دراختیارداشتن این مقادير» میتوان مقدار تابع شایستگی را به صورت زیر محاسبه نمود: M(@&) = M(x+ap) = M(a) ‏مطابق با معادله فوق» تابع شایستگی در هر تکرار تابعی از طول گام میباشد. با کم و زیاد‎ ‏كردن طول كام؛ میتوان مقدار تابع شایستگی را آنقدر تغیبر داد تا به میزان مطلوب برسد.‎ ‏در حالت کلی؛ اگر طول گام بگونهای باشد که تابع شایستگی کمینه گردد؛ مقصود اصلی‎ ‏بهینهسازی محقتق خواهد شد. پسء یکی از راههای تعیین طول گام؛ کمینهکردن معادله‎ ‏فوق برحسب ۸ با روشهای دقیق بهینهسازی است.‎ 

صفحه 67:
e Se Nee _ ‏با توجه به حجم محاسبات زیاد برای انجام بهینهسازی. روشهای دیگری به منظور تعیین‎ ‏طول كام بيشنهاد شده است. اين روشهاء کمینههای تقریبی معادله شایستگی را ارائه مینمایند‎ و پیشتر بر حفظ نزول و تقعر مطلوب حل در هر تکرار تم رکز دارند. (acktracking) > Sie ‏الف) روش‎ در اين روش با درنظر گرفتن یک مقدار اولیه برای طول گام؛ تا جاییکه شرط زیر محقق axa ‏شود مقدار طول كام را كم ميكنيم:‎ while not M(a)<M(0) Mla) < M(0) a = ta ضریب کاهش (معمولا ۰/۵ ‎end mee‏ 

صفحه 68:
ب) روش ‎Wolfe‏ ‏در این روش با درنظر گرفتن یک مقدار اولیه برای طول گام» تا جاییکه شرایط زیر محقق شوند. مقدار طول گام را کم ميكنيم: شرط کاهش ‏ ۷۸/)۵(۵ ۸۱۵۸ +۸۸۵۱ > ‎Ma)‏ ‏فرط تفر مين اعداد ‎Ky 9 Ky Cub‏ اعدادی مثبت و کوچکتر از یک هستند. مقادیری که معمولا برای اين ثابتها درنظ ركرفته ميشوند» به صورت زیر میباشند: 0 < وم 10-4 حم ا> ع »>0 

صفحه 69:
)هصغ ج) روش ‎Goldstein-Armijo‏ در این روش با درنظر گرفتن یک مقدار اولیه برای طول گام» تا جاییکه شرایط زیر محقق شوند. مقدار طول گام را کم ميكنيم: ‎M(a) < M(0)+ kia VM(O)p M(a) = M(0)+K2.a@VM(0)p‏ ‎Kia VM(0)p < M(0)—M@ <—meVMO)p‏ ~< 0 اعداد ‎Ky 9 Ky Cub‏ اعدادی مثبت و کوچکتر از یک هستند. مقادیری که معمولا برای اين ثابتها درنظ ركرفته ميشوند» به صورت زیر میباشند: 0-۱۶۱ 7۱۶210 ۶9 

صفحه 70:
(Line Search) bi 5 ST F=100x,- ¥°)?+(@- x) ‏مثال‎ ‎x2) 2x)- 2(1- 7‏ ی ‎2002 - x") ‏(د - :4006 - 9006 | ور‎ - 05 - 06 200 M=F -12 ee 

صفحه 71:
جستجوی خط (566۲6۳ ۲1۳6) د 1 1.380674157 -3.175033855 0.5828247755 0.9440273239 0.9999913913 1 1.001 cig) ‏ی‎ x -1.2 -1.175280899 0.7631148712 0.7634296789 0.9999953111 0.9999956957 1 802 - 0 - 400 0 Without Line Search Hex) -| ie 24.2 4.731884325 1411.845179 0.05596551683 0.3131890761 1.85273977e-011 0 Iter x} a} a} a] we] 

صفحه 72:
جستجوی خط (566۲6۳ ۲1۳6) Backtracking Tter F 1 x a 1 24.2 12 1 1 2 4,731884325 | -1.175280899 | 7 0.125 3 4.087398662 | -0.9329814276 | 0.8112106558 4 3.228672589 | -0.782540079 | 8 1 5 3.213898091 | -0.4599971191 6 1 6 1,942585421 | -0.3930456341 | 0.1500023692 0.25 7 1.600193694 | -0.2094119091 1 0.006770126701 8 1.178389561 | -0.0657190214 | -0.0163286562 1 9 | 09224115819 | 0.1420425452 | -0.0229887839 1 10 | 0.5974886168 | 0.2311071976 | 0.04547802446 0.5 11 | 0.4526250978 | 0.3797428192 | 0.1181458046 1 12 | 0.2807624382 | 0.4795948897 | 2 1 13 | 0.2113933964 | 0.6534058298 | 0.3967289355 1 14 | 0132 | 3 0.4912575792 0.5, 

صفحه 73:
(Line Sea ‏زر‎ surrey Backtracking Iter ‏رد‎ x x a 15 | 0.05153540487| 0.8027855344 | 09 1 16 _| 0.01999277797| 0.8634908081 | 0.7419312454 1 17 0.9420786864 | 68 1 0.007169243633 18 0.9679918175 | 0.9363366683 1 0.001069613679 19 | 7.776846403e- | 09962103108 | 0.9916386999 1 005 20 | 2.82466949e- | 0.9994793791 | 0.9989483424 1 007 21 | 8.517074973e- | 0.9999988896 | 3 1 012 22 | 3.743975643e- | 0.9999999999 | 9 1 021 23 0 1 1 1 

صفحه 74:
جستجوی خط (566۲6۳ ۲1۳6) Wolfe Iter F 1 x a 1 24.2 7 1 1 2 | 4731884325 | -1.175280899 | 7 0.125 3 | 4.087398662 | -0.9329814276 | _0.8112106558 4 | 3.228672589 | -0.782540079 | 8 1 5 | 3.213898091 | -0.4599971191 86 1 6 | _1.942585421 | -0.3930456341 | 2 0.25 7 1.600193694 ۳ 1 1 0.006770126701 8 1.178389561 | -0.0657190214 |_-0.0163286562 1 9 |] 09224115819 | 0.1420425452 ] 9 1 10 | 0.5974886168 ] 0.2311071976 | 446 0.5 11 | 0.4526250978 | 0.3797428192 |_ 0.1181458046 1 12 | 0.2807624382 | 0.4795948897 | 2 1 13 | 0.2113933964 | 0.6534058298 | 5 1 14 0.08901950132 ] 0.7026236343 | 2 0.5 

صفحه 75:
(Line Sea ‏زر‎ surrey Wolfe Iter ‏رد‎ x x a 15 0.05153540487 | 4 0.6332210119 1 16 0.01999277797 | 1 0.7419312454 1 17 0.9420786864 0.8813361968 5 0.007169243633 18 0.9679918175 0.9363366683 1 0.001069613679 19 7.7768464036- 0.9962103108 0.9916386999 1 005 20 2.82466949e- 0.9994793791 0.9989483424 1 007 21 8.517074973e- | 0.9999988896 0.9999975093 1 012 22 3.743975643e- | 0.9999999999 0.9999999999 1 021 23 0 1 1 1 

صفحه 76:
جستجوی خط (566۲6۳ ۲1۳6) Goldstein-Armijo Tter F 1 x a 1 24.2 12 1 1 2 4,731884325 | -1.175280899 | 7 0.125 3 4.087398662 | -0.9329814276 | 0.8112106558 4 3.228672589 | -0.782540079 | 8 1 5 3.213898091 | -0.4599971191 6 1 6 1,942585421 | -0.3930456341 | 0.1500023692 0.25 7 1.600193694 | -0.2094119091 1 0.006770126701 8 1.178389561 | -0.0657190214 | -0.0163286562 1 9 | 09224115819 | 0.1420425452 | -0.0229887839 1 10 | 0.5974886168 | 0.2311071976 | 0.04547802446 0.5 11 | 0.4526250978 | 0.3797428192 | 0.1181458046 1 12 | 0.2807624382 | 0.4795948897 | 2 1 13 | 0.2113933964 | 0.6534058298 | 0.3967289355 1 14 | 0132 | 3 0.4912575792 0.5, 

صفحه 77:
(Line Sea ‏زر‎ surrey Goldstein-Armijo Iter ‏رد‎ x x a 15 | 0.05153540487| 0.8027855344 | 09 1 16 _| 0.01999277797| 0.8634908081 | 0.7419312454 1 17 0.9420786864 | 68 1 0.007169243633 18 0.9679918175 | 0.9363366683 1 0.001069613679 19 | 7.776846403e- | 09962103108 | 0.9916386999 1 005 20 | 2.82466949e- | 0.9994793791 | 0.9989483424 1 007 21 | 8.517074973e- | 0.9999988896 | 3 1 012 22 | 3.743975643e- | 0.9999999999 | 9 1 021 23 0 1 1 1 

صفحه 78:
Iters) & اس ‎Neer eee ee‏ با تعریف تابع شایستگی ميتوان يكك بیان کمی برای پیشرفت و همگرایی حل مسائل بهينهسازى مقيد ارائه داد. اما براى مواردى كه كمينهشدن تابع هدف با ارضاى قيود در تضاد باشد؛ تعیین ضرایب وزنی در تابع شایستگی قدری دشوار و تأثیرگذار خواهد بود. -روش دیگری که در بحث اطمینان از پیشرفت و همگرایی حل مسئله کاربرد دارد؛ استفاده از فیلترها برای قبول و یا عدم قبول هر تکرار از حل می‌باشد. ایده استفاده از فیلتر آن است که هر مرحله از حل» يا بايد مقدار تابع هدف را کاهش دهد و يا از میزان نقض قیود بکاهد. - برای سنجش میزان نقض قیود. می‌توان یک تابع اسکالر را براساس توابع قیود تعریف نمود و مورد استفاده قرارداد. 6۱| زعام کمینهکردن نقض 245 ‎vle(x)]‏ کمپنهکردن تابع هدف () 7 7 سس ‎wwwjamilniairimuth‏ 

صفحه 79:
(Fv) = (Fo) vfetx]} زوج ‎APO VO) Ss‏ زوج مرتب (آ۴۰۷)رتری دارد؛ اكر و تنها اكر: FY < ‏ذنام‎ vi) < WW) FO), yD FO), y ‏قهرست زوج مرتبهای تکرارهای مختلف (قیلتر) : د‎ PEK) KD شرط پذیرش یک تکرار این است که زوج مرتب دیگری بر زوج مرتب آن تکرار برتری نداشته باشد. يعنى» حداقل يكى از مقادير تابع هدف يا ميزان نقض قيود كاهش يافته باشد. 

صفحه 80:
- فیلترهاه قبول یا رد یک تکرار را بیان میکنند و راهکاری برای حل مشکل ارائه نمیکنند. مثال 32-4 -ي) + 2(2 - ‎c=4(x‏ شور + هر جر ‎2x,‏ ‎G= -2) Ax-‏ = )3 - و20 (2 1802 ۳ 9 3۳-4 -ود) + 2(۳ دز - + چرس رز 2 1 0 8[ 0 2]_ جد ده لو واه مد 

صفحه 81:
فیلترها (۴۱۱6۵۲5) Iter ۹ Xe 5 7 1 1 1 2 4 2 | 0.66666666666 | 2.66666666666 | 7.55555555555 | 3.222222222 667 67 56 222 3 | 1.07493540051 | 0.96770025839 | 2.09192990538 | 3.553220292 68 793 76 584 4 | 1.48642511208 | 1.09267782947 | 3.40340445285 | 0.692914524 25 59 78 170 5 | 1.48554401505 | 1.27527272859 | 3.83316155296 | 0.033344002 64 32 34 512 6 | 1.49435815973 | 1.27442276425 | 3.85725969162 | 0.000311479 1 280رومول) 00 86 4250 ا 1 1053 5 0 92 55 8 | 1.49429356301 | 1.27458874514 | 3.85748972172 | 8.88178420e- 76 016 

صفحه 82:
وت و6 )هصغ در روش نيوتن براى حل مسائل بهینهسازی» تابع هدف با درنظ رگرفتن سه عبارت اول سری تیلور به صورت زیر تقریب زده شد: 1 5 مك اد +و یب د وام با پیادهسازی روش نیوتن برای کمینهکردن معادله فوق برحسب متغیرهای بهینهسازی ‎OK)‏ راستای جستجو به صورت زير بدست آمد: 1 و با تعیین راستای جستجو مقادیر جدید متغیرهای بهینهسازی به صورت زیر بدست آمدند: X=x+p 

صفحه 83:
وت زور6 اس ‎ee‏ ۱۳۳ F=100(x- x’) +(1- x)? ‏مثال‎ ‏لو‎ ¥ VC 2x)- 20- x)] yy _[800K"- 400(x,- x”) - 4005 200(%- x") - 4001 200 _[-12 _{- 2156] _[1330 48 “| 1 “| - 88 ~|480 20 __ pig [0.024 ‏ار‎ 5 ‏ات اسب و و‎ 1.380 AU BESS ‎F(x)‏ 130-6 متو جر 

صفحه 84:
(Trust Region) همانگونه که در مثال ملاحظه گردید» راستای جستجوی بدستآمده در معادله زیر صادق نیست. چون معادله زیر تقریبی است. این معادله تنها در همسایگی کوچکی از نقطه < برقرار بوده و قابل اطمينان استة متام + ‎Foo+ Tp‏ 2۶( +۲ بابراین» راستای جستجو باید در چارچوب همان همسایگی بدست آید تا تقریب نزدیک به واقعیتی از تابع هدف درنظر گرفته شود. برایناساس» باید معادله فوق را برحسب راستای جستجو (0) کمینهسازی نمود و در ضمن محدودیت زیر را نیز لحاظ کرد: ess ppb ak 5 ۲ ۹ ‏شعاع لطمینان‎ 0 

صفحه 85:
وت و6 ۳ آلگوریتم کلی روش ناحیه اطمینان مقدار اولیه شعاع اطمینان ۰ 6 ‎while norm(g)>e‏ حل ستله بهینهسازی متید ۰ 0 ] ۵۲۵۲۵۱5۴۵۳۲۵+( ۱0۵(۲ 1و3 ‎norm(p)<=6‏ ‏کاهش پیشبینیشده ۰ ‎pred=m(x+p)-m(xX)‏ ‏کاهش واقعی ۰ ()۲- (۵+) 2۳60۲ ‎if (ared/pred)<n,‏ عدم پذیرش گام ‎x=x‏ ‏کامنش شماع اطمينان 6 8 ‎else‏ ‎xexep 1S ek‏ 

صفحه 86:
if (ared/pred)=>n, 6=max{6,norm(p)y,} تانيمطا ‏افزايش شاع‎ end if end if end ‏ثابتهای بکارفته در الگوریتم فوق» عموماً به صورت زير انتخاب ميشوند:‎ m = 0.25, no = 0.75, y1 = 0.5 and y2 =3 با این الگوریتم» هم راستای جستجو و هم شعاع اطمینان مناسب بدست میآید. 2 سر ‎go Oe ence‏ prec ari St Ah pS sid, 

صفحه 87:
خلاصه الگوریتم: اگر !> > ‎٩۷‏ باشد مدل مناسبى داريم. در اين حالت» گام را مپذيريم و ناحیه اطمینان را تغییری نمیدهیم. اگر ۱" * ” باشدء مدل مناسبى نداريم. در اين حالت» كام را نمييذيريم و ناحيه اطمينان را باعامل 1 > 71كاهش ميدهيم. اگر 2 2 " باشد مدل بسیار مناسبی داریم. در این حالت» گام را ميپذيريم و ناحیه اطمینان رايا عامل سدقي 

صفحه 88:
وت زور6 به منظور حل تقریبی مسئله بهینهسازی راستای جستجو میتوان از روش 00:16 بهره برد: P, = oe p,=-H'g a=Pp,; P, D=p,'P, c=(P,- P,)' (P,- Pn) quath 6 _ b- 5? = 0ك ‎qa‏ ‏2ق عطق - لل لجل رز 2 P=cp,+(1- (۳, 

صفحه 89:
نامپریزی درجه دوم متوالی ( پیشتر روش برنامهریزی درجه دوم (0۳)) برای حل مسائل بهینهسازی مقید با قیود تساوی و نامساوی معرفی گردیده بود. اين روش؛ برای مسائلی کاربرد دارد که تلبع هدف آنها درجه دوم باشد و توابع قیود آنها خطی باشند. به منظور تعمیم این روش برای مسائل برنامهریزی غیرخطی در حالت کلی به صورت زير عمل میکنیم: مسائل برنامهریزی غیرخطی در حالت کلی به صورت زیر میباشند: ‎min F(x) ox) =0‏ كه در آن» (0)26 دربر گیرنده قیود تساوی؛ نامساوی و محدودیت متغیرها میباشد. همانگونه که در روش مجموعه فعال بیان شد. قیود نامساوی را نیز میتوان به صورت قیود تساوی بر مسئله اعمال نمود. پس فعلاً قيود را به صورت قيود تساوى در نظر ميكيريم. 

صفحه 90:
)50۳( ‏متوالی‎ 0 Coe ber تابع هدف اسکالر را میتوان با درنظ رگرفتن سه جمله اول سری تبلور تقریب زد: ۲ 1 ۲ ون الود 2 + ‎F(x) = F(x) +g! (x)(K—x)‏ توابع قيود را نيز ميتوان با درنظ ركرفتن دو جمله اول سرى تيلور تقريب زد: ‎e(X) = e(x) + G(x)(X— x)‏ همانگونه که دیده میشود با تقریبهای درنظر گرفتهشده تابع هدف به شکل یک عبارت درجه دوم و توابع قیود به شکل عبارتهای درجه اول (خطی) برحسب نر آمدهاند. وقتی در هر تکران از معادلات فوق استفاده ميشود؛ مقادیر تا در آن تکرار معلوم میباشند و تنها مقادیر گر آن تکرار مجهول میباشند. 

صفحه 91:
امیریزی درجه دوم ‎rel sz9‏ 9( :اه بنابراين» مسئله برنامهریزی غیرخطی جدید به صورت زير در میا ید: 1 ۰ ‎HIN) —)‏ )8-9( 5+ )¥= كالم اع وم = ‎min F(x)‏ ‎e(X) = e(x) + G(x)(x—x) =0‏ مسئله جدید. حائز شرایط مسائل برنامهریزی درجه دوم میباشد. در تابع هدف بيانشده, میتوان عبارت (0/ را حذف نمود. چون این عبارت در هرتکرار» مقداری ثابت است و لحاظنمودن آن در فرآیند کمینهسازی تأثر گذار نخواهد بود: 1 ‎F(X) = (6+ «(11006 -‏ با توجه به مقید بودن مستله بايد تابع لاگراوین را تشکیل داد: ‎LOA) = FR) =I)‏ 

صفحه 92:
امیریزی درجه دوم ‎rel sz9‏ 9( 0000 با اعمال روش نیوتن بر معادله لاگرانژین, معادلات زير بدست ميايد: 0 + ۲۲-7 0=-—c—Gi(x—x) اگر معادلات فوق را به صورت ماتریسی درآوریم: معادلات 1161 حاصل میگردد: +5 > 3 متفیرهای بهینهسازی جدید ۳ ‎SUEZ]‏ ۳ 1 ضرايب لاگرانژ جدید © 1 0 ‎G‏ ‏با حل متوالی معادله فوق در تکرارهای مختلف و یافتن راستاهای جستجو و ضرایب لاگرانژ بهینه در هر تکرار؛ برنامهریزی درجه دوم متوالی (560۳) منجر به پاسخ بهینه خواهد شد. 

صفحه 93:
‎Sr CSCS sor as‏ عا سس سس ‎Nee‏ ‏-به دليل تقريب درجه دوم تابع هدف و تقريب خطى تولبع قيود در روش نيوتن» روش 40۳ ‏برای حالات کلی مسائل برنامهریزی غیرخطی نیز کاربرد دارد. ‏- باید توجه داشت که تقریبهای مذ کور در هرتکرار و در همسایگی محدودی از متفیرهای ‏بهینهسازی برقرار میباشد. پس در هر تکرار» یک مسئله 2 جدید حل ميشود. با حل متوالی مسائل 23۳) در تکرارهای پیدرپی؛ پاسخ بهینه نهایی بدست میآید. ‏-به منظور لحاظ نمودن قیود نامساوی» از روش مجموعه قیود فعال میتوان استفاده نمود. یعنی قيود فعال و غیرفعال را تفکیکک کرد و قیود فعال را همچون قبود تساوی درنظر گرفت. 

صفحه 94:
امیریزی درجه دوم ‎rel sz9‏ 9( 0000 در طول فر يند برنامهريزى درجه دوم متوالى ميتوان از راهكارهاى زير براى سنجش و بهبود همگرایی و پیشرفت حل استفاده نمود: - تعریف توایع شایستگی (سنجش میزان پیشرفت و همگرایی حل) -الگوریتم جستجوی خط (تعیین طول گام برمبنای توابع شایستگی) الگوریتم ناحیه اطمینان (تعیین راستای جستجو در همسایگی متغیرهای بهینهسازی) - درنظر گرفتن فیلترها (کاهش تایع هدف یا تابع نقض قیود در هر تکرار) # در مقالات و کتب مختلف. راهکارهای تر کیبی و پیچیدهتر نیز ارائه شدهاند. 

صفحه 95:
(Interior point) (39) abi در روش برنامهریزی درجه دوم متوالی (500۳) برای درنظر قیود نامساوی از رویکرد مجموعه فعال استفاده ميشود. یعنی در هر تکرار؛ قیود نامساوی فعال و غیرفعال از هم تفکیک میگردند و قیود فعال به صورت قبود تساوی بر مسئله بهینهسازی اعمال میشوند. این رویکرد سبب میشود تا روند حل با حرکت بر روی قیود تساوی پیش رود. در تقابل با روش 500 روش دیگری برای بهینهسازی مسائل مقید با قیود نامساوی مطرح گردیده است که به آن نقطه درونی میگویند. در این روش روند حل با حرکت در درون احیه شدنی پیش میرود. در روش نقطه درونی» نیازی به تفکیک قیود نامساوی نیست و اساساً محادلات > با ساختار واحدی در هر تکرار حل میشوند. 

صفحه 96:
nterior point) 3: ‏نقطه‎ _ 00 در روش نقطه درونى؛ ساختار كلى مسئله بهينهسازى به صورت زير درنظ ركرفته ميشوه ‎min F(x) ox) =0 x20‏ در این ساختار: بجای درنظرگرفتن قیود ناساوی. مجموعهای از قیود تساوی و محدودیت متغیرها درنظر گرفته ميشود. محدودیت متغیرها در این ساختار بگونهای است که تمامی متغیرهای بهینهسازی را به صورت مقادیر نامنفی تعریف مینماید. به منظور تبدیل یک قید نامساوی به یک قید تساوی و یک محدودیت متغیر میتوان به صورت زير عمل نمود: ‎Hx)<0 > Hx)+s=0 s=0‏ به متغیر 5 » متغیر کمکی (5180[6) گفته میشود. 

صفحه 97:
در روش نقطه درونی؛ برای اعمال محدودیت متغيرهاء يكك عبارت لگاریتمی به تابع هدف افزوده میشود: min F(x)- ‏نما كير‎ 000 -0 vA عبارت لگاریتمی در تابع هدف بيانشده سبب میشود تا فرآیند حل به صورت ذاتی از نزدیکشدن مقدار متغیرها به صفر جل وگیری کند تا مقدار تابع هدف کمینه گردد. در تابع هدف فوق» به پارامتر اسکالر ل پارامتر 0277167 گفته ميشود. اگر این مقدار به سمت صفر ميل کند پاسخ مسئله فوق به پاسخ مسئله اصلی نقطه درونی همگرا ميشود. برای آغاز فرآیند حل در این روش معمولاً یک مقدار اولیه برای 1 درنظ ركرفته ميشود و به تدریج مقدار آن در مراحل مختلف کاهش مییابد تا به میزان قابلقبول برسد. ‎wwwjamilniairimuth NLS!‏ 

صفحه 98:
در فرآیند بهینهسازی با روش نقطه درونی؛ تیع لاگرانژین به صورت زیر تعریف میشود: ‎L=F- uy Inx+c'‏ 2 شرایط > برای لاگرانژین فوق به صورت زیر میباشد: 81 دير و-۳ ‎Gd‏ همانگونه که در معادلات فوق دیده میشود» با نزدیکشدن متغیرهای بهینهسازی به مقدار صفرء فرآیند محاسبه گرادیان لاگرانژین با مشکل مواجه میگردد. برای رفع اين مشكل» متغیرهای جدیدی به نام متغیرهای دووگان به صورت زیر تعریف میشوند: +02 c=0 Y= | بر 

صفحه 99:
با تقریب درجه دوم تابع هدف و تقریب خطی تولبع قیوده میتوان از روش نیوتن برای حل مسئله بهینهسازی بهره برد. برایناساس میزان تغییر متغیرهای بهینهسازی؛ ضرایب لاگرانژ و متفیرهای دو گان در هر تکرار از رابطه ماتریسی زیر بدست مآیند: الا ‎H, 6" - 1۸ g+G'A-‏ ‎c‏ = ‎Xv- we‏ در رابطه فوق 26 و ۷ ماتریسهای قطری از بردارهای 2 و ۷ میباشند و 6 برداری از اعداد يك مياشد ‎Axe ma‏ كط : ۱ ‎v,eg Ax Av: nx1 G:mxn‏ 

صفحه 100:
صورت زير بدست ميآيندة جک | ار ‎O<a <1‏ حك معدا ار ‎ve lve ata‏ در هر تكرار طول كام متغيرهاى بهينهسازى بايد بككونهاى تعبين شود كه نامنفيبودن مقادير جدید متغیرهای بهینهسازی حفظ شود. برای ضرایب لاگرانژ و متغیرهای دوگان؛ ميتوان از طول گام کامل بهره برد. در روش نقطه درونی نیز میتوان از راهکارهای سنجش و بهبود همگرایی و پیشرفت حل (نظير تابع شایستگی» جستجوی خط. ناحبه اطمینان و فیلتر) استفاده نمود. 7 سس ‎wwwjamilniairimuth‏ 

صفحه 101:
(Interior point) (39) abi Neer eee ee ‏اس‎ مثال: مطلوب است کمینهکردن تابع هدف دادهشده در حضور قیود نامساوی زیر: 0 - ود + 24 600 FQ) =x) + x, 2 G(x) =4- X- 3% 20 G(x) =- ¥- %+2<0 G(X) =- X- %+%t2=0 ‏ده ود بت مه 0 - ود ب - واج‎ 4-0 x 2x, 2000 x=}? ‏۵ات هر 0 1- 1 ]_ و‎ 2 ۲ 03 0 1 2/3 0 1 0 0 0 0 ‏يد‎ 0 000 0 

صفحه 102:
(Interior point) (39) abi Ite nv Ve Va Vs 6. 9 1 2 2 2 2 0.50000000003 125 2 1 1 0 1 2.99999999995, 83 3 1 1,33333333334 | 1.33333333335 | 0.66666666669 | 1.77777777775 44 444 56 1 BAR sc66s | NBEELGKIADVIszRsb39 4LO'22222221s0rMhe) =O 38 18 568 83 

صفحه 103:
(Interior point) (39) abi FO =x} 433 ‎=x, 442-220‏ )له ‏2 ‏20 وح 4-1 مه 

صفحه 104:
(Interior point) (39) abi مثال: مطلوب است کمینهکردن تابع هدف دادهشده در حضور قیود نامساوی زیر: F=(x- 1 +(x- 25) F=(x- 1 +(x- 2.5) G=X- 2x%,+220 G =-%+2%+%- 2=0 G = %- 2x%+620 9 ‏-يد + ود2 +ها- كه‎ 6-0 ‏هد + 22 - 4< 6 0< 2 + 2 + زر -< بو‎ - 220 ‏بر < به‎ 20 )4 % قاو وده 0 ‎G=%>‏ 

صفحه 105:
(Interior point) (39) abi 1 x ‏ی د د‎ XS a 1 2 2 2 2 2 0.500000000 08 2 0 4 1 1.499999999 | 2.249999999 1.000000000 97 90 08 3 1 1533333333 | 1.433333333 | 0۰666666666 | 1.600000000 | 3 35 31 74 03 26 4 1 a 226868666 ‏8:681قتفففهرت 96101600000 44ج هد( ع( 0©7؟ ووكخدهما‎ 105 67 62 43 09 57 5 1 

صفحه 106:
درونی (۳۵۱۴ 0۸۲۵۲۱۵۲ F=(x- 1)? +(%- 2.5) G=xX- 2x%,+220 6<0+ 2 -¥ -= نو ‎G =- %+2x%,4+220‏ 20 با ه G=x%,20 

صفحه 107:
در طول فرآیند حل یک مسئله بهینهسازی» عدم تعریف صحیح مسئله میتواند سب بروز برخی مشکلات و واگراییها شود. بنابراین؛ باید این مشکلات را پیش از حل پیشبینی و عوامل ایجاد آنها را شناسایی نمود. در این بخش با برخی از اشکالات در تعریف مسائل بهینهسازی آشنا میشویم: پاسخ غیریکتا: برخی از مسائل بهینهسازی اساساً منجر به پاسخ بهینه یکتایی نمیشوند. مثال: ت(ود رمع( این مسئله بینهایت پاسخ دارد. زیرا تمام نقاط روی خط 2* ۳ ۱" پاسخ این مسئله هستند. 

صفحه 108:
قیود نشدنی: در برخی از مسائل بهینهسازی قیود متضادی وجود دارند که باهم ارضا نميشوند. ‎dite‏ 0 < دود ع مه ‎(x) = x2 > -l ‏قیود زائد: در برخی از مسائل بهینهسازی قیودی وجود دارند که بودن یا نبودنشان تأثیری در ‏حل و پاسخ بهینه ندارد. ‏مثال 1 معي ورد هه ۲-3 ‎۲0۵-2 ‏برد ورم‎ = 0 ye ox) = 242-2 = 0