Книга представляет собой введение в основные понятия, методы и ал
Метод решения оптимизационной задачи
Download 0.87 Mb.
|
machine-learning-mironov
- Bu sahifa navigatsiya:
- Доказательство.
- Лемма об отделимости.
Метод решения оптимизационной задачиВ этом пункте мы рассмотрим подход к решению общей оптимизацион- ной задачи, частным случаем которой является оптимизационная задача (2.42) при условиях (2.41). Данная общая задача имеет следующий вид: заданы → ∀ , ′ ∈ R, ∀ 𝛼 ∈ [0, 1] 𝑓 (𝛼 + (1 − 𝛼)′) ≤ 𝛼𝑓 () + (1 − 𝛼)𝑓 (′), множество условий вида 𝑔1() ≤ 0, . . . , 𝑔() ≤ 0, где 𝑔1, . . . , 𝑔 – выпуклые функции вида R → R. Обозначим записью 𝐷𝑔1,...,𝑔 множество { ∈ def
| ∀ = 1, . . . , 𝑔() ≤ 0}. (2.43) Требуется найти аргумент ˆ ∈ 𝐷𝑔1,...,𝑔 , на котором достигается мини- мальное значение функции 𝑓 , в предположении что минимальность рас- сматривается относительно множества 𝐷𝑔1,...,𝑔 , т.е. требуется, чтобы 𝑓 (ˆ) = min ∈𝐷𝑔1,...,𝑔 𝑓 (). Данную задачу можно решать с помощью теоремы Каруша-Куна- Таккера, которую называют основной теоремой выпуклой нелинейной оптимизации. Ниже мы приводим частный случай этой теоремы. Теорема 3 (W.Karush, 1942, H.Kuhn and A.Tucker, 1951). Пусть заданы выпуклые функции 𝑓 , 𝑔1, . . . , 𝑔 вида R → R, причем ∃ ∈ R : ∀ = 1, . . . , 𝑔() < 0. (2.44) Обозначим символом 𝐿 функцию (называемую функцией Лагранжа) ∑︁ 𝐿 = 𝑓 () + 𝜆𝑔(), (2.45) =1 где 𝜆1, . . . , 𝜆 – переменные, называемые множителями Лагранжа. ∀ ˆ ∈ 𝐷𝑔1,...,𝑔 следующие утверждения эквивалентны: 𝑓 (ˆ) = min ∈𝐷𝑔1,...,𝑔 𝑓 (), (2.46) ∃ 𝜆ˆ1, . . . , 𝜆ˆ ∈ R : ∀ = 1 . . . , ⎪⎩ ∀ = 1 . . . , 𝜆ˆ ≥ 0, 𝜆ˆ𝑔(ˆ) = 0, (2.47) 𝐿(ˆ, 𝜆ˆ1 . . . , 𝜆ˆ) = min 𝐿(, 𝜆ˆ1 . . . , 𝜆ˆ). ∈R Если функции 𝑓, 𝑔1, . . . , 𝑔 дифференцируемые, то функция Лагран- жа 𝐿 тоже будет дифференцируемой, и этом случае третье соотношение в (2.47) равносильно соотношению ∀ 1 = 1, . . . , 𝜕𝐿 (ˆ, 𝜆ˆ 𝜕 , . . . , 𝜆ˆ ) = 0. (2.48) Доказательство.∈ Сначала докажем, что если для точки ˆ 𝐷𝑔1,...,𝑔 верно утверждение (2.47), то для нее будет верно утверждение (2.46). Т.к. ∀ = 1, . . . , , ∀ ∈ 𝐷𝑔1,...,𝑔 𝜆ˆ𝑔() ≤ 0, то ∑︁ ∀ ∈ 𝐷𝑔1,...,𝑔 𝐿(, 𝜆ˆ1, . . . , 𝜆ˆ) = 𝑓 () + 𝜆ˆ𝑔() ≤ 𝑓 (). (2.49) =1 Из второго соотношения в (2.47) следует, что 𝐿(ˆ, 𝜆ˆ1, . . . , 𝜆ˆ) = 𝑓 (ˆ) + ∑︁ 𝜆ˆ𝑔(ˆ) = 𝑓 (ˆ) + ∑︁ 0 = 𝑓 (ˆ). (2.50) Из третьего соотношения в (2.47) следует, что ∀ ∈ R 𝐿(ˆ, 𝜆ˆ1, . . . , 𝜆ˆ) ≤ 𝐿(, 𝜆ˆ1, . . . , 𝜆ˆ). (2.51) Из (2.49) (2.50) и (2.51) следует, что для ˆ верно (2.46): ∀ ∈ 𝐷𝑔1,...,𝑔 𝑓 (ˆ) = 𝐿(ˆ, 𝜆ˆ1, . . . , 𝜆ˆ) ≤ 𝐿(, 𝜆ˆ1, . . . , 𝜆ˆ) ≤ 𝑓 (). ∈ Теперь докажем, что если для точки ˆ 𝐷𝑔1,...,𝑔 верно утверждение (2.46), то для нее будет верно утверждение (2.47). {︂ Обозначим символом Λ множество всех векторов (𝜆0, . . . , 𝜆) ∈ R+1, каждый из которых удовлетворяет следующему условию: ∃ ∈ R: 𝜆0 > 𝑓 () − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆 ≥ 𝑔(). Очевидно что множество Λ непусто. {︂ Нулевой вектор ¯0 = (0, . . . , 0) не входит в Λ, т.к. иначе ∃ ∈ R: 0 > 𝑓 () − 𝑓 (ˆ) (⇒ 𝑓 () < 𝑓 (ˆ)), ∀ = 1, . . . , 0 ≥ 𝑔() (⇒ ∈ 𝐷𝑔1,...,𝑔 ), т.е. min ∈𝐷𝑔1,...,𝑔 𝑓 () < 𝑓 (ˆ), что противоречит предположению (2.46). 𝜆(𝛼) def Докажем, что множество Λ выпукло, т.е. ∀ 𝜆, 𝜆′ ∈ Λ, ∀ 𝛼 ∈ [0, 1] = 𝛼𝜆 + (1 − 𝛼)𝜆′ ∈ Λ. (2.52) Действительно, если 𝜆 и 𝜆′ имеют вид (𝜆0, . . . , 𝜆) и (𝜆′0, . . . , 𝜆′) соответ- ственно, и вектора , ′ таковы, что 𝜆0 > 𝑓 () − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆 ≥ 𝑔() 𝜆′0 > 𝑓 (′) − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆′ ≥ 𝑔(′) то нетрудно проверить (используя выпуклость 𝑓 , 𝑔1, . . ., 𝑔), что вектор = (𝛼) def 𝛼 + (1 − 𝛼)′ обладает свойством 0 (2.53) {︃ 𝜆(𝛼) > 𝑓 ((𝛼)) − 𝑓 (ˆ), ∀ = 1, . . . , 𝜆 ≥ 𝑔((𝛼)). Распишем (2.53) во всех деталях: ⎪⎧ 𝜆(𝛼) = 𝛼𝜆0 + (1 − 𝛼)𝜆′ > 0 0 ⎨ > 𝛼𝑓 () − 𝛼𝑓 (ˆ) + (1 − 𝛼)𝑓 ( ) − (1 − 𝛼)𝑓 (ˆ) ≥ ≥ 𝑓 (𝛼 + (1 − 𝛼)′) − 𝑓 (ˆ) = 𝑓 ((𝛼)) − 𝑓 (ˆ), ⎪ ∀ = 1, . . . , 𝜆(𝛼) = 𝛼𝜆 + (1 − 𝛼)𝜆′ ≥ ⎪ ′ ≥ 𝛼𝑔() + (1 − 𝛼)𝑔( ) ≥ 𝑔(𝛼 + (1 − 𝛼) ) = 𝑔( Таким образом, (2.52) верно. ). ⎩ ′ ′ (𝛼) Лемма об отделимости.Множество Λ обладает свойством отделимости: ∃ 𝜆* ∈ R+1: 𝜆* ̸= ¯0, ∀ 𝜆 ∈ Λ ⟨𝜆*, 𝜆⟩ ≥ 0 (2.54) (т.е. Λ содержится в одном из полупространств, на которые де- лит пространство R+1 гиперплоскость, определяемая уравнением ⟨𝜆*, ⟩ = 0). Доказательство.Если размерность 𝐿(Λ) линейной оболочки множества Λ (т.е. ми- нимального линейного подпространства пространства R+1, содер- жащего Λ) меньше чем + 1, то в качестве искомого вектора 𝜆* можно взять любой ненулевой вектор из ортогонального дополне- ния 𝐿(Λ). В этом случае (2.54) верно по причине того, что ∀ 𝜆 ∈ Λ ⟨𝜆*, 𝜆⟩ = 0. Пусть размерность 𝐿(Λ) равна + 1. В этом случае Λ содержит линейно независимое множество из +1 векторов. Обозначим век- торы, входящие в это множество, записями 1, . . . , +1. Λ = Определим ⃗ def {𝜉𝜆 | 𝜉 > 0, 𝜆 ∈ Λ}. Отметим, что Λ ⊆ Λ⃗ , и ¯0 ̸∈ Λ⃗ . Множество Λ⃗ выпуклое, т.к. ∀ 𝜉, 𝜉′ > 0, ∀ 𝜆, 𝜆′ ∈ Λ⃗ , ∀ 𝛼 ∈ [0, 1] 𝛼(𝜉𝜆) + (1 − 𝛼)(𝜉′𝜆′) ∈ Λ⃗ . (2.55) Действительно, вектор в (2.55) равен 𝜉′′𝜆′′, где 𝜉′′ = 𝛼𝜉 + (1 − 𝛼)𝜉′ > 0, и 𝜆′′ = 𝛼𝜉 𝜆 + (1−𝛼)𝜉′ 𝜆′ ∈ [𝜆, 𝜆′], поэтому 𝜆′′ ∈ Λ. 𝜉′′ Докажем, что 𝜉′′ ∑︀
= =1 – внутренняя точка Λ⃗ , т.е. ∃ 𝜀 > 0: 𝜀–окре- =
Обозначим символом 𝑉 множество, состоящее из всех векторов ви- = ∈ { ∈ | | | } единичной сферы 𝑆 def R+1 = 1 обозначим записью 𝜀 максимальное число, такое, что 𝜀 𝑉 (такое число существует, т.к. множество 𝑉 является ограниченным). Поскольку единичная ↦→ сфера в R+1 – компакт, то непрерывная функция 𝜀 на 𝑆 достигает наименьшего значения 𝜀 > 0 на некотором элементе 𝑆. 0 Итак, ∀ ∈ 𝑆 𝜀 ∈ 𝑉 , откуда следует, что 𝑈¯𝜀 ⊆ 𝑉 , поэтому 𝜀 𝜀 ∑︀+1 1 3 ⃗ −
0 𝑈 = + 𝑈¯0 ⊆ + 𝑉 = { 𝛼 | 2 ≤ 𝛼 ≤ 2 } ⊆ Λ. Следовательно, каждый элемент 𝑈 𝜀 = −+𝑈¯𝜀 не лежит в Λ⃗ (иначе − некоторый отрезок из Λ⃗ с концами в 𝑈 𝜀 и 𝑈 𝜀 содержал бы ¯0). Обозначим записью Λ⃗ 𝑐 замыкание множества Λ⃗ , т.е. множество, получаемое добавлением к Λ⃗ всех его предельных точек. Нетрудно доказать, что замыкание любого выпуклого множества является выпуклым множеством. В частности, множество Λ⃗ 𝑐 выпукло. − Поскольку 𝑈 𝜀 ∩ Λ⃗ = ∅, то − не является предельной точкой мно- жества Λ⃗ , поэтому − ̸∈ Λ⃗ 𝑐. Определим 0 как такой вектор, из Λ⃗ 𝑐, что 𝜌(−, 0) = min{𝜌(−, ) | ∈ Λ⃗ 𝑐}. где 𝜌 – евклидово расстояние между векторами. Такой вектор су- ществует. Действительно, обозначим символом 𝑅 расстояние от − до какого-либо элемента Λ⃗ 𝑐, и − записью 𝐵𝑅 замкнутый шар с центром в − радиуса 𝑅. −
− жество Λ⃗ 𝑐 ∩ 𝐵𝑅 тоже замкнуто и ограничено, т.е. оно компактно. Нетрудно видеть, что − min{𝜌(−, ) | ∈ Λ⃗ 𝑐} = min{𝜌(−, ) | ∈ Λ⃗ 𝑐 ∩ 𝐵𝑅 }. Существование точки 0, на которой функция ↦→ 𝜌(−, ) на − компактном множестве Λ⃗ 𝑐 ∩ 𝐵𝑅 принимает наименьшее значение, обосновывается теми же методами, которыми обосновывается ана- логичное утверждение в теореме из параграфа 2.1. − Также аналогичными методами обосновывается следующее утвер- ждение: гиперплоскость 𝑃 , проходящая через точку 0 и ортого- нальная отрезку [ , 0], делит пространство R+1 на два полу- пространства, одно из которых (обозначим его 𝐿) имеет вид 2 𝐿 = { ∈ R+1 | = 0 или −^0 ≥ 𝜋 } и Λ⃗ 𝑐 ⊆ 𝐿. Докажем, что ¯0 ∈ 𝑃 . Пусть ¯0 ̸∈ 𝑃 . Тогда ¯0 ≠ 0 ∈ 𝑃 . Т.к. ¯0 ∈ Λ⃗ 𝑐 (0¯ 2 = 2 – предельная точка Λ⃗ ), то −^0¯0 ≥ 𝜋 . Поскольку 1 def 0 ∈ Λ⃗ 𝑐, то 2 2 −^01 ≥ 𝜋 . Однако углы (−00¯) и (−01) являются смежными, сумма их величин равна 𝜋, что возможно только если −^0¯0 = 𝜋 , поэтому ¯0 ∈ 𝑃 . — − − Вектор, определяемый отрезком [ , 0], т.е. 0 ( ) = 0 + , ортогонален 𝑃 и принадлежит 𝐿, поэтому 𝐿 = { ∈ R+1 | ⟨0 + , ⟩ ≥ 0} и в качестве искомого вектора 𝜆* можно взять 0 + . Продолжим доказательство теоремы Каруша-Куна-Таккера. Пусть вектор 𝜆*, обладающий свойством (2.54), имеет вид (𝜆*0, . . . , 𝜆*). 1. Докажем, что ∀ = 0, . . . , 𝜆* ≥ 0. Поскольку Λ содержит вектора 𝜆(0) = (1, 0, . . . , 0) и 𝜆() = (𝜀, 0 . . . , 0, 1, 0, . . . , 0) (∀ = 1, . . . , ) где 𝜀 > 0, и единица в 𝜆() стоит в позиции номер (мы считаем, что первая позиция в 𝜆() имеет номер 0), то из (2.54) следует, что ⟨𝜆*, 𝜆(0)⟩ = 𝜆*0 ≥ 0 ∀ = 1, . . . , ⟨𝜆*, 𝜆()⟩ = 𝜆*0𝜀 + 𝜆* ≥ 0 откуда, ввиду произвольности 𝜀, заключаем, что 𝜆* ≥ 0. Докажем, что ∀ ∈ {1, . . . , } 𝜆* 𝑔(ˆ) = 0. (2.56) Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор 𝜆 def = (𝜀, 0, . . . , 0, 𝑔(ˆ), 0, . . . , 0), то из (2.54) следует, что ⟨𝜆*, 𝜆⟩ = 𝜆0*𝜀 + 𝜆*𝑔(ˆ) ≥ 0, откуда, ввиду произвольности 𝜀, заключаем, что 𝜆*𝑔(ˆ) ≥ 0. Таким образом, либо 𝜆*𝑔(ˆ) = 0, либо 𝜆* 𝑔(ˆ) > 0. Однако если бы было верно неравенство 𝜆*𝑔(ˆ) > 0, то, учитывая доказанное в предыдущем пункте неравенство 𝜆* ≥ 0, заключаем, что 𝑔(ˆ) > 0, что противоречит условию 𝑔(ˆ) ≤ 0. Докажем, что ∀ ∈ R 𝜆*0𝑓 (ˆ) + ∑︁ 𝜆* 𝑔(ˆ) ≤ 𝜆0*𝑓 () + ∑︁ 𝜆* 𝑔(). (2.57) Из (2.56) следует, что левая часть (2.57) равна 𝜆*0𝑓 (ˆ). Т.к. ∀ 𝜀 > 0 множество Λ содержит вектор 𝜆 def = (𝑓 () − 𝑓 (ˆ) + 𝜀, 𝑔1(), . . . , 𝑔()), то из (2.54) следует, что ∑︁ ⟨𝜆*, 𝜆⟩ = 𝜆0*(𝑓 () − 𝑓 (ˆ) + 𝜀) + 𝜆*𝑔() ≥ 0, =1 откуда, ввиду произвольности 𝜀, следует (2.57). Докажем, что 𝜆*0 0. Если 𝜆*0 = 0, то из 𝜆* ̸= ¯0 следует, что ∃ ∈ {1, . . . , } : 𝜆* > 0. ∈ По предположению, для некоторого R выполнено условие (2.44). Для этого верно также (2.57), однако в данном случае левая часть (2.57) равна 0, а правая часть (2.57) меньше 0, что невозможно. Искомые значения 𝜆ˆ , . . . , 𝜆ˆ определяются как 𝜆*1 , . . . , 𝜆* . 1 𝜆*0 𝜆*0 Истинность каждого из трех соотношений в (2.47) следует из соот- ветствующих пунктов изложенного выше рассуждения. Докажем, что если функции 𝑓, 𝑔1, . . . , 𝑔 дифференцируемые, то тре- тье соотношение в (2.47) равносильно соотношению (2.48), т.е. 𝐿(ˆ, 𝜆ˆ) = min 𝐿(, 𝜆ˆ) ⇔ ∀ = 1, . . . , 𝜕𝐿 (ˆ, 𝜆ˆ) = 0, (2.58) ∈R где 𝜆ˆ = (𝜆ˆ1 . . . , 𝜆ˆ). 𝜕 ⇒ Импликация « » в (2.58) верна потому, что ее правая часть является необходимым условием минимума дифференцируемой функции. Обоснуем импликацию «⇐» в (2.58). Из выпуклости 𝑓, 𝑔1, . . . , 𝑔 и неотрицательности 𝜆ˆ1, . . ., 𝜆ˆ следует выпуклость функции ↦→ 𝐿(, 𝜆ˆ): ∀ , ′ ∈ R, ∀ 𝛼 ∈ [0, 1] 𝐿(𝛼 + (1 − 𝛼)′, 𝜆ˆ) = = 𝑓 (𝛼 + (1 − 𝛼) ) + 𝜆𝑔(𝛼 + (1 − 𝛼) ) ≤ ≤ 𝛼𝑓 () + (1 − 𝛼)𝑓 ( ) + 𝜆(𝛼𝑔() + (1 − 𝛼)𝑔( )) = =1 ′ ∑︀ ˆ ′ ′ ∑︀ ˆ ′ = 𝛼𝐿(, 𝜆ˆ) + (1 − 𝛼)𝐿(′, 𝜆ˆ), откуда на основании такого же рассуждения, которое приведено в конце пункта 2.3.2, следует, что значение аргумента ˆ, удовлетворяющее пра- вой части (2.58), является глобальным минимумом этой функции. Download 0.87 Mb. Do'stlaringiz bilan baham: 
|