И.В. Бейко, Б.Н. Бублик, П.Н. Зинько - Методы оптимизации и алгоритмы. Решения задач оптимизации (1121207), страница 59
Текст из файла (страница 59)
а ~в з*6х Замечание 7. Если во вспомогательной задаче (5.40) — (5.41) вместо ограничения (й, й) ( 1 поставить ограничение шах [Ь,~(1 (6.42) гй[п 1 (таким образом вспомогательная задача становится задачей линейного программирования), то для такого алгоритма теорема 7 остается в силе. Библиоерофячесжы укаягппл. Пункт 1 написан на основании работ [285, 563, 172, 574, 1751, пункты 2, 3 — на основании работ [320, 2851. При написании пункта 4 использовалась работа [5171, пункты 5 н 6 основаны на работах [95, 141, пункт 7 написан на основании работ [37, 8, 168, 189, 167, 5721. В работе [4471 изучается обобщенный алгоритм возможных направлений, объединяющий известные алгоритмы Зойтендейка и Э.
Полака. В работе [5051 разработана общая теория сходимости алгоритмов, использующих е-параметр, для устранения зигзагоподобного движения в методах возможных направлений. 5.8. Методы центров 3 а д а ч а О. Найти ага гп[п (е (х) для заданной функции «бх уз:,[[е -~ г[' и заданного множеотва Х~(к[11(х)(0, 1= 1, ..., т, хе Н"). Предположения О.
(з) — функции )П 1 = О, 1, ..., т — непрерывно дифференцируемы; (1«) — существует такая точка хе а х, что множество Х'(хе) = (х[~~(х) — ~~(хо)(0, /~(х)<0, у'=1, ..., т,) компактно и имеет внутренность. Методы центров по своей идее тесно связаны как с методами штрафных функций, так и о методами возможных направлений— их можно трактовать как не содержащие параметров барьерные методы, основанные на внутренних штрафных функциях, или как не содержащие параметров методы возможных направлений. В методах центров по заданной точке х' строится следующая точка хь+' в «центре» множества Х' (х'), т.
е. в некотором множестве точек, наиболее «удаленных» от границы множества Х'(х'). В качестве функции расстояния между точками х и х' можно взять 315 функцию д(х', х) = шах(~,(х') — Ге(х); 1!(х'), ! = 1, ..., т). (ЗАЗ! Другие способы выбора функции расстояния можно найти в (442, 497, 564). Следующая точка х+' вычисляется из условия с((ха+', ха) = ппп (с((х, х")(хС В").
(5.44! к Таким образом, как и методы штрафных функций, методы центров разбивают решение задачи О на последовательность задач минимизации без ограничений. 1. Овновной варнант Алгоритм 1 Н а ч а л о. 1. Найти точку хе С Х, удовлетворяющую условию (И) предположения О. П. Положить й = О.
Основной цикл. [П. Найти такую точку х'~В", что «! (х', хе) = ш 1п д (х, ха). (6,4$! к 1У. Если д (х', х") = О, то положить хеав х» и прекратить вычисления; иначе перейти к шагу Ч. Ч. Положить хе+' = х', й = й -(- 1 и перейти к шагу Ш. Теорема 1. Пусть выполнены предположения О и пусть, кроме того, ((И) — множество Х имеет внутренность и ее замыкание вовпадает в Х, т.
е. !и! Х = Х; («о) — ~! (х) ~ О для всех х а Е !и! Х, ! = 1, т. Если построенная алгоритмом 1 последовательность (х")а е бесконечна, то она имеет предельные точки и все они оптимальны для задачи О, а если последовательность (х») конечна, то ее последний глемент также оптимален для задачи О. На практике было обнаружено, что алгоритм 1 — незффективный в оановном из-за трудностей вычисления точки х', определяемой вогласно (5 45), которые требуют очень больших аатрат времени.
Это привело к необходимости разработки методов, которые прерывали бы отыскание точки х', когда уже найдена точка х", являющаяся «е-центром», где е выбирается по возможности малым. Опишем модифицированный метод, прерывающий поиск центра х' множества Х' (ха) после единственной итерации процедуры поиска. 2. Модвфвцврованный метод центров Алгоритм 2 Н а ч ал о.
1. Найти точку хе 5Х, для которой выполнено условие (И) предположения О. П. Положить й = О. Основной цикл. Ш. Положить х=х«. 1Ч. Вычислить решение И, = И, (х), И = И (х) задачи линейного программирования: найти ш!пИ, «„« (5.46) при ограничениях — И~+ (Ч~,(х), Ь)(0; (5.47) Ьо+ )) (х) + (Чо (х), И) ~(0, 1 = 1, ..., ш; (5.48) 1Ис )(~ 1' ~ 1~ ' п~ (И = (Ип Ьл)) (5 46) У, Если И, (х) = О, то положить х'= х«и прекратить вычисления (если х' — оптимальное решение задачи О, то Ь,(х«) йш!п(шах ((),(х*), И); ))(х*)+ «ез +(Ч))(х*), И), 1= 1...,, т)) = О, где ЗЬ(ЬЕВ !)И~)~~! 1=1, ..., и)). 3!7 иначе перейти к шагу У1. Ч!.
Вычислить наименьшее положительное значение р (х), удов- летворяющее условию Н(х+ р,(х) И(х), х) = ш)пд(х+ рЬ(х), х), и>о где д(, ) определяется формулой (5.43). Ч11. Положить х"+' = х+ р (х) Ь(х), Ь = И+ 1 и перейти к шагу 111. Замечание 2. Вектор Ь (х), вычисляемый на шаге 1У алгоритма 2, неоднозначно определяется из решения задачи (5.46) — (5.49), поскольку решение задачи линейного программирования может не быть единственным.
Считается, что Ь (х) — это любой вектор, яв- ляющийся оптимальным решением задачи (5.46) — (5.49); его мож- но получить методами, описанными в гл. 4. Замечание 2'. Точку х' р Х, т. е. начальное приближение на шаге 1 алгоритма 2 можно вычислить, применяя алгоритм 2 к сле. дующей задаче (в пространстве векторов (х„х)): ш!и (х,)г)(х) — х,(0, /= 1, ..., т), м„м причем в качестве допустимого начального решения для этой зада- чи можно взять х«Ь (х«, х«) ~ В"~', где точка х« ~ Л" — произ- вольная и х3 = шах (1) (х'), )Е (1, ..., )и)).
Найдется такое ко- нечное целое число 1, что х' = (х«, х') будет удовлетворять условиям х«( О, х Е Х. Тогда положить х' = х' и перейти к решению зада- чи 0 с помощью алгоритма 2 Теорема 2. Пусть выполнены предположения О. Тогда последовательность хе, хт, ..., построенная алгоритмом 2, либо конечна и ее последний элемент х* = хь удовлетворяет условшо Ь, (хе) = О, либо бесконечна и каждая ее предельная слочка хе удовлетворяет условию Ь, (х') = О. 3. Реалиаацвл водифицвровалвого метода цоттров с исволааеваввев метода аолотого сечевик Рассмотрим, как заменить принципиальную операцию (5.50) в алгоритме 2 другой, которую можно было бы реализовать на цифровой ЭВМ.
Простейший — это случай, когда все функции ~1 ( ), 1 = О, 1, ..., т — выпуклы. Легко видеть, что в этом случае функция й (, х), определяемая согласно (5.43) при х Е Х, также выпуклая. Алгоритм Ю Н а ч а л о. 1. Выбрать числа е, ) О, р ~ 1 и т1 ) 1 (обычно 11 = 2), П. Вычислить начальное приближение х' ~ Х. П1. Положить Ь = О. Основной цикл. !Ч. Положить х=х'. Ч. Решить задачу линейного программирования (5,46) — (5.49) и получить (и+ 1)-мерный вектор (Ь, (х), Ь (х)). Ч1.
Если Ь, (х) = О, то положить хе+' = ха н прекратить вычисления; иначе перейти к шагу ЧП. Примечание. Следующие далее шаги ЧП вЂ” Х заменяют шар Ч1 алгоритма 2 при вычислении величины р (х). НП. Для Л в О положить Е(Л) =й(х+ЛЬ(х), х). (ая1) ЧП1.
Положить е, = е, и 1 = О. 1Х, Использовать для вычисления р алгоритм поиска минимума одномерной функции по методу золотого сечения (см. р 2.4, алгоритм 2В), где 8 ( ) определяется равенством (5.51), р определяется на шаге 1и е=е,. Х. Если й (х+ рЬ (х), х) ( — е„то положить )т (х) = р и перейти к шагу Х1; иначе положить е~+1 = е,l!), ! 1+ 1 и перейти к шагу 1Х, Х!.
Положить хл+' = х+ 9 (х) Ь (х), Ь = Ь+ 1 и перейти к шагу 1Ч. Теоремой. Пусть выполнены предположения О и пусть функции 11 ( ), 1 = О, 1, ..., т — выпуклы. Тогда последовательность хе, х', ..., построенная алгоритмом д, либо конечна и ее последний элемент ха+' = хе удовлетворяет условию Ье (хе) = О, либо бесконечна и тогда каждая ее предельная точка хе удовлетворяет условию Ь, (х*) = О. Замечание д. Можно построить другие реализации алгоритма 2, 313 заменяя операцию (5.50) на шаге Ч1 любым алгоритмом поиска минимума (или стационарной точки) действительной функции одной переменной.
4. реалиеацвл модифицированного метода центров е иепольеованием фуввция прерывании На практике алгоритмы изложенного ниже типа эффективны в ситуации, когда они по существу решают много раз одну и ту же вадачу. В этом случае следует предварительно потратить определенное время на тщательный подбор «функции прерывания», которая будет использоваться, и попытаться получить алгоритм, действующий быстрее, чем алгоритм 3 о е-процедурой. Определение 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
