Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
(z'-z(X), X) >0, т.е. (Zt, X) 3= F(X).
Ho z* = {z0, 0, ..., 0}, т.е. (z*, X) = z0. Точно так же величина F(Xt) = (z*, Xt) = Zt0. Итак, F(X) *? (z*, X) = (z*, X*) = F(Xt). Теорема доказана.
Для того чтобы на основе этой теоремы построить достаточно эффективные алгоритмы, нужно указать способ вычисления градиента F^(X). Этот вопрос (и это очень важное обстоятельство) допускает совсем простое решение.
Теорема 2. Пусть 3) — строго выпуклая ограниченная область. Тогда функция F(X) дифференцируема и ее градиент вычисляется по формуле ^
= z(X) = arg min (z, X).
ze.9>
§ 26]
ПОИСК МИНИМУМА
423
He проводя полного доказательства, укажем его основные моменты. Начнем с формального вычисления производной:
™=|-(z(X),X)=^X + z(X).
Строками матрицы z} являются векторы Oz(X)ZdXj. Если граница области 3! в точке z(X) имеет касательную гиперплоскость, все эти векторы лежат в ней, так как при малом изменении X точка z(X) непрерывно перемещается по дЭ). А так как в этом случае X есть нормаль к касательной гиперплоскости, то ZxX = O. Если z(X) есть угловая точка границы дЗ>, то при малом изменении X точка z(X) не смещается и Zx(X) =0. Мы опускаем анализ смешанных ситуаций, когда граница дЯ> в точке z(X) имеет характер «ребра».
Перейдем к описанию алгоритма решения задачи (1), (2) на основе доказанных теорем. Задаем начальные значения х и X. Фиксируя X, начинаем поиск min.S?(;t, X) из заданной точки х. Получаем новую
X
точку Jt(X). Тогда F(X) = _S?(jt(X), X), a OF(X)ZdXj = /'(jt(X)). В общем случае /' ^ 0, поэтому делаем пересчет множителей Лагранжа с целью максимизации J?:
Xi==X^sZi(Jt(X))5 і = 1,2, ...,/. (?)
Реализация этого алгоритма связана с двумя достаточно сложными вопросами. Первый вопрос: с какой точностью находить Jt(X)? Решая эту задачу слишком точно, мы затратим, видимо, без особой нужды слишком большое машинное время. Решая задачу слишком грубо, мы рискуем снизить эффективность процесса в целом. Второй вопрос — выбор шага s в (7).
Ограничимся постановкой этих вопросов, адресуя читателя, интересующегося их решением (решения могут быть различными; их основа — не строгие теоремы, а различного рода эвристические соображения) к специальной литературе. Алгоритмы такого сорта оказываются достаточно эффективными, но подчеркнем еще раз, что существенной предпосылкой их применимости является строгая выпуклость множества достижимости. А это свойство нельзя считать типичным в прикладных задачах, оно встречается достаточно редко.
Метод штрафных функций. Следующая простая конструкция одно время была очень популярна среди теоретиков оптимизации. Решение задачи на условный экстремум (1), (2) «сводится» к решению задачи на безусловный экстремум для функции
F(x, А) = /°(дг) + Л 2 Ufi(X) - F+}1 + [FJ - Zi(X)M). (8)
І ~1
424
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
Здесь [а]+ = а, если а > О, |а]+ = 0 в противном случае; А — большой коэффициент «штрафа» за нарушение условий.
Функцию F(x, А) называют «штрафной функцией». Сведение задачи (1), (2) к минимизации F(х, А), разумеется, приближенное, но тем более точное, чем больше А. К сожалению, практика применения метода оказалась не очень успешной. Введение в конструкцию (8) большого параметра А приводит к тому, что в точках х, где f‘(x) г» 0 (i = 1, 2, 3, ...), функция F оказывается очень негладкой, имеет сложное «овражное» строение и очень трудно минимизируется.
Скорость сходимости методов поиска минимума оказывается столь медленной, что точки «минимизирующей» последовательности Xі практически «стоят на месте», и это часто принимают за достижение минимума. Таким образом, метод дает неверные результаты, которые нередко принимаются за решение сложных задач. Полезно еще раз отметить, что эффективность методов приближенных вычислений существенным образом связана с гладкостью используемых функциональных зависимостей. Метод штрафных функций достигает своих целей (замена задачи на условный экстремум задачей безусловной оптимизации) ценой именно этого важнейшего фактора, делая из «хороших» функций f'(x) «плохую» функцию F (см. (8)).
Недостатки метода пытаются преодолеть следующим образом. Параметр А сначала берется не очень большим, так что свойства гладкости F еще немногим хуже свойств /. Найденное решение задачи х(А) = arg min F(x, А), конечно, сильно нарушает условия
/' = 0 (i = 1, 2, 3, ...), и его используют как начальное приближение в задаче с несколько увеличенным значением А, и т.д. Однако и эта идея не привела к очень уж большим успехам.
Метод модифицированной функции Лагранжа. Перейдем к одной из наиболее удачных вычислительных конструкций. Исходная задача заменяется следующей:
min F(x, А) при условиях f‘(x) = 0, і =1,2, ...,/. (S)
X
Суть дела в том, что теперь параметр А принимает умеренные значения. Его цель — сделать границу области достижимости выпуклой вниз (хотя бы локально, в окрестности искомого решения; см. рис. 47). Применим к задаче (9) алгоритм выпуклого программирования.
