روش نلدر-مید کیست؟ توضیح بده.
روش نلدر-مید یا روش سیمپلکس سراشیبی، یک روش عددی رایج در پیدا کردن کمینه یا بیشینه یک تابع هدف در فضای بهینه‌سازی چند بعدی می‌باشد. این یک "روش جستجوی مستقیم" (بر اساس مقایسه عملکرد) است و اغلب برای مشکلات بهینه‌سازی غیرخطی است که مشتقات آن ممکن است مشخص نباشد، استفاده می‌شود. با این حال، تکنیک Nelder-Mead یک روش جستجوی اکتشافی است که می‌تواند به نقاط غیر ثابت، در مورد مسائلی که می‌توان با روشهای جایگزین حل گردد، همگرا شود.روش نلدر-مید توسط جان نلدر و راجر مید در سال ۱۹۶۵ پیشنهاد شد، که به عنوان توسعه ای از روش Spendley و همکاران بود.بررسی اجمالی.در این روش از مفهوم سیمپلکس استفاده شده‌است، که یک چندبر ویژه با "n+1" راس در یک "n" بعدی می‌باشد. نمونه‌هایی از سیمپلکس‌ها عبارتند از: یک پاره خط بر روی یک خط، یک مثلث در صفحه، یک چهار وجهی در فضای سه بعدی و غیره.هنگامی که تابع هدف به نرمی تغییر می‌کند و یکتا می‌باشد، این روش یک بهینه‌سازی محلی برای یک مسئله با "n" متغیر را تقریب می‌کند. پیاده‌سازی‌های معمولی توابع را به حداقل می‌رسانند، یا با به کمینه کردن formula_1 ،formula_2 را بیشینه می‌کنند.به عنوان مثال، در یک پل تعلیق مهندس باید انتخاب کند که هر بند، کابل و اسکله چقدر ضخیم باشد. این عناصر به هم وابسته هستند، اما تجسم تأثیر تغییر هر عنصر خاص کار ساده ای نیست. شبیه‌سازی چنین ساختارهای پیچیده‌ای از لحاظ محاسباتی اغلب پر هزینه بوده و احتمالاً ساعت‌ها برای اجرای آن طول می‌کشد. روش Nelder-Mead، در نوع اصلی نیاز به بیش از دو ارزیابی در هر تکرار ندارد، به جز عملیات منقبض شدن که در ادامه شرح داده شده‌است، که در مقایسه با برخی دیگر از روش‌های بهینه‌سازی جستجوی مستقیم، مورد توجه است. با این حال، مجموع تعداد تکرارها، ممکن است از حد مطلوب پیشنهادی بیشتر باشد.روش نلدر – مید در یک مسئله "n" بعدی، مجموعه از "n+1" نقطه آزمایشی که به صورت سیمپلکس است را در نظر می‌گیرد. سپس به منظور پیدا کردن یک نقطه آزمایشی جدید و جایگزینی یکی از نقاط آزمایشی قدیمی با مورد جدید، رفتا تابع مورد نظر در هر نقطه آزمایشی، مورد بررسی قرار می‌گیرد و سپس این روش ادمه پیدا می‌کند. ساده‌ترین رویکرد جایگزینی بدترین نقطه، از لحاظ مقدار، با یک نقطه منعکس شده، از طریق مرکز "n" نقطه باقی مانده می‌باشد. اگر این نقطه منعکس شده بهتر از نقطه فعلی باشد، می‌توانیم کشیدگی را در امتداد این خط امتحان کنیم. از طرفی دیگر، اگر این نکته جدید بهتر از مقدار نقطه قبلی نباشد، در واقع ما در یک دره قدم می‌گذاریم، بنابراین سیمپلکس را در جهت بدست آوردن یک نقطه بهتر منقبض می‌کنیم. توضیح شهودی الگوریتم از "دستور العمل‌های عددی": روش سرازیر سیمپلکس یک سری مراحل را طی می‌کند به طوریکه بیشتر مراحل فقط نقاط سیمپلکس را در جایی که خروجی تابع بیشینه است، از طریق نقطه مقابل سیمپلکس، به یک نقطه کمینه انتقال می‌دهد. این مراحل بازتاب نامیده می‌شوند، و برای حفظ حجم سیمپلکس ساخته می‌شوند. وقتی این مراحل انجام می‌شود، سیمپلکس در جهت یا جهت دیگر گسترش می‌یابد تا گام‌های بزرگتری برداشته شود. هنگامی که به «کف دره» رسید، این روش خود را در جهت عرضی منقبض می‌کند و سعی می‌کند از دره بیرون رود. اگر شرایطی وجود داشته باشد که سیمپلکس سعی کند «از چشم سوزن عبور کند»، خود را از همه جهات منقبض می‌کند، و خود را به پایین‌ترین (بهترین) نقطه می‌کشد. بر خلاف روش‌های بهینه‌سازی مدرن، روش اکتشافی نلدر-مید می‌تواند به یک نقطه غیر ثابت همگرا شود، مگر اینکه این ممسئله شرایط قوی تری از آنچه برای روش‌های نوین لازم است را برآورده کند. بهبودهای جدیدی بر روش اکتشافی نلدر-مید از سال ۱۹۷۹ شناخته شده‌است.بسته به ماهیت واقعی مسئله حل شده، تغییرات زیادی وجود دارد. یک نوع رایج از یک سیمپلکس کوچک با اندازه ثابت استفاده می‌کند که تقریباً از جهت شیب پیروی می‌کند. این روش همچنین به عنوان روش چندضلعی انعطاف‌پذیر شناخته می‌شود.حالتی از الگوریتم ممکن برای NM.هدف ما به حداقل رساندن تابع formula_2 می‌باشد، جایی که formula_4. نقاط آزمایشی فعلی ما formula_5 هستند.۱. مرتب‌سازی با توجه به مقادیر تابع در رئوس:۲. محاسبه formula_7، که مرکز همه نقاط به جز formula_8 می‌باشد.۳. بازتاب۴. گسترش۵. انقباض۶. کوچک شدنتوجه: formula_31، formula_32، formula_33 و formula_34 ضرایب بازتاب، گسترش، انقباض و کوچکی هستند. مقادیر استاندارد formula_35، formula_36، formula_37 و formula_38 هستند.برای بازتاب، از آن زمان که formula_8 راس با ارزش بالاتر در بین رئوس است، می‌توان انتظار داشت که در بازتاب، formula_8 مقدار کمتری داشته باشد که توسط همه راسها formula_41 جز formula_8 در طرف مخالف شکل گرفته‌است.برای گسترش، اگر نقطه بازتاب formula_13 کمینه جدید در بین رئوس باشد، می‌توان انتظار داشت که مقادیر جالبی را در طول مسیر از formula_7 به formula_13 پیدا کنیم.در مورد انقباض، اگر formula_46 باشد، می‌توان انتظار داشت که یک مقدار بهتر در بین سیمپلکس تشکیل شده توسط همه راسها formula_41 باشد.در نهایت، کوچک شدن یک مورد نادر است، که انقباض از بزرگترین نقطه ای که formula_48 افزایش می‌یابد، اتفاق می‌افتد. اتفاقی که نمی‌تواند به اندازه کافی نزدیک به یک حداقل غیر تکین رخ دهد. در این صورت در انتظار یافتن دورنمایی ساده‌تر انقباض می‌یابد که به پایین‌ترین نقطه می‌رسیم. با این حال، نش اشاره می‌کند که با دقت محدود عددی گاهی اوقات نمی‌تواند در کوچک کردن سیمپلکس عمل کند، و بررسی ای را انجام داد که اندازه در واقع کاهش یافته‌است.سیمپلکس اولیه.سیمپلکس اولیه بسیار مهم است. در واقع، یک سیمپلکس اولیه خیلی کوچک می‌تواند به جستجوی محلی منجر شود، در نتیجه NM می‌تواند به راحتی جوابگو نباشد؛ بنابراین این سیمپلکس باید بستگی به ماهیت مسئله داشته باشد. با این حال، مقاله اصلی سیمپلکس ای را پیشنهاد می‌کند که یک نقطه اولیه به عنوان formula_49 داده می‌شود، همراه با نقاط دیگر که با یک گام ثابت در طول هر بعد تولید می‌شود؛ بنابراین روش به مقیاس متغیرهای که formula_50 را تشکیل می‌دهد، حساس است.شرط خاتمه.معیارهایی برای شکستن چرخه تکراری لازم است. نلدر و مید از انحراف استاندارد برای مقادیر تابع، به ازای سیمپلکس فعلی استفاده کردند. اگر مقادیر تابع کوچکتر از یک مقدار معین گردد، چرخه متوقف می‌شود و پایین‌ترین نقطه در سیمپلکس به عنوان یک نقطه بهینه پیشنهادی بازمی‌گردد. توجه داشته باشید که یک تابع بسیار «مسطح» ممکن است مقادیر عملکرد تقریباً برابر با یک دامنه بزرگ داشته باشد، به طوری که جواب به مقدار تلرانس حساس خواهد بود. نش آزمایشی برای shrinkage به عنوان یکی دیگر از معیارهای خاتمه اضافه می‌کند. توجه داشته باشید که برنامه‌ها خاتمه می‌یابند، در حالی که تکرارها ممکن است همگرا شوند.