Правило множителей Лагранжа для гладких нелинейных задач

Задачу нелинейного программирования вида

f₀(x) → min,f_i(x) ≤ 0, i=1,..., m; F(x) = 0. (5.6.1)

назовем гладкой, если функционалы f_i:X→R, i=0,…,m и оператор F:X→Y являются строго дифференцируемыми.

Покажем, что в случае, когда задача (5.6.1) не является выпуклой, к ее исследованию тоже можно применять правило множителей Лагранжа.

Для этого применим следующую теорему, известную как теорема Люстерника о касательном пространстве (теорему применим без рассмотрения ее доказательства).

Теорема 5.6.1. Пусть X, Y – банаховы пространства, F:X→Y, M={x∈X | F(x)=0}, x₀∈M, F строго дифференцируемо в точке x₀, причем Im(DF(x₀))=Y (условие регулярности). Тогда следующие условия эквивалентны:

а) DF(x₀)h = 0;

б) существуют ε>0 и отображение r:[-ε, ε]→X, для которых при всех α∈[-ε, ε] выполняется условие

x₀+αh+r(α)∈M, причем r(α)=o(α) при α→0.

Следствие 1. Если x₀ – решение задачи (5.6.1), то h₀=0 является решением задачи

g(h) = max _0≤i≤mDf_i(x₀)h → min,DF(x₀)h = 0. (5.6.2)

Доказательство. Предположим, что найдется h₁∈X, такой что DF(x₀)h₁=0 и при этом для всех i=0,…,m справедливы неравенства A_i = Df_i(x₀)h₁ < 0. Тогда по теореме Люстерника для вектора h₁ найдется ε>0 и отображение r:[-ε, ε]→X, такое что при всех α∈[-ε, ε] выполняется F(x₀+αh₁+r(α)) = 0, причем r(α)=o(α) при α→0.

Используя условие дифференцируемости отображений f_i, при α→+0 получим

f_i (x₀+αh₁+r(α)) = f_i (x₀)+ Df_i (x₀)(αh₁+r(α))+o(α) = f_i (x₀)+ αDf_i (x₀)h₁+o(α) =

= f_i (x₀)+ α(A_i +o(1)) < f_i (x₀) (При достаточно малых α>0).

Таким образом, при достаточно малых α > 0 вектор x_α=x₀+αh₁+r(α) удовлетворяет всем ограничениям задачи (5.6.1):

f_i (x_α) = f_i (x₀+αh₁+r(α)) < f_i (x₀) ≤ 0 при i=1,…,m;

F(x_α) = F(x₀+αh₁+r(α)) = 0,

и при этом f₀ (x_α) < f₀ (x₀) – т.е. x₀ не является решением задачи (5.6.1).

Полученное противоречие завершает доказательство следствия.

В результате получаем, что если x₀ – решение задачи (5.6.1), то

min _{DF(x0)h = 0} max _0≤i≤mDf_i(x₀)h = 0 (5.6.3)

Лемма 5.6.2. Если M – векторное пространство, A_i:M→R, i=0,…,m – линейные операторы. Следующие условия эквивалентны:

а) каждого h∈M найдется номер j, для которого A_jh ≥ 0;

б) существуют λ_i ≥ 0, i=0,…,m (не все равные нулю), такие что для всех h∈M выполняется равенство ∑_0≤i≤mλ_iA_ih = 0.

Доказательство. Не ограничивая общности, можно считать, что М – конечномерное пространство. Доказательство проведем индукцией по m. Заметим, что при всех m операторы A_i:M→R, i=0,…,m линейно зависимы, т.к. в противном случае система уравнений A_i(h) = –1, i=0,…,m имела бы решение, что противоречит условию.

m = 1. В данном случае у нас есть два линейных оператора A₀:M→R, A₁:M→R. В силу их линейной зависимости существует λ, такое что для всех h∈M выполняется равенство A₁(h) + λA₂(h) = 0 (или A₂(h) + λA₁(h) = 0). Если предположить, что λ<0, получим, что числа A₁(h) и A₂(h) всегда одного знака, что противоречит условию а). Таким образом, λ>0.

Предположим, что условие леммы справедливо при всех M и всех m<n. Докажем справедливость утверждения при m=n.

Пусть M₁= {h∈M | A_nh=0}. Тогда для каждого h∈M₁ найдется номер j<n, для которого A_jh ≥ 0. Действительно, если для всех j=0,…,n-1 выполняется A_jh ≤C< 0, то найдется h*∈M, для которого A_nh*<0 и при этом для всех φ=0,…,n-1 A_jh* <C/2< 0, т.е. не выполнено условие леммы.

Таким образом, по предположению индукции существуют не все равные нулю числа λ_i ≥ 0, i=0,…,n-1, такие что для всех h∈M₁={h∈M | A_nh=0} выполняется равенство Bh = ∑_0≤i≤n-1 λ_iA_ih = 0. В итоге получаем, что всех h∈M справедливо Bh = ∑_0≤i≤n-1 λ_iA_ih = - λ_nA_nh.

Если равенство Bh = ∑_0≤i≤n-1 λ_iA_ih = 0 выполняется на всем М, то λ_n= 0 и задача решена. Если же равенство Bh = ∑_0≤i≤n-1 λ_iA_ih = 0 не выполняется на всем М, согласно предположению индукции существует h₀∈M, для которого для всех j=0,…,n-1 A_ih₀<0 и поэтому Bh₀<0, а значит, - λ_n A_n h₀<0. Поскольку должно выполняться A_n h₀≥0, получаем λ_n>0.

Лемма доказана.

Применим доказанную лемму к результатам следствия 1. Согласно следствию 1, если x₀ – решение задачи (5.6.1), то для любого h∈{h∈X | DF(x₀)h=0} существует номер j, для которого Df_j(x₀)h≥0.

Следовательно, существуют λ_i ≥ 0, i=0,…,m (не все равные нулю), такие что для всех h∈M={h∈X | DF(x₀)h=0} выполняется равенство ∑_0≤i≤m λ_iDf_i(x₀)h = 0.

Теорема 5.5.3 (об аннуляторе ядра). Пусть X, Y – банаховы пространства, A:X→Y – линейный ограниченный оператор, такой что ImA=Y (регулярность). Тогда множество всех линейных ограниченных функционалов, равных нулю на множестве M={h∈X | Ah=0} (аннулятор ядра оператора А) совпадает с образом сопряженного оператора A*, т.е. если B:X→R и для всех h∈M={h∈X | Ah=0} выполняется равенство Bh=0, то найдется линейный ограниченный функционал y*∈Y*, такой что B = y*A.

Применив к предыдущим рассуждениям теорему об аннуляторе ядра, получаем следующий результат:

Если существуют λ_i ≥ 0, i=0,…,m (не все равные нулю), такие что для всех h∈M={h∈X | DF(x₀)h=0} выполняется равенство ∑_0≤i≤m λ_iDf_i(x₀)h = 0, то найдется линейный ограниченный функционал y*∈Y*, такой что Bh = ∑_0≤i≤m λ_iDf_i(x₀)h = y* DF(x₀)h.

Теорема 5.6.4 (Правило множителей Лагранжа). Пусть x₀ – решение гладкой задачи нелинейного программирования (5.6.1), причем X, Y – банаховы пространства, Im DF(x₀) – замкнутое подпространство в Y (полурегулярность).

Тогда существуют множители Лагранжа – числа λ_i , i=0,…,m и линейный ограниченный функционал y*∈Y*, (не все равные нулю), такие что выполняются следующие условия:

1. ∑_0≤i≤m λ_iDf_i(x₀) + y* DF(x₀) = 0; (5.6.4)

2. λ_if(x₀) = 0, i = 1,…,m; (5.6.5)

3. λ_i ≥ 0, i=0,…,m. (5.6.6)

Доказательство существования множителей Лагранжа и выполнение условий (5.6.4) и (5.6.6) получено ранее. Если x₀ – решение задачи (5.6.1) и для некоторого i выполняется строгое неравенство f_i(x₀) < 0, то в силу непрерывности функционала f_i в некоторой окрестности точки x₀ данное неравенство будет сохраняться, т.е. это неравенство не накладывает существенного ограничения в задаче, т.е. при удалении этого ограничения вектор x₀ останется решением. Этот факт можно отразить путем выбора соответствующего λ_i равным 0. Если же f_i(x₀)=0, условие (5.6.5) будет тоже выполнено.

Поиск по сайту: