محدبیت، Hessian و برنامه‌ریزی درجه‌دو

از مشتق دوم و Hessian تا مثبت‌نیمه‌معین بودن؛ ریاضیات لازم برای فهم ساختار Convex QP.

بهینه‌سازی و متاهیوریستیک‌هاپیشرفته

مشاهده آموزش‌های دیگر مشاهده پروژه مرتبط

هدف یادگیری

بتوانید محدبیت یک تابع درجه‌دو را با Hessian تحلیل کنید، مفهوم positive semidefinite را بفهمید و ارتباط آن را با Convex QP توضیح دهید.

پیش‌نیازها

مشتق چندمتغیره
جبر خطی مقدماتی
مبانی بهینه‌سازی

محدب یعنی چه؟

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

تعریف محدبیت

f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y),\qquad 0\le\theta\le1

مشتق دوم و Hessian

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

ماتریس Hessian

H_f(x)=\nabla^2 f(x)

شرط مثبت‌نیمه‌معین بودن

v^T H_f(x)v\ge0\qquad\forall v

تابع درجه‌دو

در Convex QP، بخش درجه‌دو objective به شکل x^T P x ظاهر می‌شود. اگر P متقارن و مثبت‌نیمه‌معین باشد، این بخش محدب است.

تابع هدف درجه‌دو

f(x)=\frac12x^TPx+q^Tx

نقش P

P\succeq0\quad\Longrightarrow\quad f\;\text{convex}

یک مثال ساده

تابع دو متغیره

f(x_1,x_2)=x_1^2+2x_2^2

Hessian

\nabla^2f=\begin{bmatrix}2&0\\0&4\end{bmatrix}

دو مقدار ویژه Hessian مثبت‌اند؛ بنابراین تابع strict convex است.

ارتباط با Convex QP Solver

در پروژه Convex QP Solver، مثبت‌نیمه‌معین بودن P بخشی از ساختار مسئله است و بعد روش عددی روی objective و قیود کار می‌کند.

Convex QP

\min_x\;\frac12x^TPx+q^Tx\quad\text{s.t.}\quad Ax=b,\;Gx\le h

تمرین

Hessian تابع f(x,y)=x²+xy+y² را به دست آورید.
مشخص کنید Hessian مثبت‌معین است یا مثبت‌نیمه‌معین.
توضیح دهید چرا convex بودن objective برای solver مهم است.

پروژه مرتبط

Convex Quadratic Programming Solver

از positive semidefinite بودن P تا حل عددی Convex QP.

باز کردن منبع

راهکارهای مرتبط

مدل‌سازی، الگوریتم و بهینه‌سازی

یک مسئله بهینه‌سازی سخت دارید؟

می‌توان ابتدا ساختار ریاضی مسئله را بررسی کرد و بعد سراغ روش حل رفت.

گفت‌وگو درباره مسئله