Лабораторна робота 12. Автоматичний підбір кроку за правилом Armijo

Коротко про роботу

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

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

▶ Відкрити робочий зошит у браузері

1. Ситуація

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

Головне питання роботи: Як алгоритм вирішує, що запропонований крок завеликий, і як це побачити з журналу проб?

2. Що вже потрібно знати

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

напрям спадання;
градієнтний крок;
пошук довжини кроку;
умова Armijo;

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

3. Як перейти від ситуації до математики

Backtracking не шукає «ідеальний» крок. Він починає з пробного значення і зменшує його, доки зменшення функції не стане достатнім за правилом Armijo.

Спочатку сформулюйте зміст задачі словами. Лише після цього записуйте формули й код. Це зменшує ризик правильно порахувати не ту задачу.

4. Ваш варіант

У notebook змініть тільки один рядок:

STUDENT_X = 1  # поставте свій номер 1..30

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

Після запуску комірки «Дані вашого варіанта» notebook покаже всі числа, потрібні для роботи. Вручну підставляти STUDENT_X у формули не потрібно. Спочатку подивіться на отримані дані та підпишіть, що означає кожен масив або параметр.

5. Де тут треба подумати

Найважливіша частина — перша ітерація. Не приховуйте внутрішній цикл. Покажіть кожну спробу alpha: яке було нове значення функції, яка межа Armijo і чому крок прийнято або відхилено.

Перед тим як писати код, дайте собі відповідь на два питання:

Чому Armijo іноді відхиляє крок, який усе ж трохи зменшує функцію?
Що можна побачити з журналу проб, чого не видно з одного фінального alpha?

Відповідь не треба робити довгою. Достатньо 1–2 речень на кожне питання. Це допомагає перевірити, що ви розумієте задачу до запуску обчислень.

6. Послідовність роботи

Крок 1. Перевірити напрям

У стартовій точці покажіть, що \(\nabla f(x)^T d<0\) для \(d=-\nabla f(x)\).

Крок 2. Реалізувати `backtracking`

Починайте з alpha0; якщо Armijo не виконується — множте крок на rho.

Крок 3. Зберегти журнал першого пошуку

Для кожної проби запишіть alpha, f_trial, праву частину Armijo та статус.

Крок 4. Порівняти два `alpha0`

Покажіть, як початкове припущення впливає на кількість відхилених проб.

Крок 5. Вбудувати пошук у градієнтний спуск

Запускайте до малого градієнта або до ліміту ітерацій.

Крок 6. Перевірити фінальну точку

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

7. Python

Використовуйте: NumPy, Matplotlib.

Не намагайтеся вмістити всю роботу в одну велику комірку. Зручніше мати окремі невеликі блоки: дані → модель → обчислення → перевірка → висновок. Назви змінних повинні показувати їхній зміст.

8. Локальна самоперевірка

У робочому notebook наперед створені назви змінних, які читає автоматична перевірка. Не перейменовуйте їх. Ви самі пишете спосіб розв’язання, але фінальний результат записуєте у визначені змінні.

Змінна	Що записати
`first_search_log`	список словників alpha, f_trial, rhs, accepted для першого пошуку з alpha0=1
`x_solution`	фінальна точка градієнтного спуску з Armijo
`objective_value`	f(x_solution)
`grad_norm`	норма градієнта у фінальній точці
`iterations`	кількість зовнішніх ітерацій

Після виконання всіх кроків запустіть комірку «Локальна самоперевірка». Для вашого STUDENT_X вона читає наперед обчислені контрольні значення та порівнює з ними всі результатні змінні з таблиці вище. Числові значення порівнюються з указаним допуском; логічні, текстові та дискретні результати — точно. Для множин індексів порядок елементів не має значення, а для напрямів власних векторів враховується еквівалентність v та -v.

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

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

9. Що має бути у звіті

Звіт не повинен бути переписаним notebook. Покажіть вихідні дані, ключові проміжні результати, перевірки та короткий висновок своїми словами. У звіті обов’язково мають бути:

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

Наприкінці дайте відповідь на головне питання лабораторної одним коротким абзацом.

10. Контрольні питання

Навіщо умова Armijo, якщо напрям уже є напрямом спадання?

Показати відповідь

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

Що робить параметр rho?