Лабораторна робота 18. Перевірка оптимуму за умовами KKT
Коротко про роботу
Ви отримаєте кандидата на оптимум задачі з нерівностями та незалежно перевірите його за KKT. У звіті мають бути пряма допустимість, множники, стаціонарність і комплементарність з явними числовими нев’язками.
Ця робота виконується після лекцій 25. Вона спирається лише на матеріал, який уже пройдено до цього заняття.
▶ Відкрити робочий зошит у браузері
1. Ситуація
Дві установки охолодження хочеться тримати близько до бажаних режимів. Але вони мають спільний ліміт і ще одне технологічне обмеження. Чисельний розв’язувач знаходить кандидат, але вам треба самостійно перевірити, що він відповідає умовам оптимальності.
Головне питання роботи: Які обмеження активні в оптимумі і чи можна повністю перевірити знайдену точку за умовами KKT?
2. Що вже потрібно знати
Перед початком достатньо розуміти такі речі з попередніх лекцій:
- пряма допустимість;
- множники для нерівностей;
- стаціонарність;
- комплементарна нежорсткість;
Якщо якийсь пункт забувся, поверніться до відповідної лекції. У цій роботі нова теорія не вводиться без пояснення.
3. Як перейти від ситуації до математики
KKT — це не окрема магічна формула. Це чотири перевірки: чи допустима точка, чи допустимі множники, чи збалансовані градієнти та чи узгоджені активність обмежень з множниками.
Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.
4. Ваш варіант
У notebook змініть тільки один рядок:
STUDENT_X = 1 # поставте свій номер 1..30
Номер варіанта змінює числа, але не дає готового способу розв’язання. Основна частина роботи однакова для всіх: побудувати правильну модель, зробити потрібний вибір і перевірити результат.
Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.
5. Де тут треба подумати
Не починайте з множників. Спочатку подивіться, які обмеження реально активні. Для неактивного обмеження множник має бути нульовим; множники активних обмежень відновіть з рівняння стаціонарності.
Перед тим як писати код, дайте собі відповідь на два питання:
- Чому множники треба шукати після визначення активних обмежень?
- Які чотири групи умов разом утворюють KKT-перевірку?
Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.
6. Послідовність роботи
Крок 1. Знайти кандидат
Використайте SLSQP лише для отримання точки \(x^*\).
Крок 2. Перевірити пряму допустимість
Порахуйте всі \(g_i(x^*)\) і знайдіть активні обмеження.
Крок 3. Відновити множники
Побудуйте рівняння стаціонарності для активного набору і розв’яжіть його.
Крок 4. Перевірити знак множників
Для нерівностей потрібні невід’ємні множники у прийнятому записі.
Крок 5. Перевірити комплементарність
Для кожного обмеження порахуйте \(\lambda_i g_i(x^*)\).
Крок 6. Зібрати підсумкову KKT-перевірку
Окремо покажіть максимум прямого порушення, двоїстого порушення, стаціонарності та комплементарність.
7. Python
Використовуйте: NumPy, SciPy SLSQP.
Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.
8. Локальна самоперевірка
У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.
| Змінна | Що записати |
|---|---|
x_solution |
кандидат оптимуму [x1,x2] |
objective_value |
f(x_solution) |
active_constraints |
номери активних обмежень серед [g1,g2,-x1,-x2] |
multipliers |
чотири множники у тому самому порядку |
primal_violation |
максимальне порушення прямої допустимості |
dual_violation |
максимальне порушення lambda>=0 |
stationarity_residual |
максимальна нев’язка стаціонарності |
complementarity_residual |
max(abs(lambda_i*g_i)) |
Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.
✅ OKозначає, що всі результатні змінні збігаються з контрольними значеннями в межах заданих допусків.❌означає, що біля конкретної змінної буде вказано, яке порівняння не пройдено.
Самоперевірка не замінює короткий предметний висновок: після OK поясніть своїми словами, що означає отриманий результат у ситуації цієї лабораторної.
9. Що має бути у звіті
Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:
- номер вашого варіанта;
- вихідні дані, які реально використовувалися;
- ключовий проміжний результат, на якому ґрунтується рішення;
- фінальний результат;
- незалежна числова перевірка;
- коротке пояснення, що цей результат означає в початковій прикладній ситуації.
Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.
10. Контрольні питання
- Який множник має відповідати неактивному обмеженню?
Показати відповідь
Нульовий у межах числового допуску, бо комплементарність вимагає узгодження множника із запасом обмеження.- Навіщо спочатку визначати активні обмеження?