Лекція 25. Умови KKT для задач з нерівностями

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

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

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

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

1. Навіщо потрібні умови KKT

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

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

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

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

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

1.1. Що означає назва KKT і навіщо чотири групи умов

Скорочення KKT походить від прізвищ Каруша, Куна і Таккера. Воно є міжнародно усталеним, тому його зберігаємо після першого пояснення.

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

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

2. Загальна задача

Розглянемо:

\[ \min_x f(x) \]

за умов:

\[ g_i(x)\le0, \qquad i=1,\dots,m \]

та:

\[ h_j(x)=0, \qquad j=1,\dots,p \]

Для нерівностей вводимо множники \(\mu_i\), для рівностей — \(\lambda_j\).

3. Функція Лагранжа

\[ L(x,\mu,\lambda)= f(x)+ \sum_{i=1}^{m} \mu_i g_i(x)+ \sum_{j=1}^{p} \lambda_j h_j(x) \]

Для форми \(g_i\le0\) множники нерівностей повинні бути невід’ємними:

\[ \mu_i\ge0 \]

Множники рівностей обмеження знака не мають.

4. Чотири групи умов KKT

У точці-кандидаті перевіряють:

1. пряму допустимість;
2. двоїсту допустимість;
3. стаціонарність;
4. комплементарну нежорсткість.

Кожна група відповідає на окреме запитання, тому одну нев’язку не можна замінити іншою.

Зручно читати чотири групи як чотири незалежні запитання.

1. Пряма допустимість: чи виконує кандидат початкові обмеження?
2. Двоїста допустимість: чи мають множники нерівностей правильний знак?
3. Стаціонарність: чи врівноважують градієнти обмежень градієнт цілі?
4. Комплементарна нежорсткість: чи узгоджені множники з активністю обмежень?

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

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

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

5. Пряма допустимість

Початкові обмеження повинні виконуватися:

\[ g_i(x^*)\le0 \]

і:

\[ h_j(x^*)=0 \]

Якщо точка недопустима, подальша перевірка оптимальності вже не має сенсу.

6. Двоїста допустимість

Для всіх множників нерівностей:

\[ \mu_i^*\ge0 \]

Ця умова залежить від знакової домовленості. Якщо нерівність записати у протилежному напрямі, знак відповідного множника теж зміниться. Тому перед розрахунком усі нерівності треба привести до одного стандарту.

7. Стаціонарність

Градієнт функції Лагранжа за змінними рішення повинен дорівнювати нулю:

\[ \nabla f(x^*)+ \sum_i \mu_i^*\nabla g_i(x^*)+ \sum_j \lambda_j^*\nabla h_j(x^*)=0 \]

Це баланс градієнта цілі та нормалей активних обмежень.

8. Комплементарна нежорсткість

Для кожної нерівності:

\[ \mu_i^*g_i(x^*)=0 \]

Якщо:

\[ g_i(x^*)<0 \]

то обмеження має запас, тому:

\[ \mu_i^*=0 \]

Якщо множник додатний, обмеження повинно бути активним:

\[ g_i(x^*)=0 \]

Для нерівності \(g_i(x)\le0\) умова:

\[ \mu_i g_i(x)=0 \]

має просту логіку добутку. Якщо \(g_i(x)<0\), обмеження має запас, тому добуток може дорівнювати нулю лише при \(\mu_i=0\). Якщо \(\mu_i>0\), тоді обов’язково \(g_i(x)=0\), тобто обмеження активне.

У термінах запасу \(s_i=-g_i(x)\ge0\) умову можна записати:

\[ \mu_i s_i=0 \]

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

Чисельно добуток рідко дорівнює точному нулю. Тому використовують нев’язку комплементарності й порівнюють її з допуском.

9. Наскрізна задача

Мінімізуємо:

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

за умов:

\[ x+y\le2 \]

\[ x\ge0 \]

\[ y\ge0 \]

Запишемо у формі \(g_i\le0\):

\[ g_1=x+y-2 \]

\[ g_2=-x \]

\[ g_3=-y \]

10. Пряма допустимість кандидата

Візьмемо:

\[ x^*= \begin{pmatrix} 1.5\\ 0.5 \end{pmatrix} \]

Тоді:

\[ g_1=0 \]

\[ g_2=-1.5 \]

\[ g_3=-0.5 \]

Усі нерівності виконані.

11. Набір активних обмежень

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

\[ \mu_2=0 \]

\[ \mu_3=0 \]

Залишається знайти \(\mu_1\).

12. Градієнт цілі та градієнти обмежень

У кандидата:

\[ \nabla f= \begin{pmatrix} -1\\ -1 \end{pmatrix} \]

Градієнти обмежень:

\[ \nabla g_1= \begin{pmatrix} 1\\ 1 \end{pmatrix} \]

\[ \nabla g_2= \begin{pmatrix} -1\\ 0 \end{pmatrix} \]

\[ \nabla g_3= \begin{pmatrix} 0\\ -1 \end{pmatrix} \]

Для наскрізної точки \((1.5,0.5)\) градієнт цілі дорівнює:

\[ \nabla f= \begin{pmatrix} -1\\ -1 \end{pmatrix} \]

Активне обмеження \(g_1=x+y-2\) має градієнт:

\[ \nabla g_1= \begin{pmatrix} 1\\ 1 \end{pmatrix} \]

Тому з множником \(\mu_1=1\) маємо точний баланс \(\nabla f+\mu_1\nabla g_1=0\). Межі \(x\ge0\) та \(y\ge0\) неактивні, тож їхні множники дорівнюють нулю.

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

13. Стаціонарність

Оскільки \(\mu_2=\mu_3=0\):

\[ \nabla f+ \mu_1\nabla g_1=0 \]

Тобто:

\[ \begin{pmatrix} -1\\ -1 \end{pmatrix}+ \mu_1 \begin{pmatrix} 1\\ 1 \end{pmatrix}= \begin{pmatrix} 0\\ 0 \end{pmatrix} \]

Отже:

\[ \mu_1^*=1 \]

Множник невід’ємний, тому двоїста допустимість виконується.

14. Перевірка комплементарності

\[ \mu_1g_1=1\cdot0=0 \]

\[ \mu_2g_2=0\cdot(-1.5)=0 \]

\[ \mu_3g_3=0\cdot(-0.5)=0 \]

Усі добутки дорівнюють нулю.

15. Геометрія балансу KKT

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

\[ \nabla f+ \mu_1\nabla g_1=0 \]

Це формальна версія геометричної картини з попередніх двох лекцій.

16. Чому неактивний множник дорівнює нулю

Якщо \(g_i(x^*)<0\), то добуток \(\mu_i g_i(x^*)\) може дорівнювати нулю лише за \(\mu_i=0\). Отже, неактивне обмеження не бере участі у стаціонарному балансі.

Важливе уточнення: активне обмеження може мати нульовий множник. Тому «активне» не завжди означає «множник строго додатний».

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

17. Повний порядок ручної перевірки

Для кандидата зручно діяти так:

1. привести всі нерівності до однакового знакового стандарту;
2. обчислити значення обмежень;
3. перевірити пряму допустимість;
4. визначити набір активних обмежень;
5. знайти або отримати множники;
6. перевірити їхні знаки;
7. обчислити вектор стаціонарності;
8. перевірити комплементарні добутки;
9. оцінити всі нев’язки з числовим допуском.

Такий порядок зменшує ризик знакових помилок.

Для невеликої задачі корисно дотримуватися сталого порядку.

Спочатку підставляємо кандидат у всі обмеження і визначаємо активний набір. Далі перевіряємо невід’ємність множників. Після цього обчислюємо градієнти цілі та обмежень у кандидатові й формуємо вектор стаціонарності. Наприкінці перевіряємо добутки \(\mu_i g_i(x)\).

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

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

18. Пряма нев’язка

Для нерівностей:

\[ r_{\text{primal}}= \max_i \max(0,g_i(x^*)) \]

Для нашого прикладу:

\[ r_{\text{primal}}=0 \]

19. Двоїста нев’язка

Порушення умови \(\mu_i\ge0\) можна виміряти:

\[ r_{\text{dual}}= \max_i \max(0,-\mu_i) \]

Для \(\mu=(1,0,0)^T\) маємо нуль.

20. Нев’язка стаціонарності

Введемо:

\[ r_s= \nabla f(x^*)+ \sum_i \mu_i^*\nabla g_i(x^*) \]

Скалярна міра:

\[ \|r_s\|_2 \]

У нашому точному прикладі вона дорівнює нулю.

21. Нев’язка комплементарності

Для кожного обмеження:

\[ c_i=\mu_i g_i(x^*) \]

Використаємо:

\[ r_c= \max_i|c_i| \]

У нашому прикладі \(r_c=0\).

22. Єдина нев’язка KKT

Для стислого звіту можна визначити:

\[ r_{\text{KKT}}= \max \left( r_{\text{primal}}, r_{\text{dual}}, \|r_s\|_2, r_c \right) \]

Одна величина зручна для автоматичної перевірки, але окремі складові треба зберігати для діагностики.

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

\[ r_{\text{KKT}}= \max \left\{ r_{\text{primal}}, r_{\text{dual}}, r_{\text{stationarity}}, r_{\text{comp}} \right\} \]

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

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

У звіті варто зберігати і агреговане число, і чотири складові. Тоді причина невдалого сертифіката одразу видима.

23. Умова регулярності обмежень

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

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

У нашій задачі точка \((0.5,0.5)\) строго виконує всі нерівності, тому ця структура добре поводиться.

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

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

В опуклих задачах часто використовують умову Слейтера: існує точка, яка строго виконує всі опуклі нерівності та задовольняє афінні рівності. За такої умови теорія двоїстості та KKT має сильні властивості.

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

24. Коли умови KKT достатні

У загальній неопуклій задачі точка KKT може бути лише кандидатом. Для опуклої задачі ситуація сильніша.

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

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

Для опуклої задачі мінімізації з опуклими нерівностями \(g_i(x)\le0\), афінними рівностями та коректною знаковою домовленістю будь-яка точка, що задовольняє KKT, є глобальним мінімізатором.

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

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

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

25. Вхідні дані перевіряльника KKT

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


# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
point = np.array([
    1.5,
    0.5,
])

# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
multipliers = np.array([
    1.0,
    0.0,
    0.0,
])

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
constraint_values = np.array([
    point[0] + point[1] - 2.0,
    -point[0],
    -point[1],
])

# Обчислюємо окрему складову KKT-перевірки.
gradient_objective = np.array([
    2.0 * (point[0] - 2.0),
    2.0 * (point[1] - 1.0),
])

# Задаємо матрицю коефіцієнтів; порядок рядків і стовпців має збігатися з математичною моделлю.
constraint_gradients = np.array([
    [1.0, 1.0],
    [-1.0, 0.0],
    [0.0, -1.0],
])

# Виводимо базові величини, які далі використовуються у KKT-перевірці.
print("Точка:", point)
print("g(x):", constraint_values)
print("Градієнт цілі:", gradient_objective)

Порядок рядків у constraint_gradients повинен збігатися з порядком обмежень і множників.

26. Обчислення нев’язок

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
primal_residual = np.max(
    np.maximum(
        constraint_values,
        0.0,
    )
)

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
dual_residual = np.max(
    np.maximum(
        -multipliers,
        0.0,
    )
)

# Обчислюємо нев’язку стаціонарності безпосередньо з градієнтів і множників.
stationarity_vector = (
    gradient_objective
    + constraint_gradients.T
    @ multipliers
)

# Обчислюємо нев’язку стаціонарності безпосередньо з градієнтів і множників.
stationarity_residual = np.linalg.norm(
    stationarity_vector
)

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
complementarity = (
    multipliers
    * constraint_values
)

# Обчислюємо комплементарні добутки для кожного обмеження окремо.
complementarity_residual = np.max(
    np.abs(complementarity)
)

# Обчислюємо комплементарні добутки для кожного обмеження окремо.
kkt_residual = max(
    primal_residual,
    dual_residual,
    stationarity_residual,
    complementarity_residual,
)

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

PRIMAL_RESIDUAL: 0.0
DUAL_RESIDUAL: 0.0
STATIONARITY_RESIDUAL: 0.0
COMPLEMENTARITY_RESIDUAL: 0.0
KKT_RESIDUAL: 0.0

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

28. Числове визначення активності

# Обчислюємо окрему складову KKT-перевірки.
active_tolerance = 1e-6

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
is_active = (
    np.abs(constraint_values)
    <= active_tolerance
)

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

Очікувано:

[ True False False]

Активність і комплементарність особливо чутливі до допусків. Нехай чисельний результат має:

\[ g_1(x)=-2\cdot10^{-9} \]

а множник:

\[ \mu_1=0.9999998 \]

Математично активне обмеження мало б \(g_1=0\). Чисельно значення дуже близьке до нуля, тому при \(\varepsilon_{\text{active}}=10^{-8}\) обмеження класифікується як активне.

Добуток комплементарності:

\[ |\mu_1g_1(x)|\approx 2\cdot10^{-9} \]

також малий. Така пара узгоджується з KKT у межах допуску.

Інша ситуація: \(g_2(x)=-0.4\) та \(\mu_2=10^{-9}\). Обмеження має значний запас, а множник практично нульовий. Це природна неактивна пара.

Небезпечний випадок виникає, коли \(g_3(x)=-0.3\), але \(\mu_3=0.7\). Комплементарний добуток великий, тому кандидат або множники некоректні.

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

29. Чому множники з API треба перевіряти

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

Бібліотеки можуть використовувати іншу знакову домовленість для обмежень або повертати множники в іншому порядку. Наприклад, математична модель може записувати \(g(x)\le0\), а внутрішній інтерфейс — нижні та верхні межі окремими масивами.

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

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

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

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

Типова помилка. Обмеження \(x\ge0\) залишають у такому вигляді, але знак множника перевіряють за правилом для \(g(x)\le0\). Спочатку потрібно уніфікувати запис нерівностей.

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

31. Множники як чутливість

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

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

У ресурсній інтерпретації множник активного обмеження можна читати як локальну оцінку цінності послаблення межі. Якщо обмеження записане як \(g_i(x)=a_i^Tx-b_i\le0\), збільшення \(b_i\) розширює допустиму область.

За відповідних умов похідна оптимального значення за \(b_i\) пов’язана з множником \(\mu_i^*\). Знак залежить від того, як саме параметр входить у \(g_i\). Тому чутливість завжди читається разом із формулою обмеження.

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

32. Комплементарність через запас

Якщо \(s_i=-g_i(x)\ge0\), то умову можна записати:

\[ \mu_i s_i=0 \]

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

Якщо ввести запас:

\[ s_i=-g_i(x)\ge0 \]

то комплементарність набуває форми:

\[ \mu_i s_i=0 \]

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

Для чисельного кандидата можна вивести таблицю:

обмеження | запас | множник | добуток

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

У великих моделях ця форма часто зрозуміліша за один вектор KKT-нев’язки.

33. Методи внутрішньої точки і наближена комплементарність

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

\[ \mu_i s_i\approx\tau \]

де \(\tau>0\) поступово зменшується до нуля. Це пояснює, чому проміжні ітерації можуть не задовольняти точну комплементарність, але кінцевий розв’язок має до неї наближатися.

Методи внутрішньої точки під час ітерацій зазвичай тримають нерівності строго всередині допустимої області. Тому запас \(s_i\) і множник \(\mu_i\) можуть одночасно бути додатними.

Замість точної комплементарності алгоритм підтримує наближене співвідношення:

\[ \mu_i s_i\approx\tau \]

де параметр \(\tau>0\) поступово зменшується. Коли \(\tau\) наближається до нуля, траєкторія підходить до KKT-умов початкової задачі.

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

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

34. KKT як сертифікат, а не магічна формула

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

Тому числову нев’язку завжди треба читати разом із структурою задачі.

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

Такий підхід захищає від механічного розв’язування системи рівнянь. Сам факт, що деяка система дала числа, ще не показує, що точка допустима або глобально оптимальна. Значення KKT виникає з поєднання геометрії, опуклості та перевірених нев’язок.

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

Перевірку KKT після округлення варто використовувати як демонстрацію. Основний чисельний сертифікат повинен працювати з повною точністю. Наприклад, точний внутрішній вектор множників може давати нев’язку \(10^{-10}\), а округлення до двох знаків збільшить її до \(10^{-2}\).

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

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

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

35. Підсумок

Умови KKT об’єднують чотири групи перевірок: пряму допустимість, двоїсту допустимість, стаціонарність і комплементарну нежорсткість. Для домовленості \(g_i(x)\le0\) множники нерівностей повинні бути невід’ємними, а добуток \(\mu_i g_i(x)\) має бути близьким до нуля. Ці умови пов’язують геометрію активних меж із балансом градієнтів.

Чисельний сертифікат краще будувати з окремих нев’язок для кожної групи. Максимум цих значень зручний як підсумкова KKT-нев’язка, але детальні складові потрібні для діагностики. Порядок обмежень і знакова домовленість мають бути зафіксовані до читання множників із бібліотечного API.

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