Математика / Численная оптимизация

Квадратичный штраф за нарушение равенства

Квадратичный штраф заменяет равенство h(x)=0 добавкой mu h(x)^2/2 к цели. При конечном mu минимум штрафовой функции обычно остаётся немного недопустимым, поэтому метод использует последовательность растущих параметров.

Опубликовано: 3 ноября 2026 г.Обновлено: 3 ноября 2026 г.

Оптимизация и исследование операций Страницы с задачами и решениями Есть историческая справка Диагностика условий

Формула

\Phi_\mu(x)=f(x)+\frac{\mu}{2}h(x)^2

Схема Квадратичный штраф при μ=10

Допустимая точка x=1 имеет Φ=4; минимум штрафной функции при x=4/3 даёт 10/3.

Обозначения

$x$: переменная оптимизации, единицы модели
$f(x)$: исходная целевая функция, единицы цели
$h(x), mu$: скалярное нарушение равенства и положительный штрафной параметр, mu согласует единицы f и h²

Условия применения

Запись относится к одному гладкому равенству h(x)=0 и mu>0. Для системы равенств h:R^n→R^m используют Phi_mu(x)=f(x)+(mu/2)||h(x)||_2². Практический метод строит возрастающую последовательность mu_k и достаточно точно минимизирует каждую Phi_mu_k; для теоретического перехода к ограниченной задаче нужны обычные условия гладкости и регулярности ограничения.

Ограничения

Конечное mu обычно не обеспечивает h(x)=0 точно: его увеличение уменьшает нарушение, но ухудшает обусловленность внутренней задачи. Квадратичный штраф не является барьером для строгого неравенства и не заменяет проверку допустимости. Нельзя сравнивать значения Phi для задач с разными единицами или параметрами mu без интерпретации масштаба.

Подробное объяснение

Штраф добавляет цену за отклонение от равенства. Квадрат симметричен: h=0.1 и h=−0.1 дают одинаковую добавку, а в допустимой точке она исчезает. Благодаря квадрату Phi остаётся гладкой, если f и h гладкие.

Параметр mu управляет компромиссом. Малый mu позволяет существенно улучшить f ценой нарушения ограничения; большой mu сильнее приближает допустимость, но создаёт разные масштабы кривизны и усложняет численную минимизацию.

В примере f=(x−3)², h=x−1, mu=10 точка x=1 допустима и даёт Phi=4. Однако стационарная точка штрафовой функции равна x=4/3 и даёт Phi=10/3, то есть при конечном mu глобальный минимум Phi остаётся вне h=0.

Поэтому квадратный штраф — не правило «взять очень большое число», а последовательный метод. Для уменьшения проблем обусловленности часто переходят к дополненному лагранжиану, который использует и штраф, и множитель. В векторной задаче это различие особенно важно: длина h должна измеряться согласованной нормой, иначе отдельные ограничения получают неявно несопоставимые веса.

Как пользоваться формулой

Запишите исходные f(x) и равенство h(x)=0, указав единицы и допустимую точность.
Выберите начальное mu>0 и сформируйте Phi_mu=f+(mu/2)h², сохранив множитель 1/2 в градиенте.
Минимизируйте Phi_mu без ограничений и отдельно вычислите нарушение |h(x)|.
Если нарушение велико, увеличьте mu и используйте решение предыдущего шага как старт.
Остановитесь по норме h и критерию внутренней минимизации; при плохой обусловленности рассмотрите дополненный лагранжиан.

Историческая справка

Штрафные методы получили систематическое развитие вместе с численной нелинейной оптимизацией в середине XX века. Идея заменить ограничение последовательностью безусловных задач позволила использовать методы гладкой минимизации, но выявила проблему роста обусловленности. Книга Фиакко и Маккормика 1968 года закрепила последовательную безусловную минимизацию как важную линию нелинейного программирования; позднее дополненные лагранжианы смягчили недостаток чистого квадратичного штрафа. Этот исторический переход важен для понимания формулы: квадратный штраф был ценен не как однократная большая константа, а как управляемая последовательность задач. Развитие теории показало, что для практической точной допустимости одних растущих штрафов часто недостаточно выгодно, поскольку внутренние минимизации становятся плохо масштабированными. Поэтому современные решатели обычно сочетают штрафы с множителями Лагранжа и контролем ограничений.

Историческая линия формулы

Квадратичный штраф не принадлежит одному автору: это общая техника развития нелинейного программирования. Фиакко и Маккормик важны для систематического изложения последовательных безусловных методов, но не являются единственными авторами идеи.

Пример

Для f(x)=(x−3)², h(x)=x−1, μ=10 и x=2 имеем Φ=1+5·1=6. В допустимой точке x=1 получаем Φ=4, потому что штраф равен нулю. В x=2 исходная цель равна (−1)²=1, а h(2)=1; коэффициент μ/2=5 даёт штраф 5 и сумму 6. В x=1 h=0, поэтому сравнивается только f(1)=4. Среди этих двух точек допустимая имеет меньшую Φ. Но минимум по всем x достигается при 2(x−3)+10(x−1)=0, то есть x=4/3: Φ=10/3<4, и точная допустимость при конечном μ не обеспечена. Штрафовая функция добавляет квадрат нарушения h(x). В допустимой точке добавка равна нулю, а при удалении от ограничения растёт симметрично по обе стороны; знак нарушения не важен для его стоимости.

Частая ошибка

Не утверждайте, что конечный mu даёт точную допустимость. Не теряйте множитель 1/2: он меняет градиент. Не применяйте скалярную h² к вектору без нормы. Не выбирайте огромный mu без контроля обусловленности. Не прекращайте внешний цикл, пока нарушение h не проверено отдельно от Phi.

Практика

Задачи с решением

Штраф за малое нарушение равенства

Условие. Для h(x)=x−1, x=1,2 и μ=8 найдите штраф.

Решение. h(1,2)=0,2; (μ/2)h²=4·0,04=0,16.

Ответ. Штрафовая добавка 0,16.

Симметрия штрафа по знаку нарушения

Условие. Для h(x)=x−1, x=0 и μ=8 найдите штраф.

Решение. h(0)=−1; (8/2)(−1)²=4.

Ответ. Штрафовая добавка 4.

Дополнительные источники

https://web.stanford.edu/~boyd/cvxbook/
https://wiki.math.ntnu.no/_media/tma4180/2022v/lecture19.pdf
https://ocw.mit.edu/courses/ids-338j-multidisciplinary-system-design-optimization-spring-2010/3745f01dbdd2a70f9c3867d945f431d7_MITESD_77S10_lec08.pdf

Связанные формулы

Математика

Метод золотого сечения: сужение интервала минимума

$\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0$

Золотое сечение находит минимум унимодальной функции без производных. Два внутренних значения позволяют отбросить часть интервала, а удачное отношение длин сохраняет одно вычисление для следующего шага.

Математика

Метод бисекции: корень и гарантированная точность

$c=\frac{a+b}{2},\qquad |c-r|\leq\frac{b-a}{2}$

Метод бисекции ищет корень непрерывной функции делением отрезка пополам. Разные знаки на концах дают гарантию существования корня, а длина отрезка — оценку ошибки.

Математика

Оценка ошибки пары Дормана—Принса 5(4)

$err=\left\|y_{n+1}^{(5)}-y_{n+1}^{(4)}\right\|$

Встроенная пара Дормана—Принса 5(4) из общих стадий даёт два приближения решения ОДУ. Норма их разности оценивает локальную ошибку и позволяет принять шаг или повторить расчёт с меньшим h.

Математика

Пятиточечный шаблон Лапласа на квадратной сетке

$\Delta_hu_{i,j}=\frac{u_{i+1,j}+u_{i-1,j}+u_{i,j+1}+u_{i,j-1}-4u_{i,j}}{h^2}$

Пятиточечный шаблон приближает оператор Лапласа в внутреннем узле равномерной квадратной сетки. Он складывает центральные разности по двум направлениям и имеет погрешность порядка O(h²) для гладкой функции.

Математика

Степенной метод: приближение доминирующего собственного значения

$x_{k+1}=\frac{Ax_k}{\|Ax_k\|},\quad\lambda_k=\frac{x_k^TAx_k}{x_k^Tx_k}$

Степенной метод многократно умножает стартовый вектор на матрицу, поэтому компоненту по простому собственному вектору с наибольшим модулем усиливает быстрее остальных. Нормировка сохраняет направление и предотвращает переполнение.

Математика

Круги Гершгорина: локализация собственных значений матрицы

$|\lambda-a_{ii}|\le\sum_{j\ne i}|a_{ij}|$

Теорема Гершгорина заключает все собственные значения квадратной комплексной матрицы в объединение дисков: центр каждого диска — диагональный элемент строки, радиус — сумма модулей остальных элементов этой строки.