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

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

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

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

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

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

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


# Задаємо матрицю кривизни у фіксованому порядку змінних.
quadratic_matrix = np.array([
    [4.0, 1.0],
    [1.0, 2.0],
])

# Обчислюємо власні значення симетричної матриці, щоб визначити знак локальної кривизни.
eigenvalues = np.linalg.eigvalsh(
    quadratic_matrix
)

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

Очікувано:

[1.58578644 4.41421356]

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

Мінімальна логіка перевірки:

# Обчислюємо власні значення симетричної матриці, щоб визначити знак локальної кривизни.
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\) дає єдиний глобальний мінімізатор. Число обумовленості додатково пояснює, наскільки легко цей результат буде отримувати чисельний алгоритм.