Прикладная математика

Марковские процессы принятия решений (MDP) в оптимизации

Марковские процессы принятия решений (Markov Decision Processes, MDP) предоставляют строгую математическую основу для стохастического динамического программирования. Они используются для оптимизации последовательности решений в среде, где результаты действий частично случайны, а частично зависят от выбора принимающего решение агента. Сегодня MDP образуют фундаментальную парадигму для современного машинного обучения с подкреплением (Reinforcement Learning), автономной робототехники и управления сложными производственными процессами.

Подробнее

Негладкая оптимизация: теория и субградиентные методы

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

Подробнее

Максиминные задачи и гарантийный подход в оптимизации

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

Подробнее

Псевдобулево программирование: оптимизация бинарных решений

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

Подробнее

Квадратичное программирование: методы решения и применение в машинном обучении

Квадратичное программирование (Quadratic Programming, QP) представляет собой особый класс задач нелинейной оптимизации, в которых целевая функция является квадратичной (содержит произведения пар переменных и их квадраты), а все ограничения — линейными. Этот класс задач обладает элегантными математическими свойствами и служит своеобразным мостом между простым линейным программированием и сложной нелинейной оптимизацией. Методы QP лежат в основе современной финансовой теории и алгоритмов машинного обучения.

Подробнее

Метод ветвей и отсечений для смешанно-целочисленного программирования (MILP)

Смешанно-целочисленное линейное программирование (Mixed-Integer Linear Programming, MILP) охватывает колоссальный класс практических оптимизационных задач, где лишь часть переменных обязана принимать дискретные (часто бинарные) значения, тогда как остальные могут быть непрерывными. Модели MILP лежат в основе планирования работы электростанций (Unit Commitment), составления расписаний авиакомпаний и проектирования телекоммуникационных сетей. Современным стандартом решения таких задач является алгоритм ветвей и отсечений (Branch-and-Cut).

Подробнее

Эвристические алгоритмы в задачах маршрутизации транспорта (VRP)

Задача маршрутизации транспорта (Vehicle Routing Problem, VRP) является одним из самых сложных естественных обобщений задачи коммивояжера и краеугольным камнем современной транспортной логистики. Задача заключается в определении оптимального набора маршрутов для парка транспортных средств, базирующихся в одном или нескольких депо, с целью обслуживания заданного набора клиентов с минимальными издержками. Учитывая NP-трудный характер VRP, применение точных математических методов ограничено небольшими размерностями, что выводит на первый план мощные эвристические и метаэвристические алгоритмы.

Подробнее

Динамическое программирование в стохастических задачах управления запасами

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

Подробнее

Теория игр и математическое программирование: вычисление равновесия Нэша

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

Подробнее

Оптимизация на графах: потоки минимальной стоимости в транспортных сетях

Задача о потоке минимальной стоимости (Minimum Cost Flow Problem, MCFP) является объединяющей и фундаментальной проблемой сетевой оптимизации. Она обобщает несколько классических задач теории графов: задачу о кратчайшем пути, задачу о максимальном потоке, транспортную задачу и задачу о назначениях. Цель MCFP заключается в поиске наиболее дешевого способа пересылки заданного объема ресурса через транспортную сеть от источников к стокам, учитывая пропускные способности ребер графа и удельные стоимости транспортировки.

Подробнее