Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
§26
ПОИСК МИНИМУМА
409
неявно используется при решении задачи методом сеток, когда берутся сетки из 1020 узлов. Вывод из проведенного обсуждения почти очевиден: возможности метода квазиобращения, видимо, достаточно ограничены, и пользоваться им следует осторожно.
§ 26. Поиск минимума
Приведем общие сведения о методах решения так называемой задачи математического программирования. Это название в современной литературе присвоено задаче на условный экстремум. Общая ее формулировка такова. Требуется найти точку х (из Rn), минимизирующую значение функции /°:
min f°(x), (1)
X
при условиях
а) X- ^ Xn ^ п = I, 2, ..., N, (2)
б) FTKfi(X)^Ft, і =1,2,...,1.
Здесь f‘(x) — заданные функции, которые, если не оговорено иное, предполагаются гладкими (например, имеющими вторые производные); Xn, Xn, FJ, Ff — заданные числа.
Начнем обзор методов решения с простейших вариантов этой общей задачи.
Поиск безусловного минимума. Имеется в виду задача (1). Никаких условий и ограничений на диапазон изменения х нет. Конструкции алгоритмов решения этой задачи основаны на идеях, которые, соответственно усложняясь и модифицируясь, используются и при решении общей задачи. Основная идея заключается в построении минимизирующей последовательности точек Xі. Начиная с некоторой заданной точки X0 (начального приближения) строят последовательность точек Xі, X2, X3, ... таким образом, чтобы значение /° монотонно понижалось:
f°(xJ+l) < f°(xj), Iim Z0(Xy) = min f°(x).
j-> CO
Эта общая идея конкретизируется построением алгоритма «улучшения» текущей точки xj: если она не является точкой минимума, в ее окрестности должна найтись другая точка xJ+l, в которой f°(xi+l) < f°(xJ). Есть несколько способов найти такую точку.
410
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
Метод покоординатного спуска. Точка xj+i ищется в виде Xі + sek, где ек — &-й орт в пространстве Rn. Скалярный параметр s («шаг спуска») определяется задачей того же типа:
min f°(xJ +
seIt)'
Ее решение (так называемый линейный поиск) осуществляется специальными алгоритмами (разумеется, приближенно), они описаны в специальной литературе. Что касается индекса к, то он меняется на каждом шаге j, циклически пробегая значения 1, 2, ..., N.
Алгоритм достаточно прост, но возникает вопрос: к чему он сходится, действительно ли он позволяет отыскивать точку минимума? Мы не будем рассматривать ситуации, когда точки Xі уходят в бесконечность, когда f(xj) -* — оо и т.п. Предположим, что все Xj остаются в ограниченной области пространства Rs. Следовательно, имеется предел Iim Xj = х* (либо предел какой-то подпоследовательности *Л). Что можно сказать о такой точке х*1 Очевидно, она является стационарной точкой метода, т.е. если задать х* в качестве х°, то попытки переместиться из нее по любому из ортов ек ни к чему не приведут.
Очевидно, стационарными для метода покоординатного спуска являются точки, в которых
Qf0(Xt)IdXk = 0, d2f(x')/dx\> 0, к= 1,2, ..., N.
Однако точка х* может и не быть точкой минимума, даже локального; она может быть точкой перегиба. Если метод приведет в такую точку, процесс изменения Xі прекратится. Однако вероятность попасть в подобную точку не очень велика, так как в ее окрестности есть точки со значениями f(x) < f(x'), и если хоть одна точка Xі именно такова, то в дальнейшем точки xj+1, ... не приблизятся к Xt.
Наиболее вероятным результатом описанного процесса является сходимость последовательности Xj к точке локального минимума /°(дс). Подчеркнем — именно локального, а не точного, «глобального» минимума. Если функция /°(х) имеет несколько точек локального минимума, результат, естественно, зависит от выбора стартовой точки х°.
Каждая точка локального минимума х* имеет свою «область притяжения» — совокупность точек х°, начиная с которых процесс спуска приводит именно к точке х*. Это относится и ко всем остальным методам построения минимизирующих последовательностей. Они отличаются друг от друга в первую очередь способом построе-
§26]
ПОИСК МИНИМУМА
411
ния направлений спуска. Легко понять, что для таких методов области притяжения к той или иной точке локального минимума практически одинаковы.
Метод спуска по градиенту. Более эффективным является метод, отличающийся от описанного выше только выбором направления спуска. В каждой точке Xі вычисляется градиент fx(xJ), и следующая точка ищется как точка минимума функции /° на луче x(s) = xJ — sf°(xJ). Очевидно, множество стационарных точек процесса здесь шире — это все точки, в которых /°(х) = 0. Однако наиболее вероятным исходом является СХОДИМОСТЬ Xі к точке локального минимума.
Метод спуска по градиенту можно получить, применяя к задаче одну из самых плодотворных в вычислительной математике конструкций — линеаризацию в окрестности текущего приближения и решение последовательности линейных задач (вспомним в связи с этим метод Ньютона). Кстати, мы не доказываем теорем о сходимости методов спуска, так как они дословно повторяли бы доказательство сходимости модифицированного метода Ньютона (см. § 1). Итак, в точке Xj найдем х*+{ = Xj + Ьх, где поправка Ьх является решением линеаризованной задачи
