Нелинейная многомерная оптимизация - это просто. Часть 1. Градиентный спуск

07.07.15

Разработка - Математика и алгоритмы

Рассказ с демонстрацией возможностей градиентного метода поиска оптимального решения.

Скачать файлы

Наименование Файл Версия Размер
ГрадиентныйСпускV01.epf
.epf 18,90Kb
19
.epf 18,90Kb 19 Скачать

Задачи оптимизации (поиска наилучшего решения) не самые популярные в среде 1С-негов. Действительно, одно дело - учет выполнения каких-либо решений, и совершенно другое дело - принятие этих самых решений. В последнее время, однако, мне кажется 1С бросилась догонять конкурентов в данном вопросе. Действительно захватывающе объединить под одной крышей все, что может потребоваться современному менеджеру, догоняя в этом вопросе SAP и заменяя MS Project и другие системы планирования.

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

Итак, первая тема - метод градиентного спуска.

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

Давайте введем обозначения:

 - Множество переменных Х, от которых зависит значение целевой функции

 

И сама целевая функция Z, вычисляемая самым произвольным образом из множества Х

 

Теперь поясним, что же такое градиент. Градиент это вектор многомерного пространства, указывающий направление наибольшего возрастания некоторой функции. Компонентами градиента являются дифференциалы всех переменных функции Z.

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

Классический метод градиентного спуска реализовывается для минимизации целевой функции через антиградиент (то есть вектор противоположный градиенту), который получается из градиента самым простым образом - умножением на -1 всех компонентов градиента. Или в обозначениях:

Теперь самый главный вопрос: а как нам найти эти самые dZ и dX1dX2 и т.д.? Очень просто! dXn - это бесконечно малое приращение переменной Xn, скажем 0,0001 от ее текущей величины. Или 0,0000000001 - главное, чтобы оно (приращение) было действительно малым:)

А как же вычисляется dZ? Тоже элементарно! Вычисляем Z для набора переменных X , а затем изменяем в этом наборе переменную Xn на величину dXn. Снова вычисляем значение целевой функции Z для этого слегка модифицированного набора (Zn) и находим разницу - это и будет dZ = Zn - Z. Ну а теперь коль нам известны dXn и dZ найти dZ/dXn проще пареной репы.

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

На следующем (k+1) этапе, нужно вычислить новые значения массива переменных X. Очевидно, что для приближения к минимуму целевой функции Z мы должны корректировать значения X предыдущего (k-го) этапа в направлении антиградиента по такой формуле:

 

Остается разобраться с этой самой альфой в формуле. Зачем она нужна и откуда она берется.

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

Поиск значения параметра α выполняется одним из методов одномерной оптимизации. Значения переменных {X} нам известны, известны и их градиенты - остается минимизировать целевую функцию в окрестностях текущего решения по одному единственному параметру: α.

Останавливаться на одномерной оптимизации я здесь на буду - методы достаточно просты для понимания и реализации, скажу лишь, что я использовал в своем решении метод "золотого сечения". ОДЗ для α находится в промежутке от 0 до 1.

Итак, резюмируя написанное, сформулируем последовательность шагов для поиска решения методом градиентного спуска:

  1. Формируем начальное опорное решение, присваивая искомым переменным случайные значения из ОДЗ. 
  2. Находим градиенты и антиградиенты для каждой переменной как отношения прироста целевой функции при относительно малом увеличении значения переменной к значению приращения этой самой переменной.
  3. Находим коэффициент α, на который нужно умножать антиградиенты перед добавлением к исходным значениям опорного решения методом одномерной оптимизации. Критерий оптимизации - наименьшее из возможных значение целевой функции для скорректированных таким образом значений {X}.
  4. Пересчитываем {X} в соответствии с наденными значениями антиградиентов и коэффициента сдвига α.
  5. Проверяем достигнута ли необходимая точность (ε) вычисления минимума целевой функции:

       

      6.  Если условие выполнено и от этапа к этапу значение целевой функции изменилось ниже установленного нами же критерия это значит, что необходимая точность достигнута и текущее множество {X} является решением задачи, иначе - переход к шагу 2.

Теперь давайте перейдем к практической задаче, которая решена в обработке.

По условию задачи необходимо установить цену на некий товар таким образом, чтобы прибыль от его реализации в планируемом периоде была максимальной. При этом нужно учитывать, что объем реализации зависит от установленной нами цены, а закупочная цена товара (влияющая на валовую прибыль) также зависит от объема закупки товара: поставщик готов предоставлять скидки тем больше, чем больше будет объем нашей закупки. То есть нам нужно одновременно с установлением цены понимать, сколько товара мы сможем реализовать и по какой цене и, следовательно, сколько товара нам нужно для этого закупить, и тогда мы будем знать, какова будет закупочная цена. В общем, такая немного рекурсивная логика поиска решения:)

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

Для решения задачи данный метод применяется дважды: на первом этапе мы находим параметры уравнения спроса на продукцию по данным продаж предыдущих периодов. То есть, предполагая некий вид зависимости спроса от цены, вычисляем значения параметров этой зависимости, минимизируя сумму квадратов отклонений между расчетными и фактическими данными о продажах. На втором этапе, пользуясь найденными параметрами зависимости между объемом продаж и ценой реализации, мы оптимизируем прибыль и тоже методом градиентного спуска, хотя бы применяемым всего для одной переменной. Так как метод градиентного спуска минимизирует целевую функцию, а прибыль как ничто другое нуждается в максимизации, мы используем не твиальную целевую функцию с названием "МинусПрибыль", которая всего-то и делает, что вычисляет прибыль по полученному значению цены, а перед возвратом умножает ее на -1:) И ведь работает! Теперь чем меньше становится "МинусПрибыль", тем больше на самом деле самая что ни на есть реальная прибыль от продаж.

Пример решения в обработке, как и универсальная функция поиска решения методом градиентного спуска. Суть универсальности в том, что переменные {X} передаются в нее в виде массива, а целевая функция передается как параметр строкой. Целевую же функцию, которая принимает массив переменных и возвращает значение, пишите сами какого угодно вида - главное, чтобы она возвращала число. И такое число, что чем меньше оно будет, тем ближе поданный массив аргументов к оптимальному решению.

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

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

оптимизация градиентный спуск оптимальное решение минимизация максимизация поиск решения

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

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

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8837    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7803    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. karpik666 3760 07.07.15 14:05 Сейчас в теме
А обещали, что будет все понятно:-)
2. dusha0020 1103 07.07.15 15:03 Сейчас в теме
(1) karpik666, Я пошутил:)
3. sasha777666 321 08.07.15 06:27 Сейчас в теме
Когда-то хотел реализовать симлекс метод для распределения затрат по белым фирмам из которой состоит серая фирма) .... хорошая вещь, скачаю, уверен найду где применить)
4. dusha0020 1103 08.07.15 08:07 Сейчас в теме
(3) sasha777666, Симплекс метод намного более производительный с точки зрения вычислений, но реализуется сложнее и оптимизирует только линейный функционал. Градиентный спуск намного проще и универсальнее и его главный недостаток - большая вычислительная емкость по мере развития железа становится все менее существенным.
5. пользователь 09.07.15 10:17
Сообщение было скрыто модератором.
...
6. Идальго 226 09.07.15 11:18 Сейчас в теме
Хм, это вроде еще методом наискорейшего спуска называют. Вроде если у нас несколько локальных экстремумов (н-р минимумов), то решение будет зависеть от начального приближения, а то все точки можем просто не найти (решение в первую же ближайшую ямку по градиенту попадёт). Даже на рисунке с диаграммой у вас есть что-то похожее на то, о чём я говорю.
7. dusha0020 1103 09.07.15 11:37 Сейчас в теме
(6) Идальго, Да - Вы правы. Проблему локальных минимумов (если они есть) данный метод оставляет открытой. Даже на картинке видно что метод "сползает" в один из возможных минимумов. Как вариант, конечно, можно строить несколько случайных опорных решений и сравнивать полученные минимумы на основе каждого из них. В конце концов механизм многопоточности позволит отработать параллельно несколько решений и с большей вероятностью найти именно глобальный минимум.
С другой стороны можно повысить качество опорного решения, приблизив его к глобальному минимуму. Есть эмпирическое соображение, что чем "глубже" яма тем круче у нее стенки, а следовательно уменьшение значения целевой функции идет быстрее. На основе этого соображения можно не искать множество минимумов, а создав некоторое количество опорных решений прогнать их на 5-10 итерациях, замерив относительную скорость сходимости для каждого. Много вычислительных ресурсов это не займет, но зато позволит выбрать самое перспективное из возможных опроных.
А можно воспользоваться и другими алгоритмами как выбора опорного решения, так и поиска глобального минимума. О которых собственно я еще планирую рассказать:)
Спасибо за ценное замечание!
8. dumal 10.07.15 11:30 Сейчас в теме
Можно попробовать реализовать решение той же задачи генетическими алгоритмами. Та же беда с вычислительными ресурсами, зато, вроде как, решается проблема с локальными экстремумами при значительных выборках начальных популяций
9. dusha0020 1103 10.07.15 13:25 Сейчас в теме
(8) dumal, Генетический алгоритм, имхо, немного не про это. Генетика вообще не о рациональных числах:) Генетический алгоритм это про то как из конечного набора деталей (генов) сложить самую правильную конструкцию (организм). А вот на бесконечных полях действительных чисел с неограниченной точностью он теряется. Впрочем именно об этом и будет моя следующая статья. Там постараюсь объяснить и обосновать это подробнее.
10. karpik666 3760 10.07.15 13:41 Сейчас в теме
(9) ildarovich перелогиньтесь =)
dj_serega; +1 Ответить
11. Артано 760 13.07.15 10:12 Сейчас в теме
(10) Не согласен, у обоих свой оригинальный стиль и слог. Шутка не смешная
12. karpik666 3760 13.07.15 10:44 Сейчас в теме
(11) Артано, может и не смешная. Просто при прочтении данной статьи я сравнивал не слог, а эмоции, которая она у меня вызывает, вот и не смог удержаться, так глупо пошутить:(
13. Mr.Rm 13.07.15 22:21 Сейчас в теме
Нужно заметить, что при выборе "действительно малой" величины приращений dXn следует учитывать, что с ее уменьшением начинает расти погрешность вычислений из-за ограниченности разрядной сетки.
dusha0020; +1 Ответить
14. dusha0020 1103 14.07.15 08:48 Сейчас в теме
(13) Mr.Rm, В общем случае - да, однако, 0,00001 от 10 000 это совсем не то, что 0,00001 от 0,001. То есть величина относительного шага приращения Х для вычисления dXn с точки зрения возможной точности вычисления зависит не только от себя, но и от величины Х. Если копаться глубже, то правильный коэффициент приращения в зависимости от величины X, величин других переменных и характера целевой функции вычисляется как метрический тензор риманова пространства. Но в заголовок статьи я включил словосочетание "это просто", что до известной степени не позволило мне так сказать растечься во всю ширь и глубину проблемы:)
А замечание Ваше полезно. Спасибо!
15. Yimaida 37 14.07.15 21:02 Сейчас в теме
Добрый вечер. В такого рода публикациях особенно полезны ссылки на литературу... Все-таки, не бытовым языком оперируете, и соответственно терминология не придуманная Вами и алгоритмы тоже. Реализация на 1с это другой момент, за это поставил + (хотя не качал :) ). Но надо давать ссылки на литературу, ресурсы, тем более если планируете цикл статей.
dusha0020; +1 Ответить
16. dusha0020 1103 15.07.15 09:19 Сейчас в теме
(15) Yimaida, Спасибо за замечание. Учту на будущее и, возможно, добавлю ссылки к данной статье. Хотя рождению этой статьи предшествовала практическая и неоднократная реализация метода, поэтому собственно при написании статьи я не пользовался литературой. Взял готовый, опробованный и отточенный метод и описал как он работает по возможности понятным языком, не претендуя, естественно, на полный копирайт, но и не восстанавливая ретроспективно источники информации и чужие идеи, которые привели меня к данному решению...
С другой стороны, действительно, может показаться, что я выдаю себя за слишком умного, не приводя источников своей осведомленности и талантливости... Учту на будущее. Еще раз благодарю за замечание.
17. Yimaida 37 15.07.15 11:01 Сейчас в теме
(16) Как раз, наоборот, сейчас придумать алгоритм оптимизации может любой программист, т.к. специфика работы располагает. Я нисколько не сомневаюсь, что метод мог быть разработан Вами. Я тоже не вспомню всю литературу, которую читал и изучал, но терминология в тексте выдает не оригинальность как минимум описания проблемы. Литература была бы полезна для более детального изучения проблемы и как хорошее дополнение к статье. Лично мне было бы приятно увидеть такие ссылки в конце статьи. Справедливости ради скажу, что на инфостарте есть статьи где авторы постарались и привели ссылки.

Про погрешности тоже справедливо было отмечено.

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

P.P.S. Все замечания не в пику, а как взгляд со стороны :)
18. user1002645 08.05.19 16:48 Сейчас в теме
Добрый день.
Андрей, интересная статья. Наша компания сейчас как раз думает над тем, как на базе платформы 1С решить методом обобщенного градиента следующую задачу:
Есть несколько торговых точек, по каждой торговой точке есть данные о продажах, остатках, пороговых значениях запасов.
Ключевым показателем здесь являются Дни запаса товара на торговой точке.
Целевая функция - коэффициент вариации дней запаса по сети(отношение стандартного отклонения к среднему значению).
Необходимо найти такие значения запасов на торговых точках, чтобы коэффициент вариации дней запасов был минимальным.
При этом в задаче действуют следующие ограничения:
1. Сумма всех перераспределяемых запасов по сети равна суммарным остаткам в сети на текущий момент плюс остатки на центральном складе
2. Запасы могут принимать только целочисленные значения.
3. На каждой торговой точке запасы должны быть не меньше минимального порогового значения.
Андрей, Вам интересна такая задача? Смогли бы написать внешнюю обработку для её решения для платформы 1С Предприятие 8.3?
19. dusha0020 1103 10.05.19 09:17 Сейчас в теме
(18) Добрый день, Денис. Задача мне интересна. Но подробности я бы обсудил в личке:)
20. user1002645 15.05.19 15:51 Сейчас в теме
Андрей, подробности готов обсудить по почте - dsolovyov.tz@gmail.com
Оставьте свое сообщение