یک طراحی مهندسی به تابعی به شکل زیر می رسد:
که در آن x و y پارامترهایی هستند که باید انتخاب شوند و یک تابع است، که مربوط به مخارج ساخت و ساز است و باید مینیمم شود.
روش های قابل استفاده برای بهینه سازی کردن نقاط را در این فصل مطالعه می کنیم.
مقدمه:
یک کاربرد مهم حساب دیفرانسیل، پیدا کردن مینیمم موضعی یک تابع است. مسائل مربوط به ماکزیمم کردن نیز با تئوری مینیمم کردن قابل حل هستند. زیرا ماکزیمم F در نقطه ای یافت می شود که -F مینیمم خود را اختیار می کند.
در حساب دیفرانسیل تکنیک اساسی برای مینیمم کردن، مشتق گیری از تابعی که می‌خواهیم آن را مینیمم کنیم و مساوی صفر قرار دادن آن است.
نقاطی که معادله حاصل را ارضا می کنند، نقاط مورد نظر هستند. این تکنیک را می توان برای توابع یک یا چند متغیره نیز استفاده کرد. برای مثال اگر یک مقدار مینیمم را بخواهیم، به نقاطی نگاه می کنیم که هر سه مشتق پاره ای برابر صفر باشند.
این روند را نمی توان در محاسبات عدی به عنوان یک هدف عمومی در نظر گرفت. زیرا نیاز به مشتقی دارد که با حل یک یا چند معادله بر حسب یک یا چند متغیر بدست می آید. این کار به همان سختی حل مسئله بصورت مستقیم است.
(معادله در فایل اصلی موجود است)
مسائل مقید[1] و نامقید[2] مینیمم سازی:
مسائل مینیمم سازی به دو شکل هستند:نامقید و مقید:
در یک مسئله ی مینیمم سازی نامقید یک تابع F از یک فضای n بعدی به خط حقیقی R تعریف شده و یک نقطه ی با این خاصیت که
(معادله در فایل اصلی موجود است)
جستجو می شود.
نقاط در را بصورت z, y, x و... نشان می دهیم. اگر نیاز بود که مولفه های یک نقطه را نشان دهیم می نویسیم:
در یک مسئله ی مینیمم سازی مقید، زیر مجموعه ی K در مشخص می شود . یک نقطه
جستجو می شود که برای آن:
(معادله در فایل اصلی موجود است)
چنین مسائلی بسیار مشکل ترند، زیرا نیاز است که نقاط در K در نظر گرفته شوند. بعضی مواقع مجموعه ی K به طریقی پیچیده تعریف می شود.
سهمی گون بیضوی به معادله‌ی
را در نظر بگیرید که در شکل 1-14 مشخص شده است. به وضوح مینیمم نامقید در نقطه ی
(1و1) ظاهر می شود، زیرا:
اگر (معادله در فایل اصلی موجود است)
مینیمم مقید 4 است و در (0،0) اتفاق می افتد.
Matlab دارای قسمتی است برای بهینه سازی که توسط اندرو گریس[3] طراحی شده و شامل دستورات زیادی برای بهینه سازی توابع عمومی خطی و غیر خطی است.
برای مثال ما می توانیم مسئله ی مینیمم سازی مربوط به سهمی گون بیضوی نشان داده شده در شکل 1-14 را حل نماییم.
ابتدا یک M-file به نام q1.m می نویسیم و تابع را تعریف می کنیم:
function f=q1(x) (معادله در فایل اصلی موجود است)
آنگاه از Matlab استفاده می کنیم تا مقدار مینیمم را در نزدیکی نقطه ی برای این تابع بدست آورد:
type q1
(معادله در فایل اصلی موجود است)
بدست می آوریم که نقطه ی مینیمم (1،1) است و مقدار تابع در این نقطه 2 میباشد.
1-14حالت تک متغیره: (معادله در فایل اصلی موجود است)
این حالت، حالت خاصی است که در آن یک تابع F بر روی R تعریف شده باشد. ابتدا بررسی می کنیم که برای حل اینگونه مسائل چگونه باید عمل کرد، زیرا مسئله ی عمومی تر n متغیره معمولاً با یک دنباله از محاسبات روی مسائل یک متغیره حل می شود.
فرض کنید است و ما بدنبال یک نقطه ی می گردیم که:
توجه کنید که اگر هیچ فرضی در مورد F در نظر گرفته نشود، این مسئله در فرم عمومی غیر قابل حل است. برای مثال تابع هیچ نقطه ای مینیممی ندارد. حتی برای توابع خوش تعریفی مانند محاسبات عددی ممکن است به مشکلاتی بر بخورد که علت آن اعداد بزرگ نقطه ی مینیمم مطلق است.
به شکل 2-14 نگاه کنید و مسئله ی کامپیوتری 6 را ببینید. توجه کنید که نقطه ی z یک مینیمم موضعی تابع F است اگر همسایگی از z وجود داشته باشد که برای تمام نقاط داخل آن داشته باشیم:
ما می توانیم از Matlab برای بدست آوردن مقادیر مینیمم موضعی تابع استفاده کنیم. ابتدا ما تابع را در یک فایل به نام q2.m مطابق زیر تعریف می کنیم.
سپس از matlab برای یافتن مقدار مینیمم در بازه ی استفاده می کنیم:
type q2
نقطه ی محاسبه شده ممکن است یک مینیمم مطلق نباشد. برای یافتن مینیمم مطلق می توانیم نقاط اولیه ی متفاوتی را انتخاب کنیم و مینیمم های مطلق را بیابیم، آنگاه مینیمم آن ها را پیدا کنیم.
(نمودار در فایل اصلی موجود است)
F تک نما[4]:
یک فرض قابل قبول این است که در یک بازه ی [a,b] که از قبل به ما داده شده، F تنها دارای یک مینیمم موضعی باشد. این خاصیت معمولاً با گفتن این که F بر روی [a,b] تک نمایی است بیان می شود.
(توجه:در علم آمار تک نمایی مربوط به ماکزیمم موضعی است)
بعضی توابع تک نمایی در شکل 3-14 نشان داده شده اند:
یک خاصیت مهم توابع تک نمایی پیوسته، که از شکل 3-14 نیز مشخص است، این است که این توابع بصورت یکنوا کاهش می یابند تا به نقطه ی مینیمم می رسند و بعد از آن بصورت یکنوا افزایش می یابند. برای مشخص کردن این موضوع، را مینیمم تابع F در بازه ی [a,b] بگیرید و فرض کنید برای مثال F بصورت یکنوا بر روی بازه ی کاهش نمی‌یابد، آنگاه نقاط و وجود دارند که:
و (معادله در فایل اصلی موجود است)
حال فرض می کنیم یک نقطه ی مینیمم روی بازه ی باشد. (توجه کنید که تابع پیوسته روی یک بازه ی بسته، مینیمم خود را اختیار می کند) ما می توانیم فرض کنیم که برای اینکه اگر مقدار اولیه ، انتخاب می شد، می توانستیم آن را با جایگذاری کنیم، زیرا
ولی اکنون می بینیم که یک نقطه ی مینیم F روی است و
وجود دو مینیمم موضعی، البته با تک نمایی بودن F تناقض دارد.
(معادله در فایل اصلی موجود است)
الگوریتم جستجوی فیبوناچی[5]
اکنون مسئله ای را مطرح می کنیم که مربوط به جستجوی نقطه مینیمم از تابع پیوسته و تک نمایی F بر روی بازه معین می باشد. تا چه اندازه دقیق می توان نقطه مینیمم را با فقط n ارزیابی از F محاسبه کرد؟ بدون هیچ گونه ارزیابی از F بهترین چیزی که می توان گفت این است که ، و با گرفتن نقطه میانی به عنوان بهترین تخمین، خطای را می دهد. یک ارزیابی به تنهایی این موقعیت را ثابت نمی نماید و بنابراین بهترین تخمین و خطا به مانند مورد قبل باقی می ماند. بنابراین حداقل دو ارزیابی تابع را نیاز داریم، تا تخمین بهتری را بدست آوریم.
فرض کنید F در و محاسبه شده باشند، نتیجه در شکل 4-14 نشان داده شده. اگر چون در سمت راست صعودی است می توانیم مطمئن باشیم که . از طرف دیگر، استدلال مشابه در مورد نشان می دهد که . برای اینکه دو بازه فوق را به حداقل ممکن برسانیم را به چپ و را به راست حرکت می دهیم. بنابراین F می بایستی در دو نقطه نزدیک در هر طرف از نقطه مرکزی ارزیابی شود، همچنانکه در شکل 5-14 نشان داده شده است. فرض کنید:
با گرفتن نقطه مرکزی زیر بازه یا به عنوان بهترین تخمین از در می یابیم که خطا از فرا تر نمی رود. این را خواننده به راحتی می تواند تأیید نماید.
برای n=3، دو ارزیابی در و از بازه را در نظر می گیریم یعنی و
(معادله در فایل اصلی موجود است)
از دو مقدار و ، می توان تعیین نمود که آیا و یا است البته هر دو مورد مشابه اند. فرض کنید بنابراین نقطه مینیمم باید در بازه باشد، همچنانکه در شکل 6-14 نشان داده شده است. سومین ارزیابی (نهایی) نزدیک به انجام می گیرد، برای مثال در اگر خواهیم داشت با گرفتن نقطه مرکزی این بازه، را به عنوان تخمین از بدست می آوریم و در می یابیم که از طرف دیگر اگر آنگاه . دوباره نقطه مرکزی را در نظر می گیریم، و در می‌یابیم که بنابراین اگر از مقدار کوچک صرفه نظر کنیم، در سه ارزیابی F، دقتمان می باشد.
با دامنه الگوی فوق در n ارزیابی از F به تخمین از می رسیم که خطای آن از مقدار زیر تجاوز نمی کند. در اینجا امین عضو از دنباله فیبوناچی است.
(1) (معادله در فایل اصلی موجود است)
(2) (معادله در فایل اصلی موجود است)
برای مثال تا عبارتند از 21،13، 8،5، 3، 2، 1، 1
در الگوریتم جستجوی فیبوناچی در ابتدا تعداد مراحل N برای خطای مطلوب را برابر اندیس کوچکترین عدد فیبوناچی بزرگتر از انتخاب می کنیم حال دنباله ای از بازه ها را تعریف می کنیم. با شروع از بازه با طول و برای از فرمول های زیر استفاده می کنیم.
(3) (معادله در فایل اصلی موجود است)
در مرحله قرار می دهیم.
در نهایت به بازه می رسیم که از آن تخمین را بدست می آوریم. این الگوریتم بعد از مرحله اول تنها به یک ارزیابی تابع در هر مرحله نیاز دارد.
برای اثبات الگوریتم، موقعیت نشان داده شده در شکل 7-14 را در نظر می گیریم از آنجا که خواهیم داشت.
(4) (معادله در فایل اصلی موجود است)
بنابراین طول بازه مربوط با فاکتور کاهش یافته است، مرحله بعد بدست می دهد.