Нелінійне програмування, Контент-платформа
1. Постановка задачі
2. Метод множників Лагранжа
3. Теорема Куна-Таккера. Умова регулярності Слейтера
4. Випукло і увігнуте програмування
5. Квадратичне програмування
6.1 Постановка задачі
Завдання нелінійного програмування у випадку формулюється так:
за умов
Завдання нелінійного програмування називається також завданням на умовний екстремум.
На відміну від задач лінійного програмування для задач нелінійного програмування немає універсального методу решения.
У задачах лінійного програмування область допустимих рішеньR(x) завжди є опуклим з кінцевим числом крайніх точок. Перебравши тільки крайні точки, за кінцеве число кроків можна знайти оптимальне рішення. У завданнях нелінійного програмування нелінійність обмежень який завжди забезпечує опуклість області допустимих рішень і кінцівка кількості його крайніх точок. Через цих особливостей виникають основні труднощі вирішення завдань нелінійного програмування.
Приклад 1. Область допустимих рішеньR(x) визначена обмеженнями:
Область допустимих рішень має вигляд (Малюнок 6.1) і не опукла.
Приклад 2. Область допустимих рішеньR(x) визначена обмеженнями:
Область допустимих рішень має вигляд (Малюнок 6.2), є опуклою, але має безліч крайніх точок.
6.2 Метод множників Лагранжа
Метод дозволяє знайти максимум (мінімум) функціїf(x1,x2, .xn) при обмеженнях-рівностях. Основна ідея методу полягає у переході від завдання на умовний екстремум дозадачі знаходження безумовного екстремуму спеціально збудованої функції Лагранжа.
Нехай потрібно знайтиminf(x1,x2, .xn)> при обмеженнях
Припустимо, що функціїf,g1,g2, .gmдиференційовані. Введемо набір змінних l1, l2, . lmза кількістю обмежень, які називаються множниками Лагранжа. Складемо функцію Лагранжа наступного виду
Для того, щоб вектор був розв'язанням задачі, необхідно існування такого вектора, що пара векторів задовольняє системі рівнянь
Таким чином, метод множників Лагранжа складається з наступних кроків:
1. Складаємо функцію Лагранжа L(X,L).
2. Складаємо систему рівнянь.
3. Знаходимо її рішення і досліджуємо функціюf(X) на околицях точкиХ0 наmin(max).
6.2.1 Дослідження функції на екстремум
Для того, щоб стаціонарна точкаХ0 була екстремальною, достатньо щоб матриця ГессеHу точціХ0 була:
Ø позитивно визначеною, тодіХ0 - точкаmin;
Ø негативно визначеної, тодіХ0 - точкаmax.
Для двовимірної функціїf(x1,x2) матриця Гессе має вигляд
Для тривимірної функціїf(x1,x2,x3) матриця Гессе має вигляд
Квадратична формаQ(X) є негативно визначеною, якщо значенняk-х кутових мінорів визначника ½А½відмінні від нуля і мають знак (-1)k(k=1, 2, .n). В цьому випадку матрицяАназивається негативно визначеною.
Квадратична формаQ(X) є позитивно визначеною, якщозначення всіх кутових мінорів визначника ½А½ позитивні. В цьому випадку матрицяАназивається позитивно визначеною.
k-м кутовим мінором визначника матриціA(n'n) називається визначник виду
Приклад. Нехай точка є точкою екстремуму функціїf(x1,x2,x3) =x1 + 2x3 +x2x3 – . Визначити характер екстремуму?
Нехай матриця Гессе має вигляд
Визначимоk-е кутові мінори:
Так як матриця Гесс є негативно визначеною, то точка є точкою максимуму.
6.3 Теорема Куна-Таккера. Умова регулярності Слейтера
Умова оптимальності розв'язання задачі нелінійного програмування формулюється в теоремі Куна-Таккера, яка має важливе значення для теорії нелінійного програмування.
Теорема. Нехайf(X),gi(X) (i=1, 2, .m) мають безперервні приватні похідні на деякій відкритій множині Ân, що міститьХ0. ЯкщоХ0 є точкою мінімуму функціїf(X) при обмеженнях, що задовольняють умові регулярності у вигляді лінійної незалежності векторів, існує такі невід'ємні множники Лагранжа , , . , що
Визначимо функцію Лагранжа так
Тоді теорему Куна-Таккера можна записати:
Умова регулярності – це додаткові припущення про природу функційgi(X) існування оптимального вектораX0. В окремому випадку, колиf(X) і всіgi(X) є опуклими функціями, умова регулярності має такий вигляд: існує такий векторХ, щовсімi=1, 2, .m. Ця умова називаєтьсяумовою регулярності Слейтера.
6.4 Випукло і увігнуте програмування
Приватним випадком задачі нелінійного програмування є задача опуклого програмування, яка формулюється так: знайтиminf(X)> за умов
Застосувавши теорему Куна-Таккера, отримаємо такі необхідні та достатні умови оптимальності: якщо функціїf(X),gi(X) диференційовані і опуклиХ, то векторХ0 є оптимальним рішенням задачі опуклого програмування тоді і тільки тоді, коли існує такий вектор , що для пари векторів будуть виконуватися такі умови:
Завдання опуклого програмування вирішують так:
1. Складають функцію Лагранжа
2. Записують умову оптимальності як системи рівнянь і нерівностей.
3. Знаходять спільне рішення.
Завдання увігнутого програмування формулюється так: знайтиmaxf(X)> за умов
Покажемо еквівалентність цієї задачі задачі опуклого програмування. Введемо позначенняf*(X) = –f(X) таg*i(X) = -gi(X). Оскількиmax<f(X)> =minf(X)>, то приходимо до завдання:
де всі функціїf*(X) іg*i(X) опуклі поX=x1 ,x2, .xn>, тому це завдання опуклого програмування.
Умови оптимальності формулюються аналогічно задачі опуклого програмування: Нехай функціїf(X),gi(X) диференційовані та увігнуті поХ. Для того, щоб векторХ0 був оптимальним рішенням задачіувігнутого програмування необхідне існування такого вектора, що для пари векторів виконуватимуться такі умови:
Таким чином, для вирішення задачі увігнутого програмування необхідно знайти спільне рішення системи рівнянь та нерівностей.
6.5 Квадратичне програмування
Завдання квадратичного програмування є спеціальним класом завдань нелінійного програмування, котрим цільова функція квадратична, проте обмеження лінійні.
Це завдання формулюється так:
знайтиmax(min)<f(X)>=BтX+XтCX= за умов
де – симетрична матриця.
МатрицяСбуде негативно визначеною задачі максимізації і позитивно визначеної задачі мінімізації. Це означає, що функціяf(X) є опуклою по зміннихХу задачі мінімізації та увігнутої у задачі максимізації. Обмеження у цій задачі передбачаються лінійними, що гарантує опуклість області допустимих рішень.
Застосувавши теорему Куна-Таккера, отримаємо такі необхідні та достатні умови оптимальності: вектор є оптимальним рішенням задачі квадратичного програмування тоді і тільки тоді, коли існують такіm-вимірні вектори іn-вимірний вектор , що
Перші дві умови утворюють систему з (n+m) лінійних рівнянь з 2(n+m) невідомими (векториX0,L0,V0,W0). Третє і четверте – це умова нежорсткості, що доповнює, які накладають додаткові обмеження на змінніX0,L0,V0,W0 , а саме:
В силу цих умов шуканевирішення завдання має бути одним із допустимих базисних рішень. Для його пошуку можна застосувати будь-який з методів лінійного програмування, наприклад, симплекс-метод.