روش نلدر-مید

بندانگشتی|320x320پیکسل| Nelder – Mead جستجوی حداقل تابع Simionescu. راس‌های سیمپلکس با مقدار آنها مرتب می‌گردد، که ۱ دارای کمترین (بهترین) مقدار است.
**روش نلدر-مید**  یا روش سیمپلکس سراشیبی، یک روش عددی رایج در پیدا کردن کمینه یا بیشینه یک تابع هدف در فضای بهینه‌سازی چند بعدی می‌باشد. این یک *روش جستجوی مستقیم* (بر اساس مقایسه عملکرد) است و اغلب برای مشکلات بهینه‌سازی غیرخطی است که مشتقات آن ممکن است مشخص نباشد، استفاده می‌شود. با این حال، تکنیک Nelder-Mead یک روش جستجوی اکتشافی است که می‌تواند به نقاط غیر ثابت، در مورد مسائلی که می‌توان با روشهای جایگزین حل گردد، همگرا شود.

روش نلدر-مید توسط جان نلدر و راجر مید در سال ۱۹۶۵ پیشنهاد شد، که به عنوان توسعه ای از روش Spendley و همکاران بود.

## بررسی اجمالی
در این روش از مفهوم سیمپلکس استفاده شده‌است، که یک چندبر ویژه با *n+1* راس در یک *n* بعدی می‌باشد. نمونه‌هایی از سیمپلکس‌ها عبارتند از: یک پاره خط بر روی یک خط، یک مثلث در صفحه، یک چهار وجهی در فضای سه بعدی و غیره.

هنگامی که تابع هدف به نرمی تغییر می‌کند و یکتا می‌باشد، این روش یک بهینه‌سازی محلی برای یک مسئله با *n* متغیر را تقریب می‌کند. پیاده‌سازی‌های معمولی توابع را به حداقل می‌رسانند، یا با به کمینه کردن - f(\mathbf x) ،f(\mathbf x) را بیشینه می‌کنند.

به عنوان مثال، در یک پل تعلیق مهندس باید انتخاب کند که هر بند، کابل و اسکله چقدر ضخیم باشد. این عناصر به هم وابسته هستند، اما تجسم تأثیر تغییر هر عنصر خاص کار ساده ای نیست. شبیه‌سازی چنین ساختارهای پیچیده‌ای از لحاظ محاسباتی اغلب پر هزینه بوده و احتمالاً ساعت‌ها برای اجرای آن طول می‌کشد. روش Nelder-Mead، در نوع اصلی نیاز به بیش از دو ارزیابی در هر تکرار ندارد، به جز عملیات منقبض شدن که در ادامه شرح داده شده‌است، که در مقایسه با برخی دیگر از روش‌های بهینه‌سازی جستجوی مستقیم، مورد توجه است. با این حال، مجموع تعداد تکرارها، ممکن است از حد مطلوب پیشنهادی بیشتر باشد.

روش نلدر – مید در یک مسئله *n* بعدی، مجموعه از *n+1* نقطه آزمایشی که به صورت سیمپلکس است را در نظر می‌گیرد. سپس به منظور پیدا کردن یک نقطه آزمایشی جدید و جایگزینی یکی از نقاط آزمایشی قدیمی با مورد جدید، رفتا تابع مورد نظر در هر نقطه آزمایشی، مورد بررسی قرار می‌گیرد و سپس این روش ادمه پیدا می‌کند. ساده‌ترین رویکرد جایگزینی بدترین نقطه، از لحاظ مقدار، با یک نقطه منعکس شده، از طریق مرکز *n* نقطه باقی مانده می‌باشد. اگر این نقطه منعکس شده بهتر از نقطه فعلی باشد، می‌توانیم کشیدگی را در امتداد این خط امتحان کنیم. از طرفی دیگر، اگر این نکته جدید بهتر از مقدار نقطه قبلی نباشد، در واقع ما در یک دره قدم می‌گذاریم، بنابراین سیمپلکس را در جهت بدست آوردن یک نقطه بهتر منقبض می‌کنیم. توضیح شهودی الگوریتم از "دستور العمل‌های عددی":
 روش سرازیر سیمپلکس یک سری مراحل را طی می‌کند به طوریکه بیشتر مراحل فقط نقاط سیمپلکس را در جایی که خروجی تابع بیشینه است، از طریق نقطه مقابل سیمپلکس، به یک نقطه کمینه انتقال می‌دهد. این مراحل بازتاب نامیده می‌شوند، و برای حفظ حجم سیمپلکس ساخته می‌شوند. وقتی این مراحل انجام می‌شود، سیمپلکس در جهت یا جهت دیگر گسترش می‌یابد تا گام‌های بزرگتری برداشته شود. هنگامی که به «کف دره» رسید، این روش خود را در جهت عرضی منقبض می‌کند و سعی می‌کند از دره بیرون رود. اگر شرایطی وجود داشته باشد که سیمپلکس سعی کند «از چشم سوزن عبور کند»، خود را از همه جهات منقبض می‌کند، و خود را به پایین‌ترین (بهترین) نقطه می‌کشد.  بر خلاف روش‌های بهینه‌سازی مدرن، روش اکتشافی نلدر-مید می‌تواند به یک نقطه غیر ثابت همگرا شود، مگر اینکه این ممسئله شرایط قوی تری از آنچه برای روش‌های نوین لازم است را برآورده کند. بهبودهای جدیدی بر روش اکتشافی نلدر-مید از سال ۱۹۷۹ شناخته شده‌است.

بسته به ماهیت واقعی مسئله حل شده، تغییرات زیادی وجود دارد. یک نوع رایج از یک سیمپلکس کوچک با اندازه ثابت استفاده می‌کند که تقریباً از جهت شیب پیروی می‌کند. این روش همچنین به عنوان **روش چندضلعی انعطاف‌پذیر** شناخته می‌شود.

## حالتی از الگوریتم ممکن برای NM

[چپ|بندانگشتی| روش Nelder-Mead برای [تابع روزن‌بروک|تابع Rosenbrock استفاده شده‌است.]]
هدف ما به حداقل رساندن تابع f(\mathbf x) می‌باشد، جایی که \mathbf x \in \mathbb{R}^n. نقاط آزمایشی فعلی ما \mathbf x_1, \ldots, \mathbf x_{n+1} هستند.

**۱.** **مرتب‌سازی** با توجه به مقادیر تابع در رئوس:

: f(\mathbf x_1) \leq f(\mathbf x_2) \leq \cdots \leq f(\mathbf x_{n+1}).

: بررسی کنید که آیا روش باید متوقف شود. '''خاتمه''' را در زیر مشاهده کنید. گاهی اوقات به گونه ای نامناسب «همگرایی» خوانده می‌شود.

**۲.** محاسبه \mathbf x_o، که مرکز همه نقاط به جز \mathbf x_{n+1} می‌باشد.

**۳.** **بازتاب**

: محاسبه نقطه منعکس شده \mathbf x_r = \mathbf x_o + \alpha (\mathbf x_o - \mathbf x_{n+1}) با \alpha > 0.
: اگر نقطه منعکس شده f(\mathbf x_1) \leq f(\mathbf x_r) ،
:: سپس با جایگزین کردن بدترین نقطه \mathbf x_{n+1}، با نقطه منعکس شده \mathbf x_r، سیمپلکس جدید را به دست آورید و به مرحله ۱ بازگردید.

**۴. گسترش**

: اگر نکته منعکس شده بهترین نقطه تا کنون است، f(\mathbf x_r) ،
:: سپس نقطه گسترش یافته را محاسبه کنید \mathbf x_e = \mathbf x_o + \gamma (\mathbf x_r - \mathbf x_o) با \gamma > 1.
:: اگر نقطه گسترش یافته بهتر از نقطه منعکس شده باشد، f(\mathbf x_e) ،
::: سپس با جایگزین کردن بدترین نکته \mathbf x_{n+1}، با نقطه گسترش یافته \mathbf x_e سیمپلکس جدید را بدست آورید و به مرحله ۱ بروید؛:: در غیر اینصورت با جایگزین کردن بدترین نکته \mathbf x_{n+1}، با نکته منعکس شده \mathbf x_r سیمپلکس جدید را بدست آورید و به مرحله ۱ بروید.

**۵.** **انقباض**

: در اینجا مسلم است که f(\mathbf x_r) \geq f(\mathbf x_n) . (توجه داشته باشید که \mathbf x_n دوم یا بالاترین «بعدی» است)
: محاسبه نقطه انقباض شده \mathbf x_c = \mathbf x_o + \rho(\mathbf x_{n+1} - \mathbf x_o) با 0 .
: اگر نقطه انقباض شده بهتر از بدترین نقطه باشد، یعنی f(\mathbf x_c) ،
:: سپس با جایگزین کردن بدترین نکته \mathbf x_{n+1}، با نقطه انقباض شده \mathbf x_cسیمپلکس جدید را بدست آورید و به مرحله ۱ بروید.

**۶.** **کوچک شدن**

: همه نقاط را به جز بهترین (\mathbf x_1) با
: \mathbf x_i = \mathbf x_1 + \sigma(\mathbf x_i - \mathbf x_1) جایگزین کنید و به مرحله ۱ بروید.

**توجه**: \alpha، \gamma، \rho و \sigma ضرایب بازتاب، گسترش، انقباض و کوچکی هستند. مقادیر استاندارد \alpha = 1، \gamma = 2، \rho = 1/2 و \sigma = 1/2 هستند.

برای **بازتاب**، از آن زمان که \mathbf x_{n+1} راس با ارزش بالاتر در بین رئوس است، می‌توان انتظار داشت که در بازتاب، \mathbf x_{n+1} مقدار کمتری داشته باشد که توسط همه راسها \mathbf x_i جز \mathbf x_{n+1} در طرف مخالف شکل گرفته‌است.

برای **گسترش**، اگر نقطه بازتاب \mathbf x_r کمینه جدید در بین رئوس باشد، می‌توان انتظار داشت که مقادیر جالبی را در طول مسیر از \mathbf x_o به \mathbf x_r پیدا کنیم.

در مورد **انقباض**، اگر f(\mathbf x_r) > f(\mathbf x_n) باشد، می‌توان انتظار داشت که یک مقدار بهتر در بین سیمپلکس تشکیل شده توسط همه راسها \mathbf x_i باشد.

در نهایت، **کوچک شدن** یک مورد نادر است، که انقباض از بزرگترین نقطه ای که f افزایش می‌یابد، اتفاق می‌افتد. اتفاقی که نمی‌تواند به اندازه کافی نزدیک به یک حداقل غیر تکین رخ دهد. در این صورت در انتظار یافتن دورنمایی ساده‌تر انقباض می‌یابد که به پایین‌ترین نقطه می‌رسیم. با این حال، نش اشاره می‌کند که با دقت محدود عددی گاهی اوقات نمی‌تواند در کوچک کردن سیمپلکس عمل کند، و بررسی ای را انجام داد که اندازه در واقع کاهش یافته‌است.

## سیمپلکس اولیه
سیمپلکس اولیه بسیار مهم است. در واقع، یک سیمپلکس اولیه خیلی کوچک می‌تواند به جستجوی محلی منجر شود، در نتیجه NM می‌تواند به راحتی جوابگو نباشد؛ بنابراین این سیمپلکس باید بستگی به ماهیت مسئله داشته باشد. با این حال، مقاله اصلی سیمپلکس ای را پیشنهاد می‌کند که یک نقطه اولیه به عنوان \mathbf x_1
 داده می‌شود، همراه با نقاط دیگر که با یک گام ثابت در طول هر بعد تولید می‌شود؛ بنابراین روش به مقیاس متغیرهای که \mathbf x را تشکیل می‌دهد، حساس است.

## شرط خاتمه
معیارهایی برای شکستن چرخه تکراری لازم است. نلدر و مید از انحراف استاندارد برای مقادیر تابع، به ازای سیمپلکس فعلی استفاده کردند. اگر مقادیر تابع کوچکتر از یک مقدار معین گردد، چرخه متوقف می‌شود و پایین‌ترین نقطه در سیمپلکس به عنوان یک نقطه بهینه پیشنهادی بازمی‌گردد. توجه داشته باشید که یک تابع بسیار «مسطح» ممکن است مقادیر عملکرد تقریباً برابر با یک دامنه بزرگ داشته باشد، به طوری که جواب به مقدار تلرانس حساس خواهد بود. نش آزمایشی برای shrinkage به عنوان یکی دیگر از معیارهای خاتمه اضافه می‌کند. توجه داشته باشید که برنامه‌ها خاتمه می‌یابند، در حالی که تکرارها ممکن است همگرا شوند.

## جستارهای وابسته

* Derivative-free optimization
*  COBYLA 
*  NEWUOA 
*  LINCOA 
* Nonlinear conjugate gradient method
* Levenberg–Marquardt algorithm
* Broyden–Fletcher–Goldfarb–Shanno or  BFGS method 
* Differential evolution
* Pattern search (optimization)
* CMA-ES

## منابع

## خواندن بیشتر

* 
* 
* 
* 
* 

## پیوند به بیرون
* توضیح و تجسم نلدر مید (Downhill Simplex) با عملکرد موز روزنزبروک
* جان بورکارد: کد نلدر-مید در ماتلب - توجه داشته باشید که تغییر روش Nelder-Mead نیز توسط fminsearch عملکرد Matlab انجام شده‌است.
* بهینه‌سازی Nelder-Mead در پایتون در کتابخانه SciPy.
* nelder-mead - اجرای پایتون از روش Nelder-Mead -
* SOVA 1.0 (نرم‌افزار رایگان) - بهینه‌سازی ساده برای کاربردهای مختلف
* https://web.archive.org/web/20190512002351/http://www.hillstormer.es/ - HillStormer، ابزاری عملی برای بهینه‌سازی ساده غیر محدود، چند متغیره و خطی توسط Nelder Mead.
رده:روش‌های بهینه‌سازی