Лекція 21. Опуклі множини та опуклі функції

Коротко про лекцію

Тут вводяться опуклі множини та опуклі функції, які дають сильні гарантії для оптимізації. Ви навчитеся розуміти геометричний зміст опуклості та пояснювати, чому локальний мінімум в опуклій задачі є глобальним.

Практичний сенс. Опуклість дає задачі оптимізації глобальну структуру. Для опуклої задачі локальний мінімум уже є глобальним. Строга опуклість часто забезпечує єдиний мінімізатор. Через це умови стаціонарності отримують значно сильніший зміст, а результат чисельного методу легше перевіряти математично.

Постановка та базові поняття

1. Чому локального мінімуму іноді недостатньо

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

Тому перед чисельним розв’язанням корисно поставити структурне запитання: чи має задача таку геометрію, яка виключає «погані» локальні мінімуми? Опуклість дає саме таку властивість для великого класу задач.

1.1. Чому властивість називають опуклістю

Геометричний образ простий. Якщо множина не має «вм’ятин», то відрізок між двома її точками не виходить назовні. Таку множину називають опуклою. Трикутник, прямокутник і круг є опуклими. Кільце з порожнім центром уже неопукле, бо відрізок між двома його точками може пройти через отвір.

Для функції слово використовується через споріднену геометрію. Графік опуклої функції лежить не вище хорди між двома своїми точками. Типовий приклад — \(f(x)=x^2\). Практична користь полягає в тому, що для опуклої задачі локальний мінімум автоматично є глобальним.

2. Практичний приклад допустимих планів

Нехай підприємство випускає два види продукції. План описуємо вектором:

\[ x= \begin{pmatrix} x_1\\ x_2 \end{pmatrix} \]

і вимагаємо:

\[ x_1\ge0 \]

\[ x_2\ge0 \]

\[ x_1+x_2\le4 \]

Візьмемо два допустимі плани:

\[ x^{(1)}= \begin{pmatrix} 1\\ 1 \end{pmatrix} \]

та:

\[ x^{(2)}= \begin{pmatrix} 3\\ 0.5 \end{pmatrix} \]

Обидва виконують усі три обмеження.

Практичний сенс цього прикладу виходить за межі геометрії. Якщо \(x^{(1)}\) і \(x^{(2)}\) описують два реальні виробничі режими, то опукла комбінація може описувати середній план за період. Наприклад, підприємство може половину тижня працювати за першим режимом, а другу половину — за другим. Середні витрати ресурсу тоді також утворюють опуклу комбінацію.

Цей аргумент працює тоді, коли змінні допускають дробові значення і предметний зміст дозволяє змішування режимів. Для кількості тонн сировини або годин роботи це природно. Для рішення «будувати склад чи ні» проміжне значення \(0.5\) уже не має прямого предметного змісту. Через це геометрія неперервної та дискретної оптимізації відрізняється.

Важливо також стежити за одиницями вимірювання. Опукла комбінація двох векторів має сенс лише тоді, коли відповідні компоненти описують однакові величини. Не можна змішувати першу координату в тоннах із другою координатою в годинах, якщо вектори побудовані в різному порядку. Порядок компонентів є частиною математичної моделі.

3. Опукла комбінація двох точок

Введемо число:

\[ 0\le\lambda\le1 \]

і побудуємо:

\[ x(\lambda)= \lambda x^{(1)}+ (1-\lambda)x^{(2)} \]

Такий вираз називають опуклою комбінацією. При \(\lambda=1\) отримуємо перший план. При \(\lambda=0\) — другий. Проміжні значення \(\lambda\) дають точки відрізка між ними.

Для \(\lambda=0.5\):

\[ x(0.5)= \begin{pmatrix} 2\\ 0.75 \end{pmatrix} \]

Сума координат дорівнює \(2.75\), тому обмеження \(x_1+x_2\le4\) виконується. Отже, середина відрізка також допустима.

4. Означення опуклої множини

Множина \(C\) є опуклою, якщо для будь-яких:

\[ x,y\in C \]

та будь-якого:

\[ 0\le\lambda\le1 \]

виконується:

\[ \lambda x+(1-\lambda)y\in C \]

Геометрично це означає, що весь відрізок між двома точками множини лежить у цій самій множині.

5. Чому лінійні обмеження дають опуклі множини

Розглянемо лінійну нерівність:

\[ a^Tx\le b \]

Нехай дві точки \(x^{(1)}\) та \(x^{(2)}\) виконують її. Тоді:

\[ a^Tx^{(1)}\le b \]

і:

\[ a^Tx^{(2)}\le b \]

Для опуклої комбінації маємо:

\[ a^T \left( \lambda x^{(1)}+(1-\lambda)x^{(2)} \right)= \lambda a^Tx^{(1)}+(1-\lambda)a^Tx^{(2)} \]

Кожний доданок праворуч не перевищує відповідну частку \(b\), тому весь вираз не перевищує \(b\). Отже, один лінійний півпростір є опуклим.

Перетин опуклих множин також опуклий. Через це допустима область лінійного програмування, утворена системою лінійних нерівностей і рівностей, має опуклу геометрію.

Рівність має аналогічну властивість. Нехай дві точки виконують \(a^Tx=b\). Для їхньої опуклої комбінації маємо:

\[ a^T \left( \lambda x^{(1)}+ (1-\lambda)x^{(2)} \right)= \lambda b+(1-\lambda)b= b \]

Тому афінна рівність також задає опуклу множину. Перетин кількох таких рівностей і нерівностей залишається опуклим. Звідси випливає фундаментальний факт: допустима область звичайної задачі лінійного програмування є опуклою.

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

Математична логіка

6. Від опуклої множини до опуклої функції

Опукла множина описує, де дозволено шукати рішення. Опукла функція описує форму цільової функції. Розглянемо:

\[ f(x)=x^2 \]

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

7. Означення опуклої функції

Функція \(f\) є опуклою на опуклій множині \(C\), якщо для всіх \(x,y\in C\) і \(0\le\lambda\le1\) виконується:

\[ f \left( \lambda x+(1-\lambda)y \right)\le \lambda f(x)+(1-\lambda)f(y) \]

Ліва частина — значення функції в проміжній точці. Права частина — висота хорди над цією самою проміжною координатою.

8. Ручна перевірка для квадрата

Візьмемо:

\[ x=-2 \]

\[ y=4 \]

та:

\[ \lambda=0.5 \]

Проміжний аргумент:

\[ 0.5(-2)+0.5(4)=1 \]

Ліва частина нерівності:

\[ f(1)=1 \]

Права частина:

\[ 0.5f(-2)+0.5f(4)= 0.5\cdot4+0.5\cdot16= 10 \]

Отримуємо \(1\le10\). Цей числовий приклад узгоджується з опуклістю.

9. Чому одного числового прикладу недостатньо

Означення вимагає нерівність для всіх допустимих \(x\), \(y\) та \(\lambda\). Один успішний приклад перевіряє лише одну трійку чисел. Тому числовий експеримент може знайти контрприклад, але відсутність контрприкладу в скінченній вибірці ще не є доказом.

Для \(f(x)=x^2\) загальний доказ можна провести без перебору точок. Розглянемо різницю:

\[ \lambda x^2+(1-\lambda)y^2- \left( \lambda x+(1-\lambda)y \right)^2 \]

Після спрощення маємо:

\[ \lambda(1-\lambda)(x-y)^2 \]

Кожний множник невід’ємний, тому різниця невід’ємна. Це доводить опуклість квадрата для всіх \(x\), \(y\) і \(\lambda\in[0,1]\).

Корисно розділяти дві різні задачі перевірки. Перша задача — знайти помилку в реалізації або в гіпотезі. Для цього один контрприклад достатній. Друга задача — довести математичну властивість на всій області. Тут скінченний набір тестів не може замінити загальний аргумент.

Наприклад, програма може перевірити тисячу випадкових трійок \(x\), \(y\), \(\lambda\) і жодного разу не знайти порушення. Такий результат підвищує довіру до коду, але не доводить опуклість функції. Якщо область велика, небезпечна ділянка може просто не потрапити до вибірки.

Для навчального звіту корисно прямо вказувати тип доказу. Формулювання «опуклість підтверджена аналітично» означає загальний математичний аргумент. Формулювання «числових контрприкладів не знайдено» описує лише тестування реалізації. Таке розділення захищає від надмірних висновків.

10. Строга опуклість

Функція є строго опуклою, якщо для різних \(x\) і \(y\) та \(0<\lambda<1\) виконується строга нерівність:

\[ f \left( \lambda x+(1-\lambda)y \right) < \lambda f(x)+(1-\lambda)f(y) \]

Строга опуклість означає, що внутрішня частина графіка лежить строго нижче хорди. Функція \(x^2\) є строго опуклою на всій дійсній прямій.

11. Чому строга опуклість дає єдиний мінімізатор

Припустимо, строго опукла функція має два різні глобальні мінімізатори \(x^{(1)}\) та \(x^{(2)}\) з однаковим значенням \(f^*\). Для будь-якої внутрішньої опуклої комбінації строга опуклість дає:

\[ f \left( \lambda x^{(1)}+(1-\lambda)x^{(2)} \right) < f^* \]

Це суперечить тому, що \(f^*\) уже мінімальне значення. Отже, строго опукла функція має не більше одного мінімізатора на опуклій області.

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

У прикладній задачі питання існування часто вирішується властивостями допустимої множини та поведінкою цілі. Якщо область замкнена й обмежена, а функція неперервна, мінімум досягається. Для необмеженої області потрібен додатковий контроль того, що ціль не «тікає» до меншого значення на нескінченності.

Тому сильний висновок виглядає так: мінімізатор існує, а строга опуклість робить його єдиним. Цей порядок міркувань корисний у майбутніх задачах квадратичного програмування та регуляризованого оцінювання.

12. Чому локальний мінімум стає глобальним

Нехай \(x^*\) — локальний мінімізатор опуклої функції. Припустимо, існує точка \(y\) з меншим значенням. Візьмемо точку на відрізку між \(x^*\) та \(y\), дуже близьку до \(x^*\). Опуклість змусить значення функції в цій точці бути меншим за \(f(x^*)\). Це суперечить локальній мінімальності.

Тому локальний мінімум опуклої функції є глобальним.

13. Першопорядковий критерій

Для диференційовної опуклої функції виконується:

\[ f(y)\ge f(x)+ \nabla f(x)^T(y-x) \]

Права частина є лінійною апроксимацією функції в точці \(x\). Опукла функція лежить над кожною своєю дотичною гіперплощиною.

Якщо в точці \(x^*\):

\[ \nabla f(x^*)=0 \]

то:

\[ f(y)\ge f(x^*) \]

для всіх \(y\). Отже, стаціонарна точка диференційовної опуклої функції є глобальним мінімізатором.

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

Це дає простий спосіб побудувати сертифікат оптимальності. Якщо \(\nabla f(x^*)=0\), права частина нерівності перетворюється на \(f(x^*)\). Отримуємо \(f(y)\ge f(x^*)\) для кожної точки області. Один локальний обчислювальний факт — нульовий градієнт — отримує глобальний зміст завдяки попередньо доведеній опуклості.

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

14. Опукла оболонка

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

Опукла оболонка є найменшою опуклою множиною, яка містить початкові точки. У дискретній оптимізації ця ідея важлива для побудови релаксацій.

15. Чому цілочисельні множини часто неопуклі

Нехай дозволені тільки цілі значення. Точки \(x=0\) та \(x=2\) допустимі, але їхня середина \(x=1\) теж ціла. Проте для двох багатовимірних цілочисельних точок середина може мати дробові координати. Наприклад, середина \((0,0)\) та \((1,1)\) дорівнює \((0.5,0.5)\) і вже не належить цілочисельній множині.

Тому дискретна допустима множина зазвичай неопукла. Саме через це цілочисельна оптимізація потребує спеціальних методів.

Алгоритм і покроковий розбір

16. Як перевіряти опуклість множини вручну

Для простої множини корисний порядок:

1. взяти дві довільні допустимі точки;
2. побудувати їхню опуклу комбінацію;
3. підставити її в усі обмеження;
4. використати допустимість початкових точок;
5. зробити висновок для всіх \(\lambda\in[0,1]\).

Для лінійних нерівностей такий доказ зазвичай короткий.

Ще один корисний приклад — евклідова куля:

\[ C= \{x:\|x\|_2\le R\} \]

Нехай \(x,y\in C\). Для опуклої комбінації за нерівністю трикутника:

\[ \|\lambda x+(1-\lambda)y\|_2\le \lambda\|x\|_2+ (1-\lambda)\|y\|_2\le R \]

Отже, куля опукла. Цей доказ показує загальний стиль роботи: формулу опуклої комбінації підставляють у визначальну властивість множини, а далі застосовують відому математичну нерівність.

Для навчальної задачі важливо прямо назвати використаний факт. Фраза «очевидно, що точка залишається всередині» не пояснює причинний крок. Нерівність трикутника робить доказ відтворюваним.

17. Як спростувати опуклість

Для спростування достатньо одного контрприкладу. Треба знайти дві точки множини та таке \(\lambda\), щоб їхня опукла комбінація вийшла за межі множини.

Наприклад, для кільця можна взяти дві протилежні точки. Їхня середина потрапляє в порожній центр. Отже, кільце неопукле.

18. Як перевіряти функцію через означення

Для простої функції зручно аналізувати різницю:

\[ \lambda f(x)+(1-\lambda)f(y)- f \left( \lambda x+(1-\lambda)y \right) \]

Якщо вдається довести її невід’ємність для всіх допустимих аргументів, функція опукла.

19. Які операції зберігають опуклість

Сума опуклих функцій є опуклою. Множення опуклої функції на невід’ємну константу також зберігає опуклість. Лінійна функція одночасно є опуклою та увігнутою, бо в нерівності опуклості завжди виконується рівність.

Наприклад:

\[ f(x)=3x^2+2x+7 \]

є опуклою, бо \(3x^2\) опукла, а лінійний і сталий доданки не руйнують цю властивість.

Є ще дві корисні конструкції. По-перше, якщо \(f\) опукла, то функція \(g(x)=f(Ax+b)\) також опукла для афінного перетворення аргументу. Це пояснює, чому вирази на кшталт \(\|Ax-b\|_2^2\) природно виникають у задачах найменших квадратів і залишаються опуклими.

По-друге, максимум скінченної кількості опуклих функцій також є опуклою функцією:

\[ g(x)= \max \left\{ f_1(x),\dots,f_m(x) \right\} \]

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

Практична звичка проста: для кожного складного виразу корисно пояснити, з яких відомих опуклих частин він побудований і яке правило збереження опуклості використано.

20. Опуклі обмеження в стандартній формі

Для задачі мінімізації типовий опуклий запис використовує нерівності:

\[ g_i(x)\le0 \]

де кожна \(g_i\) є опуклою. Множина:

\[ \{x:g_i(x)\le0\} \]

є підрівневою множиною опуклої функції й залишається опуклою.

Рівності в опуклій постановці зазвичай мають афінний вигляд:

\[ Ax=b \]

Афінна рівність задає опуклу множину.

21. Опукла задача як структурний клас

Перед чисельним розв’язанням корисно відповісти на п’ять запитань:

1. Чи опукла допустима множина?
2. Чи опукла цільова функція для мінімізації?
3. Чи всі нерівності мають форму опукла функція \(\le0\)?
4. Чи рівності афінні?
5. Чим саме доведені ці властивості?

Цей короткий структурний аналіз визначає, наскільки сильним буде висновок після знаходження стаціонарної точки.

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

Потрібно також розрізняти опуклість задачі та опуклість окремого виразу. Опукла ціль не допоможе, якщо допустима множина неопукла. Опукла допустима множина також не усуває локальні мінімуми, якщо ціль неопукла. Глобальні гарантії виникають із поєднання правильної цілі та правильної структури обмежень.

У майбутньому цей принцип дозволить швидко класифікувати QP, регуляризовані найменші квадрати та частину задач з KKT. Спочатку визначаємо структурний клас, далі обираємо метод, після цього перевіряємо чисельний результат.

Розглянемо короткий структурний аудит нової задачі:

\[ \min_{x_1,x_2} \left( (x_1-2)^2+ 3(x_2-1)^2 \right) \]

за умов:

\[ x_1+x_2\le4,\qquad x_1\ge0,\qquad x_2\ge0 \]

Допустима множина є перетином трьох лінійних півпросторів, тому вона опукла. Матриця Гессе цілі:

\[ H= \begin{pmatrix} 2 & 0\\ 0 & 6 \end{pmatrix} \]

має додатні власні значення, отже ціль строго опукла. Через це задача має не більше одного мінімізатора.

Без обмежень мінімізатор дорівнює \((2,1)\). Він допустимий, бо \(2+1\le4\). Отже, ця точка одночасно є глобальним мінімізатором задачі з обмеженнями. У такому прикладі розв’язувач фактично не потрібен для доведення.

Тепер змінимо праву частину на \(x_1+x_2\le2\). Точка \((2,1)\) стає недопустимою, але структурні властивості зберігаються: допустима множина опукла, ціль строго опукла. Тому новий глобальний мінімізатор існує на межі й залишається єдиним.

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

Програмна реалізація та перевірка

22. Числова перевірка однієї опуклої комбінації

Числова перевірка не є доказом, але корисна для налагодження.

# Імпортуємо NumPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np


# Перевіряємо опуклість на конкретному числовому прикладі.
plan_1 = np.array([1.0, 1.0])
plan_2 = np.array([3.0, 0.5])
lambda_value = 0.5

# Перевіряємо опуклість на конкретному числовому прикладі.
mixed_plan = (
    lambda_value * plan_1
    + (1.0 - lambda_value) * plan_2
)

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
is_feasible = (
    np.all(mixed_plan >= 0.0)
    and np.sum(mixed_plan) <= 4.0
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("MIXED_PLAN:", mixed_plan)
print("FEASIBLE:", is_feasible)

Очікуваний результат:

MIXED_PLAN: [2.   0.75]
FEASIBLE: True

23. Числова перевірка нерівності опуклості

# Описуємо цільову функцію тією самою формулою, що й у математичній постановці.
def objective(value):
    return value ** 2


# Задаємо параметр алгоритму, вплив якого далі перевіримо на результаті.
x = -2.0
y = 4.0
lambda_value = 0.5

# Перевіряємо опуклість на конкретному числовому прикладі.
mixed_x = (
    lambda_value * x
    + (1.0 - lambda_value) * y
)

# Перевіряємо опуклість на конкретному числовому прикладі.
left = objective(mixed_x)
right = (
    lambda_value * objective(x)
    + (1.0 - lambda_value) * objective(y)
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("LEFT:", left)
print("RIGHT:", right)
print("JENSEN_OK:", left <= right)

Очікувано ліва частина дорівнює 1, права — 10.

24. Для чого потрібні випадкові перевірки

У складній реалізації можна випадково вибирати пари точок та перевіряти нерівність опуклості. Якщо знайдено порушення, маємо конкретний контрприклад. Якщо порушення не знайдено, це лише додаткова впевненість у коді. Формальний доказ глобальної опуклості все одно повинен спиратися на математичний критерій.

25. Що потрібно зберігати в результаті структурної перевірки

Для майбутнього автоматичного контролю корисно явно фіксувати:

FEASIBLE_SET_CONVEX: True
OBJECTIVE_CONVEX: True
OBJECTIVE_STRICTLY_CONVEX: True/False
EVIDENCE: short mathematical explanation

Так чисельний результат отримує контекст. Одна й та сама мала норма градієнта має різний зміст у опуклій і неопуклій задачі.

Інтерпретація, межі та підсумок

26. Типові помилки

Типова помилка. Одну успішну числову перевірку нерівності опуклості вважають доказом. Означення вимагає властивість для всіх допустимих точок.

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

27. Увігнутість

Функція \(f\) є увігнутою, якщо \(-f\) опукла. Для увігнутої функції хорда лежить нижче графіка. У задачах максимізації увігнутість відіграє роль, симетричну опуклості для мінімізації.

Наприклад:

\[ f(x)=-x^2 \]

є увігнутою на всій дійсній прямій, а її глобальний максимум досягається в нулі.

28. Опуклість і релаксації

Якщо початкова допустима множина неопукла через цілочисельні вимоги, іноді спочатку розв’язують опуклу релаксацію. Вона послаблює частину обмежень і дає межу для початкової задачі. Розв’язок релаксації може бути дробовим, тому він не замінює кінцевий цілочисельний результат.

Ця ідея пояснює, чому опукла геометрія важлива навіть усередині алгоритмів дискретної оптимізації.

29. Опуклість і перевірка чисельного результату

Якщо задача опукла, стаціонарність має глобальний зміст. Якщо задача неопукла, мала норма градієнта підтверджує лише локальну стаціонарність. Тому структурний висновок про опуклість повинен з’являтися до остаточного тлумачення результату розв’язувача.

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

Приклад повної перевірки можна сформулювати як короткий причинний ланцюжок. Спочатку доводимо, що допустима множина опукла. Далі доводимо опуклість цільової функції. Після цього чисельний метод знаходить кандидата \(x^*\). Нарешті перевіряємо допустимість і стаціонарність кандидата.

Якщо всі ланки виконані, висновок «\(x^*\) є глобальним мінімізатором» має математичну опору. Якщо ціль строго опукла, можна додати висновок про єдиність. Якщо доведення опуклості відсутнє, той самий чисельний результат підтримує слабший висновок: знайдено допустиму стаціонарну точку з певним значенням цілі.

Таке формулювання важливе для автоматизованої перевірки робіт. Машина може обчислити нев’язки, але структурна гарантія повинна бути явно вказана в моделі або доведена в теоретичній частині.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

30. Підсумок

Опукла множина містить увесь відрізок між будь-якими двома своїми точками, а опукла функція задовольняє нерівність для кожної опуклої комбінації аргументів. Геометрично графік опуклої функції лежить не вище хорди між відповідними точками. Ці властивості створюють глобальну структуру задачі, яка суттєво спрощує аналіз оптимальності.

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

Під час аудиту потрібно окремо перевіряти опуклість допустимої множини й цільової функції, а також враховувати домени змінних. Наступна лекція перетворює цю абстрактну властивість на практичну перевірку через матрицю Гессе та власні значення.