И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 64
Текст из файла (страница 64)
)ф+'(х) — ф(х))<Х,о„, хЕХ, Х,(оо, и, +О при А оо; (1И)— 1По(х) ХУо(у)))<хг$» — уИ, Хг< оо, х, уЕХ' Аь-~-+ 0 при й-эоо; (Юо) — для всех хЕХ, й = О, 1, ..., 1) Чо+ (х) — По (х)(~ ~Хзб» где Хг( оо, бь-~-О пРи й-~ оо; (о)— Д ))+(71о(х')1+))Ь'))(Х, п. н, й = О, 1, ..., где Х, < оо. Тогда, если шаговые множители рт (й) и р, (й) выбирать такими, что рс(й)-~.+О, Х р,(й) = оо, ь=о Ю Ю ~' (р,(й))'( оо, ~ р (й)1Ьь))(оо п. н; р, (й)1р, (Ь) й„~ О, 6,1р, (Ь) то ага — Ч~ьь(хл)))-~0 п. н.
Если дополнительно выполняется условие оь/р, (й) -~ 0 при й-» оо, то последовательность (1ь (хь)) почти наверное сходится и каждая предельная точка последовательности (хл (в)), генерируемой алго- ритмом 2, почти наверное принадлежит множеству Х', определен- ному согласно определению 1. Замечание 2. Если функция 1, (х) гладкая, то для справедли- вости теоремы 2 вместо условия (йм) достаточно потребовать выпол- нения условия 1 ЧЯ (х) — Ч~ь" (У) 1( Рь1х — 4, где Ц, й = О, 1, ..., — ограниченные в совокупности константы. Тогда надо выбирать р, (и) и р, (й) такими, чтобы Рз(А)/ря(/з)-ьО при /з- оо, Если же, кРоме того, !ип 17/е (х) = 7/, (х) длЯ каждого х с Х, то теорема 2 справедлива и в том случае, когда оа и 6« при /е -ь со стремятся к нулю произвольно, т.
е. не требуется, чтобы 6/р,(й)-ьО н оа/рт(й)-~-0 при /г-~- оо. Бябяиографнзеекие указания. При иаписаиии параграфа использовались ра. боты 1154, 97, !971. 5.13. Методы отсечении 1. Лииейиьтй елтчай 3 ада ч а 1. Найти зги ппп (с, х) для ааданного вектора сй «ах Е В и множества Х(з (х1/ (х)(0, х~В"), определенного с помощью заданной выпуклой функции /з . В"-ь Вз. Заметим, что более общая задача выпуклого программирования в пространстве В"з найти агдппп/е (х), где «ах ХЬ(х)/ (х)(0, /=1, ..., т), /и / О, 1, ..., т, — выпуклые функции, легко приводится к виду задачи 1 о помощью дополнительной координаты х„+1 и неравенства / +з(х, хн+з) Ь/е(х) — х.+,~0: найти агн ппп х .ьь <«,«я+рад где Х = ((х, х„+~) ~/(х, х,+1) ~,0, (х, х„+~) ~В"+')» /(х, х„+1)Д1 шах /,(х, х„+з), хг~ в+~ /г(х, хя+г)~/,(х)+О ° х„+и 1 1, ..., т.
Предположение 1. Множество Х вЂ” непустое компактное множество. Сущность метода отсекающей гиперплоскости заключается в решении задачи 1 путем решения последовательности специальных аадач линейного программирования, полученных аппроксимацией множества ограничений Х последовательностью многогранников Хго я = О, 1, ..., каждый из которых содержит Х. раз Алгоритм 1 Н а ч а л о. 1. Выбрать целое число 1ь О, п-мерные векторы а', != — 1,— (1 — 1), ..., — 1,0ичислар!,1= — 1,— (1 — 1),- ..., — 1, О, такие, что множество Х, Ь (х ) (а!, х) — р! а ,'О, 1 — 1, ..., О, хЕ В"), компактно и содержит Х. П. Положить й = О. Основ но й ц и кл. П1.
Найти решение х = х" задачи ли- нейного программирования: найти агу ш1п (с, х) при ограничениях л (а', х) — р!(О, ! = — 1, — (1 — 1), ..., я. <з.е4) 1Ч. Если 1! (х') (О, то положить хь= х' и прекратить вы- числения; иначе перейти к шагу Ч.
Ч. Вычислить опорный вектор а"+' к функции 1, (х) в точ- ке х'. Ч1. Вычислить =- (аьь!, хь) — г (хь). ЧП. Построить множество Хь+!1й(х((аь+!, х) — рь+!(О, хе11") П Хм ЧП1. Положить я = й + 1'и перейти к шагу Ш. Замечание 1. На шаге П1 алгоритма 1 требуется решать задачу линейного программирования, число ограничений которой растет с увеличением я. Это требует большой оперативной памяти ЭВМ для хранения векторов а', ! = — 1, ..., й, и чисел ()„ 1 = — 1, ..., я. Для упрощения алгоритма на шаге П1 вместо задачи линейного программирования (5.64) можно решать двойственную ей задачу! найти агатах( — Х и!но! и при ограничениях и,.а' + с = О, и! ~ О, != — ! При решении этих двойственных задач симплекс-методом весьма существенно, что решение предыдущей задачи служит хорошим допустимым решением для последующей, так что их решение полу- чают довольно быстро.
Теорема 1. Если: (1) — 1, (х) — выпуклая непрерывная функция) (11) — множество Х вЂ” непус>пое и компактное; (И) — существу- ет такое число 6 ( оо, что при каждом х с Х, вектор а, опорный к 1! (х) в точке х, удовлетворяет неравенству ( а ( ( 6, то любая предельная точка х* бесконечной последовательности (х")ь,-о, по- рожденной алгоритмом 1, является решением задачи 1 и ~г (хь) -~ 0 при й -~ оо.
2. Общий елучай 3 а д а ч а 2, Найти ага ппп гь (х) для заданной выпуклой функкех ции 1, . В"-» В' и множества Х, задаваемого соотношением Х = (х ! !1 (х) ( О, х Е В"), где 1,: В'- В' — непрерывная выпуклая функция. Алгоритм 2 Н а ч а л о. 1. Выбрать выпуклое замкнутое множество Хы содержащее Х. П. Положить й = О. Ос н о в н о й ц и к л. П1. Решить задачу выпуклого программирования х'=-агд ппп 1,(х). «ЯХ, 1Ч. Если !1 (х') ( О, то положить хч= х" и прекратить вычисления; иначе перейти к шагу Ч.
Ч. Вычислить опорный вектор 7 1,(х") функции 1, в точке хь. Ч1. Построить множество Х4+~1,'Хь П (х)1„(х')+(Ч1,(х'), х — хь)(0, хЕВ"). ЧП. Положить й = й + ! и перейти к шагу П1. Множества Х„строят таким образом, чтобы решение втой задачи было проще, чем решение исходной задачи 2. Теорема 2. Если: (1) — !, (х) — равномерно выпуклая функция на множестве Хч; (В) — Х, — вьтуклое и замкнутое множество; (В!) — 1, (х) — непрерывная выпуклая функция, удовлетворяюшря условию Липшица на Х, то для бесконечной последовательности (х")Г ь, порожденной алгоритмом 2, справедливо: !) !!ш!„(хь)(/;!~ш!п~,(х), !ип1,(х')(О; кех 2) если, кроме того, ~,(х) — корректное ограничение и !ь (х) удовлетворяет условию Лияшица на множестве Х„то )пп х' = х', х' ~ Х; 1, (х") = Я; Иш ~, (х') = ~;; Ф 3) если, кроме того, (, (х) — сильно выпуклая функция и существует внутренняя точка х множества Х, такова, что 7, (х) (О, то имеют место следующие оценки сходимости: ! (х") — ~„'(а,lй, ~,( х" — х" ( а,ф Й, а, ( оо, 34$ 8.
Метод отсечения с растяжением иростраиства дяя регяеиия вадач выиуиного ирограммировання 3 а д а ч а 3. Найти агя ппп !с (х) для заданной функции «сх !е: Л"-» В' и заданного множества Х1~(х)!,(х)(О, ! = 1, ..., т, хЕВ"). Предположения 3. (1) — функции !о ! О, 1, ..., и — непрерыв- ны и выпуклы.
Данный метод отсечения с растяжением пространства гаранти- рует уменьшение объема области, в которой локализируется опти- мум, со скоростью геометрической прогрессии, причем знаменатель прогрессии зависит лишь от размерности задачи. Этот алгоритм относится к классу алгоритмов обобщенного градиентного спуска с растяжением пространства в направлении градиента, Кроме того, его можно рассматривать как метод отсечения, в котором операция растяжения пространства используется для снмметризации облас- ти, в которой локализован оптимум. Алгоритм Я Н а ч а л о. 1. Выбрать начальное приближение х' Е В" н чис- ло у ) О, удовлетворяющие условиям теоремы 3; положить Вс = ! (! — единичная матрица), а также р,=у/(и+1), р= )l —,, й=О. О с н о в н о й ц и к л. П.
Вычислить вектор яс(х'), если шах 1, (х")(О; 1бг<м дм(х'), если шах 1,(х")~!м(х"))О, 1<(бм где д, (х'), 1 = О, 1, ..., т — субградиенты (обобщенные градиен- ты) функций 1,, г' = О, 1, ..., и соответственно, 111. Если д (х') = О, то положить х*= х' и прекратить вычис- ления; иначе перейти к шагу 1Ч. 1Ч.
Вычислить новое направление Р для растяжения простран- ства 3с = Вта(хаУ(1 Втй(х") (, где Вс — матрица, транспонированная к матрице В„. т Ч. Вычислить следующее приближение хе+' = хс — реВсз». Ч1. Вычислить матрицу Ве» ь которая по существу является обратной к результирующей матрице Ае« ~ растяжения пространства после (я + 1)-го шага с коэффициентом растяжения сс = 1!р Ваы = В„а,т, 846 где бз $») — оператор растяжения пространства в направлении $» с коэффициентом 3 (определение оператора растяжения пространства приведено в з 3.2). Ч11. Вычислить значение шагового множителя р»+! = р» —.— ~Гла ЧШ. Положить й = я + 1 и перейти к шагу 1!.
Теорема 3. Если выполнено предположение 3 и существует оптимальная точка х* (не обязательно единственная), находящаяся в шаре радиусом у с центром в точке хо, то последовательность (х»)Г о, порожденная алгоритмом 3, удовлетворяет неравенствам 1А»(х» — х*) )(р» (и+ 1), (з.ез) где А»~5В»', й=О, 1, .... Замечание 3. Неравенство (5.65) дает полезную геометрическую интерпретацию метода, так как множество точек х, удовлетворяющих неравенству ~ А» (х» — х) (! ( (и + 1) р» = у ( ), представляет собой эллипсоид Ф», объем которого '!Ул — )/ где Уо — объем единичного п-мерного шара. В связи с этим объем эллипсоида, в котором локализуется оптимальная точка хо, убывает со скоростью геометрической прогресГг~ — ! ! л сии со знаменателем о = ~ — =~ (1.
Замечание 3'. К алгоритму 3 приводит также схема последовательных отсечений (4111. Действительно, если рассмотреть шар Зо с! (х ~ (! х — хо !) ( 7) и провести гиперплоскость (у (хо), х— — х') = О, то область локализации хо, очевидно, сужается до половины шара 3 = Зо П По, где П, Ь (х ~ (у (хо), х — х') ( О). Если теперь описать вокруг шара Я эллипсоид минимального объема, то его центр будет л+ ! Пт(хо)1 л+! т. е. 'будет совпадать с х'. Если теперь произвести растяжение пространства в направлении то в растянутом пространстве образом указанного о 1л (хо) 1 л эллнпсонда будет шар радиусом у с центром в точке г' л» вЂ” 1 0„(йо) х' и т.
д. 341 Ниже приводится обобщение алгоритма 3. //редположение 3'. Пусть у (х) — векторное поле, определенное на В", такое, что (д(х), х — х'))О, ЧхЕВ", где х* — искомая оптимальная точка функции /» (причем а (х) ~ О при х Ф х*). Приведем пример определения векторного поля д (г). Пусть задана выпукло-вогнутая функция /(х, у) двух векторных перемен ных хс В", уЕ В". Обозначим г = (х, у) Е Л" х В !,'»В"+ . Сформируем векторное поле д (г) следующим образом: к (г) = Ж (г) — а! (гИ а! (г) 6 6! (г) а!" (г) Е Ж (г), где 6! (х, у) — множество частных субградиентов (обобщенных градиентов) функции / (х, у), которая рассматривается как функция от х при фиксированном у; О/ (х, у) — множество частных субградиентов от функции / (х, у) по у при фиксированном х. Алгоритм 3' Н а ч а л о.
1. Выбрать начальное приближение х» ~ В", лежащее на расстоянии, не превышающем у от искомой оптимальной .!/н — ! точки х, положить В»= /; р = у/(п+ 1); !1 = у +, й = О. О с н о в н о й ц и к л. П. Вычислить вектор у (х») — значение векторного поля, определенного согласно предположению 3', в точке х». П1. Если д (х») = О, то положить х*= х' и прекратить вычисления; иначе перейти к шагу 1Ч. 1Ч. Вычислить вектор $» направления растяжения пространства Р= В»а(х)/)В»а(х)Ъ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
