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

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