Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

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

Содержание

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

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

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

Пример

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

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

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

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

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

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

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

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

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.