8.5. УЧЕТ ОГРАНИЧЕНИЙ В ВИДЕ НЕРАВЕНСТВ


Обзор формул условной оптимизации предваряет исследование задач программного управления с ограничениями на управление.

1. Смысл множителей Лагранжа. Рассмотрим задачу на условный экстремум функции

y = f(x) → extr, g(x) = b,


ограничения на значения вектора x заданы системой уравнений, записанных справа.

Составляем функцию Лагранжа

L(x, λ) = f(x) + (g(x)–b)Tλ,


необходимые условия экстремума имеют вид

δL/δx = δfx + (δgTx)λ = 0; δL/δλ = g(x) – b = 0.


Выясним влияние правых частей b на величину экстремума

dL/db = (δxTb) (δ(f+gTλ)/δx – λ = –λ.


Приходим к выводу, что множители Лагранжа отражают влияние элементов вектора b на величину условного экстремума. Для положительных элементов λ, например, увеличение соответствующих компонент в b приводит к уменьшению величины экстремума: dL = –λdb.

2. Ограничения вида односторонних неравенств.

Постановка задачи

y = f(x) → extr, g(x) ≤ b,


ограничения на значения вектора x заданы системой неравенств.

Предположим, что в точке условного экстремума часть неравенств переходит в равенства, отсортируем g(x), b и λ так, чтобы вторые компоненты отражали строгие равенства g = (g1T g2T)T, b = (b1T b2T)T, λ = (λ1T λ2T)T.

Как и прежде, функция Лагранжа в точке экстремума должна быть равна f(x), следовательно в ней (g(x)–b)Tλ = 0. Это означает, что если имеет место неравенство g1(x) < b1, то λ1 = 0.

Для остальных компонент, наоборот, g2(x) – b2 = 0 и λ2 = – dL /db2.

Все это вместе можно записать короче

δL/δx = δf/δx + (δgTx)λ = 0; δL/δλ ≤ 0, но (δL/δλii = 0 для каждого i.


2. Ограничения вида двусторонних неравенств.

Постановка задачи

y = f(x) → extr, a ≤ g(x) ≤ b,


ограничения на значения вектора x заданы двусторонними неравенствами.

Функция Лагранжа расширяется

L(x,η,μ) = f(x) + (g(x)–a)Tη + (g(x)–b)Tμ.


Так как в точке экстремума пребывание и на левой и на правой границе неравенства исключается, соответственные компоненты множителей η и μ никогда не бывают равными нулю одновременно. Вместо двух составляющих можно применить комбинированный множитель λ = η + μ.

Знаковые условия разнообразятся, но не более того, точка, подозрительная на условный экстремум, удовлетворяет зависимостям

δL/δx = δf/δx + (δgTx)λ = 0; δL/δη ≤ 0, δL/δμ ≥ 0, δL/δηi = (δL/δμii = 0.


Условия соблюдения знаковой политики можно объединить в одно

(δL/δη) (δL/δμ) ≤ 0.


На границах левые или правые множители Лагранжа отличны от нуля и соответствуют частным производным функции L по элементам вектора a или b, внутри разрешимой зоны они нулевые, соответственно, компоненты λ играют роль то левого, то правого отличного от нуля множителя.

Rambler's Top100