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

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

* تعاریف

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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