روشهائي براي حل مسائل بهينه سازي محدب مقيد

مقدمه

 مسائل بهينه سازی محدب مقيد، به مسائلی اطلاق می گردد که در آنها يک تابع هدف مشخص را که تابعی محدب (مقعر) از متغيرهای مورد نظر می باشد بر روی يک فضای محدوديت که بر روی متغيرها اعمال
می گردد و فضائی فشرده می باشد[68] حداکثر (حداقل) می گردد. اينگونه مسائل، با توجه به فشرده بودن فضای محدوديت ها و محدب (مقعر) بودن تابع هدف، دارای پاسخ منحصر بفرد می باشند [68]. در اين فصل بطور مختصر به معرفي روشهائي براي حل اينگونه مسائل بهينه سازي مي پردازيم [15] .

بطور خلاصه برخي از اين روشها که به دو دسته روشهای عددی ( از جمله روشهای تصوير گراديان وتصوير نيوتن) و روشهای تحليلی ( از جمله روشهای لاگرانژ، تابع جريمه و تابع سد) تقسيم بندی می شوند عبارتند از:

– روش تصوير گراديان

– روش تصوير نيوتن

– روش لاگرانژ

– روش تابع جريمه

– روش تابع سد

5-2  بهينه سازی محدب مقيد

بطوركلي در حل اينگونه مسائل با مسائل غير خطي به فرم زير روبرو هستيم:

                          Minimize                               F(X)

                              Subject to:              h₁(X) = 0         g₁(X)£ 0

                     h₂(X) = 0         g₂(X)£ 0

                     .                          .

                     .                          .

                     .                          .

                     h_m(X) = 0         g_p(X)£ 0

                                                 

                                                                 X=(x₁,…, x_n)ÎWÌEⁿ

برای اطمينان از وجود جواب بايد داشته باشيم  £ n m+p و توابع F ،h_i, i=1,2,…,m  و g_j, j=1,2,…,p توابعي پيوسته هستند ومعمولاً فرض ميگردد كه داراي مشتق دوم جزئي پيوسته هستند.

Eⁿ فضاي n بعدي اقليدسي است و W فضای محدوديت ها است که فرض می شود فضائی محدب و فشرده باشد.

براي سادگي، توابع برداري H و G را بصورت G=(g₁,…,g_p) و H=(h₁,…,h_m) در نظر مي گيريم در اين صورت، روابط فوق بصورت زير قابل توصيف است:

                            Minimize                            F(X)

                            Subject to:         H(X) = 0      ,       G(X) £ 0

                                                                       XÎW

محدوديت هاي H(X) = 0 و G(X) £ 0 از نوع تابعي و محدوديت XÎW از نوع مجموعه اي
مي باشند. يك نقطه X كه در محدوديت هاي ذكر شده صدق كند را يك نقطه مقبول1  مي ناميم.

يك محدوديت نامساوي بصورت g_i(X)£ 0 را فعال مي گوئيم اگر g_p(X) = 0 و غير فعال مي ناميم اگر g_p(X)<0 . محدوديت تساوي در هر نقطه X كه مقبول باشد، فعال است.

در مطالعه ويژگي هايی که برای تعيين نقاط مينيمم محلي بررسی مي گردند واضح است كه توجه را بايد به محدوديت هاي فعال معطوف كنيم. همانگونه كه در شكل(5-1) مشخص است پاسخ X^*  ترسيم شده در شکل به محدوديت هاي g₂ و g₃ كه غير فعال هستند، بستگي ندارد.

شكل5-1 : محدوديت هاي فعال و غير فعال در يك مسئله بهينه سازي[68]

 

 

5-2-1  روش تصوير گراديان

 

فرض مي كنيم مسئله بهينه سازي بصورت زير باشد :

Minimize    F(X)

XÎW

كه در آن W فضاي محدوديت ها مي باشد. الگوريتم تصوير گراديان بصورت زير است:

(5-1)

                           

كه عملگر {^.}⁺ آرگومان خود را همانند شكل (5-2) به نزديکترين نقطه در فضاي W تصوير
مي كند. g در رابطه (5-1) يك عدد مثبت است.

شكل5-2 : نمايش عملگر تصوير

اگر بردار X در خارج فضاي W و بردار y درون اين فضا قرار داشته باشند، چون فضاي W محدب است خواهيم داشت[15]:

(5-2)                                             

كه درآن علامت (‘) نمايشگر عملگر ترانهاده1 مي باشد.

اگر  نمايانگر نگاشت مرتبط با تكرارهاي الگوريتم تصوير گراديان باشد يعني داشته باشيم:

(5-3)                                               

و فرضيات زيرنيز همزمان برقرار باشد:

• براي هر XÎW داشته باشيم  .
• تابع ÑF  يک تابع ليپشيتز² باشد به عبارت ديگر تابع F پيوسته و مشتق پذير بوده و يك ثابت K وجود داشته باشد بطوری که:

(5-4)                        

كه در آن ||.||₂ نمايانگر نرم اقليدسي است و براي بردار X با بعد N ، بصورت زير تعريف مي شود:

 گزاره زير نشان مي دهد كه با انتخاب g به حد كافي كوچك، هر تكرار الگوريتم ما را بسمت نقطه بهينه پيش مي برد و تابع هزينه را كاهش مي دهد.

 

قضيه 5-2-1[15]

اگر F در شرايط  (i)و (ii) فوق، صدق كند و g > 0 و XÎW آنگاه:

(a1-1)                  

(a2-1) داريم T(X)=X اگر و تنها اگر براي هر  yÎWداشته باشيم:  بويژه اگر F روي W محدب باشد داريم T(X)=X اگر و تنها اگر X ، F را روي مجموعه W حداقل كند.

(a3-1) نگاشت T پيوسته است.

قضيه 5-2-2 (همگرائي الگوريتم تصوير گراديان) [15]

اگرF در فرضيات ارائه شده در قبل صدق كند و اگر  و اگر X^* يك نقطه حدي دنباله {X[n]} باشد كه با الگوريتم تصوير گراديان توليد شده باشد، آنگاه داريم:

 

 

5-2-2 الگوريتمهاي تصوير گراديان وزن دهي شده1 و نيوتن

فرم كلي الگوريتم تصوير گراديان هنگامی که وزن دهی می شود  بصورت زير است:

(5-5)                                

كه در آن M[n] يك ماتريس معكوس پذير است و بمنظور وزن دهي بردار گراديان بكار مي رود. معمولاً M[n] براي تقريب زدن ماتريس هسيان²بكار ميرود[15]. بعنوان مثال در روش
  Projected Jacobi يا Approximate Newton ماتريسM[n] قطري است و المانهاي قطري آن عناصر قطري ماتريس هسيان هستند. در حالتي كه M[n] همان ماتريس هسيان باشد الگوريتم، تبديل به الگوريتم Newton  Projected ميشود و از نظر سرعت همگرائي نسبت به الگوريتم اوليه تصوير گراديان برتري دارد. اگر بطور موقت فرض كنيم كه M[n] متقارن و مثبت معين است و نرم را به صورت زير در نظر بگيريم:

(5-6)                                           

آنگاه  عبارتست از يك بردار y كه عبارت  را به ازای هر yÎW حداقل كند. اين الگوريتم بصورت زير تعريف مي گردد :

(5-7)                           

حال اگر فرض كنيم {M[n]|n=0,1,…} يك دنباله كراندار از ماتريس هاي N×N متقارن باشد و براي  a > 0  هر M[n] در شرط (5-8) صدق كند:

(5-8)                             

و علاوه بر اين  پيش فرض های ارائه شده در قسمت هاي (a1-1) و (a2-1) بخش قبل را ارضا كند آنگاه قضيه زير برقرار است:

قضيه 5-2-3 [15]

(a1-3) براي هر  يك بردار يكتاي yÎW وجود دارد كه را روي W حداقل مي كند و آن را با نشان مي دهيم.

(a2-3) برای يک  xÎW دلخواه، بردار zÎW برابر است اگر و فقط اگر براي هر yÎWداشته باشيم:

(a3-3) براي مقادير به حد كافي كوچك g، هر نقطه حدي X^* دنباله {X[n]} توليد شده توسط الگوريتم تصوير گراديان وزن دهي شده شرط  را براي هر yÎWارضا مي كند.

 

 

5-2-3 بررسي همگرائي با استفاده از روش شيب

 

براي رسيدن به همگرائي الگوريتم هائي كه از فرمول كلي زير تبعيت مي كنند:

(5-9)                                              

كه در حالت كلي:                               

(5-10)                                       

كافي است نشان دهيم كه با تكرار الگوريتم بسمت صفر مي رود. حال فرض مي كنيم F شرايط زير را ارضاءكند.

شرط 1 : براي هر XÎW داشته باشيم:             F(X)³0

شرط 2 : (پيوستگي ليپشيتز ) تابع F بطور پيوسته مشتق پذير بوده و يك ثابت مثبت K وجود داشته باشد بطوريكه:

5-2-4 لم شيب1

 

اگر F در شرط 2 صدق كند آنگاه:

حال با توجه به فرضيات صورت گرفته و لم شيب به بررسي قضيه زير مي پردازيم. اين قضيه در اثبات همگرائي اغلب الگوريتم هاي شيب كاربرد دارد.

قضيه 5-2-4 (همگرائي الگوريتم هاي شيب) [15]

اگر شروط 1و2 بيان شده در قبل برقرار باشند و K₁ و K₂ اعدادي مثبت باشند و {X[n]} دنباله توليد شده توسط الگوريتم  باشد و s[n] در شرط صدق كند و داشته باشيم:

و اگر داشته باشيم  آنگاه:

يعني درنهايت، الگوريتم شيب همگرا مي شود و به نقطه بهينه خواهيم رسيد.

5-2-5 مفهوم سرعت همگرائي و مقايسة سرعت همگرائي الگوريتم ها

تعريف:

فرض كنيد دنباله {r_k} به r* همگرا شود. مرتبه همگرائي{r_k} طبق تعريف عبارتست از سوپريمم اعداد نامنفي p كه در رابطه زير صدق مي كنند:

(5-11)                                          

كه در آن نماد  همان limit superior  است و بدينصورت تعريف مي گردد:

دررابطه با دنباله كراندار  اعداد حقيقي اگر قرار دهيم s_k=sup{r_i : i ³ k} آنگاه دنباله {s_k} به عددي حقيقي مثل s₀ ميل مي كند كه به آن limit superior دنباله {r_k} گفته می شود و با  نمايش مي دهيم.

براي حصول اطمينان از اينكه تعريف فوق به هر دنباله اي قابل اعمال است از نماد  به جاي  استفاده شده است ولي در عمل در اكثر دنباله هاي خوش رفتار و عادي مي توان از  به جاي  بهره برد.

تعريف:

اگر دنباله {r_k}چنان به سمت r^* ميل كند كه داشته باشيم:

(5-12)                                             

مي گوئيم كه دنباله بصورت خطي به r^* ميل مي كند و نسبت همگرائي آن است. به دنباله اي كه بصورت خطي همگرا شود گاهي دنباله” همگراي هندسي“ نيز مي گويند. حالت حدي   به همگرائي فوق خطي1 موسوم است. توضيح اينكه كليه دنباله هائي كه با مرتبه p>1 همگرا شوند، همگرائي فوق خطي دارند ولي ممكن است يك دنباله همگراي فوق خطي داراي مرتبه واحد(p=1) باشد. حال با توجه به نامعادله فوق و تعاريف ذكر شده به مقايسه بين سرعت همگرائي دو الگوريتم نيوتن و تندترين شيب
مي پردازيم:

بمنظور سادگي مراحل اثبات، فرض مي كنيم x اسكالر باشد ولي در حالت كلي مباحث مطرح شده در حالت x برداري نيز صادق است.

الگوريتم تندترين شيب بصورت زير است:

(5-13)                                           

اگر  باشد داريم:

(5-14)                          

حال با بسط و با توجه به اينكه داريم:

(5-15)            

بنابراين مشاهده مي شود كه مرتبه همگرائي الگوريتم تندترين شيب برابر با واحد است.

در الگوريتم نيوتن داريم:

(5-16)                       

تعريف مي كنيم:

                                      

از آنجائيكه داريم:

(5-17)        

كه در آن  در فاصله بين x^* و x_k قرار دارد. از آنجائيكه  داريم:

(5-18)                                         

كه ثابت c به حول x^* بستگي دارد. بنابراين مرتبه همگرائي الگوريتم نيوتن برابر2 مي باشد.

5-2-6 روش لاگرانژ

 

مسئله)  ‡(  را در نظر مي گيريم:

)  ‡(             

F:Âⁿ®Â تابعي است محدب و e_i و a_j بردارهاي داده شده اي هستند و s_i و t_j اسكالرهاي مشخص
مي باشند. يك بردار X كه در محدوديت هاي مسئله )‡ (صدق كند را مقبول مي نامند. تابع لاگرانژين بفرم (5-19) تعريف مي گردد:

(5-19)                

كه در آن:

p=(p₁,…,p_m) و u=(u₁,…,u_r) ³ 0

جواب بهينة مسئله )‡ ( از حل همزمان دستگاه معادلات زير بدست می آيد.

5-2-7 روش تابع جريمه1

 

مسئله زير را در نظر بگيريد:

                                    Minimize                 F(X)                                                      (P1)

                                                Subject  to:              XÎW

كه درآن W مجموعه محدوديت هاي تابعي مي باشد. ايده اصلي روش تابع جريمه اين است كه مسئله فوق را با مسئله بهينه سازي بدون قيد زير تعويض مي كنيم:

                                    Minimize         F(X)+m.P(X)                                                (P2)

m عددي مثبت است و P تابعي است پيوسته و نامنفي و داريم P(X)=0 اگر و تنها اگر XÎW. براي مقادير بزرگ m واضح است كه نقطه كمينه مسئله (P2) در ناحيه اي است كه P كوچك است. بنابراين با افزايش m نقاط جواب به سمت ناحيه مقبول W ميل مي كنند. در حالتي كه  m®¥ ميل كند، پاسخ (P2) به پاسخ مسئله (P1) ميل مي كند.

5-2-8  روش تابع سد²

 

اين روش نيز براي حل مسائلي به فرم زير به كار مي رود:

                                           Minimize                 F(X)                  

                                           Subject  to:              XÎW

اساس اين روش بر اين است كه با ايجاد يك سد در حاشيه ناحيه مقبول W از خارج شدن الگوريتم بهينه سازی از اين ناحيه جلوگيري مي شود. يك تابع سد B(.) بر نقاط دروني W بصورت زير تعريف
مي شود :

1)B پيوسته است.

2) B(X)³0

3) هنگامي كه X به سمت مرز W ميل مي كند B(X)®¥

 مثال: فرض کنيد:

  W={X: g_i(X)£0 , i=1,2,…,p}(5-20)                                        

فرض می کنيم g_i(X) , i=1,…,p بر روي نقاط مرزی W برابر با صفر است و در نقاط دروني
W ،g_i(X)<0  و تابع   بر نقاط دروني W بصورت زير انتخاب شده باشد:

(5-21)                                                 

B(.) يك تابع سد مي باشد. حال مسئله زير را در نظر بگيريد :

اگرچه ظاهراً مسئله فوق يك مسئله مقيد است ولي در عمل با شروع از يك نقطه دروني W هر الگوريتمي را كه به كار ببريم بعلت آنكه در نزديكي مرزها مقدار تابع هزينه بسمت بي نهايت مي رود، عملاً هيچگاه محدوديت ها فعال نمي شوند و با يك مسئله نامقيد مواجه خواهيم شد.

1-Feasible                                                                                                       

1-Transpose                                                                                                                                         2-Lipschitz

1-Scaled Gradient Descent                                                                                                                    2-Hessian

1- Descent Lemma

1- Superlinear

1-Penalty function                                                                                                                    2-Barrier function