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

Оптимизация: советы и приемы

В этой статье мы рассматриваем типичные проблемы, возникающие при оптимизации и нелинейной аппроксимации. Мы постарались собрать примеры, наиболее полно покрывающие различные аспекты оптимизации.

Содержание

    1 Общие вопросы
           Переменные, сильно различающиеся по величине
           Функции с сингулярностями

Общие вопросы

Переменные, сильно различающиеся по величине

При решении практических задач параметры могут очень сильно различаться по своей величине. Например, один параметр может принимать значения в диапазоне 10 9...10 10, а другой быть примерно равен 1. Такие задачи называются плохо отмасштабированными.

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

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

Функции с сингулярностями

Довольно-таки часто приходится решать задачи с функциями, определенными только на ограниченной области, и имеющими сингулярность на границе области определения. Например, функция f(x)=(1+x) -0.2+(1-x) -0.3+x (см. первый график ниже) определена только на внутренних точках отрезка [-1,+1] и имеет сингулярности на его границах.

Минимум функции находится во внутренней точке отрезка, где функция непрерывна. Но в процессе поиска решения алгоритм оптимизации может случайно "заглянуть" за границы отрезка [-1,+1]. Что произойдет в этом случае? Скорее всего, ваша программа рухнет из-за исключения при возведении отрицательного числа в дробную степень. Как альтернативный вариант, в качестве результата будет возвращено специальное значение NaN, и программа рухнет чуть позднее, когда оптимизатор не сможет справиться с нечисловым значением целевой функции. Попытка использовать алгоритм BLEIC с простыми ограничениями -1≤x≤+1 не поможет. Алгоритм все равно будет вычислять функцию на границе, в сингулярной точке. Можно было бы использовать ограничения вида -0.999≤x≤+0.999, но это поставит нас перед сложным вопросом - сколько девяток после запятой нам надо?

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

Эта модификация не меняет решение задачи. Зачем же она нужна? А нужна она вот для чего. Если алгоритм пытается вычислить целевую функцию в сингулярной точке (либо за пределами области определения), то вы можете вернуть в качестве результата какое-нибудь большое значение (мы рекомендуем использовать 10 300). Алгоритм обнаружит, что значение функции слишком велико, намного больше значения в стартовой точке, и "подрежет" функцию: снизит её величину до безопасного уровня, который не приведен к переполнению, и обнулит градиент. В результате при попытке совершить шаг в запрещенную область алгоритм будет мягко возвращен обратно.

Документация к пакету ALGLIB включает в себя несколько примеров, демонстрирующих этот прием: mincg_ftrim, minlbfgs_ftrim, minbleic_ftrim. Все эти примеры демонстрируют решение одной и той же проблемы, различаются только используемые оптимизаторы.

Замечание #1
Некоторые пользователи пакета пытаются использовать этот прием для оптимизации с ограничениями на переменные. Не делайте так - этот прием не будет работать! Он работает только в том случае, когда минимум функции достигается во внутренней точке области - там, где функция непрерывна. В этом случае "обрезка" функции не меняет её гладкость в окрестностях минимума. Если же минимум достигается на границе, то "обрезка" сделает функцию негладкой, и алгоритм оптимизации застрянет при первом же контакте с границей. В таких случаях используйте специализированные алгоритмы для оптимизации с ограничениями, входящие в ALGLIB.

Замечание #2
Мы рекомендуем возвращать большое число (10 300) не только когда мы находимся точно в сингулярной точке X, но и тогда, когда мы находимся близко к ней (на расстоянии порядка ε·X, где ε - машинная точность). Это позволит нам гарантировать, что мы не переполним разрядную сетку во время промежуточных вычислений - до того, как мы передадим значение функции в алгоритм.

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.