Курс лекци Русакова по методам оптимизации (1083216), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

определение I(x*)).Тогда g i ( x * +ε S ) < 0 (см.(1) и (*)).Если i ∉ I (x*) , то g i ( x*) < 0 . Отсюда gi ( x * +ε S ) < 0 (ε- достаточномало).Таким образом, при достаточно малых ε, точка x* + εS- допустима,кроме этого функция f на этом луче убывает. Таким образом? точка x* неявляется экстремальной. Для экстремальной точки x* система неравенств (*)- несовместна.Лемма Фаркаша:Для любой m × n-матрицы А справедливо ровно одно из следующихдвух условий:1)либо ∃x ∈ R n , Ax < 01002)либо ∃λ ∈ R n , AT λ = 0, λ i ≥ 0,i = 1, mБез доказательства.Теорема Каруша-Джона:Пустьx*—экстремальнаяточказадачинелинейногопрограммирования.Пусть в точке x* градиенты функций, соответствующие активнымограничениям, линейно-независимы, тогда существуют λ1,...,λm ≥0 (не всенулевые), для которых выполняются следующее условия:m∇f(x*)+∑ λ i ∇gi ( x*) = 0- условие дополняющей нежесткости.i =1 λ g ( x*) = 0,i = 1, m i iДоказательство:Как показано выше, не существует такого S, для которого выполнялисьбы следующие неравенства:(∇g i ( x*), S ) < 0, для любого i∈I(x*).(∇f ( x*), S ) < 0Воспользуемся леммой Фаркаша, составим матрицу: ∇gi ( x n ) A =  ...............

 , i∈I(x*). ∇f ( x*) Не существует S такого, что AS<0. Следовательно, существуютλ 0,..., λ m ≥ 0 такие, что (по лемме Фаркаша) выполняются условия:mλ 0∇f ( x*) + ∑ λ i ∇g i ( x*) = 0( *)(λi: = 0, если i∉I(x*)).i =1Для активных ограничений gi = 0, для неактивных λi = 0. Тогдаλ i gi (x*) = 0, i = 1, m .101λ 0 ≠ 0, так как если бы он был равен 0 ,то градиенты, соответствующихактивных ограничений, были бы линейно-зависимы, что противоречитусловию. Разделим (*) на λ0и получим требуемое утверждение. Условиелинейной независимости градиентов функций активных ограничений иногданазывают условием регулярности.Упражнение.

Найти минимум функции f(x1, x2) при ограниченииx12+x22≤1.3.02 Задача выпуклого программированияРассмотрим задачу поиска минимума функции f на допустимоммножестве X.X=x∈Rn, gi(x) ≤ 0, i =1...m ,f и все gi ∀i - выпуклы.Утверждение:Допустимое множество в задаче выпуклого программирования (ЗВП)выпукло.Доказательство:Пусть x1,x2∈X ,λ∈[0,1]Рассмотрим z=λx1+(1-λ)x2∈X.

Так как Rn – выпукло, то z∈Rn. Надопроверить gi(z) ≤ 0.Воспользуемся свойством выпуклости gi :gi(λx1+(1-λ)x2) ≤ λ gi (x1) + (1- λ ) gi(x2)0тогда λ x1+(1- λ )x2∈ X (см. определение X), но рассматривается толькоотдельная gi.102Все допустимое множество X рассматривается как пересечениевыпуклых множеств ⇒ X выпукло.Определение :Функцией Лагранжа в ЗВП называется функцияmf(x)+ ∑ λ i g i ( x ) = f(x) + ( λ ,g(x)), где λ i ≥ 0.i =1Справедлива теорема Каруша-Джона:m∇f(x∗)+ ∑ λ i ∇gi ( x ∗ ) =0, λ i gi(x*) = 0, i=1..mi =1В случае выпуклости множества X условие линейной независимостивекторов ∇ gi(x), соответствующее активным ограничениям, можно заменитьболее просто проверяемыми, а именно, так называемымиусловиямирегулярности.Существуют различные условия регулярности ограничений:А) если для любого i (1 ≤ i ≤ m) существует такая точка xi∈ X : gi (xi)<0, то говорят, что множество X удовлетворяетусловию регулярности.Б) условие регулярности Слейтера:Существует точка x∈ X такая, что для всех i=1...m gi(x)<0.Легко доказать эквивалентность условий А и Б .

Очевидно, что из Бmследует А. Пусть теперь выполняется А. Выберем x = ∑ λ i xi ,i =1103m∑ λ i =1,i =1λ i ≥ 0,i=1...m это возможно, так как X выпукло. Тогда Б следует из неравенстваИенсена.Замечание:Условие регулярности означает, что допустимое множество имеетвнутреннюю точку (то есть оно не вырождено в точку)ОпределениеПусть существует функция ϕ (x,y), точка (x,y) называется седловойеслиточкойфункции ϕ ,ϕ (x ∗ ,y) ≤ ϕ (x ∗ ,y ∗ ) ≤ ϕ (x,y ∗ )выполняетсяследующееРис.

3.1. Иллюстрация седловой точки.Определение104неравенство:Седловая точка в математическом программировании — точка, гдефункция Лагранжа достигает максимума по исходным переменным (прямойзадачи) и минимума по множителям Лагранжа.Принекоторыхусловияхвзадачахвыпуклогоилинейногопрограммирования оказывается возможным заменить исходную задачузадачей разыскания С. т. функции Лагранжа, поскольку существование такойточки — необходимое и достаточное условие оптимальности решения.Вообще в математике седловая точка соответствует случаям, когдазначение функции двух переменных представляет собой одновременномаксимум относительно одной переменной (вектора переменных) и минимумотносительно других (другого вектора переменных).Теорема (о седловой точке):Пусть функция Лагранжа ЗВП имеет седловую точку, то естьmmf(x ∗ )+ ∑ λ i gi ( x*)≤ f(x ∗ )+i =1m∑ λ i*gi ( x*)≤ f (x)+∑ λ i*gi ( x )i =1i =1для любого x∈Rn, λi ≥0, i =1...mтогда x*- оптимальная точка ЗВП.Доказательство:Из левого неравенства следует:mm∑ λ i gi ( x*) ≤ ∑ λ i*gi ( x*) ,λi* ≥0, gi(x*)0 (см.

определение X)i =1i =1Так как λ -любое, то при λ =0 получится:105m0≤ ∑ λ i*gi ( x*) ⇒ (λ* , g(x*))=0.i =1Из правого неравенства имеем:mf(x*)+0 ≤ f(x)+∑ λ i*gi ( x )≤ f(x)∀ x∈ Xi =1Тогда по определению оптимальной точки x* оптимальна.Теорема Куна-Таккера:Пусть в ЗВП выполнено условие регулярности Слейтера. Тогда длятого, чтобы x* была оптимальной точкой ЗВП, необходимо и достаточно,чтобы для некоторого вектора λ* с неотрицательными компонентами точка(x*,λ*) была седловой точкой функции Лагранжа, то есть∂ ψ * ∂x =0∂ ψ * def ∂ ψ ( x,λ )=x = x*, λ =λ *∂ ψ * ≤ 0∂x∂x,где ∂λ∂ ψ * def ∂ ψ ( x,λ )∂ψ *=x = x*, λ =λ *)=0(λ *,∂λ∂λ∂λλ* ≥ 0Если на x наложены ограничения (x ≥ 0), то :∂ψ *∂ ψ *≥0;(x*,) = 0;x* ≥ 0 ∂ x∂x∂ ψ * ≤ 0;(λ*, ∂ ψ * ) = 0;λ* ≥ 0 ∂ λ∂λДоказательство:106Достаточность следует из теоремы о седловой точке.Необходимость - без доказательства.3.03 Методыусловнойминимизации.Методпроекцииградиента.Рассматривается задача поиска минимума функции f на допустимоммножестве X.X=x∈Rn, gi(x) ≤ 0, i =1...m ,Методf и все gi ∀i - выпуклы.проекции градиента является обобщением градиентногометода.

Так как возможен выход за пределы допустимого множества, товводится операция проектирования на X (поиск ближайшей точки на X).xk+1= px (xk- γ∇f(xk)), где px проектор на X.Пример:Если X- круг, то проекция точки на X есть точка пересеченияокружности и прямой, соединяющей центр и проектирующую точку. Чемсложнее область X, тем сложнее операция проектирования.Метод обладает теми же свойствами, что и градиентный метод спостоянным шагом.3.04 Метод условного градиента107В очередной точке xk линеаризуют функцию f(x) (в этом «условность»метода, то есть линеаризация и есть «условие» в названии). Затем решаютзадачу min линейной функции на X и найденную точку используют длявыбора направления движения.x k = arg min(∇f ( x k ),x)Xx k +1 = x k +γ k ( x k − x k )При этом предполагается:1.

Задача минимизации линейной функции на X имеет решение.2. Это решение может быть найдено достаточно просто, лучше всего в явнойформе.3. Нужно указать правило выбора γk. Можно γk определить из условиянаискорейшего спуска :γ k = argmin f ( x k +γ ( x k − x k ))0 ≤γ ≤1В этом случае последовательность xk сходится к специальной точке. Вчастности для гладких функций f верно: f(x*)- f* = o(1/k), где f* = min f(x) намножестве X.3.05 Метод модифицированной функции ЛагранжаФункцией Лагранжа в ЗВП называется функцияmψ(x ,λ) = f(x)+ ∑ λ i g i ( x ) = f(x) + ( λ ,g(x)), где λ i ≥ 0.i =1Выше была доказана теорема о седловой точке:Если выполняется соотношение108ψ(x* , λ)≤ ψ(x* ,λ*)≤ ψ(x ,λ*) ∀x∈Rn, λ ≥ 0,тоточка x* является оптимальной точкой задачи выпуклогопрограммирования.Это соотношение можно записать иначе:(*) ψ(x* ,λ*) = minn max ψ(x ,λ) = max minn ψ(x ,λ) = f(x*)x∈Rλ ≥0λ ≥0 x∈RЕсли назвать x прямыми переменными, а λ двойственными, то видно,что прямые и двойственные переменные равноправны.Теорема Куна- Таккера позволяет исходную задачу заменить задачейотыскания седловой точки функции Лагранжа, то есть задачи видаmax minn ψ(x ,λ).λ ≥0 x∈RМетод Эрроу-Гурвица ориентирован на поиск седловой точки функцииψ(x ,λ).Метод Эрроу- Гурвица∂ψ k k k +1kkkkk x = x −γ ∂ x ( x ,λ ) = x −γ (∇ f ( x ) + (∇g ( x ),λ ))λ k +1=λ k +γ ∂ ψ ( x k ,λ k ) = λ k +γ g( x k )∂λСходимость таких методов затруднена в общей ситуации.Метод модифицированной функции Лагранжа обладает лучшимихарактеристиками по сравнению с предыдущими методами.Определим - модифицированная функция Лагранжа:2λ12µ ( x,λ,k ) = f ( x ) +λ + k g ( x )+ −.2k2kk- некоторый параметр (штраф)109+ - взятие положительной части.Свойства модифицированной функции Лагранжа.1.

Если λ + k g(x)>0, то µ ( x,λ ,k ) = f ( x ) + (λ , g ( x )) +kg ( x)22kg ( x)22- добавка (штраф) за то, что g(x)>0.2. lim µ ( x ,λ , k ) = ψ ( x ,λ ) (функция Лагранжа),k →0иначе lim µ ( x,λ , k ) = −∞k →0Метод модифицированной функции Лагранжа. x k +1 = arg minµ ( x,λ k , k ),x ∈ R n k +1λ = [λ k +γ k ∇λ µ ( x k +1 ,λ k , k )]+Метод сходится к (x* ,λ*) со скоростью геометрической прогрессии.3.06 Метод штрафных функцийИдея метода: Сведение задачи с ограничениями к последовательностизадач без ограничений.ЗНП:min f(x), x∈X,X = {x∈Rn, gi(x) ≤0, i = 1...m}Определение:Функция ψ(x), определенная и непрерывная всюду в Rn , называетсяштрафной функцией для рассматриваемой задачи с ограничениями, если:110 ψ ( x ) = 0, x ∈ Xnψ ( x ) > 0, x ∈ R / XСтроится однопараметрическое семейство функций:ψ ( x, β ) = f ( x ) +1ψ ( x ) , где β - скалярный параметр, принимающийβстрого положительные значения.Алгоритм метода штрафных функций:1) Выбираем убывающую последовательность {β k }k =1 положительных чисел,∞такую, что lim β k = 0 .k →02) Сопоставляем каждому βк из этой последовательности соответствующуюфункцию семейства ψ(x,β).

Характеристики

Список файлов лекций