Методы оптимизации. Конспект лекций (Буряков) (2003) (1125388), страница 9
Текст из файла (страница 9)
Докажем, что при использованиитакого правила мы действительно получим угловую точку.Для точки w соответствующая ей матрица B будет иметь видB(w) = (Aj1 |· · ·|Ajs−1 |Ak |Ajs+1 |· · ·|Ajr ).Нам необходимо показать, что это есть базис. Сделаем это по определению. Пустьα1 Aj1 + . .
. + αs−1 Ajs−1 + αk Ak + αs+1 Ajs+1 + . . . + αr Ajr = 0.Подставим в это равенство Ak = Bγk = γ1k Aj1 + . . . + γrk Ajr . Тогда так как B(v)есть базис, то необходимо должно выполнятьсяαi + αk γik = 0, ∀i 6= s,αk γsk = 0.Отсюда следует, что все αi равны нулю, то есть B(w) — базис.Таким образом, по Теореме 19 мы получаем, что w действительно угловая точкамножества U.Замечания.1) В случае, когда v вырождена, θk = 0 и v = w. При этом может произойти зацикливание процесса, но правила выбора k и s (правила Блэнда) позволяют избежатьэтого.2) Если угловых точек в множестве U конечное число, то остановка процесса произойдёт через конечное число шагов на случаях 1) или 2).В конце пункта сформулируем обобщающую наши рассуждения теорему.49Теорема 20 (к задаче линейного программирования).
В задаче линейного программирования выполняются следующие утверждения:1) если U 6= ∅, то в U существует по крайней мере одна угловая точка;2) если J∗ > −∞, то во множестве U∗ содержится по крайней мере одна точка.Доказательство.Доказательство этой теоремы, по сути, приводится в обосновании симплекс-метода(перебора по угловым точкам).Замечание. Утверждение 2) справедливо именно для задачи линейного программирования.
В противном случае это, вообще говоря, не верно. Например, если J(u) = e−u(это не задача линейного программирования), то U = R1 , J∗ = 0, но U∗ = ∅.6Методы снятия ограниченийВ этой главе рассматриваются задачи минимизации функционаловJ(u) → inf, u ∈ Uс учётом ограничений на множество U.Эти ограничения могут быть “терпимыми”, например, u может принадлежать не всему пространству, а какому-либо подмножеству этого пространства. Такие ограничениямы не рассматриваем и считаем, что их можно обойти простыми методами.Нас же будут интересовать более “функциональные” ограничения на u.
Рассмотримконкретный пример:u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, . . . , gm (u) 6 0, gm+1 (u) = 0, . . . , gm+s = 0},где gi какие-либо функции.Здесь интересующие нас ограничения это m ограничений типа “неравенство” и s ограничений типа “равенство” (“терпимым” ограничением является принадлежность точкиu множеству U0 ).Естественно, какие-либо из ограничений могут отсутствовать.Метод штрафовВ этом методе рассматривается задача минимизации с ограничениями следующего вида:J(u) → inf, u ∈ U = {u ∈ U0 ⊂ H | g1 (u) 6 0, .
. . , gm (u) 6 0,gm+1 (u) = 0, . . . , gm+s = 0} (1)Рассмотрим функцию (называемую штрафом или штрафной функцией):P (u) =m+sX(gi+ (u))pi ,pi > 1 (обычно pi = 2).i=150Функции gi+ (u) называют индивидуальными штрафами. В качестве конкретного примера можно взятьgi+ (u) = max{gi (u), 0}, i = 1, m,gi+ (u) = |gi (u)| , i = m + 1, m + s.Легко видеть, что условиеP (u) = 0,u ∈ U0выполняется тогда и только тогда, когда точка u принадлежит множеству U.Из штрафной функции P (u) формируются формулы видаΦk (u) = J(u) + Ak P (u),Ak > 0, Ak → ∞ при k → ∞, u ∈ U0 , k = 1, 2, .
. .(2)Теперь от задачи (1) мы переходим к последовательности задач (2). Пусть точкиuk ∈ U0 таковы, чтоΦk∗ ≡ inf Φk 6 Φk (uk ) 6 Φk∗ + εk(3)U0(их можно получить, например, методами, изложенными в предыдущей главе). Используя эту последовательность точек, сформулируем основную теорему в этом пункте.Теорема 21. Пусть H — гильбертово пространство, множество U0 слабо замкнуто;J(u), gi+ (u) слабо полунепрерывны снизу на U0 ; точкаJ0 = inf J(u)U0конечна; множествоU(δ) = {u ∈ U0 : gi+ (u) 6 δ, i = 1, m + s}ограничено в H для некоторого δ > 0; Ak → +∞, εk → +0, тогда последовательностьJ(uk ) стремится к минимуму J(u):J(uk ) → inf(J(uk ) → J∗ ),и все слабые предельные точки последовательности {uk } содержатся во множестве U∗ .Доказательство.Прежде всего докажем, что при выполнении условий теоремы последовательность ukсуществует.
Действительно, учитывая, что Ak > 0, P (u) > 0, имеем:Φk (u) = J(u) + Ak P (u) > {u ∈ U0 } > J0 > −∞,то есть формулы (3) имеют смысл (это верно, когда Φk∗ конечны).Далее, рассмотрим цепочку неравенств:J(uk ) 6 Φk (u) 6 {(3)} 6 Φk∗ + εk 6 {∀u ∈ U0 } 6 Φk (u) + εk .51Последнее неравенство верно для любого u из U0 и, в частности, для любого u измножества U. Возьмём inf по множеству U от обеих частей неравенства, тогда справабудем иметь J∗ + εk .
Отсюда, переходя к пределу и учитывая, что εk → ∞ при k → ∞,получаем:lim J(uk ) 6 lim Φk (u) 6 lim Φk∗ 6 J∗(4)k→∞k→∞k→∞Теперь рассмотрим значение Φk (u) в точке uk :Φk (uk ) = J(uk ) + Ak P (uk ) 6 {(3)} 6 Φk∗ + εk .P (uk ) 6Φk∗ + εk − J0cΦk∗ + εk − J(uk )66 {(4)} 6→ 0.AkAkAkОтсюда, учитывая, что P (u) — суммирующий штраф из неотрицательных элементовgi+ , получаем, что каждый индивидуальный штраф gi+ → 0, при k → ∞.
Таким образом,для δ из условия теоремы существует такой номер k0 (δ), что для любого номера k > k0gi+ 6 δ i = 1, m + s, то есть uk ∈ U(δ). Так как H — гильбертово пространство, тоотсюда получаем, что у последовательности {uk } существуют слабые предельные точки.Пусть теперь {ukl } такая подпоследовательность {uk }, чтоlim J(uk ) = lim J(ukl ) ∈ U(δ) ∀l > l0l→∞k→∞(5)и u0 — одна из слабых предельных точек {ukl }.Учитывая слабую полунепрерывность снизу функций J(u), gi+ (u), имеем с одной стороныJ(u0 ) 6 lim J(ukl ) 6 J∗ ,l→∞то есть J(u0 ) не превосходит минимума на допустимом множестве U; с другой стороны0 6 gi+ (u0 ) 6 lim gi+ (ukl ) = 0l→∞и (так как U0 слабо замкнуто) u0 ∈ U, то есть точка u0 принадлежит допустимомумножеству U.
Таким образом, возможна лишь ситуация J(u0 ) = J∗ , то естьlim J(ukl ) = J∗ .l→∞В силу правила выбора (5):lim J(uk ) = J∗ ,k→∞и утверждение теоремы о сходимости последовательности J(uk ) к минимуму доказано.Сходимость по аргументу можно доказать аналогично, либо опираясь на доказательство Теоремы 2.Упражнение 15 (4). Доказать, что при выполнении условий Теоремы 21 задача (1)является слабо корректно поставленной в пространстве H.52Правило множителей Лагранжа для выпуклых задачВ этом пункте рассматриваем следующую задачу минимизации:J(u) → inf,u ∈ U = {u ∈ U0 ⊂ L | g1 (u) 6 0, .
. . , gm (u) 6 0}(1)Можно рассмотреть и случай, когда есть ограничения типа “равенство”, но при этомони обязаны быть линейными (в предыдущем методе на такие ограничения также накладываются жёсткие условия в виде слабой полунепрерывности снизу, так что они “почти”линейны).Назовём задачу (1) выпуклой, если множество U0 выпукло, L представляет собойлинейное пространство, функции gi выпуклы.Построим функцию Лагранжа:L(u, λ) = λ0 J(u) +mXλi gi (u) (λ ∈ Rm+1 ).i=1Числа λi называют множителями Лагранжа.Теорема 22 (теорема Ку́на-Та́ккера).
Пусть задача (1) выпукла в указанном смысле. Тогда1) если точка u∗ является оптимальной (u∗ ∈ U∗ ), то существует набор множителей Лагранжа λ∗ 6= 0 такой, чтоi)min L(u, λ∗ ) = L(u∗ , λ∗ ) — принцип минимума;u∈U0ii)λ∗i > 0,i = 0, m — условия неотрицательности множителей Лагранжа;iii)λ∗i gi (u∗ ) = 0,i = 1, m — условия, дополняющие нежёсткости.2) если для некоторой пары (u∗ , λ∗ ) выполняются условия i)-iii) и, кроме того,u∗ ∈ U и λ∗0 6= 0, то u∗ — оптимальная точка (u∗ ∈ U∗ ).Доказательство.1) Необходимость.Условимся считать, что J(u∗ ) = J∗ = 0 (в противном случае можно рассмотреть˜функцию J(u)= J(u) − J∗ , а функция Лагранжа “не реагирует” на сдвиг на константу).Введем множествоM = {µ = (µ0 , .
. . , µm ) ∈ Rm+1 | ∃u ∈ U0 : J(u) < µ0 , gi (u) 6 µi , i = 1, m}.Множество M не пусто, так как в нем содержится (с учётом договорённости J∗ = 0),по крайней мере, весь положительный октант Rm+1(для таких µ подходящей точкой+будет u∗ ∈ U0 ).53Множество M выпукло из-за выпуклости исходных данных (условия теоремы). Этоэлементарно доказывается по определению.Также легко доказать, что с учётом договорённости точка 0 не принадлежит множеству M.По теореме отделимости (см., например, [В2, гл.
4,§5, Теорема 1]) существует ненулевой вектор λ∗ такой, чтоhλ∗ , µiRm+1 > 0 = hλ∗ , 0iRm+1∀µ ∈ M(2)(λ∗ — нормальный вектор к гиперплоскости).Докажем для начала утверждение ii). Возьмём точкуµiε = (ε, ε, . . . , 1, . . . , ε), ε > 0,где единица стоит в i-й позиции. Эта точка принадлежит множеству M (так как онанаходится в положительном октанте). Подставив её в (2) и устремив ε к нулю, получим,что λ∗i > 0 для любого i.
Таким образом, утверждение ii) доказано.Теперь докажем утверждение iii). В случае, когда gi (u∗ ) = 0, это утверждение, очевидно, верно. Рассмотрим случай, когда gi (u∗ ) < 0. Берём точкуνεi = (ε, 0, . . . , gi (u∗ ), 0, . . . , 0) ∈ M,где gi (u∗ ) стоит на i-ом месте. Подставив эту точку в (2), получим:εJ(u∗ ) + λ∗i gi (u∗ ) > 0 ∀ε > 0.Устремляя ε к нулю, имеем λ∗i gi (u∗ ) > 0.
В то же время gi (u∗ ) < 0 и по доказанномуλ∗i > 0. Отсюда получаем утверждение iii): λ∗i gi (u∗ ) = 0.Осталось доказать основное утверждение i). Для этого зафиксируем любую точку uиз множества U0 и по ней построим семейство векторов ηε = (J(u) + ε, g1 (u), . . . , gm (u))(ε > 0). Точка ηε содержится во множестве M, так как подходящим u ∈ U0 в этом случаеявляется сама точка u. Подставляем ηε в (2) и устремляем ε к нулю. Имеем:∗L(u, λ ) =λ∗0 J(u)+nXλ∗i gi (u) > 0 = {допущение, утв.ii)} =i=1=λ∗0 J(u∗ )+nXλ∗i gi (u∗ ) = L(u∗ , λ∗ ).i=1Утверждение i) доказано.2) Достаточность.Пусть точка u∗ ∈ U, λ∗0 6= 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
