12. Постановка задачи. Теорема Куна – Таккера.

Задачами оптимизации (экстремальными задачами) будем называть задачи следующего вида:

Задано векторное пространство X, функционал f: X→R∪{+∞} и подмножество M⊆X. Требуется найти минимальное значение функционала f на множестве M.

При этом f называется целевым функционалом, множество X – основным пространством задачи, множество M задает ограничения задачи, его элементы называются допустимыми для задачи.

Заметим сразу, что нахождение минимального значения функционала f на множестве M равносильно нахождению минимального значения функционала g(x) = f(x)+ c_M(x) всем векторном пространстве X, где c_M – индикаторная функция множества ограничений М (Убедитесь в этом!). Таким образом, любую задачу оптимизации можно записать как задачу без ограничений.

С другой стороны, иногда бывает проще исследовать задачу методами анализа, если функционал f не принимает значение +∞, пусть даже при наличии ограничений.

Определение. Задачу оптимизации называют выпуклой, если целевой функционал f и ограничения M являются выпуклыми (соответственно, как функция и как множество).

В данном пункте мы увидим, что понятие выпуклости играет важную роль в исследовании задач оптимизации.

Теорема 4.2.1 (Кун, Таккер). Пусть X – векторное пространство, f_i:X→R∪{+∞}, i=0,…,m – некоторые функционалы, A⊆X. Предположим, что множество

B={(b₀, b₁,…,b_m)∈R^m+1| ∃x∈A: ∀i=0,..,m  f_i(x)≤b_i} –

непустое и выпуклое. Тогда

1) Если x* – решение задачи 

f₀(x) → min ,f_i(x) ≤ 0, i=1,..., m; ,x ∈ A  (4.2.1)

то найдется ненулевой вектор множителей Лагранжа λ*=(λ₀*,…,λ_m*)∈R^m+1, такой что для функции Лагранжа L(x,λ)= выполняются следующие условия:

а) принцип минимума для функции Лагранжа:   min_x∈A L(x,λ*)= L(x*,λ*);     (4.2.2)

б) условие дополняющей нежесткости:   λ_i*f_i(x*) = 0, i=1,…,m;     (4.2.3)

в) условие неотрицательности: λ_i* ≥  0,i=0,…,m;    (4.2.4)

2) Если λ₀* >  0, то условия (4.2.2) - (4.2.4) достаточны для того, чтобы допустимая точка x* была решением задачи (4.2.1).

3) Для λ₀* >  0  достаточно выполнения условия Слейтера:

∃x₁∈A: ∀i=1,…,m   f_i(x₁) < 0 (4.2.5)

Доказательство.

1. А) Пусть x* - решение задачи (4.2.1). Без ограничения общности будем считать, что f₀(x*)=0 (заменим f₀(x) на f₀(x) - f₀(x*)).

Б) Пусть C = {(c₀, 0,…,0)∈R^m+1| c₀ < 0}. Множество C – непустое и выпуклое. Покажем, что B∩C=Ø.

Предположим, что (c₀, 0,…,0) ∈ B∩C, т.е. c₀ < 0 и ∃x∈A: f₀(x)≤с₀ и ∀i=1,..,m  f_i(x)≤0. Тогда x является допустимым для задачи и при этом  f₀(x) ≤ с₀ < 0 = f₀(x*), т.е. x* не является решением задачи (4.2.1).

Противоречие доказывает, что B∩C=Ø.

В) Поскольку множества B и C – непустые и выпуклые, к тому же B∩C=Ø, по теореме об отделимости выпуклых множеств 4.1.8 получаем, что существует ненулевой вектор λ*=(λ₀*,…,λ_m*)∈R^m+1, для которого справедливо неравенство

inf_b∈B < λ*,b> ≥ sup_c∈C<λ*, c > = sup_c0<0 λ*₀ c₀.      (4.2.6)

Поскольку 0∈B (Проверьте!), из (4.2.6) получаем 0 ≥ sup_c0<0 λ*₀ c₀, откуда, с одной стороны,  λ₀*≥ 0, а с другой  sup_c0<0 λ*₀ c₀=0. Таким образом, для всех b∈B выполняется условие

∑_0≤i≤m λ*_i b_i≥ 0.           (4.2.7)

Г) Для каждого j=0,…,m вектор ε_j=(0,…,1,…,0) (1 на j+1-м месте) входит в множество B, поэтому его можно подставить в (4.2.7), из чего получаем условие неотрицательности (4.2.4).

Д) Зафиксируем i. Если f_i(x*) = 0, то λ_i*f_i(x*)=0. Предположим, что f_i(x*) ≠ 0, т.е. f_i(x*) < 0. Тогда вектор b=(0,…, f_i(x*),…,0) ∈B. Подставляя его в (4.2.7), получаем неравенство λ_i*f_i(x*)≥ 0. Однако с учетом того, что f_i(x*) < 0, λ_i*≥ 0, получаем, что λ_i*= 0, а значит, снова λ_i*f_i(x*)=0.

Условие дополняющей нежесткости (4.2.3) доказано.

Е) Пусть x∈A. Тогда вектор b=( f₀(x),…, f_i(x),…, f_m(x)) ∈B. Подставляя его в (4.2.7), получаем:

∑_0≤i≤m λ*_i f _i(x)= L(x,λ*) ≥ 0.

С учетом условия дополняющей нежесткости получаем, что

L(x*,λ*)=∑_0≤i≤m λ*_i f _i(x*) =0.

Следовательно, для всех x∈A выполняется неравенство L(x,λ*) ≥ 0 = L(x*,λ*), которое означает выполнение принципа минимума (4.2.2).

Докажем утверждение 2.

Пусть выполняются условия (4.2.2) – (4.2.4) и λ₀* >  0. Поскольку главное в векторе λ*– его направление, а не длина, можно считать, что λ₀*=1.

Для любого допустимого x (т.е. удовлетворяющего всем ограничениям задачи (4.2.1) получаем:

f₀(x) ≥ f₀(x) +∑_1≤i≤m λ*_i f _i(x) = L(x,λ*) ≥  L(x*,λ*) = f₀(x*) + ∑_1≤i≤m λ*_i f _i(x*)= f₀(x*).

Докажем утверждение 3. Предположим, что выполнено условие Слейтера, но λ₀* = 0. Тогда с одной стороны, в силу принципа минимума  L(x₁,λ*) ≥ L(x*,λ*).

С другой стороны, в силу условия Слейтера (4.2.5) ∀i=1,…,m   f_i(x₁) < 0, а из (4.2.4) λ_i* ≥ 0, i=0,…,m. Получаем, что L(x₁,λ*)= ∑_1≤i≤m λ*_i f _i(x₁) < 0 = L(x*,λ*).

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

Замечание. Если f_i(x), i=0,…,m – выпуклые функционалы, и множество A – выпуклое, то множество B из условия теоремы Куна-Таккера тоже будет выпуклым. Поэтому теорема Куна-Таккера применима ко всем выпуклым задачам.

Определение. Пусть F=F(x,λ) – функция двух переменных, определенная для всех x∈Q⊆X  и всех λ∈M⊆R^m+1. Точка (x*,λ*), x*∈Q, λ*∈M называется седловой для функции F, если для всех x∈Q и всех λ∈M,  выполняется неравенство:

F(x*, λ) ≤ F(x*, λ*) ≤ F(x, λ*).

С помощью понятия седловой точки можно сформулировать теорему Куна-Таккера следующим образом.

Теорема 4.2.2. Рассмотрим выпуклую задачу (4.2.1), для которой выполнено условие Слейтера (4.2.5).

1) Если x*- допустимый вектор, λ*≥0 (λ*₀=1) и (x*,λ*) – седловая точка для функции Лагранжа L(x,λ)=  на множестве допустимых векторов x и λ≥0 (λ₀=1), то x*- решение задачи (4.2.1).

2) Пусть x*- решение задачи (4.2.1). Тогда найдется вектор λ*≥0, такой что пара (x*,λ*) – седловая точка для функции Лагранжа L(x,λ) на множестве допустимых векторов x и λ≥0 (λ₀=1).

Кроме этого, в обоих случаях выполняются условия дополняющей нежесткости (4.2.3).