Модуль 2

Нелінійна оптимізація, обмеження та стійкість рішень

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

20лекцій

15лабораторних

200питань із поясненнями

15змістових блоків

Що ви опануєте

аналізувати функції через похідні, градієнт і кривизну;

реалізовувати та перевіряти чисельні методи пошуку мінімуму;

працювати з рівностями, нерівностями, Лагранжем і KKT;

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

Як проходити модуль

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

Почати модуль

Детальний маршрут

Блок 1. Функція однієї змінної та її екстремуми

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

Л11Функції однієї змінної та екстремумиЛекція. Починаємо нелінійну оптимізацію з функції однієї змінної. Ви розберете область допустимих значень, локальні та глобальні екстремуми й навчитеся читати графік функції як задачу пошуку найкращого режиму. Л12Похідна як інструмент одновимірної оптимізаціїЛекція. Лекція показує, як похідна описує напрям і швидкість зміни функції. Ви навчитеся знаходити стаціонарні точки, аналізувати знак похідної та не забувати про межі інтервалу під час пошуку мінімуму. ЛР08Коли проводити профілактичне обслуговуванняЛабораторна. Ви знайдете економічно доцільний інтервал профілактичного обслуговування. Потрібно дослідити функцію витрат, використати похідну, перевірити стаціонарну точку та порівняти її з допустимими межами.

Блок 2. Чисельний пошук мінімуму на відрізку

Після блоку. Ви маєте розуміти, як працюють bounded-пошук, золотий переріз і Brent, навіщо потрібні інтервал і критерій зупинки та як порівнювати чисельні результати.

Л13Чисельна одновимірна оптимізація: обмежений пошук, золотий переріз і метод БрентаЛекція. Тут мінімум шукається чисельно, коли зручної аналітичної формули немає. Ви порівняєте обмежений пошук, золотий переріз і метод Брента та навчитеся контролювати інтервал, точність і критерій зупинки. ЛР09Пошук найкращого режиму насосної станціїЛабораторна. Ви чисельно знайдете найкращий режим насосної станції на заданому інтервалі. Потрібно реалізувати або відтворити кроки золотого пошуку, порівняти результат із bounded та Brent і пояснити роль tolerance.

Блок 3. Кілька змінних і напрям зміни функції

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

Л14Функції багатьох змінних і часткові похідніЛекція. Лекція переносить оптимізацію на функції кількох змінних. Ви навчитеся читати часткові похідні, розглядати зміну однієї координати за фіксованих інших і пов’язувати математичний запис зі змістом параметрів моделі. Л15Градієнт і геометрія напрямів зміниЛекція. Ви зберете часткові похідні у вектор градієнта та побачите його геометричний зміст. Лекція пояснює напрям найшвидшого зростання, напрям спадання та прогноз зміни функції вздовж заданого вектора. ЛР10У який бік змінювати два параметриЛабораторна. Ви дослідите, як два параметри калібрування впливають на помилку приладу. Потрібно обчислити градієнт, зробити кілька прогнозів для різних напрямів і перевірити ці прогнози реальними значеннями функції.

Блок 4. Градієнтний спуск

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

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

Блок 5. Вибір довжини кроку

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

Л17Вибір кроку, пошук довжини кроку і збіжністьЛекція. Тут головне питання — як вибрати довжину кроку, щоб рух уздовж хорошого напряму справді зменшував функцію. Ви познайомитеся з line search, умовою Armijo та практичними ознаками занадто малого або великого кроку. ЛР12Автоматичний підбір кроку за правилом ArmijoЛабораторна. Ви реалізуєте backtracking за правилом Armijo для автоматичного вибору кроку. Потрібно вести журнал пробних значень, розрізняти прийняті й відхилені кроки та перевірити, що прийнятий рух справді дає достатнє зменшення функції.

Блок 6. Кривизна і матриця Гессе

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

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

Блок 7. Newton і квазіньютонівські методи

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

Л19Метод Ньютона: локальна квадратична модельЛекція. Ви побачите, як метод Ньютона використовує градієнт і Гессіан для побудови локальної квадратичної моделі. Лекція пояснює Newton-крок, швидку локальну збіжність і ситуації, коли кривизна робить крок небезпечним. Л20BFGS і L-BFGS: практичні квазіньютонівські методиЛекція. Лекція показує, як використовувати інформацію про кривизну без прямого обчислення повного Гессіана на кожній ітерації. Ви розберете ідею BFGS, L-BFGS та практичний вибір між Newton і квазіньютонівськими методами. ЛР14Newton чи BFGS для нелінійного калібруванняЛабораторна. Ви розв’яжете одну задачу нелінійного калібрування двома методами — Newton і BFGS. Потрібно порівняти траєкторії, кількість кроків, фінальні значення та пояснити, яку інформацію про кривизну використовує кожен метод.

Блок 8. Опуклість і гарантії оптимізації

Після блоку. Ви маєте вміти пояснити геометричний зміст опуклості та перевірити квадратичну модель за Гессіаном і власними значеннями.

Л21Опуклі множини та опуклі функціїЛекція. Тут вводяться опуклі множини та опуклі функції, які дають сильні гарантії для оптимізації. Ви навчитеся розуміти геометричний зміст опуклості та пояснювати, чому локальний мінімум в опуклій задачі є глобальним. Л22Практична перевірка опуклості: матриця Гессе і додатна визначеністьЛекція. Лекція дає практичний спосіб перевіряти опуклість гладкої функції через матрицю Гессе. Ви навчитеся розрізняти додатно визначену, напіввизначену й невизначену кривизну та пов’язувати це з формою цільової функції. ЛР15Чи можна довіряти опуклості моделіЛабораторна. Ви перевірите три квадратичні моделі з різною кривизною. За матрицями Гессе та власними значеннями потрібно визначити, яка модель строго опукла, яка має плоский напрям, а яка взагалі не є опуклою.

Блок 9. Допустимість та активні обмеження

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

Л23Оптимізація з обмеженнями: допустимість і активні обмеженняЛекція. Ви переходите до нелінійної оптимізації з обмеженнями. Лекція пояснює допустимі точки, запас обмеження, активні межі та роль tolerance, щоб коректно класифікувати точки біля границі допустимої області. ЛР16Які обмеження реально стримують планЛабораторна. Ви проаналізуєте кілька планів відносно системи обмежень. Потрібно обчислити запаси, розрізнити допустимі, активні та порушені обмеження й правильно використати числовий tolerance біля межі.

Блок 10. Оптимум за рівнянням-обмеженням

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

Л24Множники Лагранжа для рівностейЛекція. Лекція показує, як шукати оптимум за рівнянням-обмеженням через множник Лагранжа. Ви навчитеся будувати функцію Лагранжа, читати умову стаціонарності та розуміти геометричне узгодження градієнтів у точці розв’язку. ЛР17Як розподілити обмежений ресурс між чотирма каналамиЛабораторна. Ви розподілите обмежений ресурс між чотирма каналами так, щоб сумарні втрати були мінімальними. Потрібно скласти систему Лагранжа, знайти розв’язок і пояснити, що означає множник для зміни загального ресурсу.

Блок 11. Нерівності та умови KKT

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

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

Блок 12. Квадратичне програмування

Після блоку. Ви маєте вміти записати квадратичну ціль і лінійні обмеження, отримати розв’язок у CVXPY та незалежно перевірити його через обмеження, dual values і KKT-нев’язки.

Л26Квадратичне програмування і CVXPYЛекція. Лекція вводить квадратичне програмування та показує, як задавати такі моделі у CVXPY. Ви навчитеся читати квадратичну ціль, формувати обмеження, отримувати dual values і незалежно перевіряти результат після solver-а. ЛР19Квадратичний план заряджання акумуляторного паркуЛабораторна. Ви побудуєте квадратичну модель заряджання чотирьох акумуляторних модулів у CVXPY. Після solver-а потрібно перевірити межі, баланс потужності, dual values та сформувати незалежний KKT-аудит розв’язку.

Блок 13. Оцінювання параметрів за надлишковими даними

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

Л27Метод найменших квадратів як оптимізаційна модельЛекція. Метод найменших квадратів розглядається як оптимізаційна модель для оцінювання параметрів за надлишковими даними. Ви навчитеся будувати матрицю ознак, знаходити параметри та аналізувати вектор і норму залишків. ЛР20Калібрування датчика за багатьма вимірюваннямиЛабораторна. Ви оціните три параметри промислового датчика за дванадцятьма вимірюваннями. Потрібно самостійно побудувати матрицю ознак, знайти оцінку методом найменших квадратів та перевірити якість моделі через залишки й їхню норму.

Блок 14. Стабільність оцінювання та Ridge

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

Л28Регуляризація та стабілізація оцінюванняЛекція. Лекція пояснює, чому майже залежні ознаки роблять оцінки нестійкими. Ви побачите, як Ridge-регуляризація додає штраф до моделі, зменшує чутливість коефіцієнтів і створює контрольований компроміс між точністю та стабільністю. ЛР21Як стабілізувати модель Ridge-регуляризацієюЛабораторна. Ви побачите нестійкість методу найменших квадратів на майже залежних ознаках і перевірите, як її змінює Ridge. Потрібно порівняти коефіцієнти до і після малої зміни даних, вибрати $\lambda$ та кількісно оцінити стабілізацію.

Блок 15. Кілька критеріїв і фінальний аудит

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

Л29Багатокритеріальна оптимізація та Парето-компромісиЛекція. Тут одна ціль замінюється кількома критеріями, які можуть конфліктувати. Ви навчитеся знаходити доміновані рішення, будувати множину Парето та обґрунтовано вибирати компроміс через ваги або інший прозорий критерій. Л30Чисельна надійність та аудит оптимізаційного розв’язкуЛекція. Завершальна лекція збирає чисельний аудит оптимізаційного розв’язку в єдину процедуру. Ви навчитеся перевіряти статус, допуски, нев’язки, обмеження, цільову функцію та відтворюваність результату перед практичним використанням. ЛР22Як обрати між кількома добрими рішеннямиЛабораторна. Ви проаналізуєте набір альтернатив за трьома критеріями й відкинете доміновані рішення. Потім потрібно вибрати компроміс двома способами, порівняти результати та завершити роботу чисельним аудитом обраної альтернативи.

Практика в браузері

Для лабораторних використовується JupyterLite. Відкрийте notebook потрібної лабораторної, задайте свій STUDENT_X, виконайте роботу та запустіть точну самоперевірку.

Відкрити JupyterLite