1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 4
Текст из файла (страница 4)
Пусть x∗ — локальный экстремум задачи (1), (2), функции f ,ϕi, i = 1, m, непрерывны и непрерывно0дифференцируемы и вектора ϕi(x∗), i ∈I(x∗), линейно независимы. Тогда найдутся такие множители λi ≥ 0, i = 1, m, чтоmX00∗(18)−f (x ) =λiϕi(x∗),i=1λiϕi(x∗) = 0, i = 1, m.(19)-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 6Необходимые и достаточныеусловия экстремума1. Необходимые условия оптимальностии теорема о замыкании конуса возможныхнаправлений2. Критерий оптимальности в локальнойи нелокальной формах-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема 10 (Необходимые условия оптимальности Куна–Таккера).
Пусть x∗ — локальный экстремум задачи (1), (2), функции f ,ϕi, i = 1, m, непрерывны и непрерывно0дифференцируемы и вектора ϕi(x∗), i ∈I(x∗), линейно независимы. Тогда найдутся такие множители λi ≥ 0, i = 1, m, чтоmX00∗(18)−f (x ) =λiϕi(x∗),i=1λiϕi(x∗) = 0, i = 1, m.(19)-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДоказательство. Из теоремы 9 =⇒ найдутся такие не все равные0 множители λi ≥ 0, i = 0, m, что0λ0f (x∗) +mX0λiϕi(x∗) = 0n.(15)i=1λiϕi(x∗) = 0, i = 1, m.(16)Также получили равенствоλ0 +Xλi = 1.(17)i∈I(x∗ )Покажем, что λ0 6= 0 (от противного). Пусть λ0 = 0. Из (17)0=⇒ ∃ λi 6= 0 =⇒ {ϕi(x∗)}i∈I(x∗) линейно зависимые вектора.Противоречие.
=⇒ λ0 > 0-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТеорема о замыкании конуса возможных направлений0K≤ (x) = {s 6= 0|(ϕi (x), s) ≤ 0, ∀ i ∈ I(x)}.Т.к. Kf (x) ⊆ K≤ (x), то конус K≤ (x) называется внешней аппроксимацией конуса возможных направлений.Теорема 11.Если K< (x) 6= ∅, то K f (x) = K≤ (x).Доказательство. Действительно, пусть конус K< (x) не пуст. Тогда найдётся sтакой, что0(ϕi (x), s) < 0, ∀ i ∈ I(x).Пусть s ∈ K≤ (x), т.е.0(ϕi (x), s) ≤ 0, ∀ i ∈ I(x).Очевидно, что для любого λ ∈ [0, 1):λs + (1 − λ)s ∈ K< (x).-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitТаким образом s предел последовательности направлений из K< (x) при λ стремящимся к 1 снизу.
Учитывая, чтоK< (x) ⊆ K≤ (x),получим K < (x) = K≤ (x).Т.к.K< (x) ⊆ Kf (x) ⊆ K≤ (x),то0K f (x) = K≤ (x) = {s 6= 0|(ϕi (x), s) ≤ 0, ∀ i ∈ I(x)}.-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случайЗадача (1), (2) называется задачей выпуклого программирования, если функции f ,ϕi , i = 1, m, — выпуклы.Множество Q выпукло. По прежнему считаем, что f , ϕi ∈ C 1 .Условие регулярности для выпуклого случая:∀i, i = 1, m, ∃xi ∈ Q : ϕi (xi ) < 0.Эквивалентно условию регулярности Слейтера∃ex ∈ Q : ϕi (ex) < 0, i = 1, m.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случайЛемма 8. Функция f дифференцируемая на выпуклом множестве Q,выпукла в том и только в том случае, когда для любых x, y ∈ Q:0(f (x), y − x) ≤ f (y) − f (x).Доказательство.
∀x 6= y ∈ Q, ∀α 0 < α ≤ 1f (x + α(y − x)) ≤ f (x) + α(f (y) − f (x)).Перепишем неравенство:ky − xkгде s =y−x,ky−xkf (x + βs) − f (x)β≤ f (y) − f (x),β = αky − xk. Устремим β к 0. В пределе получим-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случай0(f (x), s) ky − xk ≤ f (y) − f (x).Но00(f (x), s) ky − xk = (f (x), y − x).Итак, доказали неравенство0(f (x), y − x) ≤ f (y) − f (x).0В обратную сторону. Пусть ∀x, y ∈ Q : (f (x), y − x) ≤ f (y) − f (x).-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случайПо условию ∀ α ∈ [0, 1] : z = αx + (1 − α)y ∈ Q.0Умножим неравенство (f (z), x − z) ≤ f (x) − f (z) на α, а0неравенство (f (z), y − z) ≤ f (y) − f (z) на (1 − α) и сложим их00 = (f (z), α(x − z) + (1 − α)(y − z)) ≤ αf (x) + (1 − α)f (y) − f (z)=⇒ f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y).-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случайЛемма 9.
ЕслиQ = {x|ϕi (x) = (ai , x) − bi ≤ 0, i = 1, m},то условия(ai , s) ≤ 0, i ∈ I(x∗ )необходимы и достаточны для того, чтобы направление s было возможным в точке x∗ ∈ Q.Доказательство. Пусть β > 0. Рассмотримϕi (x∗ + βs) = (ai , x∗ + βs) − bi = (ai , x∗ ) − bi + β(ai , s).∀i 6∈ I(x∗ ) (ai , x∗ ) − bi < 0 ⇒ ∀i 6∈ I(x∗ ) ϕi (x∗ + βs) ≤ 0,для достаточно малых β.-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitНеобходимые условия оптимальности Куна–Таккера: выпуклый случай∀i ∈ I(x∗ ) ϕi (x∗ + βs) = (ai , x∗ + βs) − bi = β(ai , s) ⇒⇒ x∗ + βs ∈ Q ∀β > 0 ⇔ (ai , s) ≤ 0 ∀i ∈ I(x∗ ).Другими словами в лемме утверждается, что Kf (x) = K≤ (x)Эта лемма позволяет элиминировать условие Слейтера в задаче выпуклого программирования в случае линейных ограничений.Помним: функции f, ϕi — выпуклые, непрерывно-дифференцируемые.
Множество допустимых решений Q удовлетворяет условию Слейтера.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКритерий оптимальности: выпуклый случайТеорема 12 (Теорема Куна-Таккера в локальной форме). Точка x∗ ∈ Q — оптимальноерешение задачи выпуклого программирования в том и только в том случае, когдасуществуют такие числа λi ≥ 0, i = 1, m,чтоmX00∗−f (x ) =λiϕi(x∗),i=1λiϕi(x∗) = 0, i = 1, m.-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitДоказательство. Из леммы 8 и условия Слейтера следует, что для любого i ∈ I(x∗)0∗e−x∗).0 > ϕi(ex) = ϕi(ex)−ϕi(x ) ≥ (ϕi(x∗), xТаким образом вектор s = (ex −x∗) ∈ K<(x∗).Следовательно, по теореме о замыкании конуса возможных направлений имеем K f (x∗) = K≤(x∗).Повторяем соответствующие рассуждения второгодоказательства теоремы 10.-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКритерий оптимальности: линейный случайТеорема 13 (Теорема Куна-Таккера в локальнойформе).
Точка x∗ ∈ Q — оптимальное решениезадачи выпуклого программирования с линейными ограничениями в том и только в том случае,когда существуют такие числа λi ≥ 0, i = 1, m,чтоmX0−f (x∗) =λiai,i=1λi (ai, x) − bi = 0, i = 1, m.-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКритерии оптимальностиФункциюL(x, λ) = f (x) +mXλiϕi(x),i=1определенную при всех x и λ, назовем функцией Лагранжадля задачи (1), (2).Пара (x∗, λ∗) называется седловой точкой функции Лагранжа, если∗(3)∗∗(4)L(x , λ) ≤ L(x , λ ) ≤ L(x, λ∗) ∀x ∈ Rn, ∀λ ≥ 0.-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitКритерии оптимальностиТеорема 14 (Теорема Куна-Таккера в нелокальной форме).Вектор x∗ ∈ Q является оптимальным решением задачивыпуклого программирования тогда и только тогда, когдасуществует такой вектор λ∗, что пара (x∗, λ∗) является седловой точкой функции Лагранжа.Доказательство. Необходимость.
Пусть x∗ ∈ Q — оптимальное решение. Тогда из теоремы 12 имеемmX∂L(x,λ)00∃λ∗ ≥ 0 :λ∗i ϕi(x∗) = 0 и ∗ ∗ = f (x∗) +(x ,λ )∂xi=1λ∗i ϕi(x∗) = 0, i = 1, m.Достаточность. Как в теореме 1. -16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЛЕКЦИЯ № 7Методы разработки алгоритмов решения1. Преобразования и стратегии решения2. Декомпозиция Бендерса3. Декомпозиция для максиминной задачи (стратегия решения)-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетоды разработки алгоритмов решенияПреобразование: сведение исследуемой задачи к "координирующей"задаче.Стратегия решения: сведение "координирующей"задачи к последовательности связанных, но более простых задач.-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМетоды разработки алгоритмов решенияМЕТОД РЕШЕНИЯ = НАБОР ПРЕОБРАЗОВАНИЙ + СТРАТЕГИЯ РЕШЕНИЯПреобразования: дуализация, проекция,внутренняя линеаризация, внешняя линеаризация ...Стратегии решения: декомпозиция, допустимые направления, разложение, сужение,релаксация...-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСинтез методов решения:1.
(проекция/декомпозиция) – точный метод решения для задачи о (r, p)-центроиде2. (проекция, внешняя линеаризация/релаксация) – декомпозиция Бендерса3. (проекция/разложение) – алгоритмы разбиения Розена-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСинтез методов решения:4.
(внутренняя линеаризация/сужение) –декомпозиция Данцига-Вулфа5. (проекция/допустимые направления) –6. (дуализация/допустимые направления)– метод Такахаши7. (внешняя линеаризация/релаксация) –метод Келли-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПроекция задачи на пространство переменных xРассмотрим задачу (P ):minx∈X,y∈Yf (x, y)ϕi(x, y) ≤ 0, i = 1, m.Введём функцию возмущения данной задачи:ρ(x) = inf f (x, y),y∈Yϕi(x, y) ≤ 0, i = 1, m.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПроекция задачи на пространство переменных xПоложимV = {x|∃y : ϕi(x, y) ≤ 0, i = 1, m}.Множество V является проекцией области допустимых решений задачи P на пространство переменных x.
Нетрудно проверить, что задача P эквивалентна следующей задаче (Px):min ρ(x),x∈X∩Vкоторая и является проекцией задачи P на пространство переменных x.-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПроекция задачи на пространство переменных xЛемма 10. Задача P недопустима или неограничена снизу тогда и только тогда, когда тоже самое выполняется для её проекции. Если (x∗, y ∗) –оптимальное решение задачи P , то x∗ – оптимальное решение проекции Px.
Если x∗ – оптимальноерешение проекции и инфинум в ρ(x∗) достигаетсяна y ∗, то (x∗, y ∗) – оптимальное решение исходной задачи P .-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСтратегия релаксации (идея)Свести решение задачиmin f (x)x∈Xϕi(x) ≤ 0, i = 1, m,к решению семейства задач вида (PS ):(1)(2)min f (x)x∈Xϕi(x) ≤ 0, i ∈ S.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСтратегия релаксацииШаг 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
