Нехай . Нехай . Задачею опуклого програмування будемо назив. таку екстремальну задачу

Озн: Точка є допустимою точкою в з-чі, якщо Зрозуміло, що множина допустимих точок є опуклою. Точка , якщо , .

Теорема Куна-Таккера: 1) , тоді існує ненульовий вектор множників Лагранжа: , такий, що і виконуються умови : а) – умова стаціонарності; б) – умова допповнюючої нежорсткості; в) – умова невід’ємності. 2) Якщо для допустимої точки викон. умови а)-в) і , або викон. умови а)-в) і умова Слейтера, тоді . Множина доп. ел-тів в задов. умову Слейтера, якщо .

Доведення: Без зменшення загальності будемо вважати, що . Якщо це не вик. завжди можна розглянути ф-цію і для цієї ф-ції умова викон. Нехай . Позначимо ч/з множину . Покажемо, що – непорожня і опукла. Б-я невідємний вектор буде належати . Це з того, що ми припустили , . Тоді . Покажемо, що – опукла: виберемо і покажемо, ел-нт , . . Оскільки є також опуклою, то . Внаслідок опуклості ф-й будемо мати . Це озн, що , тобто множина є опуклою. Розглянемо множину . Вона є непорожньою і опуклою. Покажемо, що . Якщо б існував ел-нт , тоді цей ел-нт , , , . Це озн, що є допустимою точкою задачі , крім того . А це суперечить тому, що . Це озн, що множини і є віддільними. На підстави теореми віддільності їх можна відділити. Це озн, що і виконується . Із нерівності (*) виведемо умови а)-в). в) Умова невідємності: . , бо він з невідємними координатами. Підставляючи в нерівність (*) отримаємо , . б) умови доповнюючої нежорсткості: розглядаємо вектор , . на підставі обмежень задачі . Підставляємо в (*) отримаємо . Якщо , то на підставі в) випливає , а це суперечить тому, що точка є допустимою в зад. , . а) принцип min для ф-ції Лагранжа. . На підставі нерівності (*) маємо: . Для дов. доп. точки викон. нер-ть , а отже . Це дов. 1-шу частину теор. - необх. умови. Нехай викон. умови а)-в) і . Нехай , викон. нер. . Для точки викон. , тобто . Нехай викон. умови а)-в) і умова Слейтера. Покажемо, що з цих умов випливає . Припустимо, що . Оскільки . на підставі умови в) випливає, що хоча б один , . Тоді , отже для точки – протирічить а), бо

. Припущення є невірним, тому на підставі пункту 1) . З теор. К-Т отримали достатні умови для опуклої з-чі з обмеж-ми типу нер-й, але без вкладень.

5. Чисельні методи оптимізації (методи дихотомії, золотого поділу, Фібоначчі, найшвидшого спус-ку, Ньютона, можливих напрямів)

Нелінійним рівнянням називають алгебричне рівняння виду , (5.1)

де - аргумент, а функція (5.2)

є деякою довільною неперервною алгебричною функцією цього аргументу.

Під розв-м нелінійного р-ня (коренем, нулем відповідної нелінійної ф-ї) роз-ть таке знач-ня аргументу , підстав-ня якого в р-ня (1) пер-є його у тот-ть.

У цьому поділі мова буде йти про відшукування дійсних кор-в нелін-х р-нь. Загальних способів відшукання дійсних кор-в довільних нелін-х р-нь не існує. Нел-на ф-я може не мати взагалі дійсних кор-в, може мати один, два і навіть нескінченну к-ть їх.

У загальному випадку процес відшукування коренів розпадається на два етапи. Перший етап, дії за яким не можна формалізувати, - пошук інтервалу змінювання аргументу, всередині якого існує єдиний корінь. Немає загальних правил, за якими можна було б установлювати такий (такі) інтервал. Перш за все це має бути аналітичне дослідження поводження заданої функції у різних інтервалах змінювання аргументу. Н-д, якщо задана нелінійна ф-я є аналітичною, тобто необмежено диферен-ною, то умови, за яких функція має єдиний корінь всередині інтервалу змінювання аргументу , мають бути наступними:

*Зн-ня ф-ї на кінцях цього інт-лу повинні бути протил-го знаку;

*перша похідна функції не змінює знаку на цьому інтервалі;

*друга похідна ф-ї також не змінює знака на цьому інтервалі.

Другий етап - процес уточнення знач-ня кореня. Відомі чис-ні алгоритми відшукування коренів нелінійного рів-ня, розглядувані у подальшому, насправді є лише алгоритмами уточнення знач-ня кореня, бо зводяться до послідовного звуження інт-лу , всередині якого знаходиться корінь. Слід узяти до уваги, що встановлення інтервалу, всередині якого знаходиться єдиний корінь ф-ї, фактично є визначенням наближеного значення цього кореня .

При цьому похибкою такого знач-ня може вважатися величина

Метод дихотомії (ділення навпіл) y

y=f(x)

f(b)

a f[(a+b)/2]

f(a) (a+b)/2 b x

Заданий інтервал ділиться навпіл. Цим знаходиться наближене значення кореня. Обчислюється значення функції при цьому значенні аргументу. Якщо воно дорівнює нулю, є точним значенням кореня й процес закінчується. Якщо ні, то визначається знак значення . Обирається той інтервал, на межах якого задана функція набуває значень протилежного знаку. Наприклад, якщо виявиться, що , то як нове значення верхньої межі інтервалу приймається : . У протилежному випадку змінюється нижня межа інтервалу . Далі процес повторюється для нового звуженого удвічі інтервалу доти, поки значення похибки (5) не стане меншою за задане припустиме її значення

. (5.6)

За остаточне значення кореня при цьому слід узяти знач-ня (4). Якщо обчислення потрібно проводити з макс-ю точністю, процес звуження інтер-лу слід продов-ти доти, поки нижня й верхня межі інт-лу не збіжаться у машинному поданні.

Метод дотичних (Ньютона)

Наступний метод може бути