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

О масштабировании переменных

В этой статье мы рассмотрим понятие масштаба переменных и его влияние на процесс оптимизации.

Содержание

    1 Переменные с различным масштабом
    2 Нецентрированные переменные
    3 Обсуждение

Переменные с различным масштабом

Чтобы понять, какую роль масштаб переменных играет в процессе оптимизации, рассмотрим гипотетическую задачу оптимизации, пришедшую из физики элементарных частиц. Предположим, что мы обрабатываем экспериментальные данные, чтобы определить массу частицы, прошедшей через детектор, и её скорость. В нашей задаче одной из переменных является масса частицы, указанная в килограммах, а другой - скорость частицы, измеренная в метрах в секунду. Мы не знаем заранее ни массы, ни скорости, но можем предположить, что масса будет порядка 10 -27 килограмм, а скорость - порядка 10 7 метров в секунду. Что же будет, если мы попытаемся решить такую задачу оптимизации? Проблемы придут с двух сторон.

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

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

Эти проблемы могут быть решены, если мы сообщим алгоритму, что масштаб первой переменной составляет 10 -27, а масштаб второй - 10 7. Для этого каждый из оптимизаторов, входящих в состав ALGLIB, имеет соответствующую функцию, имя которой заканчивается на ...setscale(). Как именно это решит проблему?

Во-первых, при проверке критерия остановки будет учитываться масштаб каждой из переменных. Например, критерий "шаг размером 0.001" будет интерпретироваться, как совершение шага длиной 0.001 от масштаба каждой из переменных. То есть, по первой координате длина шага должна быть 10 -30, а по второй - 10 4, чтобы алгоритм остановился. Схожим способом будет модифицирован критерий, проверяющий величину градиента функции.

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

Нецентрированные переменные

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

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

При первом взгляде на задачу можно подумать, что масштаб цены равен её величине - на уровне 1000 EUR. Однако если присмотреться к задаче получше, то выяснится, что здесь мы имеем дело с ситуацией, когда масштаб переменной намного меньше её величины. Наш торговец металлом не может повысить цены больше чем на 10 EUR, потому что продать металл с более высокой наценкой будет нереально (что найдет отражение в виде резкого роста штрафной функции). Не может он и продать товар дешевле со скидкой больше 10 EUR, потому что понесет слишком большой убыток. Очевидно, что масштаб переменной "цена" равен 10 EUR, что в 100 раз меньше, чем её средняя величина.

Обсуждение

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

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

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.