Задача о рюкзаке (Knapsack Problem) — это классическая задача комбинаторной оптимизации, входящая в список NP-трудных задач. Суть ее заключается в выборе набора предметов с заданным весом и стоимостью, чтобы максимизировать суммарную стоимость при ограничении по общей грузоподъемности рюкзака. Простота постановки контрастирует со сложностью нахождения точного решения при увеличении числа предметов.
Метод эллипсоидов, предложенный советским математиком Леонидом Хачияном в 1979 году, стал исторической вехой в математическом программировании. Этот алгоритм впервые строго доказал, что задачи линейного программирования могут быть решены за полиномиальное время. В отличие от классического симплекс-метода, который в худших сценариях (например, на кубе Клее-Минти) требует экспоненциального количества шагов, метод эллипсоидов гарантирует нахождение оптимума с оценкой сложности, зависящей только от размера входных данных, что навсегда изменило теоретический ландшафт теории алгоритмов и вычислительной сложности.
Эволюционные алгоритмы (ЕА) — это методы стохастического поиска, имитирующие биологические процессы естественного отбора, кроссовера (скрещивания) и мутации. В задачах оптимизации, где классические градиентные методы терпят неудачу из-за недифференцируемости функции, наличия шума или сложности ландшафта, ЕА показывают поразительную живучесть и способность находить качественные решения.
Алгоритм Франка-Вульфа, также известный как метод условного градиента, был предложен Маргерит Франк и Филипом Вульфом в 1956 году для решения задач квадратичного программирования с линейными ограничениями. Сегодня этот алгоритм переживает мощный ренессанс в машинном обучении и анализе данных благодаря своему уникальному свойству: он не требует выполнения операции проекции на допустимое множество. Для задач оптимизации огромной размерности, где проекция является вычислительно неподъемной, метод Франка-Вульфа стал элегантным и высокоэффективным решением.
Псевдобулево программирование представляет собой специализированный раздел дискретной нелинейной оптимизации, фокусирующийся на исследовании и минимизации функций, аргументы которых принимают лишь два дискретных значения (0 и 1), а сами функции принимают действительные значения. Этот класс задач имеет колоссальное значение для математического моделирования бинарных решений, таких как выбор инвестиционных проектов, распределение ресурсов, проектирование логических схем и анализ надежности сложных технических систем.
В современную эру машинного обучения, сжатия данных и обработки сигналов (Compressed Sensing) регулярно возникают задачи оптимизации огромной размерности, в которых целевая функция является суммой гладкой и негладкой составляющих. Классическим примером является задача регуляризованной регрессии LASSO, где гладкая квадратичная ошибка штрафуется негладкой L1-нормой для обеспечения разреженности решения. Для эффективного решения таких задач традиционные градиентные методы неприменимы, а субградиентные методы сходятся недопустимо медленно. Решением стал математический аппарат проксимальных операторов и методы проксимального градиента.
Сепарабельное программирование представляет собой исторически важный и практически ценный раздел математического программирования, позволяющий находить глобальные оптимумы для определенного класса нелинейных задач, используя мощный алгоритмический аппарат линейного программирования. Этот метод применяется в случаях, когда целевая функция и функции ограничений являются сепарабельными, то есть могут быть представлены в виде суммы функций, каждая из которых зависит только от одной переменной. Такая структура повсеместно встречается в экономике при моделировании издержек производства и эффектов масштаба.
Взаимосвязь между теорией игр и математическим программированием представляет собой один из самых плодотворных симбиозов в современной прикладной математике. Еще на заре развития этих дисциплин Джон фон Нейман доказал, что любая конечная антагонистическая игра двух лиц с нулевой суммой может быть сформулирована и решена как пара двойственных задач линейного программирования. Сегодня методы оптимизации являются основным вычислительным инструментом для нахождения равновесий Нэша в сложных стратегических взаимодействиях.
Коническое программирование (Conic Programming) представляет собой естественное и невероятно мощное обобщение классического линейного программирования. Если в линейном программировании переменные ограничиваются неотрицательным ортантом пространства, то в коническом — они должны принадлежать произвольному замкнутому выпуклому конусу. Этот переход от ортантов к конусам позволяет с элегантностью линейной алгебры решать сложнейшие нелинейные задачи, а теория двойственности в таких пространствах открывает фундаментальные свойства выпуклой оптимизации.
Симплекс-метод, разработанный Джорджем Данцигом в 1947 году, остается наиболее эффективным и широко применяемым алгоритмом для решения задач линейного программирования. Несмотря на развитие методов внутренних точек, симплекс-метод сохраняет свою актуальность благодаря высокой скорости сходимости на реальных задачах и способности эффективно находить оптимальное решение, перемещаясь по вершинам выпуклого многогранника допустимых решений.
Метод отсекающих плоскостей Ральфа Гомори стал прорывом в решении задач целочисленного линейного программирования в конце 50-х годов XX века. В отличие от метода ветвей и границ, который разделяет задачу на подзадачи, метод Гомори итеративно добавляет новые линейные ограничения (отсечения), которые "отрезают" нецелочисленные вершины области допустимых решений, не исключая при этом целочисленные точки.
Стохастическое программирование — это расширение методов математического программирования на задачи, где коэффициенты модели являются случайными величинами. В отличие от детерминированных постановок, здесь необходимо находить решение, которое остается допустимым и оптимальным при различных сценариях реализации случайных параметров. Эти методы жизненно важны для принятия решений в условиях рыночной неопределенности, логистических рисков и нестабильности производственных процессов.
Программирование в конусах второго порядка (Second-Order Cone Programming, SOCP) представляет собой широчайший класс задач выпуклой оптимизации, который обобщает как линейное (LP), так и выпуклое квадратичное программирование (QP, QCQP). В задачах SOCP линейная целевая функция минимизируется на пересечении аффинного подпространства и декартова произведения конусов второго порядка. Эта математическая структура обладает исключительной выразительной силой, позволяя моделировать сложнейшие инженерные и экономические ограничения, сохраняя при этом возможность решения за строго полиномиальное время.
Нечеткое математическое программирование (Fuzzy Mathematical Programming) представляет собой глубокое развитие классических методов оптимизации, предназначенное для работы с неопределенностью, имеющей не вероятностную, а лингвистическую и когнитивную природу. Инициированное трудами Ричарда Беллмана и Лотфи Заде в 1970-х годах, это направление позволяет строить математически строгие модели производственных и экономических систем в условиях, когда ограничения, цели и параметры не могут быть заданы точными числами, а описываются субъективными категориями.
В современном менеджменте принятие решений редко происходит в условиях полной определенности. Большинство задач управления, таких как планирование инвестиционного портфеля или логистическая маршрутизация, требуют учета стохастических факторов. Сценарный подход к стохастической оптимизации позволяет трансформировать непредсказуемость внешней среды в структурированный набор альтернатив, обеспечивая принятие робастных решений.
Нелинейное программирование охватывает задачи оптимизации, в которых целевая функция или ограничения являются нелинейными. В отличие от линейных задач, здесь локальный экстремум не всегда является глобальным, а сложность алгоритмов зависит от свойств выпуклости функции. Методы градиентного спуска составляют основу итерационных процедур для поиска локального минимума дифференцируемых функций.
Транспортная задача линейного программирования выделяется специфической структурой матрицы ограничений, что делает применение классического симплекс-метода вычислительно избыточным. Метод потенциалов (метод разрешающих множителей) был разработан Леонидом Канторовичем и Тьяллингом Купмансом как специализированный алгоритм, идеально учитывающий сетевую структуру задачи и позволяющий находить глобальный оптимум транспортных потоков значительно быстрее стандартных симплекс-процедур.
Метод последовательного квадратичного программирования (SQP) является одним из самых эффективных численных алгоритмов для решения задач нелинейного программирования с ограничениями. Алгоритм основывается на итеративной аппроксимации исходной задачи, где на каждом шаге решается квадратичная подзадача, которая локально моделирует поведение исходной нелинейной задачи.