روش برنامه ریزی درجه دوم (Quadratic Programming)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش برنامه ریزی درجه دوم (Quadratic Programming) :
کمینه سازی تابع درجه دوم با قیود خطی:
\[ \min \frac{1}{2} x^T Q x + c^T x \]توضیح ساده: برنامه ریزی درجه دوم (QP) یک مسئله بهینه سازی است که در آن تابع هدف یک تابع درجه دوم (با ماتریس Q) و قیود (اگر وجود داشته باشند) خطی هستند. این مسائل در میان مسائل بهینه سازی از اهمیت ویژه ای برخوردارند، زیرا هم در کاربردهای فراوانی (مانند ماشین بردار پشتیبان، کنترل بهینه، و برنامه ریزی مالی) ظاهر می شوند و هم به عنوان زیرمسئله در روش های پیشرفته تری مانند SQP استفاده می گردند. اگر ماتریس Q مثبت معین (Positive Definite) باشد، مسئله محدب بوده و یک جواب منحصر بفرد دارد که با روش های کارآمدی مانند روش های فعال-مجموعه (Active-Set) یا روش های نقاط داخلی (Interior Point) قابل حل است.
شرح گام به گام: مسئله QP به صورت زیر تعریف می شود:
\[ \min_x \frac{1}{2} x^T Q x + c^T x \]با قیود:
\[ A x \le b \]،
\[ A_{eq} x = b_{eq} \]، و
\[ x \ge 0 \](اختیاری).
روش فعال-مجموعه (Active-Set):
۱. با یک حدس اولیه شروع کنید که در قیود صدق کند.
۲. مجموعه قیود فعال (قیودی که در نقطه فعلی برابری می شوند) را تعیین کنید.
۳. با فرض فعال بودن این قیود، یک زیرمسئله QP نامقید (یا با قیود برابری) را حل کنید.
۴. اگر جواب این زیرمسئله قیود فعال را نقض کند، یک جستجوی خطی انجام دهید تا به مرز قیود برسید.
۵. مجموعه فعال را به روز کنید و تا همگرایی تکرار کنید.
روش نقاط داخلی (مانند روش های پیش بینی-تصحیح) نیز برای QP استفاده می شوند.
مثال عددی: ماشین بردار پشتیبان (SVM) برای طبقه بندی داده ها به یک مسئله QP منجر می شود: کمینه سازی ½ ||w||² با قیود yᵢ(w·xᵢ + b) ≥ 1. این مسئله با روش های QP حل می شود و به یافتن ابرصفحه بهینه می انجامد.
مزایا: اگر Q مثبت معین باشد، مسئله محدب است و جواب سراسری دارد. روش های کارآمدی برای حل آن وجود دارد.
معایب: اگر Q نامعین (Indefinite) باشد، مسئله غیرمحدب شده و یافتن جواب سراسری دشوار است.
کاربردها: در یادگیری ماشین (SVM)، در کنترل پیش بین (MPC)، در بهینه سازی سبد سهام، در زیرمسائل SQP.
نکته: نرم افزارهایی مانند quadprog در MATLAB و CVXOPT در Python برای حل QP وجود دارند.
