Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Классификация методов локальной оптимизации
Методы поиска локального экстремума принято ранжировать следующим образом [12-18]: 1. Метод Ньютона и его модификации. 2. Квазиньютоновские методы. . Градиентные методы. . Методы прямого поиска. Согласно этой классификации первенство держат ньютоновские методы, поскольку использование информации второго порядка обеспечивает им высокие скорости сходимости и позволяет делать качественные выводы относительно найденного численного решения. Когда получение аналитических выражений первых и вторых производных затруднено, лучшим будет использование квазиньютоновских методов с конечно-разностной аппроксимацией производных. Градиентные методы значительно уступают по своей эффективности ньютоновским и квазиньютоновским вследствие низких скоростей сходимости, но наиболее широко используются из-за простоты реализации. Методы прямого поиска при минимизации используют только значения целевой функции, поэтому они гораздо менее эффективны, чем градиентные, в тех случаях, когда последние применимы. Таким образом, чем больше информации о производных, которую можно получить ценой приемлемых затрат, будет использовано при решении задачи, тем лучше. Большинство методов минимизации являются итерационными по своей природе. Это означает, что, начиная с заданной точки , называемой начальным приближением, в дальнейшем получается последовательность точек , которая, в принципе, должна сходится к точке минимума целевой функции . Вычисление называется k -й итерацией, а точка - k -м приближением. В результате основное уравнение для k -й итерации записывается в виде:
, ,
где - скалярная величина (длина шага), обеспечивающая неравенство , - направление поиска, правила вычисления которого «определяют лицо алгоритма» минимизации и его эффективность. Так, в методе Ньютона направление поиска определяется системой линейных алгебраических уравнений:
,
где - матрица Гессе, матрица вторых частных производных, а - вектор градиента функции . Необходимо заметить, что численное определение матрицы Гессе на каждой итерации существенно снижает скорость сходимости (из-за наличия ошибок округления), а также значительно увеличивает объем вычислительных затрат.
В квазиньютоновских методах направление поиска вычисляется по формуле [14,17]:
,
где - приближение обратной матрицы Гессе. Матрица на первой итерации является единичной и преобразуется от итерации к итерации в соответствии со следующей формулой пересчета:
,
где - поправочная матрица различных рангов. Существуют различные формулы пересчета приближений обращенной матрицы Гессе, использующие поправки разных рангов [14, 17]: 1. Симметричная формула ранга один (SR1-формула):
,
где , а - соответствующее приращение градиента. 2. Формула Бройдена-Флетчера-Гольдфарба-Шанно (BFGS-формула):
, где . 3. Формула Дэвидона-Флетчера-Пауэлла (DFP-формула):
.
В последнее время в литературе, посвященной квазиньютоновским методам, был предложен ряд алгоритмов, использующих иную схему безусловной минимизации [14, 18]. Она отличается от классической квазиньютоновской схемы тем, что предполагает непосредственную оценку прямой матрицы Гессе , а не обратной к ней. В этом случае направление спуска определяется из уравнения:
,
которое решается с использованием разложения матрицы по методу Холесского . Каждой квазиньютоновской формуле для пересчета оценки обратной матрицы Гессе , соответствует (в том смысле, что из следует , где - единичная матрица) преобразованная формула пересчета матрицы [14, 15, 18]: 4. Преобразованная симметричная формула ранга один (SR1-формула):
, где .
5. Преобразованная BFGS-формула:
.
6. Преобразованная DFP-формула:
, где .
Следует отметить, что преобразованные формулы не содержат операции умножения матрицы на вектор. Имея разложение Холесского матриц , можно получать оценки их чисел обусловленности. Так справедливо неравенство [14] , где - максимальный и минимальный диагональные элементы фактора . На промежуточных операциях такие оценки позволяют выявить ситуации, когда матрица обусловлена так плохо, что вычисляемый вектор из-за ошибок округления не будет направлением спуска. При этом факторы разложения можно подправить так, что обусловленность реализующей матрицы станет приемлемой [14, 15].
Помимо этого, использование факторизации Холесского позволяет избежать потери положительной определенности матриц , что имеет место в обычных квазиньютоновских методах из-за ошибок округления. Эта проблема возникает при практической реализации алгоритма и, как правило, опускается в теории. Утрата положительной определенности нежелательна, поскольку это приводит к внесению в квазиньютоновскую аппроксимацию матриц () ошибочных поправок, уничтожающих накопленную информацию о кривизне . Следствием этого является то, что вектор может указывать в сторону возрастания минимизируемой функции. При этом по данным функционирования обычного (без факторизации) квазиньютоновского алгоритма невозможно определить момент утраты положительной определенности . Таким образом, при реализации квазиньютоновского метода необходимо обеспечить численную положительную определенность приближений матрицы Гессе (или обратной к ней). Используя в квазиньютоновском поиске факторизацию Холесского, легко обеспечить положительную определенность матрицы [14, 17]. Для этого на очередном шаге вычислений коэффициентов множителей Холесского соответствующий диагональный элемент матрицы увеличивается настолько, чтобы окончательное произведение было положительно определенным и хорошо обусловленным. Когда этот элемент выбран, очередной столбец множителя однозначно определяется требованием совпадения матриц и . Таким образом, в результате получается представление:
,
где - неотрицательная диагональная матрица, равная нулю, если матрица существенно положительно определена. Методы сопряженных градиентов относятся к классу алгоритмов минимизации, в которых вычисление направлений поиска не предполагает решения каких-либо систем линейных уравнений. Это принципиально отличает их от методов Ньютона и квазиньютоновских методов [12, 14]. ожно показать [12, 14], что направление для очередной итерации в методе сопряженных градиентов при минимизации квадратичных функций вычисляется как линейная комбинация градиента в текущей точке и предыдущего направления :
,
где вычисляются по следующим теоретически эквивалентным формулам [12]:
Формула Флетчера-Ривса: . Формула Полака-Рибьера: .
Теоретически этот метод конечен [12]: при точных вычислениях он должен найти решение не более чем за n шагов. Метод сопряженных градиентов легко обобщается на задачи минимизации нелинейных функций общего вида. Для этого надо заменить используемую в нем формулу расчета какой-нибудь процедурой одномерного поиска и уточнить, будет ли направление всегда вычисляться по формуле (2.2-17) или допускаются периодические отступления. Последние принято называть рестартамиили восстановлениями [11, 14]. Можно, например, принимая во внимание n -шаговую теоретическую сходимость в квадратичном случае, через каждые n шагов отказываться от направления (15) и брать в качестве очередного антиградиент . Соответствующий метод называют традиционным [11]. Традиционный метод сопряженных градиентов сходится в тех же предположениях, что и метод наискорейшего спуска [11,15]. Для достаточно широкого класса функций теоретическая скорость его сходимости при точной одномерной минимизации оказывается n -шаговой сверхлинейной. Однако, как показывает практический опыт, из-за ошибок округления реальная скорость сходимости метода сопряженных градиентов почти всегда линейна независимо от того, применяются рестарты или нет [11]. Поэтому применение метода сопряженных градиентов следует считать успешным, когда удовлетворительное решение удалось получить менее чем за 5 n шагов.
В заключение следует отметить, что, хотя схема сопряженных градиентов далека от идеала, на сегодня она является единственным разумным универсальным средством решения задач безусловной минимизации с очень большим числом переменных.
|
|||||||
Последнее изменение этой страницы: 2020-03-13; просмотров: 186; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.116.40.177 (0.024 с.) |