بهینه‌سازی محدب برای مسائل گراف (بهار ۹۵-۹۶)

درس در مورد چیست؟

اگر مبحث الگوریتم‌های گراف را مطالعه کرده باشید، چه در قالب قسمتی از درس آنالیز الگوریتم و چه در قالب درسی با همین نام، و حتی چه به صورت مطالعۀ انفرادی این درس، با جنبۀ ترکیبیاتی گراف و الگوریتم‌هایی از این جنس آشنا شده‌اید. مثلا در برخورد ترکیبیاتی با گراف با مسیرها، برش‌ها، درخت‌ها، شارها، و از این قبیل چیزها سروکار داریم و تلاش می‌کنیم با استفاده از داده‌ساختارهایی بتوانیم خوب این اشیاء ترکیبیاتی را محاسبه کنیم. در مجموع این نوع برخورد ترکیبیاتی تصور ما نسبت به الگوریتم‌های گراف را شکل داده است.

شصت سالی است که نگاهی به مسئله‌های ترکیبیاتی رایج شده است، که از نگاه جبر خطی به گراف نشئات می‌گیرد. اما حدود شش سالی است که ابزار بهینه‌سازی محدب به کمک حل مسئله‌های بهینه‌سازی روی گراف‌ها آمده تا با آن بتوانیم صورت‌بندی جبر خطی مسئله‌های گراف را در زمان بهینه‌تری حل کنیم.

در این کلاس ارتباط بین این سه موضوع را بررس می‌کنیم و کاربرد آنها در تولید الگوریتم‌های کارا برای مسئله‌های گراف را توضیح می‌دهیم. این درس بر اساس درسی به همین نام که توسط آقای الکساندر مدری (که البته تلفظ صحیحش مندری است) در پاییز ٢٠١۵ در دانشگاه MIT ارائه شده، تدوین شده است.

ابزارهای درس و رابطه‌شان در شکل زیر نشان‌داده شده:

تصویر رابطهٔ مفاهیم درس مدری-۹۵۲

سعی می‌کنیم درس شامل مفاهیم کاملا شهودی باشد، اگرچه در تمام طول درس شهود خود را اثبات خواهیم کرد.

برنامه کلاس‌ها

  1. بهینه‌سازی محدب روش حرکت در جهت گرادیان، روش به‌روزرسانی وزن ضربی، بهینه‌سازی محدودیت، روش نقطهٔ میانی. در این قسمت بیشتر تلاش می‌کنیم به بهانهٔ حل تقریبی مسئلهٔ شار بیشینه روش‌های حل مسئله‌مان را تقویت و تقویت کنیم. مرحله به مرحله راه حل‌مان بهتر می‌شود.
  2. نظریهٔ طیفی گراف قدم‌زدن تصادفی، لاپلاسین گراف، شار الکتریکی. با وجود اینکه می‌توانیم مسئلهٔ قبل را حل کنیم، اما یک زیرمسئلهٔ آن باقی می‌ماند. آن را با حل سریع شار الکتریکی حل می‌کنیم.
  3. الگوریتم سریع حل دستگاه معادلات خطی در نهایت یک الگوریتم خیلی سریع برای حل دستگاه معادلات خطی، که ماتریس ضرایب آن لاپلاسین یک گراف باشد، ارائه می‌شود.
  4. مفاهیم پیشرفتهٔ الگوریتم‌های گراف تنک‌سازی، درخت‌های فراگیر با کشیدگی کم، تجزیهٔ برش مبنای گراف، مسیریابی بدون حافظه

در ضمن هر دانشجو باید مبحثی مرتبط با درس را مطالعه کرده و ارائه‌ای در آن زمینه داشته باشد. هر دانشجو باید گزارش مختصری در مورد مبحث ارائهٔ خود نیز تهیه کرده و تحویل دهد.

پیش‌نیاز

آشنایی با نظریهٔ گراف، الگوریتم‌ها، جبر خطی، و احتمال برای این درس ضروری است.

منابع پیشنهادی

منبع این درس، منابع کلاس آقای الکساندر مدری است با عنوان Graphs, Linear Algebra, and Optimization که در پاییز ۲۰۱۵ ارائه شده است.

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

منابعی برای انتخاب موضوع ارائه
این هم یک لیست از منابع احتمالا مناسب. حتما منابع را مطالعه کنید و پس از مطالعه منبع و این‌که مطمئن شدید برای درس مناسب است منبع مورد نظر خود را برای بنده ارسال کنید.
توجه کنید این‌ها منابع احتمالا مناسب هستند و البته منابع دیگر و شاید بهتری هم وجود خواهند داشت.

توضیح تاریخ عنوان مقاله نویسندگان تاریخ عنوان مقاله نویسندگان
Empirical 2015 An Empirical Comparison of Graph Laplacian Solvers Engineering a Combinatorial Laplacian Solver: Lessons Learned
۲۰۱۵ Fast Generation of Random Spanning Trees and the Effective Resistance Metric Aleksander M , adry∗ EPFL Damian Straszak† University of Wroc law Jakub Tarnawski‡ University of Wroc law
۲۰۱۵ Approximate Undirected Maximum Flows in O(mpolylog(n)) Time Richard Peng
Optimization, Learning, and Games with Predictable Sequences Alexander Rakhlin University of Pennsylvania Karthik Sridharan University of Pennsylvania
۲۰۱۶ Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in O˜ m10/7 log W Time Michael B. Cohen Aleksander Mądry Piotr Sankowski Adrian Vladu
۲۰۱۶ Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs Michael B. Cohen∗ Jonathan Kelner∗ John Peebles+ Richard Peng‡ Anup B. Rao Aaron Sidford Adrian Vladu∗
کمی لسو ۲۰۱۲ Runtime Guarantees for Regression Problems Hui Han Chin Aleksander M¸adry Gary L. Miller Richard Peng †‡
۲۰۱۷ Matrix Scaling and Balancing via Box Constrained Newton’s Method and Interior Point Methods Michael B. Cohen Aleksander Mądry Dimitris Tsipras Adrian Vladu

کلاس‌ها

جلسه موضوع تاریخ نکات اضافه
جلسه ۰ معرفی درس ۱۷ بهمن
جلسه ۱ بهینه‌سازی محدب برای شار بیشینه ۱۹ بهمن
جلسه ۲ الگوریتم کاهش زیرگرادیان ۲۴ بهمن
جلسه ۳ الگوریتم کاهش گرادیان (برای توابع هموار) ۲۶ بهمن اثبات لم ۸ و مشاهده ۶، اثبات هم‌گرایی الگوریتم کاهش گرادیان تصویرشده (قسمت ۱ و ۲) جزوه ۳
جلسه ۴ تغییر تابع هدف مسئله شار بیشینه، شروع محاسبه مقاومت معادل ۱ اسفند
جلسه ۸ تنک‌ساز ‍۱۷ اسفند جزوه روش تقریبا خطی کتاب روش تقریبا خطی مسائل پیاده‌سازی

برای جزوه‌نویسی از این قالب استفاده کنید.

7 thoughts on “بهینه‌سازی محدب برای مسائل گراف (بهار ۹۵-۹۶)

  1. کمی بیشتر از کاربردهای این درس میگویید؟
    و به نظر شما چه پیشنیازهایی برای درس لازم است؟(به معنی مهارت) و آیا دانستن قضایای کلاسیک گراف لازم است؟
    و منظورتان از بررسی شهودی مباحث چیست؟

    1. کاربرد؟! در این درس با روش آشنا می‌شوید، با این روش‌ها ممکن است خیلی مسئله‌ها را بتوانیم در آینده حل کنیم، اما الآن نمی‌دانیم.
      قضایای کلاسیک گراف را نمی‌دانم، ولی باید گراف را بشناسید. باید قدرت تحلیل مسئله و قدرت تحلیل جبر خطی داشته باشد.
      در مجموع درس ساده‌ای نیست و قرار نیست باشد.

  2. عجیب است. الآن داشتم به یکی می‌گفتم خیلی از این الگوریتم‌هایی که به عنوان الگوریتم جدید چاپ می‌کنند مثلاً نسخه‌ی LP همان الگوریتم جستجوی محلی هستند. یعنی همان محدودیت گسسته بودن را برمی‌دارند اما دوباره با یک سری قید مدلش می‌کنند. این قیدها هم از نظریه طیفی گراف و امثالهم می‌آورند.
    برای مسیریابی فراموشکار هم من خودم یک کران پایین و مصالحه با استفاده از گسترگراف به دست آورده بودم. باید زودتر چاپش کنم! (اگر هنوز جدید باشد!)
    اما این درس حداقل LP را به عنوان پیشنیاز می‌خواهد، نه؟

    1. دانستن LP خیلی به درس کمک می‌کند، اما ندانستنش خیلی اوضاع را خراب نمی‌کند. خیلی عجیب به نظر می‌رسد، ولی ظاهرا که این‌گونه است.

      1. خب اینکه پیشنیاز برای یک درس باشد به عمق مطلب کمک می‌کند. وقتی یک درس پیشنیاز نداشته باشد همه‌ی وقت صرف مطالب تکراری با درس‌های دیگر می‌شود. در ضمن هیچ وقت کسی که بار اول LP را می‌شنود مثل کسی که یک ترم پیش آن را خوانده نمی‌تواند مسئله حل کند و همین درس را به سمت حفظی بودن پیش می‌برد. البته خیلی از افرادی که تحقیق می‌کنند و مقاله می‌نویسند خودشان هیچ دیدی نسبت به پیشینه‌ی کاری که می‌کنند ندارند. یعنی مثلاً سه مقاله‌ی آخر در آن زمینه را می‌خوانند و روی جزئیات آن کار می‌کنند. این درس برای چنین کاری خوب است و مثلاً دانشجوهای ورودی جدید ارشد را سریع به بازدهی می‌رساند. اما از نظر اینکه واقعاً مفهومی را منتقل کند جالب نیست چون همه چیز را نصفه توضیح می‌دهد. یک جورهایی برمی‌گردد به سوال علم بهتر است یا ثروت (تعداد مقاله)!

پاسخ دهید

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