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

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

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