XIV Аттетков и др. Методы оптимизации (1081420), страница 56
Текст из файла (страница 56)
В каче- ~а,(е стве нулевого приближения (при л = 1) можно принять хе~ = х~, а условием прекращения последовательных приближений можно считать выполнение неравенства (х~ — х1 1~ ( Б, где Б > 0-- заданный параметр точности. При выполнении этого неравенства полагаем х1 = х1 и ~(х1) = 1'(х1).
Выбирая д = 0,01, получаем х' = (0,9211, 0,7191), при этом д(х1) — 0,0003. 4. Проверяем условие прекращения итераций: ~х — х ~ = (0,9211)и+ (0,7191)и = 1,168 > с = 0.,01. Так как требуемая точность еще не достигнута, поиск точки х* Е Й минимума целевой функции Т(х) на множестве Й следует продолжить. Для этого переходим к п. 1, заменив точку х~ на найденную на первой итерации точку х'.
Результаты расчетов на первой и последующих трех итерациях приведены в табл. 8.3, траектория поиска точки хл представлена на рис. 8.15. Сме Ренлейтис Г., Рейвиндран А., Рэесдел Л. 389 8.6. Другие методы провхгироваяия Таблица 8.3 Рис. 8.15 Таким образом, результат четвертой итерации с заданной точностью совпал с точным решением задачи ж* = (1, 1). При реализации изложенного алгоритма может оказаться, что в точке ж Е й, найденной на Й-й итерации, )о(ж ) ) > 1в(л~ 1).
В этом случае следует использовать модифицированный алгоритм, в котором выбор значения ягь проводится с помощью метода дробления таза, а не с помощью исчерпывающего спуска. 8.6. Другие методы проектирования Помимо метода проекции антиерадиента для минимизации целевой функции существуют близкие по своей идее методы, в которых также используется операция проектирования векто- 390 8. НИСДЕННЪ|Е МЕТОДЫ ра на некоторое подпространство.
Кратко рассмотрим некото- рые из них. Проектирование сопряженных направлений. Эффективность поиска точки х* Е Й минимума дифференцируемой целевой функции 1в(х), х е ж", на допустимом множестве Й можно повысить, если на каждой в-й итерации возможное направление спуска определять нс по антиградиенту ы" = = — 8гад1в(х ) в точке х е Й, а по одному из сопряженных направлений.
Нри этом сопряженные направления удобно находить последовательно в процессе итераций. Рассмотрим допустимое множество вида Й=(хек": (а,,х) =6„1=1,т), где векторы а, е К" линейно независимы. Согласно теореме 8.2, для поиска точки минимума функции 1в(х) на множестве Й можно использовать зада ~у безусловной минимизации функции ~Р(У) = 1в(х + Р У), У Е яс", где хв Е Й начальнаЯ точка:, Р* = 1п — А (АА ) 'А пРоекиионная матрица порядка и; 1„, единичная матрица того же порядка; А — " матрица размера гп х и, составленная из матриц- Т строк а,, ю' = 1, т.
Опишем алгоритм метода сопряженных направлений применительно к поиску минимума функции р(у) (см. 5.2). На первой итерации (к = 1) полагаем, что у" = 0 и Р' = = — ягас1р(ув), а на любой й-й итерации по точке у" " находим точку у =у +нвр", к ЕМ., (8.62) причем для направления спуска при й ) 1 имеем Р = 8™~Р(У ) + ~ ~ ( я з)~з Р ' 18'08) ~8гад~р(у~ ')(а я ~К ~Фуя ')Р 391 8.б. Другие методы проектирования Значение гее в (8.62) на каждой 1е-й итерации подбираем либо при помощи исчерпывающего спуски в направлении вектора рн, либо из условия ~р(уь) < ~р(уь 1) методом дробления шага.
Условием прекращения итераций может быть выполнение неравенства )р~) < ез, .где ез > 0 -- параметр точности поиска. Теперь перейдем в описании алгоритма к исходному аргументу х = хв + Р*у целевой функции 1в(х). На первой (й = 1) итерации по известной начальной точке х е йт", учитывая (8.44), находим р1 = — Р'8гас11в(хв). На (й — 1)-й и й-й итерациях в соответствии с (8.45) имеем х~ ' = хо+ Р'уь ' и х" = хо+ Р*уь. Вычитая из второго равенства первое, получаем хь — хн 1 = Р*(у" — у" ').
Отскеда с учетом (8.62) имеем х =х" '+иьР'рь, ЙЕИ, (8.64) причем теперь для направления спуска при и > 1, используя (8.44), можно написать Р = Р Кгае1Ь(х )+ рч,о ь — 2 2Р . (8.65) ~Р'8тае11о(хн 'Д ~Р. 8гад Д(хь — 2) ~2 Правила выбора значения иг в (8.64) на каждой й-й итерации и условие прекращения итераций остаются прежними.
Подход, в котором используется проектирование сопряженных направлений, можно обобщить на случай., когда допустимое множество П с Кв задано в виде (8.52), т.е. линейными ограничениями типа неравенства и линейными ограничениями пгипа равенства. В этом случае для поиска точки минимума квадратичной функции требуется не более и итераций".
Обобщенный приведенный градиент. Если объединить идею метода приведенного градиента с линеаризацией нелинейных ограничений, то можно построить алгоритм, позволяющий искать решение общей задачи нелинейного прогром- Смл Пшеничный Б.Н., Данилин Ю.М. 392 8. ЧИСЛЕННЪ|Е МЕТОДЫ мироеанил. Пусть требуется минимизировать непрерывно дифференцируемую целевую функцию То(х), х Е К', на множестве Й = (х Е Б'."„: ~(х) = 0), (8.66) где | (х) — непрерывно дифференцируемая векторная функция с координатными функциями Т<(х).
г = 1, т. причем т < н. Пусть в любой точке х Е й матрица Якоби функции Т"(х) имеет ранг, равный т. Обозначим,7 = (1, ...., п) и выделим подмножество >'„С,У таких и< индексов, что в некоторой точке х, Е П квадратная матрица Якоби В, этой функции но части переменных и, у Е .>„~, будет являться невырожденной и иметь обратную матрицу В„>. Как и в методе приведенного градиента, переменные х., | Е >'„, являющиеся координатами В точки х Е К~, назовем базисными, а остальные переменные хц > Е,7, =,7 ><,>,", ЯвлЯющиесЯ кооРДинатами точки хж Е Е К" ~, свободными.
Тогда функции Л(х), 1 = 1, т, можно представить в виде Т, [х, х ), г Е Хо. Согласно теореме о неявной функции [ ><), существует такая окрестность <>(х, ) точки х, Е К" ™, что в этой окрестности система и> уравнений |> (х, х ) = О, 1 = 1, т, задает непрерывно дифференцируемую функцию х (х ), х Е П(х„), причем хн(х~ ) = х|'. Из этой же теоремы следует, что матрицу Якоби |у функции х~(х' ) в точке х'~ по всем свободным переменным х, | Е,>„~, можно найти по формуле Х(х,'~) = — В„'Х„, где Х, матрица Якоби функции Т"(х) в точке х„по свободным переменным. Используя представление целевой функции в виде 1о(х) = =То(хн(х» ), х>ч) = <<>(х~) и пРавило ДиффеРенциРованиЯ слож|я ной функции, вычисляем ее градиент в точке х'„Е К" '": и(х~) = ига<1 Ч>(х~ ) = д~Х(х~) + д„'~, (8.67) где дн и д~ матрицы Якоби целевой функции по свободным и базисным переменным.
Матрицу-строку и(х~) длины 8. 7. Метод яозможяых яаяраолеяяй и — т в (8.67) называют обобхценным приведенным ерадиенхпом целевой функции относительно свободных переменных в точке х~ С Кн ~. Сравнивая его с приведенным градиентом и в (8.10), .видим, что элементы матрицы Х(х~) зависят от координат точки х„, тогда как элементы матрицы Х остаются неизменными при фиксированном наборе свободных переменных. Алгоритм минимизации целевой функции на множестве й (8.66) с использованием обобщенного приведенного градиента аналогичен описанному выше алгоритму метода приведенного градиента, но требует пересчета матрицы Х(х~ ) на каждой итерации даже при неизменном наборе свободных переменных.
Кроме того, на каждой й-й итерации вновь полученная точка х Е еен может и нс принадлежать множеству Й в силу линеаризации нелинейных ограничений типа равенства в (8.66) в окрестности точки х~ '. Поэтому дополнительно приходится находить проекцию полученной тонки х на множество Й и лишь затем переходить к следующей итерации.
Обобщенный приведенный градиент можно применить для поиска минимума целевой функции на множестве, заданном в неотрицательном ортанте К", при помощи нелинейных ограничений не только типа равенства, но и типа неравенства, в том числе с использованием нелинейных функций, значения которых ограничены и сверху, и снизу*. 8.7. Метод возможных направлений Метод проекции антиерадиенгпа, а также проектирование, сопряженных направлений и приведенного врадиента эффективны только в том случае, когда в задаче оптимизации присутствуют лишь линейные ограничения (см.
8.5, 8.6). Однако в случае нелинейных ограничений алгоритм решения оптимизационной задачи усложняется. Главный недостаток рассмотрен- *См.: Ренееатне Г., Реавиндрон А., Ряегдее К. 8. ЧИСЛЕННЫЕ' МЕТОДЫ Й=(ха~к: д(х) <О, л=1,т), (8.68) где д,(х) непрерывно дифференцируемые функции. На й-й итерации известна точка х ' Е Й. Обозначим через Хя множея — 1 ство индексов активнвгх ограничений,т.е.тех индексов л, для которых д,(х~ ) = О. Отметим, что если Хь = Я, то х~ внутренняя точка множества Й.
Рассмотрим вспомогательную задачу оптимизации: найти минимальное значение ц = шах((йгаг1Д(х" '), р), (8гадд;(х" ), р), л Е Хь) (8.69) т на множестве векторов р = (р1 ... р„) е гГ'", удовлетворяющих ограничениям ~р ~ < 1., у = 1, .п. Эту задачу можно представить как задачу линейного программирования Н вЂ” ~ пйв; (Кг ~А(*" '),Р) <Н; (8гаод,(х ), р) < ц, л Е Хе, р <1, у'=1,п; — р <1, у'=1,п. (8.70) Ясно, что допустимое множество И4 сформулированной задачи оптимизации не пусто, поскольку содержит нулевой вектор. На этом векторе значение л1 целевой функции равно нулю, ных методов состоит в том, что на й-й итерации при движении из точки ху ' 6 Й нелинейные ограничения, как правило, нарушаются. Тем не менее и в этом случае можно построить такой алгоритм выбора возможного направления спуска, что перемещение точки по этому направлению на некоторое расстояние не будет приводить к нарушению ограничений задачи.
Сначала рассмотрим задачу оптимизации, в которой целевая функция Тв(х) непрерывно дифференцируема и ограничена снизу на допустимом множеепне Й, заданном ограничениями типа неравенства. Пусть множество Й имеет вид 395 8.7. Метод яоотгожных направлений поэтому точная нижняя грань тс на множестве Игь не превышает нуля. Рассматриваемая задача оптимизации состоит в минимизации непрерывной функции (8.69) на замкнутом ограниченном множестве векторов р Е гк", удовлетворяющих условиям ~р.~ < 1, у =1, и.
Следовательно, она имеет решение, т.е. в задаче (8.70) целевая функция г1 достигает наименьшего значения в некоторой точке яь = (р, Оя), причем тгв < О. Это решение можно найти, например, .при помощи симплекс-метода. Предположим, что эта задача решена, причем получена такаа точка вв = (Р~, Уь) ЕИггг, что г1с <О. Тогда вектоРР задает возможное направление спуска из точки х~ ~ Е Й. Действительно, поскольку я" удовлотворяет огрвличепиям задачи (8.70), имеем (8гас1Ь(х~ '),р~) <тсь<0, гбтас1дс1х~ '),р")<г1г<0, гЕХМ Следовательно, р~ ~ О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
