مقدمه

بهینه‌سازی ایستا

ماتریس‌ها

تعاریف

همسایگی اپسیلونی

$N_{\epsilon }(x)={y\in X:d_{2}(x,y)<\epsilon }$

مجموعهٔ باز

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

مجموعهٔ فشرده

مجموعهٔ فشرده (به انگلیسی: Compact set)، در فضای اقلیدسی (در $\mathbb {R} ^{n}$ ) مجموعه‌ای است که بسته و کراندار باشد.

تقعر و تحدب توابع

تابع مقعر

تابع مقعر (به انگلیسی: Concave function) تابعی است که اگر دو نقطه روی تابع را به هم وصل کنیم در زیر یا روی نمودار قرار بگیرد.

اگر یک تابع صعودی را بر یک تابع مقعر اعمال کنیم، مقعر بودن به هم می‌ریزد ولی خاصیت شبه‌تقعر نه (؟)

تابع محدب

تابع محدب (به انگلیسی: Convex funtion) تابعی است که اگر دو نقطه روی تابع را به هم وصل کنیم در بالا یا روی نمودار قرار بگیرد. نکته: اشتراک دو مجموعه محدب همچنان محدب است اما اجتماع آن‌ها نه (مثلا دو دایره کنار هم)

در مجموعه‌های محدب اکید، نقاط نمی‌توانند روی مرز باشند. (مثلا در یک مربع اضلاع آن همگی روی خود مرز هستند پس محدب است ولی نه اکیدا) به همین علت چون مجموعه‌های باز نقاط مرزی ندارند، اگر مجموعهٔ بازی محدب باشد محدب اکید است.

تابع شبه مقعر

$f[(1-\Theta )x'+\Theta x'']>min\{f(x'),f(x'')\}$

طبق تعریف، مقدار تابع شبه مقعر (به انگلیسی: quasi-concave) در بین دو نقطهٔ $x'$ و $x''$ از دو مقدار $f(x)$ و $f(x')$ پایین‌تر نمی‌رود و از این رو تابع دارای حداکثر یک مقدار ماکسیمم و یک قله است. اما تابع شبه مقعر می‌تواند قسمت پخی (به انگلیسی: flatness) داشته باشد، پس با اینکه جواب یکتاست اما می‌تواند در چند $x$ رخ دهد، حال آنکه در شبه مقعر اکید، خیر.

ضمناً مزیت دیگر تابع شبه مقعر آن است که، شبه تقعر برخلاف تقعر با اعمال یک تابع صعودی به هم نمی‌ریزد.

اثبات می‌شود که تابعی که مقعر است، شبه مقعر نیز هست.

تفسیر اقتصادی محدب‌بودن ترجیحات یک فرد

نوشتار اصلی: :w:ترجیحات محدب‎

زمانی که برای مثال منحنی‌های بی‌تفاوتی، محدب هستند، معنی آن این است که «متوسط از دو طیف حداکثری همواره بهتر،‌ یا لااقل به همان اندازه خوب است».^[۱]

توجه داشته باشید که مطابق یک لم در اقتصاد خرد^[۲]، رابطه‌ی ترجیحات (به انگلیسی: Preference Relation) محدب است اگر و تنها اگر تابع مطلوبیت، شبه‌مقعر باشد. اگر رابطه‌ی ترجیحات محدب باشد، تمامی منحنی‌های بی‌تفاوتی نسبت به مبدا محدب هستند.

تفسیر جمعی بودن مطلوبیت یک فرد

اگر تابع مطلوبیتی همچون $U(c,l)=u(c)+v(l)$ را در نظر بگیریم، خاصیت additive بودن باعث می‌شود که مطلوبیت نهایی مصرف یک کالا بر مطلوبیت نهایی مصرف کالای دیگر موثر نباشد.

وجود جواب

در صورت برقراری شروط قضیهٔ مقدار کرانی (به انگلیسی: Extreme Value Theorem) یعنی:

بسته‌بودن بازه‌ی تعریف تابع (مثلا قید سوال بهینه‌سازی یا دامنه) و تهی نبودن این مجموعه

پیوسته‌بودن خود تابع در این بازه (یا مجموعه)

تابع اقلا یکبار مقادیر ماکسیمم و می‌نیمم خود را می‌گیرد. این دو شرط برای وجود جواب کافی هستند.

برای مطالعه بیشتر به صفحه‌ی همین قضیه در ویکی‌پدیا مراجعه کنید.

یکتایی جواب

اگر مجموعهٔ قید، محدب باشد و تابع هدف، شبه مقعر اکید باشد، مسئلهٔ حداکثرساز یا حداقل‌سازی حداکثر یک جواب دارد. (درمورد وجود جواب اظهار نظر نمی‌کند)

نکته: از آنجایی که مقعر بودن از شبه مقعر بودن قوی‌تر است، اگر تابع هدف، مقعر اکید هم باشد، جواب یکتا است.

شرط لازم و کافی برای جواب‌های مسئلهٔ بهینه‌سازی

شرط لازم کاندیداهای جواب را بررسی و حذف می‌کند، اگر یک نقطه بخواهد جواب باشد باید شرط لازم را دارا باشد.
و از بین آن‌ها که پس از حذف با شرط لازم باقی ماند، اگر نقطه‌ای در شرط کافی صدق کند جواب مسئله است.

قضیهٔ تابع ضمنی

قضیهٔ تابع ضمنی اگرچه به ما تابع صریح را نمی‌دهد ولی اولاً به ما شروط کافی برای وجود چنین تابعی را، و ثانیاً نحوهٔ محاسبهٔ مشتق این تابع را به ما می‌دهد. شروط کافی یعنی ممکن است تابعی باشد که فرم صریح داشته باشد اما قضیه نتواند وجود آن را اثبات کند. مثلاً تابع $F(x,y)=(x-y)^{3}$ با اینکه فرم صریح دارد ( $y=x$ ) ولی به علت صفر شدن مشتقش $3(x-y)^{2}$ در نقاطی که خود تابع صفر می‌شود (یعنی به ازای همهٔ $y=x$ ها) دیگر تابع اینجا کاربرد ندارد ولی همانطور که دیدیم فرم صریح دارد.

مقعر یا محدب بودن یک تابع

برای درک هرچه بهتر کاربرد ماتریس‌ها و مباحث بیشتر، می‌توانید به بخش ماتریس‌های همین کتاب سر بزنید.

ماتریس هشین

شرط متقارن شدن ماتریس هشین آن است که مشتقات مرتبه دوم تابع $f$ همگی پیوسته باشند. یک مثال خوب در اینجا یافت می‌شود. این آدرس نیز حاوی مثال‌های پیشرفته‌تر است.

حالت کلی

برای بررسی تقعر و تحدب یک تابع می‌توان از ماتریس هشین استفاده کرد.^[۳]

اگر $f'(x)=0$ و $H(x)$ مثبت معین باشد، تابع $f$ دارای یک مقدار کمینهٔ موضعی اکید در نقطهٔ $x$ است.
اگر $f'(x)=0$ و $H(x)$ منفی معین باشد، تابع $f$ دارای یک مقدار بیشینهٔ موضعی اکید در نقطهٔ $x$ است.
اگر $f'(x)=0$ و $H(x)$ دارای مقادیر ویژهٔ مثبت و منفی باشد، تابع $f$ دارای یک مقدار کمینه یا بیشینهٔ موضعی در نقطهٔ $x$ نیست و این یعنی نقطهٔ زینی است.
اگر $H(x)$ به ازای تمامی مقادیر دامنهٔ تابع $f$ ، مثبت نیم‌معین باشد، آنگاه تابع $f$ محدب است. این تابع به ازای نقطه‌ای که در آن $f'(x)=0$ و $H(x)$ مثبت معین باشد، دارای کمینهٔ سراسری اکید است.
اگر $H(x)$ به ازای تمامی مقادیر دامنهٔ تابع $f$ ، منفی نیم‌معین باشد، آنگاه تابع $f$ مقعر است. این تابع به ازای نقطه‌ای که در آن $f'(x)=0$ و $H(x)$ منفی معین باشد، دارای بیشینهٔ سراسری اکید است.

تابع دو متغیره

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

برای توابع دو متغیره، که دو بار مشتق پذیر باشند تابع هشین فوق را داریم: ${\begin{bmatrix}a&b\\b&d\end{bmatrix}}$ که دترمینان آن هست: $ad-b^{2}$

در این حالت:

دترمینان مثبت است:
- اگر $f'(x)=0$ و $ad-b^{2}>0$ در حالی که $a>0$ آنگاه $f$ به‌ازای $x$ کمینهٔ موضعی دارد.
- اگر $f'(x)=0$ و $ad-b^{2}>0$ در حالی که $a<0$ آنگاه $f$ به‌ازای $x$ بیشینهٔ موضعی دارد.
- اگر به ازای تمامی مقادیر دامنه داشته باشیم: $ad-b^{2}\geq 0$ و $a,d>0$ ، آنگاه $f$ محدب است و یک مقدار کمینهٔ اکید سراسری در هر نقطه‌ای که $f'(x)=0$ و $ad-b^{2}>0$ و $a>0$ دارد.
- اگر به ازای تمامی مقادیر دامنه داشته باشیم: $ad-b^{2}\leq 0$ و $a,d>0$ ، آنگاه $f$ مقعر است و یک مقدار بیشینهٔ اکید سراسری در هر نقطه‌ای که $f'(x)=0$ و $ad-b^{2}>0$ و $a<0$ دارد.
دترمینان منفی است:
- اگر $f'(x)=0$ و $ad-b^{2}<0$ ، آنگاه $f$ به‌ازای $x$ حالت زینی دارد.