Лекція 20. Опуклі множини та опуклі функції; Практична перевірка опуклості: матриця Гессе і додатна визначеність

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

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

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

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

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. Підсумок

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

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

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

---

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

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

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

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

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

1. Від означення до робочого критерію

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

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

В одній змінній знак другої похідної показує вигин графіка. У багатьох змінних напрямів безліч, тому одного числа вже недостатньо. Матриця Гессе дозволяє обчислити кривизну вздовж будь-якого напряму \(d\) через квадратичну форму \(d^THd\).

Через це перевірка опуклості переходить від питання «чи виконується нерівність Єнсена для всіх пар точок?» до питання «чи невід’ємна кривизна в кожному напрямі?». Для двічі диференційовної функції на опуклій області ці формулювання пов’язані строгим математичним критерієм.

1.1. Що означають «додатно визначена» і «додатно напіввизначена» матриця

Нехай \(H\) — симетрична матриця. Якщо для кожного ненульового напряму \(d\) виконується:

\[ d^THd>0 \]

матрицю називають додатно визначеною. Якщо дозволяється рівність нулю:

\[ d^THd\ge0 \]

маємо додатно напіввизначену матрицю.

Для кривизни різниця суттєва. Додатна визначеність означає вигин угору в кожному напрямі. Напіввизначеність допускає плоскі напрями. У міжнародній літературі часто використовують скорочення PD і PSD; у поясненні далі переважно використовуватимемо українські назви.

2. Одновимірне нагадування

Для функції однієї змінної друга похідна описує кривизну. Якщо:

\[ f''(x)\ge0 \]

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

Наприклад:

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

має:

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

для всіх \(x\).

3. Багатовимірний критерій

Для двічі диференційовної функції \(f\) на опуклій області \(C\) опуклість забезпечується умовою:

\[ \nabla^2f(x)\succeq0 \]

для кожного \(x\in C\).

Позначення \(\succeq0\) означає додатну напіввизначеність матриці Гессе.

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

4. Наскрізна квадратична функція

Розглянемо:

\[ f(x)= \frac{1}{2}x^TQx+c^Tx \]

де:

\[ Q= \begin{pmatrix} 4 & 1\\ 1 & 2 \end{pmatrix} \]

та:

\[ c= \begin{pmatrix} -1\\ 2 \end{pmatrix} \]

Вектор змінних:

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

5. Градієнт і матриця Гессе

Для симетричної \(Q\):

\[ \nabla f(x)=Qx+c \]

Тому:

\[ \nabla f(x)= \begin{pmatrix} 4x_1+x_2-1\\ x_1+2x_2+2 \end{pmatrix} \]

Матриця Гессе постійна:

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

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

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

6. Власні значення як перевірка визначеності

Для симетричної матриці знаки власних значень дають зручну класифікацію.

Для нашої \(Q\):

\[ \lambda_1\approx1.5858 \]

\[ \lambda_2\approx4.4142 \]

Обидва значення додатні. Тому \(Q\) додатно визначена, а цільова функція строго опукла.

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

Цю властивість можна записати через спектральний розклад. Для симетричної матриці існує ортонормована матриця \(V\) та діагональна матриця \(\Lambda\):

\[ Q=V\Lambda V^T \]

Тоді для довільного напряму \(d\) можна ввести \(z=V^Td\) і отримати:

\[ d^TQd= z^T\Lambda z= \sum_i \lambda_i z_i^2 \]

Квадрати \(z_i^2\) невід’ємні. Тому знак усієї квадратичної форми визначається знаками власних значень. Це пояснює, чому np.linalg.eigvalsh дає практично корисний сертифікат для симетричної матриці.

7. Геометричний зміст власних значень

Власні вектори задають головні напрями кривизни. Власне значення показує силу кривизни у відповідному напрямі. Менше власне значення відповідає пласкішому напряму, більше — крутішому.

Відношення найбільшого власного значення до найменшого для додатно визначеної матриці дає число обумовленості:

\[ \kappa(Q)= \frac{\lambda_{\max}}{\lambda_{\min}} \]

Для нашої матриці воно приблизно дорівнює 2.78. Це помірна різниця масштабів кривизни.

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

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

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

8. Додатна напіввизначеність

Розглянемо:

\[ Q_{ psd}= \begin{pmatrix} 2 & 0\\ 0 & 0 \end{pmatrix} \]

Її власні значення — 2 і 0. Матриця додатно напіввизначена. Відповідна квадратична функція опукла, але за другою координатою кривизна відсутня.

Наприклад:

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

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

9. Невизначена матриця

Розглянемо:

\[ Q_{ ind}= \begin{pmatrix} 2 & 0\\ 0 & -1 \end{pmatrix} \]

Одне власне значення додатне, друге від’ємне. Матриця невизначена. В одному напрямі поверхня вигинається вгору, в іншому — вниз. Така квадратична функція не є опуклою на всьому просторі.

10. Чому діагональних елементів недостатньо

Матриця:

\[ Q= \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix} \]

має додатні діагональні елементи. Проте її визначник:

\[ 1\cdot1-2^2=-3 \]

від’ємний. Власні значення мають різні знаки, тому матриця невизначена.

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

11. Критерій Сильвестра для матриці 2×2

Для симетричної матриці:

\[ Q= \begin{pmatrix} a & b\\ b & d \end{pmatrix} \]

додатна визначеність виконується, якщо:

\[ a>0 \]

та:

\[ ad-b^2>0 \]

Для нашої \(Q\):

\[ 4>0 \]

і:

\[ 4\cdot2-1^2=7>0 \]

Отже, критерій Сильвестра підтверджує додатну визначеність.

Для симетричної матриці:

\[ Q= \begin{pmatrix} a & b\\ b & d \end{pmatrix} \]

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

\[ a>0 \]

та:

\[ ad-b^2>0 \]

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

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

12. Розклад Холєцького як практична перевірка

Додатно визначену симетричну матрицю можна подати у вигляді:

\[ Q=LL^T \]

де \(L\) — нижня трикутна матриця. Такий розклад називають розкладом Холєцького.

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

Якщо симетрична матриця додатно визначена, її можна подати у вигляді:

\[ Q=LL^T \]

де \(L\) — нижня трикутна матриця з додатними діагональними елементами. Такий запис називають розкладом Холєцького.

Його геометричний сенс видно з квадратичної форми:

\[ d^TQd= d^TLL^Td= \|L^Td\|_2^2 \]

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

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

13. Сильна опуклість

Якщо для деякого \(m>0\) виконується:

\[ \nabla^2f(x)\succeq mI \]

функцію називають сильно опуклою. Для квадратичної функції роль \(m\) може виконувати найменше власне значення \(Q\).

Сильна опуклість дає кількісну нижню межу кривизни. Вона корисна для оцінювання швидкості збіжності градієнтних методів.

Сильна опуклість посилює звичайну опуклість кількісною нижньою межею кривизни. Якщо для деякого \(m>0\) виконується:

\[ \nabla^2f(x)\succeq mI \]

на всій області, то функція є \(m\)-сильно опуклою. Це означає, що найменша кривизна ніде не падає нижче \(m\).

Для квадратичної функції параметром сильної опуклості можна взяти найменше власне значення матриці \(Q\). У нашому прикладі воно приблизно дорівнює \(1.5858\), тому функція має помітну додатну кривизну в кожному напрямі.

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

14. Найбільша кривизна і крок градієнтного методу

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

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

Найбільше власне значення матриці Гессе задає верхній масштаб локальної кривизни. Для квадратичної функції з додатно визначеною матрицею \(Q\) стабільність градієнтного спуску зі сталим кроком пов’язана з умовою:

\[ 0<\alpha< \frac{2}{\lambda_{\max}(Q)} \]

Цей результат уже з’являвся в лекції про вибір кроку. Тепер видно його структурне походження: \(\lambda_{\max}\) описує найкрутіший головний напрям.

Якщо відношення \(\lambda_{\max}/\lambda_{\min}\) велике, один крок \(\alpha\) погано підходить одночасно для всіх напрямів. Метод змушений обережно поводитися в крутому напрямі й повільно просуватися в пологому. Такий ефект називають поганою обумовленістю квадратичної моделі. У фінальній лекції курсу це поняття стане частиною загального аудиту чисельної надійності.

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

15. Знаходимо мінімізатор наскрізної функції

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

Розв’язуємо:

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

тобто:

\[ Qx+c=0 \]

Звідси:

\[ Qx=-c \]

У координатах:

\[ 4x_1+x_2=1 \]

\[ x_1+2x_2=-2 \]

16. Ручний розв’язок системи

З першого рівняння:

\[ x_2=1-4x_1 \]

Підставляємо у друге:

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

Отримуємо:

\[ -7x_1=-4 \]

тому:

\[ x_1^*=\frac{4}{7} \]

Друга координата:

\[ x_2^*= 1-\frac{16}{7}= -\frac{9}{7} \]

Отже:

\[ x^*= \begin{pmatrix} \dfrac47\\ -\dfrac97 \end{pmatrix} \]

17. Чому це глобальний і єдиний мінімум

Маємо три кроки. По-перше, \(Q\) додатно визначена. По-друге, цільова функція строго опукла. По-третє, знайдена точка виконує умову стаціонарності.

Цього достатньо, щоб зробити глобальний висновок. Додатковий пошук інших локальних мінімумів не потрібен.

18. Виділення повного квадрата у векторній формі

Якщо \(Qx^*+c=0\), можна записати:

\[ f(x)= f(x^*)+ \frac{1}{2} (x-x^*)^TQ(x-x^*) \]

Другий доданок додатний для кожного \(x\ne x^*\), бо \(Q\) додатно визначена. Це ще один прямий доказ глобальності та єдиності мінімізатора.

Квадратичну функцію з додатно визначеною \(Q\) можна переписати відносно мінімізатора. Якщо \(x^*\) задовольняє \(Qx^*+c=0\), то:

\[ f(x)= f(x^*)+ \frac{1}{2} (x-x^*)^TQ(x-x^*) \]

Цей запис одразу пояснює глобальну оптимальність. Друга частина невід’ємна для додатно напіввизначеної \(Q\) і строго додатна для \(x\ne x^*\) при додатно визначеній \(Q\).

Така форма також показує роль власних значень. Для будь-якого вектора похибки \(e=x-x^*\) виконується:

\[ \frac{1}{2}\lambda_{\min}\|e\|_2^2\le f(x)-f(x^*)\le \frac{1}{2}\lambda_{\max}\|e\|_2^2 \]

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

19. Числовий допуск для власних значень

У арифметиці з рухомою комою значення, яке математично дорівнює нулю, може виглядати як \(-10^{-14}\) або \(10^{-15}\). Тому класифікацію треба виконувати з числовим допуском.

Наприклад:

• якщо \(\lambda_{\min}>\varepsilon\), матриця чисельно додатно визначена;
• якщо \(\lambda_{\min}\ge-\varepsilon\) і є власні значення поблизу нуля, матриця чисельно додатно напіввизначена;
• якщо \(\lambda_{\min}< -\varepsilon\), є суттєва від’ємна кривизна.

У машинній арифметиці власне значення, яке теоретично дорівнює нулю, може бути обчислене як \(-10^{-12}\) або \(10^{-13}\). Автоматичне правило «будь-яке від’ємне число означає неопуклість» у такій ситуації створить хибний висновок.

Допуск потрібно вибирати з урахуванням масштабу матриці. Для навчального прикладу з коефіцієнтами порядку одиниць абсолютний поріг на кшталт \(10^{-10}\) може бути достатнім. Для матриць із дуже великими коефіцієнтами корисно масштабувати поріг відносно норми матриці.

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

20. Чому область також важлива

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

Наприклад:

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

має:

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

Біля нуля друга похідна від’ємна, а для великих \(|x|\) — додатна. Отже, функція не є опуклою на всій дійсній прямій.

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

Наприклад, одновимірна функція може мати \(f''(x)>0\) біля нуля і \(f''(x)<0\) далеко від нього. Тоді локальна «чаша» не дає глобальної гарантії.

У звіті корисно писати область прямо: «матриця Гессе додатно напіввизначена для всіх \(x\in C\)». Якщо доказ стосується лише конкретної точки, формулювання повинно бути локальним.

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

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

21. Власні значення та власні вектори у NumPy

Для симетричної матриці np.linalg.eigh повертає власні значення та відповідні власні вектори. Значення впорядковані за зростанням. Тому перший стовпець матриці власних векторів відповідає найменшому власному значенню.

import numpy as np

quadratic_matrix = np.array([
    [4.0, 1.0],
    [1.0, 2.0],
])

eigenvalues, eigenvectors = np.linalg.eigh(quadratic_matrix)
minimum_index = int(np.argmin(eigenvalues))
minimum_eigenvalue = float(eigenvalues[minimum_index])
minimum_eigenvector = eigenvectors[:, minimum_index]

print("Власні значення:", eigenvalues)
print("Найменше власне значення:", minimum_eigenvalue)
print("Відповідний власний вектор:", minimum_eigenvector)

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

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

Мінімальна перевірка додатної напіввизначеності має такий вигляд:

eigenvalues = np.linalg.eigvalsh(Q)
min_eigenvalue = np.min(eigenvalues)
is_psd = min_eigenvalue >= -eigenvalue_tolerance

Допуск враховує округлення. Значення \(-2\cdot10^{-12}\) можна трактувати як нуль за порогу \(10^{-10}\).

22. Перевірка симетрії

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
symmetry_residual = np.linalg.norm(
    quadratic_matrix
    - quadratic_matrix.T
)

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

Для нашої матриці очікується 0.

23. Обчислення мінімізатора

# Перевіряємо кривизну та стаціонарність квадратичної функції.
linear_term = np.array([
    -1.0,
    2.0,
])

# Розв’язуємо лінійну систему напряму, без явного обчислення оберненої матриці.
solution = np.linalg.solve(
    quadratic_matrix,
    -linear_term,
)

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

Очікувано:

[ 0.57142857 -1.28571429]

24. Перевірка стаціонарності

# Виконуємо матричний або скалярний добуток, який прямо відповідає формулі математичної моделі.
gradient = (
    quadratic_matrix @ solution
    + linear_term
)

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
gradient_residual = np.linalg.norm(
    gradient
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print(gradient)
print(gradient_residual)

Нев’язка градієнта повинна бути близькою до нуля.

25. Перевірка розкладом Холєцького

# Будуємо розклад Холєцького як чисельну перевірку додатної визначеності матриці.
cholesky_factor = np.linalg.cholesky(
    quadratic_matrix
)

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

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

26. Мінімальний звіт перевірки опуклості

Для квадратичної задачі корисно зберігати:

SYMMETRY_RESIDUAL
MIN_EIGENVALUE
MAX_EIGENVALUE
CONDITION_NUMBER
CONVEXITY_CLASS
GRAD_NORM

Такий звіт відокремлює структурну перевірку матриці від перевірки знайденого розв’язку.

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

MATRIX_SYMMETRY_RESIDUAL: 0.0
EIGENVALUES: [1.5858, 4.4142]
MIN_EIGENVALUE: 1.5858
MAX_EIGENVALUE: 4.4142
POSITIVE_DEFINITE: True
CONDITION_NUMBER: 2.7836
STATIONARY_POINT: [0.5714, -1.2857]
GRAD_NORM: near 0

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

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

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

Така структура звіту готує студента до фінального аудиту курсу. Мета перевірки полягає в тому, щоб кожне сильне твердження мало числове або аналітичне обґрунтування, яке можна відтворити.

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

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

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

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

28. Опуклість і існування мінімізатора

Опуклість сама по собі не завжди гарантує існування скінченного мінімізатора. Наприклад:

\[ f(x,y)=x^2+y \]

має додатно напіввизначену матрицю Гессе, але значення можна необмежено зменшувати через \(y\to-\infty\).

Для додатно визначеної квадратичної матриці без обмежень ситуація сильніша: для будь-якого лінійного доданка існує єдиний мінімізатор.

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

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

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

29. Обумовленість і швидкість методу

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

Число обумовленості для додатно визначеної симетричної матриці можна оцінити як:

\[ \kappa(Q)= \frac{\lambda_{\max}(Q)} {\lambda_{\min}(Q)} \]

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

Метод Ньютона частково компенсує різні масштаби кривизни через розв’язання системи з матрицею Гессе. Проте сама система також стає чисельно чутливою при великому \(\kappa\). Отже, погана обумовленість впливає і на алгоритм першого порядку, і на лінійну алгебру другого порядку.

Практичний висновок: класифікація «додатно визначена» відповідає на питання про форму, а число обумовленості — на питання про чисельну складність цієї форми.

30. Зв’язок із задачами з обмеженнями

У наступних лекціях умови KKT будуть використовуватися як сертифікат оптимальності. Для опуклої задачі такий сертифікат має глобальний зміст. Тому перевірка опуклості входить до математичної перевірки чисельного результату.

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

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

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

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

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

31. Підсумок

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

У квадратичній моделі матриця Гессе стала й дорівнює \(Q\), тому її достатньо класифікувати один раз. Власні значення, критерій Сильвестра та розклад Холєцького утворюють взаємодоповнювальні способи перевірки. Симетрія матриці та числовий допуск для власних значень біля нуля повинні бути явною частиною чисельного аудиту.

Після структурної перевірки стаціонарність набуває глобального змісту. Для строго опуклої квадратичної функції рівняння \(Qx+c=0\) дає єдиний глобальний мінімізатор. Число обумовленості додатково пояснює, наскільки легко цей результат буде отримувати чисельний алгоритм.