Лекція 26. Квадратичне програмування і CVXPY

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

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

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

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

1. Що називають квадратичним програмуванням

Типова задача квадратичного програмування має вигляд:

\[ \min_x \left( \frac{1}{2}x^TQx+c^Tx \right) \]

за лінійних обмежень:

\[ Ax\le b \]

та, за потреби:

\[ Ex=d \]

Матриця \(Q\) задає квадратичну частину цільової функції. Вектор \(c\) задає лінійну частину. Матриці \(A\) та \(E\) описують лінійні обмеження.

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

\[ \min_x \left( \frac{1}{2}x^TQx+c^Tx \right) \]

за умов:

\[ Ax\le b \]

та, за потреби:

\[ Ex=d \]

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

Практично QP лежить між лінійним програмуванням і загальною нелінійною оптимізацією. Структура складніша за LP, але для додатно напіввизначеної \(Q\) задача залишається опуклою. Це дозволяє використовувати сильні глобальні гарантії.

1.1. Що означає назва і навіщо CVXPY

У словосполученні квадратичне програмування слово «програмування» означає математичне планування, як і в лінійному програмуванні. «Квадратичне» означає, що ціль містить члени другого степеня.

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

CVXPY — назва Python-бібліотеки для опису опуклих задач. Вона дозволяє записувати змінні, ціль і обмеження у формі, близькій до математичного запису, а потім передає задачу чисельному розв’язувачу. Назву бібліотеки не перекладаємо, бо це ім’я програмного засобу.

2. Звідки береться квадратична ціль

Квадратичний штраф природно виникає, коли великі відхилення мають бути значно дорожчими за малі. Наприклад:

\[ (x-2)^2 \]

дорівнює 1 при відхиленні на одиницю, але 9 при відхиленні на три одиниці.

У багатовимірній задачі квадратичний вираз записують через:

\[ x^TQx \]

Матриця \(Q\) визначає, як сильно штрафуються різні напрями і як змінні взаємодіють між собою.

3. Розклад знайомої функції

Візьмемо:

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

Розкриємо дужки:

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

Введемо:

\[ z= \begin{pmatrix} x\\ y \end{pmatrix} \]

Тоді:

\[ f(z)= \frac{1}{2}z^TQz+c^Tz+5 \]

де:

\[ Q= \begin{pmatrix} 2 & 0\\ 0 & 2 \end{pmatrix} \]

і:

\[ c= \begin{pmatrix} -4\\ -2 \end{pmatrix} \]

4. Чому перед квадратичною формою ставлять одну другу

Для симетричної матриці \(Q\):

\[ q(x)= \frac{1}{2}x^TQx+c^Tx \]

має градієнт:

\[ \nabla q(x)=Qx+c \]

Без множника \(1/2\) перед квадратичною частиною з’явився б додатковий множник 2. Тому такий запис спрощує похідні та умови KKT.

Множник \(1/2\) не змінює місце мінімуму, бо масштабує лише квадратичну частину за відповідно визначеної \(Q\). Його використовують для зручної похідної.

Для симетричної матриці \(Q\):

\[ \nabla \left( \frac{1}{2}x^TQx \right)= Qx \]

Без множника \(1/2\) у градієнті з’явився б коефіцієнт 2. Через це стандартна форма робить рівняння стаціонарності коротшим:

\[ Qx+c=0 \]

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

5. Розмірності об’єктів

Якщо змінних \(n\), то:

\[ x\in\mathbb R^n \]

\[ Q\in\mathbb R^{n\times n} \]

\[ c\in\mathbb R^n \]

Якщо є \(m\) нерівностей:

\[ A\in\mathbb R^{m\times n} \]

\[ b\in\mathbb R^m \]

Кожний рядок \(A\) відповідає одному обмеженню. Порядок стовпців повинен збігатися з порядком змінних у \(x\).

6. Чому матрицю Q вважають симетричною

Скаляр:

\[ x^TQx \]

не змінюється, якщо \(Q\) замінити її симетричною частиною:

\[ Q_s= \frac{1}{2}(Q+Q^T) \]

Тому квадратичну матрицю зручно відразу вважати симетричною. Для гладкої квадратичної функції матриця Гессе також симетрична.

Будь-яку квадратну матрицю можна розкласти на симетричну та кососиметричну частини:

\[ Q= \frac{1}{2}(Q+Q^T)+ \frac{1}{2}(Q-Q^T) \]

Для квадратичної форми кососиметрична частина не впливає на значення:

\[ x^T(Q-Q^T)x=0 \]

Тому:

\[ x^TQx= x^T \left( \frac{1}{2}(Q+Q^T) \right)x \]

Отже, для аналізу цілі достатньо симетричної частини \(Q_s=(Q+Q^T)/2\). Це важливо і для опуклості, бо власні значення та визначеність коректно інтерпретуються для симетричної матриці.

У коді корисно явно перевіряти нев’язку симетрії. Значна асиметрія часто означає помилку в побудові коефіцієнтів.

7. Стала частина цільової функції

У початковій функції є стала 5. Вона зсуває всі значення цільової функції на однакову величину, але не змінює точку мінімуму.

Тому QP часто записують без сталої:

\[ q(x)= \frac{1}{2}x^TQx+c^Tx \]

У звіті важливо пам’ятати, яка саме форма використовується. Інакше можна отримати правильні координати, але різні числові значення цілі.

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

8. Опуклість квадратичного програмування

Для квадратичної цілі матриця Гессе дорівнює \(Q\). Якщо:

\[ Q\succeq0 \]

цільова функція опукла. Якщо:

\[ Q\succ0 \]

вона строго опукла.

Лінійні нерівності й рівності задають опуклу допустиму множину. Тому при \(Q\succeq0\) вся задача QP є опуклою.

Для квадратичної цілі матриця Гессе є сталою:

\[ \nabla^2f(x)=Q \]

Тому опуклість перевіряється один раз. Якщо:

\[ Q\succeq0 \]

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

Якщо \(Q\succ0\), ціль строго опукла. Тоді за існування допустимого мінімізатора він єдиний. Це дає сильний практичний висновок: різні коректні чисельні методи повинні збігатися до одного й того самого вектора рішення з урахуванням числового допуску.

Якщо \(Q\) має від’ємне власне значення, глобальна опуклість зникає. Тоді локальний KKT-кандидат уже не дає автоматичної глобальної гарантії.

9. Чому це важливо

У опуклій задачі умови KKT мають глобальний зміст за стандартних умов регулярності. Якщо \(Q\succ0\), ціль строго опукла, тому допустимий мінімізатор єдиний.

Отже, перевірка власних значень \(Q\) повинна відбуватися до остаточного тлумачення чисельного результату.

10. Наскрізний приклад

Мінімізуємо:

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

за умов:

\[ x+y\le2 \]

\[ x\ge0 \]

\[ y\ge0 \]

У QP-формі без сталої:

\[ q(z)= \frac{1}{2}z^TQz+c^Tz \]

де \(Q\) і \(c\) наведені вище.

Розглядаємо ціль:

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

за умов:

\[ x+y\le2,\qquad x\ge0,\qquad y\ge0 \]

Після розкриття дужок:

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

Стала 5 не впливає на мінімізатор. Для вектора \(z=(x,y)^T\) можна взяти:

\[ Q= \begin{pmatrix} 2 & 0\\ 0 & 2 \end{pmatrix}, \qquad c= \begin{pmatrix} -4\\ -2 \end{pmatrix} \]

Тоді \(\frac{1}{2}z^TQz+c^Tz\) відтворює змінну частину цілі. Власні значення \(Q\) дорівнюють 2, отже ціль строго опукла. Це пояснює, чому знайдений кандидат \((1.5,0.5)\) є єдиним глобальним мінімізатором.

11. Геометричне тлумачення

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

Геометрія QP

Найближча точка лежить на активній прямій \(x+y=2\) і дорівнює \((1.5,0.5)\).

12. Безумовний мінімізатор

Без обмежень:

\[ Qz+c=0 \]

Тому:

\[ \begin{pmatrix} 2 & 0\\ 0 & 2 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix}+ \begin{pmatrix} -4\\ -2 \end{pmatrix} =0 \]

Отримуємо \((2,1)\). Ця точка порушує \(x+y\le2\), тому обмеження справді змінює розв’язок.

13. Умови KKT для QP

Запишемо нерівності у формі:

\[ g_1=x+y-2\le0 \]

\[ g_2=-x\le0 \]

\[ g_3=-y\le0 \]

Для кандидата \((1.5,0.5)\) перше обмеження активне, інші мають запас. Множники:

\[ \mu= \begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix} \]

задовольняють стаціонарність.

Для QP з нерівностями \(g_i(x)\le0\) функція Лагранжа має вигляд:

\[ L(x,\mu)= \frac{1}{2}x^TQx+c^Tx+ \sum_i\mu_i g_i(x) \]

Стаціонарність:

\[ Qx+c+ \sum_i\mu_i\nabla g_i(x)=0 \]

Оскільки обмеження лінійні, їхні градієнти сталі. Тому KKT-система для опуклого QP має особливо прозору структуру.

У наскрізному прикладі активне лише \(x+y\le2\). Його градієнт дорівнює \((1,1)^T\), а множник \(\mu_1=1\). Підстановка в стаціонарність дає нульовий вектор.

Для опуклого QP за стандартних умов KKT є глобальним сертифікатом. Через це незалежна KKT-перевірка добре підходить для контролю результату CVXPY.

14. Перевірка стаціонарності QP

Градієнт цілі у формі без сталої:

\[ \nabla q(z)=Qz+c \]

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

\[ Qz+c= \begin{pmatrix} -1\\ -1 \end{pmatrix} \]

Градієнт активного обмеження:

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

Тому:

\[ Qz+c+ \mu_1\nabla g_1=0 \]

при \(\mu_1=1\).

Баланс KKT у QP

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

У формі QP без сталої:

\[ q(1.5,0.5)=-4.5 \]

Після повернення сталої 5:

\[ f(1.5,0.5)=0.5 \]

Різниця рівно 5, тому мінімізатор однаковий.

16. Додатно напіввизначена і додатно визначена Q

Якщо \(Q\succeq0\), задача опукла, але мінімізатор може бути неєдиним. Якщо \(Q\succ0\), квадратична ціль строго опукла і на опуклій допустимій множині має не більше одного мінімізатора.

Ця різниця впливає на автоматичну перевірку: для неєдиного оптимуму не можна вимагати один конкретний вектор координат.

17. Що відбувається при невизначеній Q

Якщо \(Q\) має від’ємне власне значення, цільова функція неопукла. На необмеженій області може існувати напрям, уздовж якого ціль прямує до \(-\infty\). На обмеженій області мінімум може існувати, але умови KKT вже не дають автоматичної глобальної гарантії.

Тому знак власних значень \(Q\) є частиною класифікації задачі, а не технічною деталлю.

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

18. Як перетворити прикладну задачу на QP

Послідовність така:

визначити змінні рішення;
записати квадратичну та лінійну частини цілі;
побудувати \(Q\) і \(c\);
перевірити симетрію \(Q\);
перевірити власні значення \(Q\);
записати всі обмеження;
розв’язати задачу;
незалежно перевірити допустимість, ціль і KKT.

Перетворення варто виконувати в чіткій послідовності.

Спочатку визначаємо вектор змінних і фіксуємо порядок компонентів. Далі записуємо предметну ціль у звичайній алгебраїчній формі. Після цього збираємо квадратичні коефіцієнти в \(Q\), лінійні — у \(c\), а сталу частину зберігаємо окремо для перевірки значення цілі.

Потім усі обмеження переводимо в матричний вигляд. На цьому етапі потрібно перевірити розмірності: \(Q\) має бути \(n\times n\), \(c\) — довжини \(n\), а кожен рядок матриці обмежень — також довжини \(n\).

Останній крок до запуску алгоритму — перевірка симетрії та власних значень \(Q\). Так математична класифікація задачі визначається до чисельного розв’язання.

19. Перевірка матриці Q вручну

Для нашої матриці:

\[ Q= \begin{pmatrix} 2 & 0\\ 0 & 2 \end{pmatrix} \]

власні значення дорівнюють 2 і 2. Матриця додатно визначена. Число обумовленості дорівнює 1, тому сама квадратична частина добре масштабована.

20. Перевірка обмежень

У кандидата:

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

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

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

\[ A= \begin{pmatrix} 1 & 1\\ -1 & 0\\ 0 & -1 \end{pmatrix}, \qquad b= \begin{pmatrix} 2\\ 0\\ 0 \end{pmatrix} \]

так що:

\[ Az\le b \]

для \(z=(x,y)^T\). У кандидатові \(z^*=(1.5,0.5)^T\) маємо:

\[ Az^*= \begin{pmatrix} 2\\ -1.5\\ -0.5 \end{pmatrix} \]

і вектор нев’язок \(Az^*-b\):

\[ \begin{pmatrix} 0\\ -1.5\\ -0.5 \end{pmatrix} \]

Максимальне позитивне порушення дорівнює нулю.

Цей матричний запис корисний для незалежного перевіряльника, бо не залежить від синтаксису CVXPY. Ті самі \(A\), \(b\) і \(z^*\) можна перевірити NumPy.

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

21. Нев’язки KKT

Для повного контролю обчислюють:

пряму нев’язку;
двоїсту нев’язку;
нев’язку стаціонарності;
нев’язку комплементарності.

У точному навчальному прикладі всі вони дорівнюють нулю.

Для знайденого кандидата корисно обчислити ті самі чотири групи нев’язок, що й у попередній лекції.

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

\[ r_s= \left\| Qx+c+A^T\mu \right\|_2 \]

для відповідної матричної форми. Комплементарна нев’язка контролює добутки множників на запаси.

Для опуклого QP малі нев’язки разом із підтвердженою додатною напіввизначеністю \(Q\) дають значно сильніший висновок, ніж статус optimal сам по собі. Статус описує завершення програмного алгоритму, а KKT-вектор відтворює математичні умови задачі.

22. Рівності в QP

Якщо присутня рівність:

\[ Ex=d \]

до функції Лагранжа додається:

\[ \lambda^T(Ex-d) \]

Стаціонарність набуває вигляду:

\[ Qx+c+A^T\mu+E^T\lambda=0 \]

Тому QP природно об’єднує матеріал про матриці, опуклість, Лагранжа і KKT.

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

23. Відповідність математики і Python

Математика	Python	Зміст
\(Q\)	`Q`	квадратична матриця
\(c\)	`c`	лінійні коефіцієнти
\(x\)	`x`	змінні рішення
\(Ax\le b\)	`constraints`	лінійні обмеження
\(q(x)\)	`objective_value`	значення цілі

24. Перевірка власних значень

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


# Задаємо матрицю кривизни у фіксованому порядку змінних.
Q = np.array([
    [2.0, 0.0],
    [0.0, 2.0],
])

# Обчислюємо власні значення симетричної матриці, щоб визначити знак локальної кривизни.
eigenvalues = np.linalg.eigvalsh(Q)

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

Очікувано:

[2. 2.]

25. Модель у CVXPY

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


# Задаємо матрицю кривизни у фіксованому порядку змінних.
Q = np.array([
    [2.0, 0.0],
    [0.0, 2.0],
])

# Задаємо коефіцієнти цільової функції в тому самому порядку, що й компоненти вектора змінних.
c = np.array([
    -4.0,
    -2.0,
])

# Описуємо змінні, квадратичну ціль і обмеження у CVXPY в тому самому порядку, що й у формулах.
x = cp.Variable(2)

# Виконуємо матричний або скалярний добуток, який прямо відповідає формулі математичної моделі.
objective = cp.Minimize(
    0.5 * cp.quad_form(x, Q)
    + c @ x
)

# Описуємо або перевіряємо квадратичну модель.
constraints = [
    x[0] + x[1] <= 2.0,
    x >= 0.0,
]

# Описуємо змінні, квадратичну ціль і обмеження у CVXPY в тому самому порядку, що й у формулах.
problem = cp.Problem(
    objective,
    constraints,
)

# Запускаємо CVXPY-розв’язувач; після завершення незалежно перерахуємо ціль та обмеження.
problem.solve()

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

Очікувана точка близька до \((1.5,0.5)\). Значення problem.value відповідає формі без сталої й має бути близьким до \(-4.5\).

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

Для квадратичної форми часто використовують cp.quad_form(x, Q). Перед цим \(Q\) повинна мати правильний розмір і відповідну визначеність. Помилка в порядку змінних або коефіцієнтах не буде виправлена бібліотекою автоматично.

Тому код моделі має супроводжуватися таблицею відповідності «математичний об’єкт → Python-об’єкт». Після problem.solve() потрібно читати статус, значення змінних і цілі, а далі незалежно повторити перевірки в NumPy.

26. Що робить CVXPY

CVXPY не є самою математичною теорією QP. Бібліотека будує формальний опис задачі, перевіряє правила допустимої опуклої композиції та обирає або викликає чисельний розв’язувач.

Тому правильність моделі треба перевіряти до виклику solve(), а результат — після нього.

27. Незалежна перевірка результату CVXPY

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
solution = np.asarray(
    x.value,
    dtype=float,
)

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

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

# Виконуємо матричний або скалярний добуток, який прямо відповідає формулі математичної моделі.
qp_value = (
    0.5 * solution @ Q @ solution
    + c @ solution
)

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

Незалежна перевірка не повинна повторювати ті самі обчислення тим самим шляхом. Якщо CVXPY сформував модель, перевіряльник може працювати без CVXPY: взяти числовий вектор \(x^*\) і початкові масиви \(Q\), \(c\), \(A\), \(b\).

Далі обчислюємо:

\[ f_{\text{check}}= \frac{1}{2}{x^*}^TQx^*+ c^Tx^* \]

разом із усіма обмеженнями та максимальним порушенням. Якщо доступні множники, додаємо KKT-нев’язки.

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

28. Альтернативна перевірка через SciPy

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

Ту саму маленьку QP-задачу можна розв’язати загальним методом scipy.optimize.minimize, передавши ціль, градієнт та обмеження. Такий запуск корисний як незалежне чисельне порівняння з CVXPY.

Очікуваний вектор повинен бути близьким до \((1.5,0.5)\). Проте збіг двох бібліотек ще не є математичним доказом. Обидві реалізації можуть отримати однаково помилкові дані.

Тому після порівняння все одно обчислюються власні значення \(Q\), допустимість, ціль та KKT-нев’язки. Найсильніший результат виникає, коли незалежні чисельні методи узгоджуються, а математичний перевіряльник підтверджує структуру.

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

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

Типова помилка. Матрицю \(Q\) передають у бібліотеку без перевірки симетрії та власних значень. Через це математичний клас задачі залишається невідомим.

Інша помилка — плутати значення цілі з постійною 5 і без неї. Також не варто вважати успішний статус бібліотеки заміною перевірки обмежень.

30. Коли QP є природною моделлю

Квадратичне програмування доречне, коли:

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

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

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

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

Не варто штучно перетворювати довільну нелінійну функцію на QP лише заради зручного розв’язувача. Клас задачі визначається математичною структурою. Якщо ця структура є, спеціалізовані методи дають і швидкість, і сильні перевірки.

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

Мінімальний звіт QP:

STATUS
X
OBJECTIVE
MIN_EIGENVALUE_Q
MAX_CONSTRAINT_VIOLATION
KKT_RESIDUAL

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

Мінімальний звіт QP повинен дозволяти відтворити і модель, і сертифікат. Корисні поля:

Q:
c:
constraints:
status:
x:
objective:
min_eigenvalue_Q:
max_constraint_violation:
stationarity_residual:
complementarity_residual:

Для маленької задачі матрицю \(Q\) можна показати повністю. Для великої достатньо зберегти її джерело та ключові структурні метрики.

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

Окремо варто вказувати, чи додано до цільової функції сталу частину. Вона не змінює мінімізатор, але впливає на OBJECTIVE. Якщо CVXPY і незалежний перевіряльник використовують різні константи, вектори рішень збігатимуться, а значення цілі — ні.

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

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

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

32. Підсумок

Квадратичне програмування поєднує квадратичну ціль \(\frac{1}{2}x^TQx+c^Tx\) з лінійними обмеженнями. Матриця \(Q\) визначає кривизну, тому її симетрія та власні значення задають структурний клас задачі. Додатна напіввизначеність дає опуклість, а додатна визначеність — строгу опуклість і, за наявності розв’язку, його єдиність.

У наскрізному прикладі матриця \(Q=\operatorname{diag}(2,2)\) є додатно визначеною, а оптимальний план дорівнює \((1.5,0.5)\). Початкова ціль має значення 0.5, тоді як QP-форма без відкинутої сталої дає \(-4.5\); різниця не змінює мінімізатор. KKT-баланс підтверджує оптимальність на активній межі.

CVXPY робить запис моделі компактним і близьким до математичної постановки, але незалежний аудит залишається обов’язковим. Після solve() повторно перевіряють статус, допустимість, початкову ціль, визначеність \(Q\) і KKT-нев’язки. Такий цикл «структура → розв’язання → сертифікат» переноситься на більші опуклі моделі.