آشنایی با روش‌های بهینه‌سازی نامقید (1)

ضرورت و پیشینه:

هنگامی که مسائل بهینه‌سازی نامقید را مطالعه می‌کنیم ممکن است این‌طور به نظر آید که این مسائل چنان عاری از ویژگی‌های ساختاری هستند که مانع از کاربری آن‌ها به‌عنوان مدل‌های مفید برای مسائل با اهمیت می‌شوند. اما به دو دلیل، کاملاً عکس این مطلب صحیح است؛ اولاً می‌توان این استدلال قانع کننده را پیش کشید که اگر قلمروی مسئله گسترش یابد به‌طوری که همه‌ی متغیرهای مربوط به تصمیم‌گیری در نظر گرفته شوند، وجود هیچ قیدی لازم نیست. به عبارت دیگر، قیود مبیّن محدودیت تصنعی میدان عمل هستند و زمانی که این میدان توسعه داده شود از صحنه خارج می‌شوند. بنابراین به‌طور مثال، می‌توان استدلال کرد که قید بودجه یک مشخصه‌ی لازم در فرموله‌کردن یک مسئله‌ی معنی‌دار نیست؛ زیرا دست‌یابی به منابع مالی بیش‌تر همواره با وام گرفتن با یک نرخ بهره‌ی مشخص امکان‌پذیر است و بنابراین به جای معرفی قید بودجه، می‌توان جمله‌ای که هزینه‌ی پول مورد استفاده را منعکس سازد به‌کار گرفت. شبیه همین استدلال در مورد قیودی که مبین دسترس‌پذیری منابع دیگری هستند و با هزینه‌ی مشخص (هر چند زیاد) قابل تأمین می‌باشند، نیز صادق است.

دلیل دوم برای این‌که بسیاری از مسائل مهم را می‌توان بدون قید در نظر گرفت، آن است که مسائل مقید در برخی مواقع به سادگی قابل تبدیل به مسائل نامقید هستند. برای مثال تأثیر نهایی قیود تساوی در یک مسئله‌ی مقید فقط این است که درجات آزادی را، با معرفی برخی از متغیرها به عنوان توابعی از سایر متغیرها محدود کند. این وابستگی‌ها در برخی موارد به‌طور صریح قابل توصیف‌اند و می‌توان یک مسئله‌ی جدید که تعداد متغیرهایش همان درجه‌ی واقعی آزادی است، مشخص کرد. به عنوان یک نمونه‌ی ساده فرض کنید قیدی به‌صورت ${{x}_{1}}+{{x}_{2}}=B$ در یک مسئله‌ی مقید وجود داشته باشد. این قید را می‌توان با جای‌گذاری ${{x}_{1}}=B-{{x}_{2}}$ در تمام قیودی که متغیر ${{x}_{1}}$ در آن‌ها حضور دارد، به سادگی حذف نمود.

مطالعه‌ی مسائل نامقید صرف‌نظر از این‌که به تبیین دسته‌ی مهمی از مسائل عملی می‌انجامد، مسلماً گامی است در راه دسترسی به حالت کلی‌تر یعنی مسائل مقید. بسیاری از جنبه‌های نظری و الگوریتم‌ها در حالت نامقید، و قبل از تعمیم به حالت مقید، به‌صورت بسیار طبیعی‌تری قابل طرح و تحقیقند.

تاریخ بهینه‌سازی نامقید و به‌طور کلی روش‌های بهینه‌یابی را می‌توان به روزگار ریاضی‌دانان گذشته از جمله نیوتن، لاگرانژ و کوشی مرتبط دانست. نخستین مسئله‌ی بهینه‌سازی، 300 سال قبل از میلاد مسیـح توسط اقلیدس شکل گرفت؛ وی نشـان داد که کم‌ترین فاصله‌ی بین یک نقطه و یک خط، طول پاره‌خطی است که از آن نقطه بر خط مورد نظر عمود می‌شود. توسعه‌ی روش‌های بهینه‌سازی در حساب دیفرانسیل مدیون کارهای نیوتن و لایبنیتس است. نیوتن (1669) اندکی پس از ابداع حسابان، با خطی‌سازی توابع، روشی را برای یافتن ریشه‌های یک چندجمله‌ای ارائه کرد. رافسون (1690) روش نیوتن را به کل توابع تعمیم داد. البته نه نیوتن و نه رافـسون هیچ‌کدام از مشتق توابع استفاده نکردند تا این‌که با معرفی سری تیلور (1715)، شکل امروزی این روش که به روش نیوتن- رافسون معروف است، به‌صورت

$${{x}_{n+1}}={{x}_{n}}-\frac{f\left( {{x}_{n}} \right)}{{f}'\left( {{x}_{n}} \right)},~~{{x}_{0}}\in \left( a,b \right),~n=0,1,2,\ldots $$

ثابت شد. ایده‌ی اولیه‌ی روش نیوتن در بهینه‌سازی نامقید از همین روش شکل گرفت. لاگرانژ (1806) برای نخستین بار با معرفی روش ضرایب لاگرانژ، روش بهینه‌سازی برای توابع هدف با محدودیت را طرح نمود و کوشی برای نخستین بار در سال 1847 روش تندترین کاهش را برای حل مسائل بهینه‌سازی نامقید ارائه کرد. تحولات اساسی در بهینه‌سازی نامقید در قرن بیستم رخ داد و ظهور رایانه به این تحولات سرعت بسیاری بخشید. دهه‌ی 1960 را می‌توان دهه‌ی اصلی توسعه‌ی روش‌های عددی در بهینه‌سازی نامقید دانست. در این دهه، هستینز و اشتیفل روش گرادیان مزدوج را ابداع نمودند و دیویدان نخستین روش‌‌ شبه‌نیوتن را به دست آورد. عمده‌ی کارهای محققان در طی دهه‌های بعدی، طرح روش‌های جدید، اصلاح روش‌های قبلی و یا تعمیم روش‌های موجود به مسائلی در ابعاد بزرگ‌تر بوده است و مثلاً از میان آن‌ها می‌توان به ابداع روش $BFGS$ توسط برویدن، فلچر، گلدفارب و شانو ، اصلاح اشنیبل و اسکوو از روش نیوتن و تعمیم روش $BFGS$ به مسائل در مقیاس بزرگ توسط نوسدال اشاره کرد.

طرح مسئله:

یک مسئله‌‌ی بهینه‌سازی در کلی‌ترین صورت خود شامل پیدا کردن مقدار بهینه (بیشینه یا کمینه) تابع $f\left( {{x}_{1}},\ldots ,{{x}_{n}} \right)$ با $n$ متغیر ${{x}_{n}},\ldots ,{{x}_{1}}$ است. در اینجا باید توجه کنیم که از نقطه نظر ریاضی، در نظر گرفتن بیشینه‌سازی و کمینه‌سازی، هر دو، ضرورت ندارد، زیرا بیشینه‌سازی $~f$ هم‌ارز کمینه‌سازی $-f$ است. در نتیجه طبیعتاً در ادامه‌، بحث ما محدود به کمینه‌سازی خواهد شد. گاهی اوقات ممکن است متغیرهای مسئله‌ی بهینه‌سازی به قید یا قیود خاصی محدود شده باشند، که در این صورت با یک مسئله‌ی بهینه‌سازی مقید سروکار داریم و چنان‌چه قیدی روی متغیرها نباشد، مسئله از نوع بهینه‌سازی نامقید است که در این جا، هدف ما آشنایی با این نوع مسائل است. در حالت کلی یک مسئله‌ی بهینه‌سازی نامقید به صورت زیر است:

$$\min\left\{ f\left( x \right)|~x\in {{\mathbb{R}}^{n}} \right\},$$

که در آن فرض می‌شود که $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ تابعی دو بار به‌طور پیوسته مشتق‌پذیر است. برای مطالعه‌ی مسئله‌ی کلی فوق لازم است دو نوع از نقاط جواب، یعنی نقاط کمینه‌ی موضعی و نقاط کمینه‌ی سراسری را متمایز ‌کنیم.

تعریف: فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ و $\bar{x}\in {{\mathbb{R}}^{n}}$. اگر ${{N}_{\varepsilon }}\left( {\bar{x}} \right)$ چنان موجود باشد که به‌ازای هر $x\in {{N}_{\varepsilon }}\left( {\bar{x}} \right)$ داشته باشیم $f\left( {\bar{x}} \right)\le f\left( x \right)$ ، در این صورت $\bar{x}$ را یک کمینه‌ی موضعی تابع $f$ می‌نامیم. هرگاه به ازای هر $x\in {{N}_{\varepsilon }}\left( {\bar{x}} \right)$  که $x\ne \bar{x}$ نامساوی‌ به‌طور اکید برقرار باشد، $\bar{x}$ یک کمینه‌ی موضعی اکید تابع $f$ نامیده می‌شود.

تعریف: فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ و $\bar{x}\in {{\mathbb{R}}^{n}}$ . اگر به ازای هر $x\in {{\mathbb{R}}^{n}}$ داشته باشیم $f\left( {\bar{x}} \right)\le f\left( x \right)$، در این صورت $\bar{x}$ کمینه‌ی سراسری تابع $f$ می‌نامیم. هرگاه به ازای هر $x\in {{\mathbb{R}}^{n}}$ که $x\ne \bar{x}$ نامساوی‌ به‌طور اکید برقرار باشد، $\bar{x}$ یک کمینه‌ی سراسری اکید تابع $f$ نامیده می‌شود.
باید توجه داشت که یافتن کمینه‌ی سراسری یک تابع همواره امکان‌پذیر نیست و معمولاً در عمل به یافتن کمینه‌های موضعی بسنده می‌شود. در ادامه توسط قضایایی به این پرسش که تحت چه شرایطی، یک نقطه، کمینه‌ی موضعی است و چه هنگام یک کمینه‌ی موضعی، کمینه‌ی سراسری نیز هست، پاسخ داده می‌شود.

تعریف: اگر $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ دارای مشتقات جزئی مرتبه اول پیوسته باشد، آنگاه گرادیان $f$ در نقطه‌ی $x=\left( {{x}_{1}},\ldots ,{{x}_{n}} \right)$ که آن را با نماد $\nabla f\left( x \right)$ نشان می‌دهیم، به صورت زیر تعریف می‌شود:

$$\nabla f\left( x \right)=\left( \frac{\partial f}{\partial {{x}_{1}}},\frac{\partial f}{\partial {{x}_{2}}},\ldots ,\frac{\partial f}{\partial {{x}_{n}}} \right).$$

چنان‌چه $f$ دو بار به‌طور پیوسته مشتق‌پذیر باشد، آنگاه هسین $f$ در نقطه‌ی $x=\left( {{x}_{1}},\ldots ,{{x}_{n}} \right)$ که آن را با نماد ${{\nabla }^{2}}f\left( x \right)$  یا $H\left( x \right)$ نشان می‌دهیم ماتریسی $n\times n$ است که به صورت زیر تعریف می‌شود:

$${{\left( H\left( x \right) \right)}_{ij}}=\frac{{{\partial }^{2}}f\left( x \right)}{\partial {{x}_{i}}\partial {{x}_{j}}}.$$

قضیه: (تیلور)

فرض کنید $p\in {{\mathbb{R}}^{n}}$  و $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ به‌طور پیوسته مشتق‌پذیر باشد. در این صورت $t\in \left( 0,1 \right)$  وجود دارد به‌طوری که: $$f\left( x+p \right)=f\left( x \right)+\nabla f{{\left( x+tp \right)}^{t}}p.$$هم‌چنین اگر $f$ دو بار به‌طور پیوسته مشتق‌پذیر باشد، آنگاه:$$\nabla f\left( x+p \right)=\nabla f\left( x \right)+\int_{0}^{1}{{\nabla }^{2}}f\left( x+tp \right)pdt,$$و$$f\left( x+p \right)=f\left( x \right)+{{p}^{t}}\nabla f\left( x \right)+\frac{1}{2}{{p}^{t}}{{\nabla }^{2}}f\left( x+tp \right)p.$$

قضیه: فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ در $x$ مشتق‌پذیر باشد. اگر یک بردار ناصفر $p\in {{\mathbb{R}}^{n}}$ موجود باشد به‌طوری که $\nabla f{{\left( x \right)}^{t}}p<0$ ، در این صورت $T>0$ ی وجود دارد به‌طوری که به ازای هر $t\in \left( 0,T \right)$ داریم: $f\left( x+tp \right)\le f\left( x \right)$. در این حالت بردار $p$ یک جهت کاهشی $f$ در $x$ نامیده می‌شود.

قضیه: (شرایط لازم مرتبه اول)

فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ در یک همسایگی باز از $\bar{x}$ به‌طور پیوسته مشتق‌پذیر باشد.
اگر $\bar{x}$  یک کمینه‌ی موضعی تابع $f$ باشد، آن‌گاه $\nabla f\left( {\bar{x}} \right)=0$؛ به عبارت دیگر $f$ در $\bar{x}$ فاقد جهت کاهشی است.

اثبات: (برهان خلف) فرض کنید $\nabla f\left( {\bar{x}} \right)\ne 0$ . قرار دهید $p=-\nabla f\left( {\bar{x}} \right)$. داریم

$$\nabla f{{\left( {\bar{x}} \right)}^{t}}p=-\nabla f{{\left( {\bar{x}} \right)}^{t}}\nabla f\left( {\bar{x}} \right)=-\nabla f{{\left( {\bar{x}} \right)}^{2}}<0$$

حال از قضیه‌ی قبل نتیجه می‌شود که حداقل یک $\bar{t}>0$ وجود دارد که $f\left( \bar{x}+\bar{t}p \right)<f\left( {\bar{x}} \right)$ اما این با کمینه‌ی موضعی بودن $\bar{x}$ تناقض دارد. این تناقض ناشی از فرض $\nabla f\left( {\bar{x}} \right)\ne 0$ است.

نقطه‌ی $\bar{x}$ به‌طوری که $\nabla f\left( {\bar{x}} \right)=0$، یک نقطه‌ی ایستای تابع $f$ نامیده می‌شود. بنابراین مطابق قضیه‌ی بالا، هر کمینه‌ی موضعی $f$ ، یک نقطه‌ی ایستای $f$ است.

تعریف: ماتریس $A\in {{\mathbb{R}}^{n\times n}}$ را معین مثبت می‌نامیم اگر و تنها اگر به ازای هر $0\ne x\in {{\mathbb{R}}^{n}}$  داشته باشیم ${{x}^{t}}Ax>0$  .

چنان‌چه به ازای هر $x\in {{\mathbb{R}}^{n}}$ داشته باشیم ${{x}^{t}}Ax\ge 0$ ، آنگاه $A$ نیمه‌معین مثبت نامیده می‌شود.

قضیه: فرض کنید مجموعه‌ی ناتهی $S\subseteq {{\mathbb{R}}^{n}}$ مجموعه‌ای محدب و باز باشد و $f:S\to \mathbb{R}$ روی $S$ دوبار مشتق‌‌پذیر باشد. در این‌صورت $f$ تابعی محدب است اگر و تنها اگر ماتریس هسین $f$ در هر نقطه از $S$ نیمه معین مثبت باشد.

در قضیه‌ی فوق، چنان‌چه ماتریس هسین $f$  در هر نقطه از $S$  معین مثبت باشد، آن‌گاه $f$  روی $S$  تابعی اکیداً محدب است ولی عکس این مطلب، لزوماً صحیح نیست. یعنی ممکن است $f$  روی $S$  اکیداً محدب باشد ولی ماتریس هسین $f$  روی $S$  معین مثبت نباشد. برای مثال تابع$f\left( x \right)={{x}^{4}}$  روی اعداد حقیقی را در نظر بگیرید که اکیداً محدب است ولی ماتریس هسین آن، نیمه معین مثبت است.

قضیه: (شرایط لازم مرتبه دوم)  فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ دو بار به‌طور پیوسته مشتق‌پذیر و  $\bar{x}$ یک کمینه‌ی موضعی باشد.
اگر ${{\nabla }^{2}}f\left( {\bar{x}} \right)$ موجود و در یک همسایگی باز از $\bar{x}$ پیوسته باشد، آن‌گاه $\nabla f\left( {\bar{x}} \right)=0$ و ${{\nabla }^{2}}f\left( {\bar{x}} \right)$ نیمه معین مثبت است.

قضیه: (شرایط کافی مرتبه دوم) فرض کنید $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$، $\nabla f\left( {\bar{x}} \right)=0$، ${{\nabla }^{2}}f\left( x \right)$ در یک همسایگی باز از $\bar{x}$ پیوسته و ${{\nabla }^{2}}f\left( {\bar{x}} \right)$ معین مثبت باشد. در این صورت $\bar{x}$ یک کمینه‌ی موضعی اکید تابع $f$ است.

قضیه: اگر $f:{{\mathbb{R}}^{n}}\to \mathbb{R}$ محدب و $\bar{x}$ یک کمینه‌ی موضعی $f$ باشد، آن‌گاه $\bar{x}$ کمینه‌ی سراسری $f$ نیز هست. به علاوه اگر $f$ مشتق‌پذیر باشد، آن‌گاه هر نقطه‌ی ایستای $f$ مانند $\bar{x}$، یک کمینه‌ی سراسری $f$ نیز هست.