در پست های قبلی مقاله ای با عنوان تحلیل و بهینه سازی پروفایل ساقه کولتیواتور برایتان گذاشتم که از روش SQP برای بهینه سازی مسئله خودش استفاده کرده بود.
برنامه ریزی درجه دوم متوالی یک روش تکرار پذیر بسیار مناسب و مفید برای حل عددی مسائل بهینه سازی غیر خطی است. این روش دنباله ای از یک مجموعه مسائل بهینه سازی را حل میکند که هر کدام از آن مسائل یک مدل دو بعدی از موضوع هدف را به یک خطی سازی از شروط بهینه میکنند. اگر مسئله هیچ گونه محدودیت و شرطی نداشت، این روش به روش نیوتن کاهش پیدا میکند. در روش نیوتن نقطه ای پیدا می شود که در آن نقطه گرادیان هدف ناپدید می شود. محدودیت ها به دو نوع برابری و نابرابری (شروط مساوی و نامساوی) تقسیم می شوند. اگر مسئله فقط شروط مساوی داشت، روش SQP معادل استفاده از روش نیوتن برای شرایط بهینگی مرتبه اول مسئله (یا شروط کاروش-کان-تاکر ) است. روش SQP را می توان در متلب اجرا کرد.
مطابق یک مسئله بهینه سازی غیر خطی (NLP) به شکل زیر داریم:
روش SQP یک روش تکرار پذیر است که NLP را برای یک تکرار مشخص x^k که k∈N_0 و با یک سری زیر مسئله برنامه ریزی دو بعدی مدل می کند. زیر مسئله ها را حل میکند و از حل آنها برای ساخت یک تکرار جدید x^(k+1) استفاده میکند. این ساختار پایان می پذیرد به گونه ای که دنباله (x^k )_(k∈N_0 ) به یک x^* مینیمم همگرا می شود. روش حل و بیان تئوری آن به علت پیچیده بودن و نیاز به دانش ریاضی پیشرفته در این نوشته نمی گنجد. توجه شود که توابع هدف و شرط باید توابع غیر خطی صاف (یکنواخت) باشند. یکنواختی بدان معنی است که حداقل قابلیت مشتق پذیری درجه اول را داشته باشند.
برای حل اینگونه مسائل در MATLAB، جعبه ابزاری به نام جعبه ابزار بهینه سازی وجود دارد. یکی از ابزارهای این جعبه برای حل مسائل SQP استفاده می شود:
همچنین در شکل دیگر از این ابزار داریم:
برای اینکه توابع شروط نامساوی و مساوی غیر خطی را هم منظور کرد شکل زیر از تابع را داریم:
پارامترهای ورودی:
(x) : برداری که حدس اولیه از حل مسئله را میدهد. طول آن برای تعیین تعداد متغیر ها (n) استفاده می شود.
(lm) – دلخواه: برداری که حدس اولیه از راه حل دوگانه میدهد که 4 حالت متفاوت دارد.
(lb) - دلخواه: برداری که مرز حداقل x را مشخص میکند که میتواند مقدار بینهایت را هم بگیرد.
(ub) - دلخواه: برداری که مرز حداکثر x را مشخص میکند که میتواند مقدار بینهایت را هم بگیرد.
(options) - دلخواه: ساختار تعریف شده برای حل.
پارامترهای خروجی:
(x) : بردار ابعادی که راه حل ابتدایی محاسبه شده برای x را مشخص میکند.
(lm) : برداری ابعادی که حل محاسبه شده راه حل دوگانه را میدهد.
(info) : ساختاری که اطلاعات را برای حداقل سازی مشخص میکند.
برنامه ریزی درجه دوم متوالی یک روش تکرار پذیر بسیار مناسب و مفید برای حل عددی مسائل بهینه سازی غیر خطی است. این روش دنباله ای از یک مجموعه مسائل بهینه سازی را حل میکند که هر کدام از آن مسائل یک مدل دو بعدی از موضوع هدف را به یک خطی سازی از شروط بهینه میکنند. اگر مسئله هیچ گونه محدودیت و شرطی نداشت، این روش به روش نیوتن کاهش پیدا میکند. در روش نیوتن نقطه ای پیدا می شود که در آن نقطه گرادیان هدف ناپدید می شود. محدودیت ها به دو نوع برابری و نابرابری (شروط مساوی و نامساوی) تقسیم می شوند. اگر مسئله فقط شروط مساوی داشت، روش SQP معادل استفاده از روش نیوتن برای شرایط بهینگی مرتبه اول مسئله (یا شروط کاروش-کان-تاکر ) است. روش SQP را می توان در متلب اجرا کرد.
مطابق یک مسئله بهینه سازی غیر خطی (NLP) به شکل زیر داریم:
minimize f(x) ,over x∈R^n , subject to h(x)=0 ,g(x)≤0
که در آن f تابع هدف و توابع h و g، شروط مساوی و نامساوی را توصیف میکنند. اگر تابع هدف دو بعدی باشد و توابع شرط معین مسئله (NLP) حالت دو بعدی پیدا می کند.روش SQP یک روش تکرار پذیر است که NLP را برای یک تکرار مشخص x^k که k∈N_0 و با یک سری زیر مسئله برنامه ریزی دو بعدی مدل می کند. زیر مسئله ها را حل میکند و از حل آنها برای ساخت یک تکرار جدید x^(k+1) استفاده میکند. این ساختار پایان می پذیرد به گونه ای که دنباله (x^k )_(k∈N_0 ) به یک x^* مینیمم همگرا می شود. روش حل و بیان تئوری آن به علت پیچیده بودن و نیاز به دانش ریاضی پیشرفته در این نوشته نمی گنجد. توجه شود که توابع هدف و شرط باید توابع غیر خطی صاف (یکنواخت) باشند. یکنواختی بدان معنی است که حداقل قابلیت مشتق پذیری درجه اول را داشته باشند.
برای حل اینگونه مسائل در MATLAB، جعبه ابزاری به نام جعبه ابزار بهینه سازی وجود دارد. یکی از ابزارهای این جعبه برای حل مسائل SQP استفاده می شود:
x = fmincon(fun,x0,A,b)
در این شکل، ابزار از مقدار x_0 شروع کرده تا حداقل x تابع fun را بیابد با توجه به A*x≤b*x_0. پارامتر های A و b نامساوی های خطی هستند.همچنین در شکل دیگر از این ابزار داریم:
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)
در این شکل از استفاده نیز ابزار با تعریف حداقل و حداکثر x (lb,ub)، جواب بین این دو مقدار بدست می آید. پارامتر های Aeq و beq مساوی های خطی هستند.برای اینکه توابع شروط نامساوی و مساوی غیر خطی را هم منظور کرد شکل زیر از تابع را داریم:
x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)
این شروط در قسمت nonIcon وارد می شوند. مثلاً:x = fmincon(@myfun,x0,A,b,Aeq,beq,lb,ub,@mycon)
که پارامتر mycon به قرار زیر است:function [c,ceq] = mycon(x)
c = ... % Compute nonlinear inequalities at x.
ceq = ... % Compute nonlinear equalities at x.
به عنوان یک مثال از مسئله بهینه سازی در متلب، می خواهیم xای پیدا کنیم که تابع f(x)=-x_1 x_2 x_3 را با شروع از نقطه x=[10;10;10] و با توجه به شرط 0≤x_1+2x_2+2x_3≤72 حداقل کند. ابتدا در متلب m-فایلی را برای تعریف تابع هدف می نویسیم:function f = myfun(x)
f = -x(1) * x(2) * x(3);
سپس شرط ها را بازنویسی میکنیم تا دو شرط کوچکتر مساوی داشته باشیم:-x_1-2x_2-2x_3≤0
x_1+2x_2+2x_3≤72
هر دو شرط خطی هستند که آنها را به صورت ماتریسی و به شکل A.x≤b بازنویسی میکنیم:A=[-1,-2,-2;1,2,2], b=[0;72]
و در ادامه:x0 = [10; 10; 10]; % Starting guess at the solution
[x,fval] = fmincon(@myfun,x0,A,b)
که بعد از 66 تکرار مقدار زیر حاصل شد:fval =
-3.4560e+03
و شروط نامساوی خطی به مقدار کمتر یا مساوی صفر تخمین زده شدند.A*x-b=
-72
0
همچنین کتابخانه ای پیشرفته تر به نام SQPLab برای این منظور ساخته شده است که مسائل با شرایط بیشتری را می تواند حل کند. فرم استفاده از این کتابخانه به شکل زیر است:[x,lm,info] = sqplab (@simul, x, lm, lb, ub, options)
که در آن پارامتر ها به قرار زیر هستند:پارامترهای ورودی:
(x) : برداری که حدس اولیه از حل مسئله را میدهد. طول آن برای تعیین تعداد متغیر ها (n) استفاده می شود.
(lm) – دلخواه: برداری که حدس اولیه از راه حل دوگانه میدهد که 4 حالت متفاوت دارد.
(lb) - دلخواه: برداری که مرز حداقل x را مشخص میکند که میتواند مقدار بینهایت را هم بگیرد.
(ub) - دلخواه: برداری که مرز حداکثر x را مشخص میکند که میتواند مقدار بینهایت را هم بگیرد.
(options) - دلخواه: ساختار تعریف شده برای حل.
پارامترهای خروجی:
(x) : بردار ابعادی که راه حل ابتدایی محاسبه شده برای x را مشخص میکند.
(lm) : برداری ابعادی که حل محاسبه شده راه حل دوگانه را میدهد.
(info) : ساختاری که اطلاعات را برای حداقل سازی مشخص میکند.
