Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 89
Текст из файла (страница 89)
Подставляя это выражение в (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 Р(х, А) = /О(х) + А ~' ((~/(х) — Р~)з + [Г,. — //(х))з). (8) / ! 424 игиелижеииые методы вычиглительиой «изики 1ч. и Здесь 1а) = а, если а > О, 1а) = О в противном случае; А — большой коэффициент «штрафа» за нарушение условий. Функцию Р(х, А) называют «штрафной функцией».
Сведение задачи (1), (2) к минимизации Р(х, А), разумеется, приближенное, ио тем более точное, чем больше А. К сожалению, практика применения метода оказалась не очень успешной. Введение в конструкцию (8) большого параметра А приводит к тому, что в точках х, где У~(х) ~ О (1 = 1, 2, 3, ...), функция Р оказывается очень негладкой, имеет сложное «овражноь~ строение и очень трудно минимизируется. Скорость сходимости методов поиска минимума оказывается столь медленной, что точки «мииимизирующей» последовательности хз практически «стоят на месте», и зто часто принимают за достижение минимума. Таким образом, метод дает неверные результаты, которые нередко принимаются за решение сложных задач.
Полезно еще раз отметить, что эффективность методов приближенных вычислений существенным образом связана с гладкостью используемых функциональных зависимостей. Метод штрафных функций достигает своих целей (замеиа задачи на условный экстремум задачей безусловной оптимизации) ценой именно этого важнейшего фактора, делая из «хороших» функций ~'(х) «плохую» функцию Р (см. (8)). Недостатки метода пытаются преодолеть следующим образом. Параметр А сначала берется не очень большим, так что свойства гладкости Р еще немногим хуже свойств ~. Найденное решение задачи х(А) = агй пйп Р(х, А), конечно, сильно нарушает условия ~' = О (1= 1, 2, 3, ...), и его используют как начальное приближение в задаче с несколько увеличенным значением А, и т.д.
Однако и эта идея не привела к очень уж большим успехам. Метод модифицированной функции Лагранжа. Перейдем к одной из наиболее удачных вычислительных конструкций. Исходная задача заменяется следующей: ппп Р(х, А) при условиях У'(х) =О, 1=1,2, ..., 1. (9) Суть дела в том, что теперь параметр А принимает умеренные значения. Его цель — сделать границу области достижимости выпуклой вниз (хотя бы локально, в окрестности искомого решения; см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
