Задача о нахождении минимального остовного дерева (Minimum Spanning Tree, MST) является фундаментальной задачей теории графов с огромным количеством прикладных приложений. Остовным деревом связного неориентированного графа называется подграф, включающий все вершины графа и образующий дерево. Минимальное остовное дерево — это то, для которого сумма весов ребер минимальна.
Методы штрафных функций представляют собой элегантный и исторически значимый подход к решению задач нелинейного программирования с ограничениями. Концептуальная идея метода заключается в сведении сложной задачи условной оптимизации к последовательности более простых задач безусловной оптимизации. Это достигается путем модификации целевой функции: к ней добавляется искусственный штраф за нарушение ограничений, что заставляет алгоритм "самостоятельно" избегать недопустимых областей.
Многоуровневое (в частности, двухуровневое) математическое программирование описывает сложный класс задач оптимизации, в которых целевая функция и ограничения содержат переменные, являющиеся оптимальным решением другой задачи оптимизации. Этот математический аппарат идеально подходит для моделирования иерархических систем принятия решений, где участники обладают асимметричными полномочиями. В экономике и теории игр такие задачи известны как модели Штакельберга, где существует «Лидер», делающий первый ход, и «Ведомый», реагирующий на действия Лидера.
Метод Ньютона по праву считается одним из самых мощных и быстро сходящихся алгоритмов в арсенале нелинейного математического программирования. В то время как методы градиентного спуска первого порядка анализируют только "наклон" целевой функции, метод Ньютона привлекает информацию о ее "кривизне", используя вторые производные. Это позволяет алгоритму строить точную параболическую аппроксимацию функции и достигать оптимума с квадратичной скоростью сходимости.
Задача маршрутизации транспорта (Vehicle Routing Problem, VRP) является одним из самых сложных естественных обобщений задачи коммивояжера и краеугольным камнем современной транспортной логистики. Задача заключается в определении оптимального набора маршрутов для парка транспортных средств, базирующихся в одном или нескольких депо, с целью обслуживания заданного набора клиентов с минимальными издержками. Учитывая NP-трудный характер VRP, применение точных математических методов ограничено небольшими размерностями, что выводит на первый план мощные эвристические и метаэвристические алгоритмы.
Метод покоординатного спуска (Coordinate Descent, CD) является одним из старейших интуитивных алгоритмов безусловной оптимизации, в котором на каждой итерации функция минимизируется только по одной переменной (или небольшому блоку переменных), в то время как остальные остаются фиксированными. Несмотря на кажущуюся простоту, в эпоху больших данных этот алгоритм был переосмыслен и стал одним из самых мощных вычислительных инструментов для решения гигантских задач разреженного машинного обучения (таких как LASSO и Elastic Net), где классические методы второго порядка не справляются с размерностью.
Жадная рандомизированная адаптивная поисковая процедура (Greedy Randomized Adaptive Search Procedure, GRASP) — это мощная мультистартовая метаэвристика, разработанная Томасом Фео и Маурисио Резенде в конце 1980-х годов для решения комбинаторных задач высокой сложности. Метод изящно решает фундаментальную проблему классических жадных алгоритмов — их "близорукость" и склонность к застреванию в слабых локальных минимумах, внедряя контролируемую случайность прямо в процесс конструирования решения.
Методы внутренней точки представляют собой мощную альтернативу симплекс-методу, особенно для задач большой размерности и задач с выпуклыми ограничениями, к которым относится квадратичное программирование. В отличие от симплекс-метода, идущего вдоль границ допустимой области, алгоритмы внутренней точки движутся внутри этой области, что обеспечивает полиномиальную сложность решения и высокую устойчивость к структуре задачи.
В реальных бизнес-задачах редко существует только один критерий оптимальности. Чаще всего приходится балансировать между противоречивыми целями: минимизацией затрат и максимизацией качества, или снижением времени выполнения и увеличением надежности. Теория мультиобъектной оптимизации занимается поиском не одного решения, а множества компромиссных вариантов, называемых множеством Парето.
Программирование в ограничениях (Constraint Programming, CP) — это мощная вычислительная парадигма, изначально возникшая в области искусственного интеллекта и логического программирования, но ставшая одним из важнейших инструментов современного исследования операций. В отличие от классического математического программирования, где фокус направлен на оптимизацию целевой функции при линейных или выпуклых ограничениях, CP концентрируется на поиске допустимого решения в сложных комбинаторных пространствах с жесткими логическими и нелинейными связями.
В то время как классический метод ветвей и границ ассоциируется преимущественно с дискретной и целочисленной оптимизацией, его архитектура нашла блестящее применение в решении сложнейших задач глобальной непрерывной невыпуклой оптимизации. Метод пространственного ветвления и границ (Spatial Branch-and-Bound, sBB) позволяет находить доказанный глобальный оптимум для нелинейных функций со множеством локальных экстремумов, что критически важно в химическом инжиниринге, проектировании нейронных сетей и решении задач упаковки (Packing Problems).
Управление запасами является одной из классических и наиболее экономически значимых областей применения методов динамического программирования. От поддержания оптимального количества комплектующих на конвейере до управления ассортиментом гипермаркетов — везде требуется балансировка между издержками хранения и штрафами за дефицит. Стохастическое динамическое программирование предоставляет математический аппарат для принятия оптимальных решений о пополнении запасов в условиях случайного и непредсказуемого спроса.
Задача о размещении объектов (Facility Location Problem, FLP) является одной из важнейших задач в логистике и операционном планировании. Требуется выбрать точки на карте для размещения складов или заводов так, чтобы минимизировать суммарные транспортные расходы до клиентов и фиксированные затраты на открытие объектов. Это комбинаторная задача, сочетающая выбор дискретных точек с непрерывной оптимизацией транспортных потоков.
Геометрическое программирование — это специальный класс задач нелинейного программирования, имеющий дело с оптимизацией целевых функций и ограничений, представимых в виде многочленов или мономов. Хотя название может вводить в заблуждение, метод напрямую связан с геометрическими неравенствами, такими как неравенство о средних. Геометрическое программирование эффективно для инженерного проектирования, где параметры моделей часто связаны степенными зависимостями.
Полуопределенное программирование (Semidefinite Programming, SDP) — это высшая ступень иерархии выпуклого конического программирования, поглощающая в себя линейное, квадратичное и коническое программирование второго порядка. В SDP переменной оптимизации выступает не вектор, а симметричная матрица, и задача состоит в минимизации линейной функции от ее элементов при условии, что сама матрица (или аффинная комбинация заданных матриц) является положительно полуопределенной. Этот математический аппарат совершил настоящую революцию в теории управления, комбинаторной оптимизации и квантовой теории информации.
Максиминные задачи и гарантийный подход формируют математическую базу для принятия оптимальных решений в условиях глубокой, нестохастической неопределенности. В отличие от стохастического программирования, где известны распределения вероятностей будущих сценариев, здесь предполагается, что природа или разумный противник выбирают наихудший для нас вариант из заданного множества. Гарантийный подход ищет стратегию, которая максимизирует результат при самом неблагоприятном стечении обстоятельств.
Метод Нелдера-Мида, широко известный как метод деформируемого многогранника, представляет собой один из самых популярных и надежных алгоритмов прямого поиска. Разработанный в 1965 году Джоном Нелдером и Роджером Мидом, этот алгоритм решает задачи нелинейной безусловной минимизации функций многих переменных без использования вычисления градиентов или матриц Гессе. Это свойство делает его бесценным инструментом для оптимизации сложных функций черного ящика, зашумленных данных и недифференцируемых математических моделей, где классические ньютоновские методы терпят сокрушительное поражение.
В численной нелинейной оптимизации существуют две глобальные стратегии обеспечения математической сходимости алгоритмов к локальному минимуму из произвольной стартовой точки: методы линейного поиска (Line Search) и методы доверительных областей (Trust-Region Methods). Если линейный поиск сначала выбирает направление движения, а затем пытается подобрать оптимальную длину шага вдоль этого направления, то метод доверительных областей работает принципиально иначе. Он сначала определяет радиус многомерной окрестности, внутри которой локальная квадратичная аппроксимация функции считается надежной, а затем ищет оптимальный шаг, не покидая пределов этой доверительной зоны.