Опукла (увігнута) функція - студопедія
Завдання оптимізації значно ускладнюється, якщо цільова функція f () може мати в допустимої області G не один, а кілька максимумів або мінімумів. В цьому випадку глобальний екстремум може досягатися на кордоні області і не збігатися з локальним екстремумів. Якщо заздалегідь відомо існування глобального екстремуму у функції f () (наприклад, на підставі Теореми 5.2.), То досить знайти всі стаціонарні точки і порівняти значення функції f () в цих точках з екстремальними значеннями на кордоні області. Найбільше значення буде відповідати глобальному максимуму. Рішення такого завдання може виявитися дуже трудомістким, зважаючи на велике число обмежень виду (5.1) в практичних завданнях.
Тому значний інтерес представляють такі завдання, в яких цільова функція має всього один максимум або мінімум і в яких, отже, локальний екстремум є в той же час глобальним. Для виявлення класів таких задач функціональну роль відіграють поняття опуклості і угнутості функцій.
Нехай f () цільова функція, задана на опуклій множині G; 1. 2 - дві довільні точки з G. 0 £ t -довільний точка відрізка, що з'єднує 1. 2. Розглянемо відрізок з'єднує значення f (1) і f (2) функції f ()
Визначення 5.7. Функцію f () називають опуклою, якщо вона цілком лежить вище (не нижче) відрізка, що з'єднує дві її довільні точки, т. Е. Для будь-яких 1. 2, і буде виконуватися нерівність:
Визначення 5.8. Функцію f () називають увігнутою, якщо вона цілком лежить нижче (не вище) відрізка, що з'єднує дві її довільні точки, т. Е. Якщо
Мал. 5.3 ілюструє визначення локального, глобального екстремумів, стаціонарних точок, опуклих і увігнутих функцій.
Мал. 5.3 Функції: опукла а); увігнута б); загального вигляду в).
Наведемо властивості опуклих і увігнутих функцій, які є важливими для вирішення завдань нелінійного програмування.
Теорема 5.4. Будь-який локальний максимум опуклою або локальний мінімум увігнутої функції є одночасно глобальним.
Теорема 5.5. Сильний глобальний мінімум опуклою або максимум увігнутої функцій, заданих в опуклою області може досягатися (а в закритій обмеженою області - досягається) тільки на кордоні області.
Наведені теореми дозволяють виділити деякі прийоми, що спрощують знаходження глобального екстремуму:
1. Якщо функція опукла (увігнута) і з рівнянь (5.4) отримана стаціонарна точка, то в ній досягається глобальний максимум (мінімум).
2. Для відшукання глобального мінімуму опуклою або глобального максимуму увігнутою функції досить дослідження екстремумів функції тільки на кордоні області.
І, нарешті, варто відзначити, що сума опуклих (увігнутих) функцій є опукла (увігнута).
Розглянемо деякі важливі види опуклих і увігнутих функцій.
Лінійна функція f () = є опуклою (і увігнутою) на всьому просторі R (n). Однак вона не є ні строго опуклою, ні строго ввігнутої. Квадратична функція:
є опуклою на всьому просторі R (n). якщо вона негативно (не позитивний) певна, тобто, якщо f () £ 0 при будь-якому. крім = 0. Квадратична функція є увігнутою на всьому просторі R (n). якщо вона позитивно (нейтрально) певна, тобто, якщо f ()> 0 при будь-якому. крім = 0.
Зазначені властивості квадратичної функції можна встановити в загальному випадку по знакам коренів lI характеристичного рівняння матриці C =. має вигляд:
Тут, діагональні елементи cij є коефіцієнтами при хi 2. а недіагональні елементи cij = cji рівні половині коефіцієнта при xi xj у формулі (5.7).
Теорема 5.6. Для того щоб квадратична функція (5.7) була позитивно (негативно) певною, необхідно і достатньо, щоб всі корені рівняння (5.8) були позитивними (негативними).
Якщо серед цих коренів є хоча б один рівний нулю - квадратична функція невід'ємна (непозитивним). Нарешті, якщо є коріння різного знака - квадратична функція невизначена.