روش SQP (انگلیسی : Sequential Quadratic Programming)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش SQP (انگلیسی : Sequential Quadratic Programming) :
حل مسائل غیرخطی مقید با حل دنباله ای از مسائل درجه دوم
توضیح ساده: برنامه ریزی درجه دوم متوالی (SQP) یکی از موثرترین روش ها برای حل مسائل بهینه سازی غیرخطی مقید (NLP) است. ایده اصلی این است که در هر تکرار، یک تقریب درجه دوم از تابع هدف لاگرانژ و یک تقریب خطی از قیود ساخته شود و یک مسئله برنامه ریزی درجه دوم (QP) حل گردد. جهت به دست آمده از حل QP به عنوان جهت جستجو استفاده می شود. این روش ترکیبی از روش نیوتن برای حل شرایط KKT و روش های شبه-نیوتن برای تقریب هسین لاگرانژین است. SQP همگرایی سریع (ابرخطی یا درجه دوم) دارد.
شرح گام به گام: برای مسئله minimize f(x) subject to g(x) ≤ 0, h(x) = 0:
۱. با یک نقطه شروع x₀ و یک تقریب اولیه از هسین لاگرانژین B₀ (معمولا I) شروع کنید.
۲. برای k = ۰,۱,۲,... تا همگرایی:
- مسئله QP زیر را حل کنید تا جهت جستجو dₐ بدست آید:
\[ \min_d \frac{1}{2} d^T B_k d + \nabla f(x_k)^T d \] \[ \text{s.t. } \nabla g_i(x_k)^T d + g_i(x_k) \le 0 \] \[ \nabla h_j(x_k)^T d + h_j(x_k) = 0 \]- با جستجوی خطی (مثلا با تابع جریمه l₁) اندازه گام αₐ را بیابید.
- xₐ₊₁ = xₐ + αₐ dₐ را به روز کنید.
- لاگرانژین را به روز کرده و با استفاده از تغییرات x و گرادیان لاگرانژین، Bₐ₊₁ را با فرمول شبه-نیوتن (مثل BFGS) به روز کنید.
۳. شرایط KKT در جواب بررسی می شود.
مثال عددی: مسئله بهینه سازی طراحی یک مخزن با قیود تنش و جابجایی. SQP می تواند این مسئله غیرخطی را با تعداد نسبتا کمی تکرار (معمولا ۲۰-۵۰) حل کند. این روش در نرم افزارهایی مانند fmincon در MATLAB (با الگوریتم SQP) استفاده می شود.
مزایا: کارآمد، همگرایی سریع، قابل اعتماد برای طیف وسیعی از مسائل.
معایب: نیاز به مشتق (حداقل گرادیان)، ممکن است برای مسائل با ابعاد بسیار بزرگ پرهزینه شود، نیاز به یک روش QP خوب.
کاربردها: استانداردترین روش برای حل NLP در مهندسی، اقتصاد، و علوم.
نکته: SQP توسط بسیاری از محققان از جمله Biggs، Han، و Powell توسعه یافت.
