1612726855-66ce2678ed92310585f0bb1a36623206 (828576), страница 16
Текст из файла (страница 16)
Пусть Fh = min f ( x i1Kin ) .QhТеорема 4. Для любой функции f (x ) , удовлетворяющей условию Липшица (18), справедлива оценкаf * £ Fh £ f * + e .Доказательство. МножествоQi1Kin = {x Î R n x - x i1 Kin¥£ h / 2}является кубом с центром в точке x i1Kin и гранями, параллельными осям координат, с длиной ребра равной h . Множество всех кубов Qi1Kin с центрами86x i1Kin Î Qh покрывает весь параллелепипед Q , поэтому для любой точкиx Î Q найдется гиперкуб Qi1 Kin , содержащий эту точку. Учитывая усло-вие(18), получим, что для любого x Î Q выполняетсяf ( x ) ³ f ( xi1Kin ) - L x - x i1Kin¥³ Fh - Lh= Fh - e .2Отсюда f * £ Fh £ f * + e . ▄Рассмотрим произвольный гиперкуб G[ x c , h ] с центром x c и длиной стороны h :hG[ x c , h ] = {x Î R n : x - x c £ }.¥ 2Из доказательства теоремы 4 следует, что для любого x Î G[ x c , h] верноhf ( x) = f ( x) - f ( x c ) + f ( x c ) ³ - L | x - x c | + f ( x c ) ³ f ( x c ) - L .2Естественно тогда определить нижнюю границу на гиперкубе G[ x c , h] равенhством H (G[ x0 , h]) = f ( x c ) - L .2Функцию выбора наилучшего решения определим на гиперкубах, которыеeявляются атомарными множествами, со стороной h £ 2 .
ПоложимLx ( G [ x c , h ]) = x c . Подмножества решений будем задавать в виде набора гиперкубов.На первом шаге имеем t1 = G[ x R , D ] , где первый рекорд x R является центром гиперкуба со стороной DR = D .Пусть к очередному шагу имеется разбиение t1 = G[ x1, h1],K, tL = G[ x L , hL ]и рекорд x R – центр гиперкуба со стороной DR .
Очередной шаг начинается спроверки гиперкуба с номером l . Он считается проверенным и отбрасывается, если выполняется одно из следующих условий:1. f ( x R ) £ H (G[ xl , hl ]) ;e.LПри этом если реализуется второй случай и f ( xl ) < f ( x R ) , то устанавли2. сторона гиперкуба hl не превосходит величины 2ваются новые значения рекорда x R = x l и величины DR = hl .В рассматриваемой задаче дополнительно можно использовать следующие правила проверки подмножеств.87Случай 1. Если f ( xl ) < f ( x R ) , то есть текущий рекорд хуже, то пересчитываем рекорд и среди оставшихся гиперкубов разбиения отбрасываем те,которые содержатся в гиперкубе G[ x R ,2( f ( x R ) - f ( xl )) / L ] .
По определениюлюбогоx Î G[ x c , h]вернонеравенствоhf (x) ³ H (G[ xc , h])= f ( x c - L ) . Поэтому для любой точки x из данного ги2перкуба имеемнижнейграницыдля2( f ( x R ) - f ( x l ))L 2( f ( x R ) - f ( x l ))]) = f ( x R ) = f ( xl ) .L2LСлучай 2. Если f ( x R ) £ f ( x l ) , то есть текущий рекорд не хуже, то средиоставшихся гиперкубов разбиения отбрасываем те, которые содержатся вf ( x ) ³ H ( G[ x R ,f ( xl ) - f ( x R )] , так как для любой точки x из данного гиперкуба имеLем f ( x ) ³ f ( x R ) .Если отброшены все элементы разбиения, то алгоритм заканчивает работуи x R – требуемое решение.
Если остались неотброшенные множества, товыбираем «перспективное» по одному из правил, которые описаны в схемеметода, подмножество G[ x l , hl ] . Функция ветвления b(×) разбивает его на 2nодинаковых гиперкубов со стороной hl / 2 . После этого начинается следующий шаг. Конечность алгоритма МВГ обсуждалась в предыдущем параграфе.G[ x l ,Замечание.Если в процессе работы алгоритма ни разу не происходит смены рекордапо 2 условию, когда функция x (d ) является определенной на проверяемоммножестве, то полученный рекорд является оптимальным решением задачи.В противном случае полученный рекорд является e -оптимальным решением.§ 6.
МЕТОДЫ ШТРАФАВ этом параграфе представлены методы штрафа, общая идея которых заключается в замене решения исходной задачи на решение последовательности экстремальных задач без ограничений. Эти методы интересны тем, чтоони просты при обосновании сходимости и оказываются практически эффективными при решении оптимизационных задач.Опишем в общем виде идею метода штрафов, используемого для решенияследующей задачи (1)-(3). Рассмотрим функцию h : R ® R видаì0, y £ 0,h(Y ) = íî + ¥ , y > 0.88mОпределим функцию штрафа H ( x) = å h(ji ( x)) . Очевидно, чтоi =1ì0, x Î Q,H ( x) = íî+ ¥, x Ï Q.Следовательно, решение задачи (1)-(3) эквивалентно решению следующейзадачи без ограниченийg ( x ) = f ( x ) + H ( x ) ® min .x ÎR nОсновной недостаток этого подхода связан с разрывностью функцииштрафа H , так как минимизация функции g в этом случае является весьманепростой задачей, для решения которой неприменимы методы главы 2.6.1 Метод внешних штрафовЗатруднений, связанных с разрывностью функции g , можно избежать,рассматривая непрерывные и непрерывно дифференцируемые штрафныефункции.
Покажем реализацию этого подхода на примере метода внешнихштрафов.Определение 1. Функция Pk (x) называется штрафной функцией множества Q , если Pk ( x ) ³ 0 , k = 1,2,K , x Î R n , иì0, x Î Q,lim Pk ( x) = ík ®¥î + ¥, x Ï Q.В дальнейшем будем предполагать, что штрафная функция имеет следующий вид: Pk ( x ) = kH ( x ) , где k = 1,2,K – коэффициент штрафа. Например,возьмемH ( x=)må [ji ( x)]+2или=i 1H ( x=)må [ji ( x)]+ ,здесь=i 1[ a]=+ max( 0, a) .Теперь решение задачи (1)-(3) сводится к решению последовательностизадач минимизации вида(19)Fk ( x) = f ( x) + Pk ( x ) ® min , k = 1,2, K.nxÎRДля упрощения последующих рассуждений будем считать, что имеетсяметод нахождения оптимального решения x(k ) задачи (19) для любого коэффициента штрафа k = 1,2K . Обычно с этой целью выбирается один из итерационных алгоритмов безусловной оптимизации.89С практической точки зрения мы не можем использовать сведение задачи(1)-(3) к задачам вида (19), так как оптимальное значение целевой функциизадачи (1)-(3) является пределом оптимальных значений задач вида (19).
Припрактических вычислениях приходится довольствоваться теми приближениями x(k ) , для которых величина H ( x (k )) достаточно мала.Соответствующий итерационный алгоритм может быть описан следующим образом.Шаг l + 1 . Найти решение задачи (19) с коэффициентом штрафа kl +1 > kl .Если H ( x l +1 ) £ e , то алгоритм завершает работу, иначе перейти на следующий шаг.Понятно, чтобы этот алгоритм представлял интерес с вычислительнойточки зрения необходимо найти условия, которые гарантировали бы сходимость приближений к оптимальному решению.Для этого рассмотрим ситуацию, когда алгоритм не останавливается. Положим e = 0 .
Тогда получается последовательность приближений {x}lÎN .При очень простых условиях она сходится к оптимальному решению задачиP . Будем считать, что1) H Î C 0 , H ( x) ³ 0 для всех x Î R n ,2) H ( x) = 0 тогда и только тогда, когда x Î Q ,3) f Î C 0 и множество Q – замкнутое.Теорема 5. Пусть выполняется хотя бы одно из условий:a) f ( xk ) ® +¥ при k ® ¥ для любой последовательности {xk }kÎN Î Qтакой, что || xk ||® +¥ при k ® ¥ ,б) множество Q – ограничено и H ( xk ) ® +¥ при k ® ¥ для любой последовательности {xk }kÎN Î Q такой, что || xk ||® +¥ при k ® ¥ .Тогда последовательность x l = x (kl ) , l Î N , имеет хотя бы одну предельную точку, и всякая предельная точка этой последовательности есть оптимальное решение задачи, и H ( x l ) ® 0 при l ® ¥ .Доказательство.
Покажем, что в задаче (1)-(3) существует оптимальноерешение. В случае б) это очевидно, так как множество Q является компактным. Рассмотрим случай а). Если множество Q ограничено, то тогда оноснова является компактным и искомый оптимум x* существует. Пусть x* –оптимальное решение. В противном случае найдется последовательность{xk }kÎN Î Q такая, что || xk ||® +¥ при k ® ¥ .
Рассмотрим множество Лебега вида {x Î Q | f ( x) £ f ( x0 )} . Вне этого множества функция f неограничен-90но возрастает. В силу того, что данное множество ограничено и замкнуто, тои в этом случае также существует оптимальное решение.Учитывая, что kl +1 > kl , xl – оптимальное решение задачи (19) с коэффициентом штрафа kl , получим следующие неравенства:Fl +1( xl +1) = f ( xl +1 ) + kl +1H ( xl +1) > f ( xl +1) + kl H ( xl +1 ) ³³ f ( x l ) + kl H ( x l ) = Fl ( x l ) .(20)lОтсюда следует, что последовательность {Fl ( x )}lÎN является монотонновозрастающей.Из следующих двух неравенств:f ( x l ) + kl H ( x l ) £ f ( x l +1 ) + kl H ( x l +1 ) ,f ( x l +1 ) + kl +1H ( x l +1) £ f ( x l ) + kl +1H ( xl ) ,получим (kl +1 - kl ) H ( x l +1 ) £ (kl +1 - kl ) H ( x l ) , тогдаH ( x l +1 ) £ H ( x l ) , l Î N .Аналогично,f ( xl ) £f ( xl ) + kH ( xl ) £lf ( xl ) £Flf ( x* ) + k( xl ) £(21)H ( x* ) ,lf ( x* ) , l Î Nследовательно,.(22)Покажем, что последовательность {x l }lÎN является ограниченной.
Допустим противное. Тогда если выполняется гипотеза а) теоремы, то f ( xl ) ® ¥при l ® ¥ , что противоречит (22). В случае выполнения гипотезы б) имеемH ( x l ) ® ¥ при l ® ¥ , что противоречит (21).Таким образом, последовательность {x l }lÎN ограничена. Без ограниченийобщности считаем, что существует предел x̂ последовательности {x l }lÎNпри l ® ¥ . Из непрерывности функции f следует, что f ( x l ) ® f ( xˆ ) приl ® ¥ . Тогда из (22) имеемf ( xˆ ) £ f ( x* ) .(23)Так как последовательность {Fl ( x l )}lÎN монотонно возрастающая и ограниченная, что следует из (20), (22), то существует lim Fl ( x l ) = F * £ f ( x * ) ,l ®¥следовательно, существует и lim kll ®¥H ( xl ) =F*- f ( xˆ ) .Учитывая, что kl ® ¥ при l ® ¥ , получим, что H ( x l ) ® 0 при l ® ¥ .Тогда H ( xˆ ) = 0 , следовательно, xˆ Î Q . Таким образом, f ( x* ) £ f ( xˆ ) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
