Лекція 23. Оптимізація з обмеженнями: допустимість і активні обмеження

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

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

Практичний сенс. Найкраща точка без обмежень часто суперечить реальним правилам задачі. Обмеження змінюють геометрію пошуку, тому перша перевірка будь-якого розв’язку — допустимість. Активні обмеження визначають, у яких напрямах можна рухатися поблизу оптимуму.

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

1. Чому обмеження змінюють результат

Розглянемо:

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

Без обмежень мінімізатор очевидний:

\[ (2,1) \]

Додамо:

\[ x+y\le2 \]

\[ x\ge0 \]

\[ y\ge0 \]

Точка \((2,1)\) уже недопустима, бо \(2+1>2\). Отже, задача повинна знайти найкращу точку серед дозволених.

Без обмежень для наскрізної функції найкраща точка очевидна: центр квадратичної чаші \((2,1)\). Обмеження \(x+y\le2\) відсікає цю точку. Через це задача змінюється геометрично: тепер алгоритм шукає найкращу точку лише серед тих, які лежать у допустимій області.

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

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

1.1. Звідки беруться слова «допустимість», «активне обмеження», «запас» і «порушення»

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

Для нерівності \(g(x)\le0\) значення \(g(x)=0\) означає, що точка лежить на межі. Тоді обмеження називають активним. Якщо \(g(x)<0\), обмеження має запас. Зручно визначити запас як \(-g(x)\).

Якщо \(g(x)>0\), правило порушене. Тоді величина \(\max(0,g(x))\) є числовою мірою порушення. Значення обмеження, запас і порушення мають різні знаки та різний зміст.

2. Загальна постановка задачі з обмеженнями

Типова задача має вигляд:

\[ \min_x f(x) \]

за умов:

\[ g_i(x)\le0 \]

та:

\[ h_j(x)=0 \]

Функції \(g_i\) задають нерівності, а \(h_j\) — рівності. Множину всіх точок, що виконують усі обмеження, позначимо \(\mathcal F\) і називатимемо допустимою множиною.

3. Допустима область наскрізної задачі

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

\[ \mathcal F= \left\{ (x,y): x\ge0,\ y\ge0,\ x+y\le2 \right\} \]

Це трикутник у першій чверті.

4. Чому оптимум лежить на межі

Цільова функція є квадратом евклідової відстані до точки \((2,1)\). Тому задача шукає допустиму точку, найближчу до \((2,1)\).

Найближча точка трикутника лежить на прямій:

\[ x+y=2 \]

і дорівнює:

\[ (x^*,y^*)=(1.5,0.5) \]

5. Перевірка цільової функції

\[ f(1.5,0.5)= (-0.5)^2+(-0.5)^2 \]

Тому:

\[ f^*=0.5 \]

Це значення має сенс лише після підтвердження допустимості точки.

6. Стандартна форма нерівностей

Запишемо всі обмеження як \(g_i\le0\):

\[ g_1(x,y)=x+y-2 \]

\[ g_2(x,y)=-x \]

\[ g_3(x,y)=-y \]

У точці \((1.5,0.5)\):

\[ g(x^*)= \begin{pmatrix} 0\\ -1.5\\ -0.5 \end{pmatrix} \]

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

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

\[ g_i(x)\le0 \]

Тоді допустима точка має непозитивні значення всіх \(g_i\). Нуль означає активну межу, від’ємне значення — запас, додатне — порушення.

Наприклад, обмеження \(x+y\le2\) перетворюється на:

\[ g_1(x,y)=x+y-2\le0 \]

а нижня межа \(x\ge0\) — на:

\[ g_2(x,y)=-x\le0 \]

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

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

7. Запаси обмежень

Для форми \(g_i(x)\le0\) введемо:

\[ s_i=-g_i(x) \]

У нашій точці:

\[ s= \begin{pmatrix} 0\\ 1.5\\ 0.5 \end{pmatrix} \]

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

8. Порушення обмеження

Для числової перевірки зручно визначити:

\[ v_i= \max(0,g_i(x)) \]

Тоді найбільше порушення:

\[ v_{\max}= \max_i v_i \]

Для правильної допустимої точки \(v_{\max}=0\) у точній арифметиці.

Значення \(g_i(x)\) саме по собі містить знак і величину відхилення. Для автоматичної перевірки зручно виділити тільки додатну частину:

\[ v_i= \max(0,g_i(x)) \]

Якщо точка допустима за \(i\)-м обмеженням, маємо \(v_i=0\). Якщо обмеження порушене на 0.2 одиниці, отримаємо \(v_i=0.2\).

Для набору обмежень часто використовують максимальне порушення:

\[ v_{\max}= \max_i v_i \]

Це компактний показник, але він не замінює повний вектор. Значення \(v_{\max}=0.01\) не показує, яке саме обмеження проблемне. Тому в діагностичному звіті корисно зберігати і максимум, і індекс або назву критичного обмеження.

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

9. Числовий допуск допустимості

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

\[ g_i(x)\le\varepsilon \]

Для рівності перевіряють:

\[ |h_j(x)|\le\varepsilon \]

Числовий допуск не повинен маскувати суттєве порушення. Його потрібно задавати відповідно до масштабу даних.

10. Як визначати активність чисельно

У точній математиці активність означає \(g_i(x)=0\). У програмі зручно використовувати:

\[ |g_i(x)|\le\varepsilon_{\text{active}} \]

Наприклад, значення \(-10^{-8}\) можна вважати активним при допуску \(10^{-6}\).

У точній математиці активне обмеження має \(g_i(x)=0\). У чисельному розв’язку майже нуль може виглядати як \(-3\cdot10^{-9}\) або \(2\cdot10^{-10}\). Тому використовують окремий поріг активності:

\[ |g_i(x)|\le \varepsilon_{\text{active}} \]

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

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

Тому звіт повинен містити значення \(g_i(x)\) до округлення і використаний \(\varepsilon_{\text{active}}\).

11. Допустимий напрям

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

Для активного гладкого обмеження \(g(x)\le0\) малий напрям \(d\) локально допустимий, якщо:

\[ \nabla g(x)^Td\le0 \]

Для:

\[ g_1=x+y-2 \]

маємо:

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

Напрям \((1,1)^T\) дає додатний скалярний добуток і веде назовні. Напрям \((-1,0)^T\) веде всередину.

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

\[ g(x+\alpha d)\approx g(x)+ \alpha\nabla g(x)^Td \]

Якщо \(g(x)=0\), то для малого додатного \(\alpha\) безпечний напрям повинен задовольняти:

\[ \nabla g(x)^Td\le0 \]

Градієнт обмеження є нормаллю до межі й указує в бік зростання \(g\). Тому напрям із додатним скалярним добутком рухається назовні.

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

12. Чому антиградієнт може бути недопустимим

Градієнт цільової функції:

\[ \nabla f(x,y)= \begin{pmatrix} 2(x-2)\\ 2(y-1) \end{pmatrix} \]

У точці \((1.5,0.5)\):

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

Антиградієнт:

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

веде за межу \(x+y=2\). Отже, звичайна умова \(\nabla f=0\) більше не є правильною умовою оптимальності для точки на межі.

13. Проєкція на допустиму множину

Один інтуїтивний спосіб врахувати обмеження — спочатку зробити крок без обмежень:

\[ z_k=x_k-\alpha\nabla f(x_k) \]

а потім знайти найближчу допустиму точку:

\[ x_{k+1}= \Pi_{\mathcal F}(z_k) \]

Оператор \(\Pi_{\mathcal F}\) називають проєкцією на допустиму множину. Для замкненої опуклої множини така проєкція єдина.

Проєкція відповідає на просте запитання: якщо алгоритм запропонував недопустиму точку, яка допустима точка є до неї найближчою? Для евклідової норми проєкцію \(P_C(z)\) визначають як розв’язок:

\[ P_C(z)= \arg\min_{x\in C} \|x-z\|_2^2 \]

Якщо \(C\) опукла й замкнена, така проєкція єдина. Це робить її зручною операцією в проєкційних методах.

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

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

14. Чому оптимум не обов’язково вершина

У лінійному програмуванні оптимум можна шукати серед вершин. Для нелінійної опуклої цілі це правило вже не діє. У нашому прикладі точка \((1.5,0.5)\) лежить усередині ребра \(x+y=2\).

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

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

У нашій задачі допустима область є трикутником, але оптимум \((1.5,0.5)\) лежить усередині ребра \(x+y=2\). Він не є вершиною. Причина полягає у формі цілі: рівні квадратичної функції є колами навколо точки \((2,1)\), і найменше коло, що торкається допустимої області, дотикається до ребра.

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

15. Опуклість задачі

Матриця Гессе цілі:

\[ \nabla^2f= \begin{pmatrix} 2 & 0\\ 0 & 2 \end{pmatrix} \]

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

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

16. Повна перевірка кандидата

Для точки:

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

перевіряємо:

\[ 1.5+0.5-2=0 \]

\[ -1.5\le0 \]

\[ -0.5\le0 \]

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

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

Для наскрізного кандидата \((1.5,0.5)\):

\[ g_1=0,\qquad g_2=-1.5,\qquad g_3=-0.5 \]

Отже, перше обмеження активне, а дві межі змінних мають запас. Значення цілі дорівнює \(0.5\).

Наступний рівень перевірки — умови оптимальності. У цій лекції ми лише бачимо геометричний конфлікт антиградієнта з активною межею. Лекції 24–25 перетворять цю геометрію на рівняння з множниками.

17. Поганий кандидат

Візьмемо:

\[ \widetilde{x}= \begin{pmatrix} 1.7\\ 0.5 \end{pmatrix} \]

Тоді:

\[ g_1(\widetilde{x})=0.2 \]

Тому найбільше порушення дорівнює 0.2. При допуску \(10^{-6}\) точка однозначно недопустима.

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

18. Допустима, але не оптимальна точка

Візьмемо:

\[ \widehat{x}= \begin{pmatrix} 1\\ 0.5 \end{pmatrix} \]

Вона допустима, бо сума координат дорівнює 1.5. Проте:

\[ f(1,0.5)=1.25 \]

Це гірше за 0.5. Отже, допустимість є необхідною умовою, але ще не доводить оптимальність.

19. Межі змінних як звичайні обмеження

У API розв’язувача нижні та верхні межі змінних часто передаються окремим параметром. Математично це ті самі нерівності. Наприклад:

\[ x\ge0 \]

можна переписати як:

\[ -x\le0 \]

Під час незалежної перевірки межі треба перевіряти разом з іншими обмеженнями.

20. Порядок обмежень як частина контракту

Якщо перший елемент масиву constraint_values відповідає \(g_1\), то перший множник і перший рядок масиву градієнтів обмежень також повинні відповідати \(g_1\).

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

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

Тому корисно зберігати разом із числом назву або стабільний ідентифікатор:

budget: -3.2
capacity_machine_1: 0.0
minimum_quality: -0.7

Такий формат полегшує діагностику. Нуль одразу пов’язується з конкретною активною межею.

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

21. Мінімальний блок результату

Для задачі з обмеженнями корисно зберігати:

STATUS
X
OBJECTIVE
MAX_CONSTRAINT_VIOLATION
ACTIVE_CONSTRAINTS
ITERATIONS

У наступних лекціях до цього набору додадуться множники Лагранжа та нев’язка KKT.

Для задачі з обмеженнями машинозчитуваний блок може містити:

STATUS: candidate
X: [1.5, 0.5]
OBJECTIVE: 0.5
CONSTRAINT_VALUES: [0.0, -1.5, -0.5]
MAX_CONSTRAINT_VIOLATION: 0.0
ACTIVE_CONSTRAINTS: [0]
FEASIBILITY_TOL: 1e-8
ACTIVE_TOL: 1e-7

Поля FEASIBILITY_TOL і ACTIVE_TOL навмисно розділені. Перше відповідає за допустимість. Друге класифікує близькість до межі. Це різні рішення перевіряльника.

Якщо кандидат зміниться на \((1.50000004,0.50000003)\), сума координат трохи перевищить 2. При допуску \(10^{-8}\) така точка вже може вважатися недопустимою. При допуску \(10^{-6}\) вона пройде перевірку. Тому без записаного порогу слово «допустима» втрачає відтворюваний зміст.

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

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

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

22. Незалежна перевірка кандидата

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


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

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

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

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

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

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("CONSTRAINTS:", constraint_values)
print("SLACKS:", slacks)
print("MAX_VIOLATION:", max_violation)

Очікувано:

CONSTRAINTS: [ 0.  -1.5 -0.5]
SLACKS: [-0.   1.5  0.5]
MAX_VIOLATION: 0.0

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

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

# Додатна частина g_i(x) є порушенням, тому беремо найбільше з усіх обмежень.
max_violation = np.max(
    np.maximum(constraint_values, 0.0)
)

Такий код легко звірити з формулами \(g_1\), \(g_2\), \(g_3\). Імена та порядок повинні збігатися з математичним записом.

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

23. Перевірка цільової функції

# Описуємо цільову функцію тією самою формулою, що й у математичній постановці.
def objective(point):
    x = point[0]
    y = point[1]

    # Повертаємо результат допоміжного обчислення у погодженому числовому форматі.
    return (
        (x - 2.0) ** 2
        + (y - 1.0) ** 2
    )


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

Очікувано:

OBJECTIVE: 0.5

24. Чисельне розв’язання у SciPy

# Імпортуємо SciPy для обчислень, розв’язання моделі та її перевірки.
from scipy.optimize import minimize


# Виносимо окрему математичну операцію в допоміжну функцію, щоб її було легко перевірити.
def inequality(point):
    x = point[0]
    y = point[1]

    # Повертаємо результат допоміжного обчислення у погодженому числовому форматі.
    return 2.0 - x - y


# Запускаємо нелінійний розв’язувач із явно заданими функцією, стартом і потрібними похідними або обмеженнями.
result = minimize(
    objective,
    x0=np.array([0.5, 0.5]),
    bounds=[
        (0.0, None),
        (0.0, None),
    ],
    constraints=[
        {
            "type": "ineq",
            "fun": inequality,
        }
    ],
)

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

Очікується точка, близька до \((1.5,0.5)\).

25. Чому статус розв’язувача недостатній

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

Корисно окремо вивести найбільше порушення та повторно обчислене значення цільової функції.

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

Незалежна перевірка повинна повторно обчислити обмеження з початкових даних. Якщо бібліотека повернула \((x,y)\), перевіряльник окремо обчислює \(x+y-2\), \(-x\), \(-y\) і значення цілі. Такий підхід ловить помилки в коді моделі, які внутрішній статус бачити не може.

Корисно також перевіряти точку після округлення для звіту. Внутрішній розв’язок може бути допустимим із точністю \(10^{-9}\), а надруковані дві десяткові цифри вже порушують жорстке обмеження. Тому машинна перевірка працює з повною точністю, а округлення використовується лише для читабельного подання.

26. Перевірка скінченності

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

# Перевіряємо допустимість або активність обмежень.
is_finite = np.all(
    np.isfinite(point)
)

Ця проста перевірка повинна передувати складнішим нев’язкам.

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

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

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

Ще одна помилка — визначати активність через точну рівність з нулем у арифметиці з рухомою комою. Також часто забувають включити межі змінних у загальну перевірку.

28. Масштабування обмежень

Якщо одне обмеження має значення порядку \(10^6\), а інше — \(10^{-3}\), однаковий абсолютний допуск має різний практичний зміст. У складних моделях обмеження масштабують або використовують відносні критерії.

Це особливо важливо, якщо обмеження мають різні одиниці вимірювання.

Уявімо два обмеження. Перше вимірюється в гривнях і має праву частину \(10^6\). Друге вимірюється в частках і має масштаб близько 1. Одна абсолютна нев’язка \(10^{-4}\) має зовсім різний відносний зміст для цих двох умов.

Тому великі моделі часто масштабують або використовують відносні показники. Один варіант:

\[ \widetilde v_i= \frac{ \max(0,g_i(x)) }{ 1+s_i } \]

де \(s_i\) — характерний масштаб відповідного обмеження.

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

29. Жорсткі обмеження і штрафи

Жорстке обмеження означає, що порушення недопустиме. Якщо правило має зміст «бажано не перевищувати», іноді доречніше додати штраф до цільової функції. Це вже інша математична модель.

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

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

Наприклад, замість \(x+y\le2\) можна додати великий штраф за \(\max(0,x+y-2)^2\). Це вже інша оптимізаційна модель. Результат залежить від коефіцієнта штрафу.

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

30. Чому активні обмеження важливі далі

Активні обмеження визначають локальну межу допустимих напрямів. У наступній лекції для рівності з’явиться множник Лагранжа. Після цього умови KKT пов’яжуть активні нерівності з їхніми множниками.

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

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

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

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

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

31. Підсумок

У задачі з обмеженнями цільова функція порівнюється лише серед допустимих точок. Для домовленості \(g_i(x)\le0\) активне обмеження має значення, близьке до нуля, а неактивне — від’ємне. Запас показує резерв до межі, тоді як додатне значення \(g_i(x)\) означає порушення.

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

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