Методи оптимізації; лінійне/нелінійне програмування; градієнтний спуск

📌 Про що ця тема

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

📖 Головне

• Задача оптимізації = знайти значення змінних, за яких цільова функція f(x) набуває найбільшого або найменшого значення, можливо за наявності обмежень.

• Цільова функція — те, що оптимізуємо (прибуток, витрати, час). Обмеження — умови-нерівності чи рівняння, яких мусить дотримуватись розвʼязок.

• Допустима область — множина всіх точок, що задовольняють обмеження. Оптимум шукають тільки серед них.

• Лінійне програмування (ЛП): і цільова функція, і всі обмеження лінійні (змінні лише в першому степені, без добутків). Приклад: максимізувати 3x + 2y за умов x + y ≤ 10, x ≥ 0, y ≥ 0.

• У ЛП допустима область — многокутник, а оптимум завжди досягається у вершині цього многокутника (кутовій точці). Це основа графічного методу.

• Графічний метод (для 2 змінних): побудувати обмеження як прямі, знайти многокутник, перевірити цільову функцію у його вершинах.

• Нелінійне програмування (НЛП): цільова функція або обмеження нелінійні (квадрати, добутки, корені). Оптимум може бути всередині області, а не лише у вершині.

• Локальний мінімум — точка, краща за сусідні; глобальний — найкраща з усіх. У НЛП їх може бути багато.

• Градієнтний спуск — ітеративний метод пошуку мінімуму: рухаємось у напрямку, протилежному градієнту (напрямку найшвидшого зростання).

• Формула кроку: x_нове = x_старе − η·f′(x), де η (ета) — швидкість навчання (крок).

• Малий η → повільна збіжність; завеликий η → «перестрибування» мінімуму й розбіжність.

🔢 Як це працює на прикладі

Градієнтний спуск для f(x) = x², f′(x) = 2x, старт x = 4, η = 0.1.

• Крок 1: x = 4 − 0.1·(2·4) = 4 − 0.8 = 3.2

• Крок 2: x = 3.2 − 0.1·(2·3.2) = 3.2 − 0.64 = 2.56

• Крок 3: x = 2.56 − 0.512 = 2.048

Значення наближаються до 0 — це й є точка мінімуму функції x².

ЛП-приклад: максимізувати P = 3x + 2y, x + y ≤ 4, x ≥ 0, y ≥ 0. Вершини: (0,0)→0, (4,0)→12, (0,4)→8. Максимум P = 12 у точці (4,0).

⚠️ Типові помилки

• Плутають, що оптимізуємо: цільову функцію (її значення), а не змінні.

• У ЛП шукають оптимум усередині області, хоча він завжди у вершині многокутника.

• У градієнтному спуску додають градієнт замість віднімання — тоді замість мінімуму знаходять максимум (рух угору).

• Забувають знак у похідній або неправильно множать на η.

• Вважають, що локальний мінімум = глобальний; у нелінійних задачах це не так.

🎯 Що завчити напамʼять

• Крок спуску: x_нове = x_старе − η·f′(x).

• У ЛП оптимум — у вершині допустимого многокутника.

• ЛП = все лінійне; НЛП = є нелінійність.

• Градієнт показує напрямок зростання → для мінімуму йдемо проти нього.

• Завеликий η → розбіжність, замалий → повільність.

🧠 Перевір себе

1. У якій точці допустимої області досягається оптимум у лінійному програмуванні?

2. Чому в градієнтному спуску віднімають градієнт, а не додають?

3. Обчисли один крок спуску для f(x)=x², x=5, η=0.1.

4. Чим НЛП відрізняється від ЛП?

Відповіді: 1 — у вершині (кутовій точці) многокутника; 2 — градієнт вказує напрямок зростання, а для мінімуму потрібен спад; 3 — x = 5 − 0.1·(2·5) = 5 − 1 = 4; 4 — у НЛП цільова функція або обмеження нелінійні, оптимум може бути всередині області й мати кілька локальних мінімумів.