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

اگر در یک کار برنامه نویسی ریاضی باید قسمت انتهایی یک عملکرد را پیدا کنید ، به عنوان مثال:

در مورد مجموعه ای از راه حل های عملی ارائه شده توسط محدودیت ها

1) عملکرد هدف متفاوت و مقعر است ، یعنی شرط آن راضی است:

برای هرچی،

2) و طرف چپ همه محدودیت ها - توابع متفاوت و محدب ، یعنی برای آنها شرایط زیر رعایت شده است:

برای هرچی،

سپس مشکل (4.7) - (4.8) مشکل نامیده می شود برنامه نویسی محدب.

هر عملکرد خطی به طور هم زمان شرایط همگرا و همگرا را برآورده می کند. آن می توان آن را هم محدب و مقعر در نظر گرفت. این به ما امکان می دهد مشکلات خطی را به عنوان یک مورد خاص از مشکلات برنامه نویسی محدب در نظر بگیریم.

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

بیایید سه تعریف را معرفی کنیم:

1) عملکرد Lagrange مسئله برنامه نویسی محدب (4.7) - (4.8) یک تابع است:

, (4.9)

2) گفته می شود که مشکل برنامه نویسی محدب (4.7) - (4.8) را برآورده می کند شرط منظماگر حداقل یک نقطه داخلی از مجموعه راه حل های امکان پذیر تعریف شده توسط نابرابری های شدید به دست آمده از (4.8) وجود داشته باشد (یعنی ).

3) نکته ای گفته می شود زین اسب نقطه از عملکرد اگر برای همه انجام:

اگر عملکرد هدف (حذف)

در نظریه برنامه نویسی غیرخطی ، مکان اصلی توسط قضیه کوهن-تاکر اشغال شده است ، که روش چند برابر کننده کلاسیک لاگرانژ را به طور کلی تعمیم می دهد تا در مواردی که محدودیتهای مسئله غیرخطی به همراه محدودیت هایی در قالب برابری ، محدودیت هایی را در قالب نابرابری ها نیز دارند.

قضیه کوهن تاکر. اگر مشکل برنامه نویسی محدب (4.7) - (4.8) شرایط مرتب سازی را برآورده کند ، یک نکته راه حل بهینه برای این مشکل است اگر و فقط اگر یک نکته با مختصات غیر منفی وجود دارد که یک نقطه زین از عملکرد Lagrange این مشکل است.

شرایط کاروش - کونا - Tucker به صورت دیفرانسیل:

اگر عملکرد Lagrange از نظر محدب محدب است ، مقعر با احترام و تمایز مداوم با توجه به همه ، و سپس برای اینکه یک جفت نقطه زین از عملکرد Lagrange باشد ، لازم و کافی است که شرایط زیر راضی شود:

مثالقضیه کوهن-تاکر کاهش مسئله برنامه نویسی محدب را به مسئله یافتن نقطه زین عملکرد لاگرانژ اثبات می کند. برای اینکه چنین کاهش عملی معنای عملی داشته باشد ، لازم است که مشکل حاصل تا حدودی ساده تر از مسئله اصلی باشد. این همیشه اتفاق نمی افتد ؛ بنابراین ، تعدادی روش مستقیم برای یافتن راه حل برای مسئله غیرخطی (4.5) ، (4.6) تدوین شده است. بیایید برخی از آنها را در نظر بگیریم.

CONVEX PROGRAMMING ، بخشی از برنامه نویسی ریاضی ، که در آن مشکل به حداکثر رساندن یک تابع هدف مقعر f (x) یک بردار بردار x \u003d (x 1 ، ... ، x n) ارضای محدودیت gi (x) 0 ، x Є X، i \u003d 1 ، ... ، متر ، که در آن gi توابع مقعر است ، X یک مجموعه محدب است. نقطه x که این محدودیت ها را برآورده می کند ، قابل قبول است. نتیجه اصلی نظریه برنامه نویسی محدب قضیه نقطه زین است: برای اینکه یک نقطه قابل قبول x * از یک مسئله برنامه نویسی محدب بهینه باشد ، لازم است (در شرایط نسبتاً گسترده) و وجود یک بردار y * \u003d (y * 1 ، ... ، ym *) با اجزای غیر منفی y * به گونه ای که نقطه (x * ، y *) یک نقطه زین برای عملکرد Lagrange است

مشکلات برنامه نویسی محدب ، یعنی برای هر x Є X و y با اجزای غیر منفی ، نابرابری ها

تعدادی از روش های برنامه نویسی محدب بر اساس قضیه نقطه زین است که در آن یا عملکرد φ (y 1 ، ... ، y m) \u003d حداکثر x Є XL (x ، y) برای y i ≥ 0 ، i \u003d 1 ، به حداقل می رسد. . ، m ، یا یک نقطه زین به طور مستقیم یافت می شود ، و برخی از اصلاحات آن به جای عملکرد Lagrange گاهی اوقات استفاده می شود. یک رویکرد دیگر برای حل مسئله برنامه نویسی محدب با جستجوی مسیرهای ممکن حرکت یک نقطه قابل قبول x است که از مجموعه نقاط قابل قبول حاصل نمی شود و هنگام حرکت که در طی آن عملکرد هدف افزایش می یابد ، همراه است. این روش با استفاده از دنباله ای از تکرارها اجرا می شود. در هر تکرار ، جهت احتمالی خروجی از نقطه بعدی محاسبه می شود ، پس از آن یک تغییر در این جهت با برخی از مسافت تا نقطه بعدی انجام می شود. روش هایی برای حل مشکلات برنامه نویسی محدب وجود دارد ، به طور خاص با مورد سازگار شده که عملکرد هدف غیرخطی است و محدودیت ها خطی هستند. به طور معمول ، روش های برنامه نویسی محدب برای تعیین دقیق نقطه مطلوب به تعداد نامتناهی از تکرارها نیاز دارند. استثنائات ، مشکلات برنامه نویسی درجه دوم است (تابع هدف عبارت است از مجموع توابع درجه یک و خطی مقعر ، محدودیت ها بصورت خطی هستند) و برنامه نویسی خطی (عملکرد هدف و محدودیت ها بصورت خطی هستند) که برای آنها عمدتاً از روش های محدود استفاده می شود. بسیاری از روشهای محاسباتی برنامه نویسی محدب به صورت برنامه های رایانه ای اجرا می شوند. بسته های نرم افزاری نیز وجود دارد که مشکلات برنامه نویسی خطی و مشکلات برنامه نویسی محدب را پوشش می دهد. همچنین به تحقیقات عملیات مراجعه کنید.

Lit: Golshtein E.G. برنامه نویسی محدب. عناصر نظریه. م. ، 1970؛ برنامه نویسی غیرخطی Zangwill W.I. یک رویکرد م. ، 1973

اجازه دهید یک سیستم نابرابری از فرم

(4.3) و عملکرد

Z \u003d f (x 1، x 2، ...، x n)، (4.4)

علاوه بر این ، تمام توابع بر روی برخی از مجموعه های محدب محدب محدب هستند ، و عملکرد Z به صورت محدب بر روی مجموعه M یا مقعر است.

مشکل برنامه نویسی محدب پیدا کردن راه حلی برای سیستم محدودیت ها (4.3) است که در آن تابع هدف Z به مقدار کمترین مقدار خود می رسد ، یا عملکرد مقعر Z به حداکثر مقدار خود می رسد. (شرایط برای عدم انعطاف پذیری متغیرها را می توان در سیستم در نظر گرفت (4.3)).

با توجه به خاصیت 3 0 ، هر مشکل برنامه نویسی خطی یک مورد خاص از یک مشکل برنامه نویسی محدب است. در حالت کلی ، مشکلات برنامه نویسی محدب مشکلات برنامه نویسی غیرخطی است. تخصیص مشکلات برنامه نویسی محدب به یک کلاس خاص با خصوصیات جانبی توابع محدب توضیح داده می شود: هر حداقل محلی یک تابع محدب (حداکثر محلی یک عملکرد مقعر) همزمان جهانی است. علاوه بر این ، با توجه به ویژگی 2 0 ، یک عملکرد محدب (مقعر) تعریف شده بر روی یک مجموعه بسته بسته به حداکثر جهانی و حداقل جهانی در این مجموعه می رسد. از این رو چنین نتیجه می گیرد اگر عملکرد هدف Z کاملاً محدب باشد (کاملاً مقعر) و اگر دامنه راه حل سیستم محدودیتها خالی و محدود نیست ، پس مشکل برنامه نویسی محدب همیشه یک راه حل منحصر به فرد دارد.

تابع F (X) \u003d F (x 1 ، x 2 ، ... ، x n) نامیده می شود قابل جدا شدن، اگر بتوان آن را به عنوان مجموع توابع نشان داد ، که هر یک از آنها فقط به یک متغیر بستگی دارد ، یعنی اگر یک

(ممکن است که F i (x i) \u003d 0 برای برخی i).

بگذارید یک سیستم محدودیت (4.3) و یک تابع هدف (4.4) در یک مشکل برنامه نویسی محدب ارائه شود ، و عملکرد هدف Z و همه محدودیت ها از هم جدا هستند. سپس مشکل به نظر می رسد:

حداقل یک تابع محدب (حداکثر - مقعر) را پیدا کنید

با محدودیت

ایده روش تقریبی خطی پارگی همین است که تمام f i و همه آنها توسط خطوط شکسته متشکل از قطعه های خط مستقیم جایگزین می شوند. در این حالت ، مشکل اصلی برنامه نویسی محدب با یک مشکل جدید و تقریبی جایگزین می شود که این یک مشکل برنامه نویسی خطی است. این مشکل معمولاً با روش ساده انجام می شود و راه حل آن یک راه حل تقریبی برای مسئله اصلی برنامه نویسی محدب است.

شکل 12. حل مسئله برنامه نویسی محدب با تقریب خطی جزئی

برای ایجاد یک مشکل تقریبی ، یک تقریب خطی جزئی از یک تابع از یک متغیر h (x) داده شده در یک فاصله را در نظر بگیرید. ما این بخش را به نقاط x 0 تقسیم می کنیم

معادله بخش خط شکسته بین نقاط (x k؛ h k) و (x k + 1؛ h k + 1) فرم (معادله یک خط مستقیم در طول دو نقطه) را دارد. اگر هر یک از روابط موجود در این برابری به آن اشاره شده باشد ، دریافت می کنیم:

توجه داشته باشید که برای هر یک از شرایط رضایت بخش ارزش منحصر به فرد (4.7) وجود دارد. بازنویسی را می توان در شکل (4.7) بازنویسی کرد:

[معادلات (4.8) به معادلات پارامتری قطعه گفته می شود.

اگر h (x) \u003d 0 باشد ، دوم از این معادلات به هویت 0 \u003d 0 تبدیل می شود و حالت اول شکل (4.1) را می گیرد - معادله قطعه ای که بر روی محور abscissa قرار دارد].

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

و فقط دو مقدار همیشه غیرزو هستند (اگر x یک نقطه داخلی بخش kth پارتیشن باشد) یا یکی (اگر x همزمان با انتهای بخش باشد).

با بازگشت به مسئله برنامه نویسی محدب با کارکردهای جداکننده ، توجه می کنیم که اول از همه (بسته به سیستم محدودیت ها) لازم است که فاصله تغییرات هر متغیر x j را تعیین کنید. سپس هر یک از این فاصله ها توسط نقاط x jk و با استفاده از فرمول ها (4.9) تقسیم خطی پراکنده برای توابع f j تقسیم می شود و ساخته می شود. پس از آن ، برای مشکل اصلی (4.6) ، می توانیم مشکل تقریبی را بنویسیم:

حداکثر عملکرد را پیدا کنید

مشمول محدودیت ها (4.10)

از آنجا که مشکل تقریبی (4.10) یک مسئله برنامه نویسی خطی است که معمولاً با روش سادگی کار می شود ، شرایط عدم عدم انعطاف پذیری متغیرها به طور جداگانه از بقیه محدودیت ها نوشته می شود.

تفاوت بین مسئله به دست آمده (4.10) و مشکل برنامه نویسی خطی معمول در این است که برای هر x j بیش از دو نوع nonzero همسایه وجود ندارد و بنابراین ، نمی توان به عنوان متغیرهای اصلی دو با k و همان j همسایه استفاده کرد. توجه داشته باشید که ، البته ، انجام تقریب خطی پراکنده نیز برای شرایط عدم انعطاف پذیر بودن شرایط متغیر f j (x j) و (در صورت وجود) ضروری نیست.

در این فصل فقط تعدادی از تکنیک های بهینه سازی مورد استفاده مدیران برای تصمیم گیری های مؤثر در شرکت ها مورد بررسی قرار گرفته است. با این حال ، تکنیک های شرح داده شده ، درک اصل اساسی استفاده از دستگاه ریاضی در اقتصاد را ممکن می سازد ، که به شما امکان می دهد گزینه های گوناگونی را انتخاب کنید که برای یک مورد یا موقعیت خاص مناسب باشد.

این تابع نامیده می شود محدب

این تابع نامیده می شود مقعر در صورت وجود هر نقطه بر روی یک مجموعه محدب و یک تعداد دلخواه نابرابری زیر را شامل می شود:

گاهی اوقات یک تابع محدب بر خلاف یک عملکرد مقعر ، که بعضا محدب به سمت بالا خوانده می شود ، محدب به پایین گفته می شود. معنای این نام ها از تصویر هندسی یک توابع محدب معمولی (شکل 3.3) و مقعر (شکل 3.4) مشخص است.

شکل. 3.3 عملکرد محدب

شکل. 3.4 عملکرد مقعر

ما تأکید می کنیم که تعاریف توابع محدب و مقعر فقط برای مجموعه محدب معنی دارد ایکس، از آنجا که فقط در این مورد نکته است لزوما متعلق است ایکس.

مشکل برنامه نویسی محدب یک مورد خاص از مشکل کلی برنامه نویسی ریاضی (3.7) ، (3.8) است ، هنگامی که عملکرد هدف و توابع محدودیت بر روی یک مجموعه محدب مقعر هستند. ر.

از آنجا که مشکل به حداکثر رساندن یک عملکرد معادل مسئله به حداقل رساندن این عملکرد با علامت منفی است ، محدودیت معادل یک نابرابری است ، و محدب بودن از تعقیب و بالعکس دنبال می شود. از اینجا

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

, ,

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

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

لم 1

مجموعه برنامه های قابل قبول برای مشکلات برنامه نویسی محدب

محدب است حداکثر عملکرد محلی مقعر محلی ایکس جهانی است

اگر توابع محدودیت محدب بودند ، برای مجموعه ایکس (3.14) محدبیت دیگر دنبال نمی شود. در این حالت ، می توان محدب بودن مجموعه را اثبات کرد:

اگر تابع هدف محدب بود ، آنگاه عبارت لیما در مورد حداکثر آن نادرست می شود ، اما یک عبارت مشابه برای حداقل ها قابل اثبات است.

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

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

لم 2

مجموع توابع محدب (مقعر) محدب (مقعر) است. محصول یک تابع محدب (مقعر) و یک عدد مثبت محدب (مقعر) است. مجموع عملکردهای محدب (مقعر) و کاملاً محدب (کاملاً مقعر) کاملاً محدب است (کاملاً مقعر).

قضیه 1

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

شواهد و مدارک

فرض کنید برعکس ، یعنی که دو نکته وجود دارد ، که حداکثر امتیازات یک تابع کاملاً مقعر در هستند ایکس... نشان دادن ، ما داریم ... سپس برای هر چیزی صادق است:

آن به تضاد رسید. اثبات برای حداقل یک عملکرد کاملاً محدب مشابه است.

یک تابع خطی تنها نمونه هم محدب و هم یک عملکرد مقعر است ، به این معنی که به طور محدب محدب نیست (کاملاً مقعر). تابع درجه دوم ممکن است محدب باشد (مقعر) ، اما ممکن است کاملاً محدب باشد (کاملاً مقعر). همه اینها توسط ماتریس مشخص می شود د... عناصر ماتریس د مشتقات جزئی دوم یک تابع درجه دوم را نشان می دهد ، یعنی

بگذارید ماتریس مشتقات جزئی دوم را توسط.

لم 3

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

آنگاه کاملاً محدب است (کاملاً مقعر).

مشکل حداکثر رساندن (به حداقل رساندن) یک تابع درجه دوم تحت محدودیت های خطی ، در کجا د یک ماتریس قطعی منفی (مثبت) است و D T= دنامیده میشود مشکل برنامه نویسی درجه دوم .

از lemma نتیجه می گیرد که مسئله برنامه نویسی خطی که در بخش 2 در نظر گرفته شده است ، مانند مشکل برنامه نویسی درجه دوم ، مورد خاصی از مشکل برنامه نویسی محدب است.

توابع وجود دارد که در یک گروه از متغیرها محدب و در گروه دیگر مقعر هستند. چنین توابع یکی از کلاسهای اصلی توابع را نشان می دهد که مطمئناً یک نقطه زین وجود دارد.

قضیه 2

(در مورد وجود یک نقطه زین برای یک عملکرد مقعر محدب). بگذار ایکس و Y زیر مجموعه های محدب بسته محدب از فضاهای محدود اقلیدسی محدود ، و عملکرد مداوم در و مقعر در و محدب است ، پس از آن دارای یک نقطه زین.

عملکرد Lagrange را برای یک مشکل برنامه نویسی محدب در نظر بگیرید:

(3.15)

تعریف شده بر روی یک محصول مستقیم ، جایی که این تابع به دلیل مقعر بودن آن مقعر درون و خطی است ، بنابراین محدب است.

با این حال ، بر اساس قضیه 1 نمی توان استدلال کرد که از زمان مجموعه دارای یک نقطه زین است ر لزوماً بسته و محدود نیست ، اما Y بدیهی است نامحدود. با این وجود می توان انتظار داشت که در برخی شرایط نقطه زین همچنان وجود داشته باشد.

معروف ترین قضیه مربوط به این موضوع ، قضیه کوهن-تاکر است ، که ارتباطی بین وجود راه حل برای یک مشکل برنامه نویسی محدب و یک نقطه زین برای عملکرد Lagrange برقرار می کند. شرایط اسلاتر : یک مشکل برنامه نویسی محدب شرط Slater را برآورده می کند اگر نکته ای وجود داشته باشد که این شرط برآورده شود: .

قضیه کوهن تاکر

اگر یک مشکل برنامه نویسی محدب شرایط Slater را برآورده کند ، در این صورت یک شرط لازم و کافی برای بهینه بودن طرح وجود چنین است که جفت نقطه ای از عملکرد Lagrange (15/3) باشد.

این مسئله که اسلاتر ضروری است با مثال زیر نشان داده شده است.

مثال 1

با توجه به یک مشکل برنامه نویسی محدب:

در اینجا ، بدیهی است که ایکس = 0 یک راه حل برای مشکل دارد ، اما عملکرد Lagrange است هیچ نقطه زین وجود ندارد ، زیرا محدوده بیرونی در مشکل مینیماکس حاصل نمی شود:

تقسیم محدودیت ها در یک مشکل برنامه نویسی محدب به و همانطور که قبلاً نیز ذکر شد مشروط است. بنابراین ، معمولاً زیر ر مجموعه ای از یک فرم ساده درک می شود ، این یا کل فضا است E n، یا یک ارتود غیر منفی ، یا یک paralelipiped. پیچیدگی مسئله برنامه نویسی محدب توسط سیستم محدودیت ها تعیین می شود:

از آنجا که نقطه زین عملکرد Lagrange بر روی محصول مجموعه ها جستجو می شود ، در کجا Y همچنین مجموعه ای از فرم ساده (مستطیل غیر منفی) است ، پس معنای قضیه کوهن-تاکر کاهش مسئله یافتن اندام یک تابع با محدودیت های پیچیده بر متغیرها به مشکل یافتن قسمت انتهایی یک تابع جدید با محدودیت های ساده است.

اگر مجموعه ر مصادف است با E n، سپس شرایط اکستروم ، همانطور که مشخص است ، دارای این شکل هستند:

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

قضیه 3

برای اینکه یک تابع مقعر به طور مداوم متمایز باشد حداکثر در یک نقطه روشنایی وجود دارد E n، لازم و کافی است که شیب تابع در نقطه برابر با صفر باشد ، یعنی ...

به یاد بیاورید که شیب تابع عبارت است از:

بنابراین ، برای پیدا کردن نقطه زین عملکرد Lagrange بر روی محصول ، و در نتیجه ، یافتن راه حلی برای مشکل برنامه نویسی محدب برای ر= E n برای حل سیستم معادلات (3.16) لازم است. اما در این سیستم ن معادلات و ناشناخته ها ن+ ماز آنجا که علاوه بر این نوکتور بعدی برای ما ناشناخته است مبردار بعدی از تکثیر لاگرانژ با این حال ، یک ویژگی بسیار مهم برای نقطه زین عملکرد Lagrange وجود دارد:

. (3.17)

معادله (17/3) دلالت بر این دارد كه هم ، یا ، یا هر دو به طور هم زمان. این ویژگی شبیه به قضیه دوگانگی دوم (Sec. 2.5) برنامه نویسی خطی است. محدودیت هایی که در بعضی از موارد به عنوان برابری ارضا می شوند فعال .

بنابراین ، فقط آن دسته از ضرب های Lagrange می توانند nonzero باشند ، که مطابق با محدودیت های فعال در نقطه هستند. با در نظر گرفتن این خاصیت ، برای یافتن راه حلی برای یک مشکل برنامه نویسی محدب ، روش زیر را در نظر بگیرید.

سخنرانی 11.برنامه نویسی محدب

تعریف 1 ز توسط برنامه نویسی محدب که در آن همه توابع محدب هستند یک مشکل برنامه نویسی غیرخطی است.

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

(1)

, (2)

. (3)

ما به فضا های کمکی نیاز خواهیم داشت
بردارها
... وکتور از اول
جزء نقطه نشان داده خواهد شد ... بنابراین،
.

برای مشکل (1) - (3) ، مجموعه را تعریف کنید

جایی که
.

لم . برای مشکل برنامه نویسی محدب (1) - (3) یک دسته از محدب.

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

نابرابری های بدست آمده و دلالت بر همگرایی مجموعه دارد .

قضیه 1. (قضیه کوهن-تاکر در قالب نقطه زین عملکرد Lagrange یک مشکل برنامه نویسی محدب ) بگذارید ، در مسئله برنامه نویسی محدب (1) - (3) ، سیستم (2) شرایط Slater را با توجه به راه حل مسئله (1) - (3) ، لازم و کافی است که یک بردار غیر منفی وجود داشته باشد به طوری که
نقطه زین عملکرد Lagrange است.

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

ضرورت بگذار - راه حل مشکل (1) - (3). ما گذاشتیم
... بدیهی است که
، مانند
,
و
.

بیایید مطمئن شوید که
... برعکس فرض کنید این بدان معنی است که یک نکته وجود دارد
به طوری که
... از این رو ، - چنین نقطه مجاز ، مقدار عملکرد عینی که در آن کمتر از حداقل است. با این واقعیت تضاد می کنیم - حل مسئله برنامه نویسی محدب.

بنابراین،
... با توجه به لیم ، مجموعه محدب از این رو ، تمام الزامات قضیه 8.2 برآورده می شود. بنابراین ، یک nonzero وجود دارد

وکتور
نقطه محوری به کثرت :

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

به راحتی می توان آنرا مشاهده کرد
بردارها
گنجانده شده در بسیاری ... سپس از (4) ما:

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

ما نشان می دهیم
... بگذارید نشان دهیم که بردار ساخته شده است وکتور مورد نیاز چند برابر کننده لاگرانژ است. بدیهی است که
و از (5) به دست آوردیم

از این رو ، در
باید

. (7)

از طرف دیگر ، از آن زمان
(تا آنجا که
) و
، ما نابرابری را بدست می آوریم

... از این و (7) نتیجه می گیرد که در یک نقطه
شرط کندی مکمل راضی است:

. (8)

از (6) و (8) داریم

یا ، که همان است ،

علاوه بر این ، اجازه دهید
... سپس
... از این و (8) نابرابری را بدست می آوریم

نابرابری (9) ، (10) و معنی آن
آیا نقطه زین عملکرد Lagrange مسئله محدب است

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

پیش از آشنایی با نسخه دیگری از قضیه کوهن-تاکر ، قضیه زیر را ارائه می دهیم که از نظر مخروطهای بردار پشتیبانی حداقل یک معیار شرطی است.

قضیه 2. بگذار - محدب و متفاوت در
عملکرد ، مجموعه
محدب سپس به منظور اشاره
حداقل شرط عملکرد بود روی مجموعه
، لازم است و کافی برای ورود

. (11)

اثبات به طور مستقیم از قضیه 6.5 و تعریف مخروط پیروی می کند
بردارهای پشتیبانی در نقطه به کثرت
.

قضیه 3. (قضیه کوهن-تاکر به شکل دیفرانسیل برای یک مشکل برنامه نویسی محدب ) بگذارید یک مشکل برنامه نویسی محدب به فرم (1) ، (2) داده شود که در آن همه عملکردها وجود دارد
سیستم به طور مداوم متفاوت است ، سیستم (2) شرایط Slater را برآورده می کند. سپس ، به منظور بردار
یک راه حل برای مسئله (1) ، (2) ، لازم و کافی است که یک بردار غیر منفی وجود داشته باشد به طوری که شرایط

, (12)

شواهد و مدارک. بگذارید نشان دهیم که شرایط (12) و (13) معادل شمول (11) است. اجازه دهید نکته
چنین است که
... سپس
و
.

حالا بگذار
... سپس از قضایای 2 و 10.5 بدست می آید كه شرط لازم و كافی برای یك اكستروم وجود چنین عواملی است
,
برای کدام
... ما گذاشتیم
برای همه
و ما از آخرین شرایط برابری (12) و (13) بدست می آوریم. که مورد نیاز بود

برای نتیجه گیری این بخش ، فرمول های دو قضیه کوهن-تاکر را برای مشکل ارائه می دهیم

برنامه نویسی محدب با محدودیت های خطی.

قضیه 4. بگذارید سیستم محدودیت ها (2) در مشکل برنامه نویسی محدب (1) - (3) شکل داشته باشد

، ب - بردار ابعاد
... سپس ، به منظور بردار غیر منفی راه حل مشکل بود ، کافی و کافی است

یک بردار غیر منفی وجود دارد به طوری که
آیا نقطه زین عملکرد Lagrange از مشکل داده شده است.

توجه داشته باشید که در این حالت عملکرد Lagrange فرم دارد.

قضیه 5. بگذارید در مسئله برنامه نویسی محدب (1) ، (2) عملکرد هدف را داشته باشیم سیستم محدودیت (2) به طور مداوم متفاوت است ، شکل دارد
، جایی که A ماتریس ابعاد است
، ب - بردار ابعاد
. سپس ، به منظور بردار
یک راه حل برای مشکل بود ، لازم و کافی است که یک بردار غیر منفی وجود داشته باشد به طوری که شرایط
,
.