Основы теории оптимизации (стр. 95 )

Поэтому предпочтение отдают абсолютно устойчивым (τ ~ h), экономичным разностным схемам, в которых при переходе на очередной временной слой совершаемся всего O(N2) действий.

6. Продольно-поперечная разностная схема для уравнения теплопроводности. Экономичные разностные схемы

Введем промежуточный по t слой (т +) и рассмотрим разностную схему

(23)

Обсудим построение решения уравнения (23) на (т + 1) слое:

1) Уравнение (23.1) позволяет найти по неявной схеме относительно х1 и по явной схеме относительно х2 . Решается система с 3-х диагональной матрицей относительно переменной x1 эффективным методом прогонки по х1 при каждом k (k - раз прогонка с О(N) действий O(NK) действий).

2) Уравнение (23.2) позволяет найти по неявной схеме относительно х2 и по явной схеме относительно х1 прогонка по х2 при каждом п O(N К) действии итого О(2N К) ~ O(N2) действии.

3) Диагональные коэффициенты в соответствующих матрицах на каждом шаге преобладают — тем самым решение существует, единственно и вычисления по фор­мулам прогонки устойчивы.

4) Общее число действий при переходе на (т + 1)- ый временной слой О(30 N2 ) действий.

Другие достоинства схемы:

6.1 Устойчивость продольно-поперечной схемы

Воспользуемся методом гармоник. Рассмотрим

(свои множители роста на каждом полуслое). Тогда (23.1):

т. e.

всегда! р и q. Таким образом схема (23) безусловно (абсолютно) устойчива пo начальным данным (и по правой части тоже).

Для рассмотренной схемы имеет место абсолютная устойчивость в С но начальным условиям и по правой част.

Осталось установить аппроксимацию.

6.2 Аппроксимация продольно-поперечной схемы

Исключим из (23) слой . Для этого вычтем уравнения (1)-(2), найдём:

(*)

Складывая уравнения (1) - (2), найдем:

Откуда, с учетом (*), получим

Итак, это почти симметричная схема с σ1 = σ2 =, тем самым — схема обладает аппроксимацией при условии и порядок аппроксимации

Схема (23) безусловно устойчива и обладает повышенной аппроксимацией, следова­тельно она сходится в указанной прямоугольной области на равномерной сетке и обладает точностью не хуже, чем

Замечания:

1) Схема обладает той же сходимостью в С.

2) Для обеспечения указанного порядка точности разностной схемы грс-бусчся, чтобы решения исходной задачи обладали гладкостью не хуже, чем

Приложение 3

Downloads page

ALGLIB User Guide - Одномерная и многомерная оптимизация - L-BFGS алгоритм минимизации функции многих переменных

L-BFGS алгоритм минимизации функции многих переменных

Об алгоритме

Квази-Ньютоновские методы: принцип работы

Классический метод Ньютона ипользует гессиан функции. Шаг метода определяется, как произведение матрицы, обратной к гессиану, на градиент функции. Если функция является положительно определенной квадратичной формой, то за один шаг данного метода мы окажемся в её минимуме. В случае знаконеопределенной квадратичной формы, у которой нет минимума, мы сойдемся к седловой точке или к максимуму. Одним словом, метод ищет стационарную точку квадратичной формы.

На практике обычно приходится иметь дело с функциями, не являющимися квадратичными формами. Если такая функция гладкая, то в окрестностях минимума она достаточно хорошо описывается квадратичной формой, чтобы метод Ньютона сошелся к минимуму. Но с тем же успехом он может сойтись к оказавшемся рядом максимуму, совершив шаг в направлении возрастания функции вместо шага, уменьшающего значение функции.

Квази-Ньютоновские методы решают эту проблему следующим образом: вместо гессиана используется его положительно определенная аппроксимация. Если гессиан положительно определен, то мы совершаем шаг по методу Ньютона. Если гессиан знаконеопределен, то перед совершением шага по методу Ньютона мы модифицируем гессиан так, чтобы он был положительно определен.

Смысл данного подхода в том, что шаг всегда совершается в направлении убывания функции. В случае, если гессиан положительно определен, мы используем его для построения квадратичной аппроксимации поверхности, что должно ускорить сходимость. Если гессиан знаконеопределен, то мы просто движемся в направлении убывания функции.

Выше было сказано, что мы совершаем шаг по методу Ньютона. На самом деле это не совсем так - таким образом мы лишь определяем направление, в котором будет совершаться шаг. Некоторые модификации квази-Ньютоновских методов проводят вдоль указанной прямой точный линейный поиск минимума, но доказано, что достаточно добиться лишь существенного уменьшения значения функции, а искать точный минимум не обязательно. Данный алгоритм сначала пытается совершить шаг по методу Ньютона, а если он не приводит к уменьшению значения функции, то ищется шаг в том же направлении, меньший по величине и уменьшающий значение минимизируемой функции.

L-BFGS схема обновления гессиана

Гессиан функции доступен далеко не всегда, гораздо чаще мы можем вычислить только градиент функции. Поэтому используют следующую схему работы: на основе N последовательных вычислений градиента строится гессиан функции и совершается квази-Ньютоновский шаг. Существует специальная формула, позволяющая итеративно получать аппроксимацию гессиана, причем на каждом шаге аппроксимирующая матрица остается положительно определенной. В данном алгоритме используется BFGS-схема обновления, названная по первым буквам имен Broyden-Fletcher-Goldfarb-Shanno (если быть точным, то эта формула строит не сам гессиан, а обратную к нему матрицу; таким образом, не надо тратить время на её обращение).

Буква L в названии схемы происходит от слов "limited memory". В случае больших размерностей объем памяти порядка N 2, требуемый для хранения гессиана, оказывается слишком большой нагрузкой, также как и затраты машинного времени на его обработку. Поэтому вместо использования N значений градиента для построения гессиана можно обойтись меньшим числом значений, позволяющим использовать объем памяти порядка N·M. Обычно на практике M выбирают в промежутке от 3 до 7, в сложных случаях можно увеличить эту константу до 20. Разумеется, в результате такой экономии мы получим не сам гессиан, а лишь его аппроксимацию. С одной стороны, при этом замедляется сходимость. С другой, скорость работы может даже вырасти. На первый взгляд парадоксальное, это утверждение не содержит противоречий: сходимость измеряется числом итераций алгоритма, в то время, как скорость работы - числом тактов процессора, потраченных на вычисления.

Вообще-то говоря, изначально этот метод разрабатывался для оптимизации функций очень большого числа аргументов (сотни и тысячи), поскольку именно в этом случае увеличение числа итераций из-за пониженной точности аппроксимации гессиана полностью окупается снижением накладных расходов на обновление гессиана, однако нет причин, по котором этот метод нельзя применять для задач малой размерности. Основным его достоинством является масштабируемость, поскольку он обеспечивает высокое быстродействие на задачах большой размерности, при этом позволяя решать и задачи малой размерности.

Разностные схемы и аналитический градиент

Если известен градиент функции, то алгоритму требуется намного меньше итераций для сходимости, чем методам, не использующим информацию о градиенте. Одно значение градиента в плане информативности эквивалентно N значениям функции, так что такое различие в быстродействии вполне объяснимо. Вместе с тем, многое зависит от того, как именно вычисляется градиент. Если градиент вычисляется по разностной схеме, то уменьшение числа итераций будет компенсировано пропорциональным ростом их трудоемкости из-за использования разностной схемы. Если градиент известен в аналитической форме и эффективно вычисляется, то L-BFGS алгоритм будет значительно быстрее.

Замечание
Не вычисляйте градиент функции на основе двухточечной разностной формулы - она недостаточно точна. В ряде случаев алгоритм просто не сможет работать, и завершится с сообщение об ошибке. Используйте хотя бы четырехточечную формулу.