دانلود تحقیق مینیمم کردن توابع چند متغیره

یک طراحی مهندسی به تابعی به شکل زیر می رسد: که در آن 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، دو ارزیابی در و از بازه را در نظر می گیریم برای n=3، دو ارزیابی در و از بازه را در نظر می گیریم یعنی و از دو مقدار و ، می توان تعیین نمود که آیا و یا است البته هر دو مورد مشابه اند.

فرض کنید بنابراین نقطه مینیمم باید در بازه باشد، همچنانکه در شکل 6-14 نشان داده شده است.

سومین ارزیابی (نهایی) نزدیک به انجام می گیرد، برای مثال در اگر خواهیم داشت با گرفتن نقطه مرکزی این بازه، را به عنوان تخمین از بدست می آوریم و در می یابیم که از طرف دیگر اگر آنگاه .

دوباره نقطه مرکزی را در نظر می گیریم، و در می‌یابیم که بنابراین اگر از مقدار کوچک صرفه نظر کنیم، در سه ارزیابی F، دقتمان می باشد.

با دامنه الگوی فوق در n ارزیابی از F به تخمین از می رسیم که خطای آن از مقدار زیر تجاوز نمی کند.

در اینجا امین عضو از دنباله فیبوناچی است.

(1) (2) برای مثال تا عبارتند از 21،13، 8،5، 3، 2، 1، 1 در الگوریتم جستجوی فیبوناچی در ابتدا تعداد مراحل N برای خطای مطلوب را برابر اندیس کوچکترین عدد فیبوناچی بزرگتر از انتخاب می کنیم حال دنباله ای از بازه ها را تعریف می کنیم.

با شروع از بازه با طول و برای از فرمول های زیر استفاده می کنیم.

(3) در مرحله قرار می دهیم.

در نهایت به بازه می رسیم که از آن تخمین را بدست می آوریم.

این الگوریتم بعد از مرحله اول تنها به یک ارزیابی تابع در هر مرحله نیاز دارد.

برای اثبات الگوریتم، موقعیت نشان داده شده در شکل 7-14 را در نظر می گیریم از آنجا که خواهیم داشت.

(4) بنابراین طول بازه مربوط با فاکتور کاهش یافته است، مرحله بعد بدست می دهد.

(5) عملاً فاصله بین است بنابراین یکی از نقاط قبلی که در آن تابع ارزیابی شد در انتها یا طرف دیگر است یعنی با معادلات (2)، (4)،(5).

با توجه به معادله (4) واضح است که پس از ارزیابی تابع طول بازه نهایی برابر طول بازه ابتدایی خواهد بود، بنابراین طول نهایی است و خطای ماکزیمم (1) برقرار می باشد.

مرحله نهایی شبیه به آنچه طرح شد می باشد، و F در نقطه ای به فاصله از مرکز بازه نهایی محاسبه می شود و در نهایت از بازه نهایی قرار می دهیم یک عیب جستجوی فیبوناچی این است که الگوریتم، تقریباً پیچیده است.

هم چنین، دقت مطلوب بایستی از پیش داده شود و تعداد مراحل محاسبه برای این دقت قبل از شروع محاسبه تعیین می گردد.

بنابراین نقاط ارزیابی اولیه برای تابع F بستگی به N، تعداد مراحل دارد.

الگوریتم جستجوی نسبت طلایی الگوریتم مشابهی که این معایب را ندارد در زیر توضیح داده می شود.

این الگوریتم به این دلیل جستجوی نسبت طلایی نامیده شده که به نسبت r که به عدد طلایی در نزد یونانیان باستان معروف بوده، بستگی دارد.

این عدد در معادله صدق می کند.

در هر مرحله از این الگوریتم، بازه از اعمال قبلی بدست می آید.

این بازه، بازه ای است که می دانیم شامل نقطه مینیمم است و هدف ما یافتن بازه کوچکتری است که شامل باشد.

در هر مرحله دو مقدار از F مورد نیاز است.

(6) دو حالت ممکن است پیش بیاید: یا فرض کنید حالت اول اتفاق بیافتد شکل 8-14 این موقعیت را نشان می دهد.

از آنجا که فرض شده F پیوسته و تک نمایی است، مینیمم Fباید در بازه باشد.

این بازه، بازه ورودی در آغاز مرحله بعد است.

حال مشاهده می کنید که یک ارزیابی از F در بازه موجود است (در y ) و همچنین داریم: زیرا در مرحله بعد y نقش x را بازی می کند، و ما به مقدار F در نقطه نیاز داریم.

بنابراین کاری که باید انجام دهیم این است که این جایگذاری ها را به ترتیب انجام دهیم.

حالت دیگر هم مشابه است.

اگر نمودار، مشابه شکل 9-14 می باشد.

در این حالت نقطه مینیمم باید در بازه باشد.

در این بازه یک مقدار از F در x موجود است و همچنین داریم: (مسئله 9 را نگاه کنید) بنابراین حالا x نقش y را بازی می کند و مقدار F در نقطه محاسبه می شود، جایگزای های زیر این کارها را انجام می دهد.

مسئله های 11-10 به کمبودی از این فرایند اشاره می کنند، بسیار کند است.

کندی در این بافت اشاره به تعداد زیادی از ارزیابی های تابع دارد که برای کسب دقت منطقی مورد نیاز است.

می توان حدس زد که این کندی منسوب به عمومیت بسیار زیاد (نهایت) الگوریتم می‌باشد، هیچ مزیتی از اینکه F می تواند هموار باشد حاصل نمی گردد.

اگر بازه آغازی در جستجوی مینیمم F باشد، در آنصورت در آغاز با یک ارزیابی از F می توانیم فقط مطمئن باشیم که نقطه مینیمم در بازه ای به طول است در جستجوی نسبت طلایی، طولهای معادل در مراحل پی در پی برای دو ارزیابی از F و برای سه ارزیابی از F و به همین ترتیب بعد از n مرحله نقطه مینیمم در بازه ای به طول معین گردیده است.

چگونه این را با الگوریتم جستجوی فیبوناچی که از n ارزیابی استفاده می نماید می توان مقایسه کرد؟

طول بازه نهایی در این الگوریتم است.

اکنون، الگوریتم فیبوناچی باید بهتر باشد، چونکه بگونه ای طراحی شده که با تعداد مراحل تجویزی تا حد ممکن خوب انجام گیرد.

بنابراین ما انتظار داریم نسبت بزرگتر از یک باشد ولی این نسبت به 17/1 میل می کند (مسئله 8 را ببینید) در نهایت پیچیدگی اضافی الگوریتم فیبوناچی و بستگی آن به تعداد ارزیابی ها ممکن است استفاده آنرا به طور کلی کاهش دهد.

الگوریتم درونیابی درجه دوم(مربعی) فرض