بهینه‌سازی محدب از مقادیر ویژه گراف لاپلاس

چکیده

مسئله مطرح‌شده در مقاله، مسئله انتخاب وزن برای یال‌های یک گراف بدون جهت است که می‌خواهیم برخی توابع مقادیر ویژه ماتریس لاپلاس وابسته به گراف را ماکزیمم یا مینیمم کنیم، به‌طوری‌که روی وزن‌ها محدودیت‌هایی مثل نامنفی بودن، یا یک مقدار مجموع داده‌شده داریم. در بسیاری از موارد جالب توجه این مسئله محدب است، یعنی شامل مینیمم کردن یک تابع محدب (یا ماکزیمم کردن یک تابع مقعر) تحت یک مجموعه محدب است. لذا شرایط بهینگی لازم و کافی ساده، ناشی از مسائل دوگان[۱] جالب توجه خواهیم داشت، در برخی موارد جواب‌های تحلیلی می‌یابیم و در همه موارد جواب عددی را به‌صورت کارآمد محاسبه می‌کنیم.

بهینه‌سازی محدب از مقادیر ویژه گراف لاپلاس

در این مقاله به‌طور خلاصه برخی موارد خاص از این مسئله مطرح شده‌است:

  • سریعترین ادغام زنجیره مارکوف[۲]. احتمالات انتقال یال به‌طوری‌که سریعترین ادغام زنجیره مارکوف (متقارن، گسسته در زمان) روی دهد را در گراف می‌یابد.
  • سریعترین ادغام فرآیند مارکوف[۳]. نرخ انتقال یال به‌طوری‌که سریعترین ادغام فرآیند مارکوف (متقارن، پیوسته در زمان) اتفاق بیفتد را در گراف می‌یابد.
  • اتصال جبری مطلق[۴]. وزن یال‌ها را به‌طوری‌که اتصال جبری مطلق ماکزیمم شود می‌یابد (یعنی، کوچکترین مقدار ویژه مثبت از ماتریس لاپلاس وابسته به گراف). مقدار بهینه توسط فیلدر[۵] اتصال جبری مطلق نامیده می‌شود.
  • مینیمم مجموع مقاومت مؤثر[۶]. وزن یال‌ها را به‌طوری‌که مجموع مقاومت مؤثر گراف را مینیمم کند، می‌یابد. این حالت مشابه مینیمم کردن زمان رفت‌و‌آمد از هر گره به گره دیگر، در زنجیره مارکوف وابسته می‌باشد.
  • سریع‌ترین میانگین خطی[۷]. وزن‌ها را در یک شبکه که به‌طور متوسط توزیع شده‌است را به‌گونه‌ای می‌یابد که سریع‌ترین همگرایی حاصل شود.
  • کم‌ترین انحراف میانگین مربعات حالت پایدار[۸]. وزن‌ها را در یک شبکه که به‌طور متوسط توزیع شده‌است و به‌وسیله یک نویز تصادفی رانده شده‌است را به‌گونه‌ای می‌یابد که انحراف میانگین مربعات حالت پایدار مقادیر گره را مینیمم کند.

[۱] Dual

[۲] Fastest mixing Markov chain

[۳] Fastest mixing Markov process

[۴] Absolute algebraic connectivity

[۵] Fielder

[۶] Minimum total effective resistance

[۷] Fastest linear averaging

[۸] Least steady-state mean-square deviation

  1. مقدمه

گراف بدون جهت  با  گره و  یال با وزن‌های  روی یال‌ها را درنظر بگیرید. فرض کنید یال  رأس‌های  و  را به‌هم وصل کرده باشد که با نماد  نمایش می‌دهیم.  که ستون  ام ماتریس برخورد[۱]  است را به‌صورت روبه‌رو تعریف می‌کنیم:  و  و مابقی مؤلفه‌ها برابر با صفر. پس ماتریس برخورد  به‌فرم زیر خواهد بود:

[۱] Incidence matrix

ماتریس وزنی لاپلاس  که یک ماتریس  است به‌صورت زیر تعریف می‌شود:

که در آن  ماتریس قطری تشکیل شده از  است. لذا ماتریس  به‌فرم زیر خواهد بود:

با توجه به تعریف ماتریس  واضح است که ماتریس  یک ماتریس متقارن است (یعنی) و همچنین جمع درایه‌های هر سطر ماتریس  برابر با صفر است و از آنجایی‌که ماتریس متقارن است؛ پس جمع درایه‌های هر ستون نیز برابر صفر است. و لذا هر بردار ثابت (همه مؤلفه‌هایش یکسان باشد)  بردار ویژه ماتریس متناظر با مقدار ویژه صفر است؛ یعنی  و بالاخص رابطه برای بردار واحد برقرار است: . از طرفی زمانی‌که وزن‌ها نامنفی‌باشند ماتریس لاپلاس  نیمه معین مثبت خواهد بود؛ . پس کوچکترین مقدار ویژه ماتریس برابر با صفر است. مقادیر ویژه ماتریس لاپلاس  را به‌صورت  مشخص می‌کنیم. با توجه به قضیه‌ای در نظریه گراف داریم: با فرض ،  همبند است اگر و تنها اگر .

فرض کنید  تابعی محدب و بسته و متقارن روی یک زیر‌مجموعه محدب از  باشد، در‌این‌صورت تابع

یک تابع محدب از  خواهد بود. یعنی یک تابع محدب متقارن از مقادیر ویژه لاپلاس، یک تابع از وزن یال‌ها را به‌ما می‌دهد. چند مثال ساده از تابع  ارائه می‌دهیم:

که دو برابر مجموع وزن است و خطی است؛ در نتیجه محدب است. با توجه به تعریف ماتریس  و قطر اصلی آن واضح است که تساوی بالا برقرار است.

 

مسائل بهینه‌سازی مطرح‌شده در مقاله به فرم کلی زیر هستند:

 

که در آن  مجموعه محدب و  متغیر بهینه‌سازی است. مسئله (۲) وزن یال‌های گراف را به‌گونه‌ای انتخاب می‌کند که برخی محدودیت‌ها داشته باشد و تابع محدبی از مقادیر ویژه ماتریس لاپلاس وابسته به گراف را مینیمم می‌کند. همچنین می‌توانیم تابع مقعری از مقادیر ویژه ماتریس لاپلاس را ماکزیمم کنیم که برای اینکه این مسئله را هم به فرم مسئله (۲) بنویسیم کافی است  را مینیمم کنیم. از آنجایی‌که مسئله (۲) یک مسئله بهینه‌سازی محدب است برای حل آن راه‌حل‌های عددی ساده‌ای داریم و در برخی موارد حتی می‌توانیم مسئله را به‌راحتی تحلیل کنیم. مسائلی که در مقاله مطرح شده اند حالت خاصی از مسائل بهینه‌سازی محدب است که به آن‌ها مسائل برنامه‌ریزی نیمه معین[۱] (SDP) گوییم. حال به معرفی برنامه‌ریزی نیمه معین می‌پردازیم.

برنامه‌ریزی نیمه معین با توجه به نامساوی‌های کلی بر روی proper cone تعریف می‌شود. هنگامی‌که proper cone برابر با مجموعه ماتریس‌های نیمه معین مثبت  باشد، ، مسئله بهینه‌سازی به‌فرم زیر خواهد بود:

[۱] Semidefinite program

که در آن  و . نامساوی بیان‌شده در اینجا نامساوی وابسته به proper cone است و محدودیت  نامساوی ماتریسی خطی[۱] (LMI) نامیده می‌شود. اگر ماتریس‌های متقارن  همگی قطری باشند، آن‌گاه نامساوی ماتریسی خطی معادل با  نامساوی خطی است و برنامه‌ریزی نیمه معین به برنامه‌ریزی خطی[۲] (LP) تقلیل می‌یابد.

با مقایسه فرم استاندارد برنامه‌ریزی خطی با برنامه‌ریزی نیمه معین، فرم استاندارد برنامه‌ریزی نیمه معین دارای محدودیت‌های تساوی خطی و یک محدودیت نامساوی منفی ماتریسی روی متغیر  می‌باشد.

فرم استاندارد برنامه‌ریزی خطی:

[۱] Linear matrix inequality

[۲] Linear program

ارسال دیدگاه

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *