Федоренко Р.П. Введение в вычислительную физику (1185915), страница 88
Текст из файла (страница 88)
Численное дифференцирование в принципе реша- уо о ;о ст проблему, но это требует до- ~ ы Ы полнительных вычислений х(Х). Г К тому же не хотелось бы вычислять х(А) слишком уж точно: это требует большого объема вычислительной работы. Теперь разъясним самое важное обстоятельство — сходнмость предложенной процедуры требует (и это по существу дела) предположения о выпуклости так называемой аблпсти достижииосл1и. Так называют область Я в пространстве Ф~' точек (/о(х), г1(х), ..., уг(х)), которые могут быть получены при всех допустимых х. Не будем пока давать строгих определений некоторых понятий (выпуклость, строгая выпуклость и т.п,), апеллируя к простым геометрическим образам.
На рис. 47 показаны типичные ситуации. Ось абсцисс представляет 1-мерное пространство. Точка х(А) является самой низкой точкой области Я в направлении Х. Вектор Х является 14* 4Ю пгизлвжвнныв мкгоды вычислительной «изики 1ч. ц Метод условного градиента, Более употребительна другая форма использования идей Лагранжа, к которой можно прийти разными путями. (В зависимости от этого одинаковые по существу методы получают разные названия: метод линеаризации, метод приведенного градиента и т.п.) Мы предпочтем вывести основную конструкцию иа основе линеарнзации. Итак, пусгь точка х допустима в смысле выполнения всех условий ~' =О (1= 1, 2, ..., 2). Ищем малую поправку Ьх, линеаризуя задачу н добавляя ограничение на Ьх.
Смещение Ьх определяегся задачей (3) при условиях У'(»)+У,'(х) Ьх=О, 1=1,2, ...,1. (5) Составляя для этой задачи функцию Лагранжа: .У(Ьх, Л, р) = Ув Ьх + 2,' Х,(~'+ /„' Ьх) — йз (Ьх, Ьх), находим минимум из уравнений Э.У/эЬ» = О. В результате имеем систему уравнений для Ьх, Х, р: Ь» =-'(Уэ+ ~ 1.,У„'). Подставляя это выражение в (5), получаем для Х систему уравнений с параметром р: / рУ'+ (/э, У„')+,'Р Л,.(/„', У'„) =О, 1=1,2, „1. / ! нормалью к дЯ в точке х(А), если в этой точке граница дУ гладкая (если х(А) является угловой точкой границы, Х принадлежит множеству «опорных векторовь).
Рассмотрим характерные свтуацни, представленные на рис. 47. а) Нижняя граница Ю сгрого выпукла вниз. Описанный выше метод имеет шансы на успех, так связь между Х и х(Х) однозначна: каждому А соответствует единственная точка х(Х). б) Нижняя граница Ю вогнута. Метод не будет работать, так как даже прн точном значении Х' поиск минимума .У(х, Х') приведет к далекой от решения точке х(Л), в) Нижняя граница Я строго выпукла вниз только в окрестности оси ординат. Метод имеет шансы на успех при хорошем начальном приближении, (Напомним, что, решая задачу (4), находят именно локальный минимум.) Свойства выпуклости области .У обычно неизвестны.
Поэтому метод множителей Лаграюка в той форме, в какой он описан выше, прпменяется в вычислениях редко. Перейдем к описанию второго алгоритма. 421 й 261 поиск мииимтмА Решая систему уравнений дважды (один раз с правыми частями (У~, У1), второй раз с У1), находим общее решение вида Л,.'+ 14Л,", после чего можно определить и из условия (Ьх, Ьх) = ез. Здесь ие случайно в задачу включены значения 2'1чьО .
Ниже нам понадобится именно такая более общая конструкция. Заметим только, что при вмчислении 14 следует выбрать решение, дающее минимум, а не максимум функции Лагранжа .У'. Итак, пусть в точке х выполнены условия 21(х) = 0 и определено возмущение Ьх, Теперь есть два способа использовать этот результат. Первый способ: формируется «линия спуска» х + з Ьл. Тогда (если в точке х выполнены условия /1 = О) можно утверждать, что — У1(х + з Ьх) ~, и = ~„'(х) Ьх, т.е.
смещение по з сопровождается линейным (по з) убыванием 2'и и соблюдением (в первом порядке) условий 2' = О. Однако мы должны выбрать какое-то конечное значение ж Работающие по вышеприведенной схеме алгоритмы различаются выбором того критерия, по которому при увеличении з падение 2п считается еще выгодным, хотя оно и сопровождается нарушением условий. На следующей итерации приходится варьировать х с учетом уже имеющихся малых нарушений в условиях /1 = О, и проблема выбора з.осложняется. Второй способ: Ьх считается уже готовой вариацией, т.е. нужно переходить к точке х+ Ьх. Здесь возникают те же, в сущности, проблемы, но они должны решаться в терминах достаточно ответственного назначения величины е (в первом способе, очевидно, величина з никакой роли не играет), Выпуклое программирование.
Перейдем к описанию некоторой общей идеи, приведшей в конечном счете к одной (из двух, в сущности) фундаментальных конструкций эффективных алгоритмов математического программирования. Предположим, что область достижимости Я есть строго выпуклое множество. Определение 1. Множество Я называют строго выпуклым, если для любых двух его граничных точек з' и з" все точки соединяющего их интервала з(з) = зз'+ (1 — з)з" (з Е (О, 1)) лежат строго внутри Ы. Можно характеризовать свойство строгой выпуклости н по-другому. Для любого вектора Л = (1, Л,, ..., Л, ) задача ппп (з, Л) имегиз1 ет единственное решение з(Л) Е дЯ.
Заметим, что граница строго вгг пгизлижанныв методы вычислитзльной ьизики 1ч, и выпуклого множества может содержать угловые точки. При этом разные Л могут дать одну и ту же точку з(Л). Все такие Л называют опорными к Ы в точке з(Л). Если граница в точке св Е дЯ является гладкой, то значение Л„, для которого х(Л ) = сш является внутренней нормалью к дЯ в точке х . Докажем важную теорему. Т е орем а 1. Если область достижимости Ы является строго выпуклой, то задача иа условный экстремум (1), (2) эквивалентна суперпозиции задач на безусловный экстремум шах ( шш.й'(х, Л)1, х чхчх где.Р(х, Л) = (1(х),Л).
Эту задачу можно сформулировать в несколько иной редакции: шах Р(Л), где Р(Л) = ппп (У(х), Л). л Х а~кх Таким образом, речь идет просто о нахождении максимума функции Р(Л) при достаточно сложном ее определении: эта функция задана алгоритмом поиска минимума. Доказательство. Пусть х' — точка, решающая исходную задачу на условный экстремум (1), (2). Существование такой точки следует из общих теорем, в которых используется непрерывность функций ), а также, например, ограниченность и замкнутость Ы. Пусть Л' — опорный вектор к дЫ в точке з' = /(х').
Покажем, что для всех Л имеет место Р(Л) ж Р(Л'). В самом деле, пусть Л чь Л'. Вычислим з(Л) и Р(Л) = (з(Л), Л). Тогда вся область Ы и, следовательно, точка х' лежат выше гиперплоскости, проходящей через з(Л) ортогонально Л: (з' — з(Л), Л) «О, т.е. (з', Л) н г(Л). Но з' = (з,*„О, ..., О), т.е. (з", Л) = з~. Точно так же величина Р(Л') = (х*, Л') = з,'>. Итак, Г(Л) н (з', Л) = (з', Л*) = Р(Л'). Теорема доказана.
Для того чтобы на основе этой теоремы построить достаточно эффективные алгоритмы, нужно указать способ вычисления градиента 1г (Л). Этот вопрос (и это очень важное обстоятельство) допускает совсем простое решение. Теорема 2. Пусть Ы вЂ” строго выпуклая ограниченная область.
Тогда функция Г(Л) дифференцируема и ее градиент вычисляетсн по формуле (б) — = з(Л) =агк ппп (з, Л). дР(Л) гвЯ «2З пОиск мии!!МумА й 261 Не проводя полного доказательства, укажем его основные моменты. Начнем с формального вычисления производной: = — ~(з(Х), Х) = А 2!+ К(7!). Строками матрицы зк являются векторы дг(?!)/дХ/. Если граница области Я в точке х(А) имеет касательную гиперплоскость, все эти векторы лежат в ней, так как при малом изменении 2! точка з(Х) непрерывно перемещается по дЖ А так как в этом случае 2 есть нормаль к касательной гнперплоскости, то з/2! =О. Если з(2!) есть угловая точка границы д///, то при малом изменении Х точка г(2) не смещается и з/(Х) =О. Мы опускаем анализ смешанных ситуаций, когда граница дЫ в точке з(Х) имеет характер «ребра». Перейдем к описанию алгоритма решения задачи (1), (2) на основе доказанных теорем.
Задаем начальные значения х и Х. Фиксируя Х, начинаем поиск пнп х (х, 2.) из заданной точки х. Получаем новую » точку х(7!). Тогда Г(2) =.У'(х(Х), 7!), а дР(Х)/дд/ = 2 !(х(Х)). В общем случае /' ~ О, поэтому делаем пересчет множителей Лагранжа с целью максимизации .У: (7) Х! != Х/+ з//(х(Х)), / = 1, 2, ..., /. Реализация этого алгоритма связана с двумя достаточно сложными вопросами.
Первый вопрос: с какой точностью находить х(2!)? Решая эту задачу слишком точно, мы затратим, видимо, без особой нужды слишком большое машинное время. Решая задачу слишком грубо, мы рискуем снизить эффективность процесса в целом. Второй вопрос — выбор шага з в (7). Ограничимся постановкой этих вопросов, адресуя читателя, интересующегося их решением (решения могут быть различными; их основа — не строгие теоремы, а различного рода эвристические соображения) к специальной литературе.
Алгоритмы такого сорта оказываются достаточно эффективными, но подчеркнем еше раз, что существенной предпосылкой их применимости является строгая выпуклость множества достижимости. А это свойство нельзя считать типичным в прикладных задачах, оно встречается достаточно редко, Метод штрафных функций. Следующая простая конструкция одно время была очень популярна среди теоретиков оптимизации. Решение задачи на условный экстремум (1), (2) «сводится» к решению задачи на безусловный экстремум для функции l Р(х, А) = /О(х) + А ~' ((~/(х) — Р~)з + [Г,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
