О предобуславливании

Содержание

    1 Предобуславливатель
           Пример
           Когда нужен предобуславливатель
           Типы предобуславливателей

Предобуславливатель

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

Пример

Ниже приведен довольно-таки условный пример того, как предобуславливатель ускоряет решение проблемы. Оригинальная функция имеет вытянутый рельеф, и алгоритм оптимизации постоянно "рикошетирует" от стенок узкой аллеи, по дну которой он приближается к минимуму. В конце-концов он прибывает к линии уровня f=1, но для этого ему требуется четыре итерации. После масштабирования переменных рельеф становится более простым, и достаточно одного шага, чтобы оказаться намного ниже уровня f=1.

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

Когда нужен предобуславливатель

Предобуславливатель нужен:

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

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

Типы предобуславливателей

Пакет ALGLIB поддерживает несколько типов предобуславливателей:

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

Разные оптимизаторы поддерживают разные типы предобуславливателей, но первые три типа предобуславливателей доступны во всех оптимизаторах.

This article is intended for personal use only.