1612726833-e6f68fc32d761b4e64266f5c195a8f96 (828578), страница 7
Текст из файла (страница 7)
Метод покоординатного спуска-1•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ШТРАФОВ = (ДУАЛИЗАЦИЯ / СПУСК)min f (x)при условии, чтоϕi(x) ≤ 0, i = 1, m.Рассмотрим нелинейную функцию ЛагранжаL(x, λ) = f (x) +mXλi(ϕi(x)),i=1где для каждого i выполняется λi(ϕi(x)) = 0, если ϕi(x) ≤ 0 иλi(ϕi(x)) = +∞ иначе. Очевидно, что исходная задача эквивалентна задачеmin L(x, λ)x-2•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИДЕЯ МЕТОДА ВНЕШНИХ ШТРАФОВСвести решение задачиf (x) → minx∈Q(1)Q = {x ∈ Rn | ϕi(x) ≤ 0, i = 1, ..., m}(2)к решению последовательности задач минимизацииFk (x) = f (x)+Pk (x) → minn, k = 1, 2, . .
.x∈R(26)где Pk (x) — штрафная функция множества Q.-3•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВОпределение. Функция Pk (x) называется штрафной функцией множества Q, если Pk (x) ≥ 0 длялюбых k = 1, 2, . . . , x ∈ Rn и0,если x ∈ Qlim Pk (x) =+∞, если x ∈/ Q,k→∞где Pk (x) = kH(x), k – коэффициент штрафа,-4•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВH(x) =mP[ϕi(x)]2+ или H(x) =i=1mP[ϕi(x)]+i=1([a]+ = max(0, a)).-5•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВПусть xl = x(kl) – оптимальное решение задачи без ограничений (26) на шаге l.Шаг l+1.
Найти решение задачи (26) с коэффициентом штрафа kl+1 > kl. Если H(xl+1) ≤ ε,то алгоритм завершает работу, иначе перейти наследующий шаг.-6•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВСоглашения:1. функция H : Rn −→ R непрерывна и H(x) ≥0, ∀x ∈ Rn,2. H(x) = 0 ⇐⇒ x ∈ Q = {x|ϕi(x) ≤0, i = 1, . . . , m}3. f — непрерывная функция, а множество Qзамкнуто-7•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВТеорема 17. Пусть выполняется одно из двух условий:(a). f (xk ) −→ +∞ для любой последовательности {xk } ∈ Q, kxk k −→ +∞ или(b).
Q ограничено и H(xk ) −→ +∞ для любой последовательности {xk }, kxk k −→ +∞Тогда 1). последовательность xl имеет хотя быодну предельную точку и любая предельная точкаэтой последовательности есть оптимальное решение задачи; 2). H(xl) −→ 0-8•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВЗадача. Показать, что в случаях a) и b) существует оптимальное решение задачи.-9•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВПусть – k1 < k2 < · · · < kl < kl+1 < .
. .— коэффициенты штрафа (используемые алгоритмом). ИмеемFl+1(xl+1) = f (xl+1) + kl+1H(xl+1) >> f (xl+1)+klH(xl+1) ≥ f (xl)+klH(xl) == Fl(xl), т.е.Fl+1(xl+1) > Fl(xl) для ∀l-10•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНЕШНИХ ШТРАФОВОчевидно, что для ∀l имеемf (xl) ≤ f (xl)+klH(xl) ≤ f (x∗)+klH(x∗).Таким образом, аппроксимация координирующейзадачи происходит снизу.-11•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД ВНУТРЕННИХ ШТРАФОВ ИЛИ МЕТОД БАРЬЕРНЫХ ФУНКЦИЙПроблема метода внешних штрафов: приближенияx1 = x1(k1), x2 = x2(k2), . . . , xl = xl(kl), .
. .не являются допустимыми решениями задачи =⇒попробуем аппроксимировать оптимум изнутри.Идея метода, как и ранее, заключается в сведении исходной задачи (1)–(2) к последовательностизадач минимизации следующего вида:-12•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitFk (x) = f (x)+ak B(x) → minn, k = 1, 2, . . .x∈R(30)где B(x) — барьерная функция, ak > 0 — барьерный коэффициент, ak → 0 при k → ∞.Определение. Функция B(x) называется барьерной функцией для множества Q, если B(x) определена, конечна и неотрицательна во всех точках изIntQ иlim B(x) = +∞.x→∂QСоглашение: B(x) = +∞, для x ∈ ∂Q( граница множества ).-13•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitПримеры барьерных функций:mmmXXX−ϕi(x)−1,|ϕi(x)|−1,|ϕi(x)|−2.i=1i=1i=1Соглашение: Задачу (30) решаем методомградиентов: xk+1 = xk − αk f 0(xk ), αk ≥0.Если xk ∈ IntQ, то при достаточно малом αkxk+1 ∈ IntQ.Таким образом, если x0 ∈ IntQ, то из определения следует, что все приближения xk – допустимые решения (1)-(2)-14•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИДЕЯ МЕТОДАПусть xk — решение задачи (30) на шаге k иxk ∈ IntQ.Итерация (k + 1).
Находим решение задачи (30) со значением барьерного коэффициентаak+1 < ak . Если ak+1B(xk+1) ≤ ε, то алгоритм завершает работу. Иначе начинаем новуюитерацию.-15•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitСоглашения:1.Q замкнуто;2.IntQ 6= ∅;3. любая точка x ∈ Q есть предел последовательности точек из внутренности Q;4. f — непрерывная функция на всем Rn;5. функция B(x) непрерывна на множестве IntQ.-16•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitО СХОДИМОСТИ МЕТОДА БАРЬЕРНЫХ ФУНКЦИЙТеорема 18. Пусть выполняется одно из двух условий:(a). f (xk ) −→ +∞ для любой последовательности {xk } ∈ Q, kxk k −→ +∞ или(b).
Q ограничено.Тогда 1) последовательность xk имеет хотя быодну предельную точку и любая предельная точкаэтой последовательности есть оптимальное решение задачи; 2) ak B(xk ) −→ 0-17•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitВ задаче (1)-(2) ∃ оптимальное решение x∗ ∈Q (По теореме Вейерштрасса ).Пусть x1, x2, . .
. , xk , . . . — приближения,а a1, a2, . . . , ak , . . . – соответствующие барьерные коэффициенты.∀ k имеемf (x∗) ≤ f (xk ) ≤ f (xk )+ak B(xk ) = Fk (xk )-18•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitИз определения величин xk , xk+1 и условияak > ak+1 имеемFk (xk ) = f (xk ) + ak B(xk ) > f (xk )++ak+1B(xk ) ≥ f (xk+1)+ak+1B(xk+1) == Fk+1(xk+1)-19•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПЗадача поиска безусловного минимума:f (x) −→ minn .x∈RДля решения используются численные методы, вкоторых текущее приближение вычисляется по формулеxk+1 = xk + αk pk ,где pk — направление спуска, αk — длина шагавдоль этого направления.-20•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПМетоды, в которых последовательность векторовx0, x1, .
. . , xk , . . . , удовлетворяет условиюf (x0) ≥ f (x1) ≥ ... ≥ f (xk ) ≥ . . .называются релаксационными.Пусть x∗– минимум функции f (x). Скорость сходимости линейная: если для k = 0, 1, . . .kxk+1 − x∗k ≤ q kxk − x∗k, 0 < q < 1,-21•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПили говорят, что метод сходится со скоростью геометрической прогрессии, т.к.kxk − x∗k ≤ q k kx0 − x∗k.Скорость сходимости сверхлинейна, еслиkxk+1 − x∗k ≤ qk kxk − x∗k,где qk → 0 при k → ∞, и квадратична, еслиkxk+1 − x∗k ≤ C kxk − x∗k2, C ≥ 0.-22•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПМетод нулевого порядка, если в процессе вычислений используются только значения целевой функции.В методах первого порядка, помимо значенийцелевой функции используются её производные.и так далее.-23•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПВсе итерационные процессы, в которых направление движения pk на каждом шаге выбирается изконуса Kd(xk ), называются методами спуска (подъёма).
Если pk = −f 0(xk ) (pk = f 0(xk ), ) ∀k,то такие методы называются градиентными методами:xk+1 = xk − αk f 0(xk ), αk ≥ 0.Методы отличаются способами выбора длинышага αk .-24•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПМетод с постоянным шагом: αk = α.Метод с дроблением шага: на каждом шаге проверяется неравенствоf (xk −αk f 0(xk ))−f (xk ) ≤ − αk kf 0(xk )k2,где 0 < < 1.Метод наискорейшего спуска (подъёма):αk = arg min f (xk − α f 0(xk )).α≥0-25•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitЧисленные методы НЛПТеорема 19 (Первая теорема сходимости)Пусть функция f ∈ C 1(Rn), ограничена снизуf (x) ≥ f ∗ > −∞, выполняется условие Липшица для градиента f 0(x):kf 0(x) − f 0(y)k ≤ L kx − ykи длина шага α удовлетворяет условию 0 < α< 2/L.
Тогда f 0(xk ) → 0 при k → ∞ иf (xk+1) ≤ f (xk ), при любом выборе начального приближения x0.-26-•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitГрадиентные методыОпределение Дифференцируемая функция f называется сильно выпуклой (с константой l > 0), если для любых x и y из Rn справедливоf (x + y) ≥ f (x) + hf 0(x), yi + lkyk2/2.(23)Лемма 12. Если функция f является сильновыпуклой (с константой l > 0), то она имеет глобальный минимум на Rn.-27•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitГрадиентные методыЗадача.
Пусть функция f является сильно выпуклой (с константой l > 0). Доказать, что:1. Она не может быть константой.2. Она имеет единственный глобальный минимум.-28•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitГрадиентные методыТеорема 20 (Вторая теорема сходимости) Пусть функция f дифференцируема в Rn,является сильно выпуклой, выполняется условиеЛипшица для градиента f 0(x) : kf 0(x)−f 0(y)k ≤L kx−yk и длина шага α удовлетворяет условию0 < α < 2/L.Тогда xk → x∗ при k → ∞ и kxk −x∗k ≤ Cq k , 0 ≤ q < 1.-29•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД НЬЮТОНАПусть f — дважды непрерывно дифференцируемая функция и есть алгоритм вычисления еёвторых производных.Идея метода: заменить функцию f в окрестности текущего приближения xk её квадратичнойаппроксимацией: q(x) = f (xk ) + f 0(xk )(x −xk ) + 21 (x − xk )>f 00(xk )(x − xk ).Выбрать в качестве нового приближения xk+1точку минимума функции q(x) (если она ∃).-30•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД НЬЮТОНАПредположим, что матрица f 00(xk ) — положительно определённая =⇒ функция q(x) — сильновыпукла =⇒ у неё единственный минимум =⇒его можно найти как решение системы уравненийq 0(xk+1) = 0, которая по определению q(x) эквивалентна следующей системе линейных уравненийf 0(xk ) = −f 00(xk )(xk+1 − xk ).-31•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД НЬЮТОНА=⇒ получаем необходимую итерационную формулуxk+1 = xk − (f 00(xk ))−1f 0(xk ).Заметим, что здесь как направление, так и длинашага заданы.Пусть последовательность {xk } получена с помощью метода Ньютона и точка x∗ — глобальныйминимум функции f .-32•First •Prev •Next •Last •Go Back •Full Screen •Close •QuitМЕТОД НЬЮТОНАТеорема 21 Пусть дважды непрерывно дифференцируемая функция f сильно выпукла (с константой l > 0), вторая производная удовлетворяетусловию Липшица: для любых x, y ∈ Rnkf 00(x) − f 00(y)k ≤ L kx − yk,и q = Lkf 0(x0)k/2l2 < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
