جلسه ۵ بهینه‌سازی محدب

http://stanford.edu/class/ee364a/lectures/duality.pdf

جلسه ۴ بهینه‌سازی محدب

http://stanford.edu/class/ee364a/lectures/problems.pdf

جلسه ۳ بهینه‌سازی محدب

http://stanford.edu/class/ee364a/lectures/functions.pdf

یادآوری از جبر خطی:

مزدوج ترانهاده (conjugate transpose): علاوه بر اینکه ماتریس را ترانهاده می‌کنیم، اعدادش را هم قسمت مزدوج می‌گیریم (یعنی علامت قسمت غیرحقیقی آنها را برعکس می‌کنیم).

مقدار تکین (singular value): مقدار ویژه‌های حاصل ضرب مزدوج ترانهاده‌ی یک ماتریس در خود ماتریس هستند. اگر ماتریس متقارن و مثبت نیمه معین باشد حالت خاصی به دست می‌آید که جذر مقدار ویژه‌های ماتریس می‌شوند.

trace ماتریس: جمع درایه‌های قطر اصلی

* توابع محدب با ماتریس‌ها

تابع آفین: tr(A^T X)+b

نرم طیفی = نرم ۲ ماتریس (با تعریفش برای بردار فرق داره) = ماکسیمم مقدار تکین‌ها

* محدود کردن تابع به یک خط

اگر تابع را روی یک خط در نظر بگیریم و به ازای هر خط محدب/مقعر باشد، کلاً محدب/مقعر است. مزیت این کار کاهش ابعادی است که باید چک کنیم تا ببینیم محدب هست یا نه.

* مشتق تابع محدب

اگر مشتق تابع مشتق‌پذیر روی دامنه‌ی محدب صعودی است اگر و تنها اگر تابع محدب باشد.

مثل همین برای اینکه مشتق دومش مثبت باشد.

مثال از کاربرد این قضیه در تشخیص توابع محدب: تابع مربع، تابع میانگین مربعات، x^2/y (مربعی بر خطی!)،...

* زیرسطح‌های محدب

اگر قسمتی از سطح محدب را که مقدار تابع در آن کمتر از آلفا است ببریم، باز هم محدب است. برعکسش درست نیست.

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

*نامساوی ینسن

کاربرد: اگر f یک تابع محدب باشد،

f(E(z))<= E(f(z)

که z هر متغیر تصادفی دلخواهی است.

*مثال: مجموع i بزرگترین عدد محدب است. چون ماکسیمم یک سری تابع خطی محدب است.

* سوپریمم یک مجموعه‌ی محدب روی یک بعد محدب است.

مثال: فاصله تا دورترین نقطه

مثال: ماکسیمم مقدار ویژه‌های ماتریس مثبت نیمه‌معین

* ترکیب تابع محدب با تابع غیرنزولی محدب است.

ترکیب برداری: اگر هر مولفه با یک تابع غیرنزولی ...

* پرسپکتیو: برای تابع f تابع tf(x/t) است و اگر f محدب باشد این تابع هم محدب است.

مثال: آنتروپی نسبی با استفاده از آنتروپی

* مزدوج هر تابعی محدب است.

* تابع شبه-محدب: اگر زیرسطح‌های تابع محدب باشند.

مثال: جذر قدر مطلق x

* نامساوی ینسن تغییریافته برای توابع شبه-محدب

f ترکیب خطی x و y (که جمع ضرایبش ۱ بشود) کمتر از ماکسیمم f(x) , f(y) است.

* لگاریتمی-محدب و لگاریتمی-مقعر: یعنی لگاریتم تابع محدب / مقعر باشد.

مثال: توزیع نرمال

*...

کوییز: http://stanford.edu/class/ee364a/quizzes/functions.html

ولی به نظرم سوال آخر کوییزش یک ضریب ۱/۲ جا انداخته.

جلسه دوم بهینه سازی محدب

http://stanford.edu/class/ee364a/lectures/sets.pdf

* تعاریف

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

این معادل مجموعه‌ی جواب یک دستگاه معادلات خطی است و برعکس.

مجموعه‌ی محدب: مجموعه‌ای که پاره‌خط محدود به هر دو نقطه در آن مجموعه را شامل بشود.

ترکیب محدب یک سری نقطه: ترکیب خطی از آن نقاط که جمع ضرایبش برای نقطه‌ها ۱ بشود.

پوسته‌ی محدب: (یکی از تعریفهایش این است) مجموعه‌ی همه‌ی ترکیب‌های محدب آن مجموعه نقطه.

قیف محدب: ترکیب‌های خطی که ضرایبش مثبت است.

ابرصفحه: همه‌ی نقاطی که ضرب در یک بردار ثابت (بردار نرمال) مقدار ثابتی می‌دهند.

ابرصفحه‌ها هم آفین هستند هم محدب.

نیم‌فضا: زیر یا روی ابرصفحه.

نیم‌فضاها محدب هستند.

توپ اقلیدسی: فاصله از مرکز کمتر از شعاع = مرکز + یک بردار با اندازه‌ی حداکثر ۱ * شعاع (یعنی از مرکز دایره در یک جهت حرکت کنیم به اندازه‌ی حداکثر شعاع)

بیضی: به جای بردار با یک ماتریس مربعی وارون‌پذیر در یک جهت حرکت می‌کنیم. (یک تعریف دیگه هم گفته به نظرم یعنی تجانس در یک جهت بدهیم همان تعریف دایره - ماتریسش باید مثبت نیمه‌معین باشد) (ماتریس‌های متقارن روی اعداد حقیقی مثبت نیمه‌معین هستند.)

چندوجهی: Ax<b که منظور از > این است که هر درایه‌اش کمتر مساوی باشد. تقاطع تعداد متنهای ابرصفحه و نیم‌فضا.

قیف مثبت نیمه‌معین: همان تعریف بیضی را تعمیم داده با نامساوی که در خط بالا گفتم.

* اثبات محدب بودن

- ترکیب محدب یک سری نقطه باشد (طبق تعریف)

- ثابت کنیم اشتراک یک سری شئ محدب است. مثلاً با تقاطع یا تابع آفین یا تبدیل با کسری که صورت و مخرجش خطی باشد، یعنی این مدلی: http://mathworld.wolfram.com/LinearFractionalTransformation.html

یا تصویر کردن (در ادامه‌ی اسلایدها خودش توضیح داده)

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

کوییزش: http://stanford.edu/class/ee364a/quizzes/sets.html

جلسه ۱ بهینه‌سازی محدب

http://stanford.edu/class/ee364a/lectures/intro.pdf
اگر یک تابع محدب داشته باشیم که قیدهای محدب داشته باشد می‌شود در زمان ماکسیمم n^3, n^2 * m, F حلش کرد که F زمان محاسبه‌ی مشتق اول و دوم تابع است.

یکی از مسئله‌های معروف، کمینه کردن مجموع مربعات است.

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

- می‌دانیم که کمینه جایی رخ می‌دهد که همه با هم برابر باشند.

- به توان ۲ رسانده بود و تبدیل به مسئله‌ی کمینه کردن مربعات کرده بود. برای حالتی که قیدها نقض می‌شدند هم به نزدیک‌ترین مقدار معتبر رند کرده بود. (؟)

- از نسخه‌ی وزن‌دار کمینه کردن مربعات استفاده کرده بود. تابع هدف را به توان ۲ رسانده بود. قیدهایی که به شکل یک طرف صفر در آورده بود و به توان ۲ رسانده بود در یک ضریب متفاوت برای هر متغیر ضرب کرده بود و با تابع هدف جمع کرده بود. گفته بود مقدار ضریب را طوری تغییر بدهید که جواب در بازه‌ی مجاز بیفتد. https://en.wikipedia.org/wiki/Lagrangian_relaxation

- قدر مطلق را جدا کرده بود و با LP حل کرده بود!

- بهینه‌سازی محدب.

کوییزش: http://stanford.edu/class/ee364a/quizzes/intro.html

بهینه‌سازی محدب استنفورد

http://stanford.edu/class/ee364a/lectures.html
البته این کلاس در coursera هست اما هم آی‌پی ایران را بسته هم اینکه حجم ویدئوهایش بیشتر از چیزی که بشود دانلود کرد.

MS&E 317: Algorithms for Modern Data Models

https://stanford.edu/~rezab/amdm/

ویدئوی نگاشت-کاهش (کارگاه یک روزه)

من لینک کل talkها را می‌گذارم بقیه‌اش هم به درد می‌خورد.
https://stanford.edu/~rezab/talks.html

CME 323: Distributed Algorithms and Optimization

https://stanford.edu/~rezab/dao/

CME 305: Discrete Mathematics and Algorithms (استنفورد)

http://stanford.edu/~rezab/discrete/