Какой пакет линейного программирования следует использовать для большого количества ограничений и "теплых запусков"
У меня есть "непрерывная" задача линейного программирования, которая заключается в максимизации линейной функции в изогнутом выпуклом пространстве. В типичных задачах LP выпуклое пространство является многогранником, но в этом случае выпуклое пространство является кусочно-изогнутым, то есть имеет грани, ребра и вершины, но ребра не прямые, а грани не плоские, Вместо того, чтобы быть определенным конечным числом линейных неравенств, у меня есть непрерывно бесконечное число. В настоящее время я имею дело с этим путем аппроксимации поверхности многогранником, что означает дискретизацию непрерывно бесконечных ограничений в очень большое конечное число ограничений.
Я также нахожусь в ситуации, когда я хотел бы знать, как ответ меняется при небольших возмущениях на основную проблему. Таким образом, я хотел бы иметь возможность предоставить начальное условие для решателя на основе соседнего решения. Я считаю, что эта возможность называется "теплое начало".
Может ли кто-нибудь помочь мне различить различные пакеты LP? Меня не так беспокоит удобство пользователя, как скорость (для большого количества ограничений), высокая точность арифметики и теплый старт.
Спасибо!
РЕДАКТИРОВАТЬ: Судя по разговору с отвечающими на вопросы до сих пор, я должен быть яснее о проблеме, которую я пытаюсь решить. Упрощенная версия выглядит следующим образом:
У меня есть N фиксированных функций f_i(y) одной реальной переменной y. Я хочу найти x_i (i=1,...,N), которые минимизируют \sum_{i=1}^N x_i f_i(0), с учетом ограничений:
- \ sum_ {i = 1} ^ N x_i f_i (1) = 1 и
- \sum_{i=1}^N x_i f_i(y) >= 0 для всех y>2
Более кратко, если мы определим функцию F(y)=\sum_{i=1}^N x_i f_i(y), то я хочу минимизировать F(0) при условии, что F(1)=1, и F (y) положительно на всем интервале [2, бесконечность). Обратите внимание, что это последнее условие положительности на самом деле представляет собой бесконечное число линейных ограничений на x_i, по одному для каждого y. Вы можете думать о y как о метке - это не переменная оптимизации. Конкретный y_0 ограничивает меня полупространством F(y_0) >= 0 в пространстве x_i. Поскольку я изменяю y_0 между 2 и бесконечностью, эти полупространства непрерывно меняются, образуя изогнутую выпуклую форму. Геометрия этой формы неявно (и сложным образом) зависит от функций f_i.
3 ответа
Что касается рекомендаций LP Solver, две из лучших - это Gurobi и CPLEX (гуглите их). Они бесплатны для академических пользователей и способны решать масштабные задачи. Я считаю, что у них есть все возможности, которые вам нужны. Вы можете получить информацию о чувствительности (к возмущению) из теневых цен (то есть множителей Лагранжа).
Но меня больше интересует ваша оригинальная проблема. Насколько я понимаю, это выглядит так:
Пусть S = {1,2,...,N}, где N - общее количество функций. у скаляр. f_{i}:R^{1} -> R^{1}.
minimize sum{i in S} (x_{i} * f_{i}(0))
x_{i}
s.t.
(1) sum {i in S} x_{i} * f_{i}(1) = 1
(2) sum {i in S} x_{i} * f_{i}(y) >= 0 for all y in (2,inf]
Мне просто кажется, что вы можете попытаться решить эту проблему в виде выпуклой НЛП, а не ЛП. Крупномасштабные внутренние решения НЛП, такие как IPOPT, должны легко справляться с этими проблемами. Я настоятельно рекомендовал попробовать IPOPT http://www.coin-or.org/Ipopt
С числовой точки зрения: для выпуклых задач теплый запуск не требуется с внутренними точечными решателями; и вам не нужно беспокоиться о комбинаторном цикле активных наборов. То, что вы назвали "горячим стартом", на самом деле мешает решению - это больше похоже на анализ чувствительности. На языке оптимизации "теплый запуск" обычно означает предоставление решателю первоначального предположения - решатель возьмет это предположение и в итоге получит то же решение, которое на самом деле не то, что вам нужно. Единственное исключение - если активный набор изменяется с другим начальным предположением - но для выпуклой задачи с уникальным оптимумом это не может произойти.
Если вам нужна дополнительная информация, я с удовольствием предоставлю ее.
РЕДАКТИРОВАТЬ:
Извините за нестандартные обозначения - я бы хотел печатать в LaTeX, как на MathOverflow.net. (Кстати, вы можете попробовать опубликовать это там - я думаю, что математики там будут заинтересованы в этой проблеме)
Ах, теперь я вижу о "у> 2". На самом деле это не ограничение оптимизации, а интервал, определяющий пространство (я редактировал свое описание выше). Виноват. Мне интересно, если бы вы могли как-то преобразовать / спроецировать проблему с бесконечной на конечную? Я не могу думать ни о чем прямо сейчас, но мне просто интересно, возможно ли это.
Таким образом, ваш подход состоит в том, чтобы дискретизировать проблему для y в (2,inf). Я предполагаю, что вы выбираете очень большое число для представления inf и точной сетки дискретизации. Оооо сложно. Я полагаю, дискретизация - это, вероятно, ваш лучший выбор. Может быть, у парней, которые проводят настоящий анализ, есть идеи.
Я видел нечто подобное, что было сделано для задач, связанных с функциями Ляпунова, когда было необходимо обеспечить соблюдение свойства в каждой точке выпуклой оболочки. Но это пространство было конечным.
Я столкнулся с подобной проблемой. Я искал в Интернете и только сейчас обнаружил, что эта проблема может быть классифицирована как "полубесконечная" проблема. В MATLAB есть инструменты для решения подобных проблем (функция "fseminf"). Но я не проверял это подробно. Конечно, люди сталкивались с такими вопросами.
Вы не должны использовать решатель LP и делать дискретизацию самостоятельно. Вы можете сделать намного лучше, используя приличный общий выпуклый решатель. Проверьте, например, cvxopt. Это может обрабатывать множество различных функций в ваших ограничениях или позволить вам написать свои собственные. Это будет намного лучше, чем пытаться выполнить линеаризацию самостоятельно.
Что касается теплого старта, то для LP он имеет больше смысла, чем обычная выпуклая программа. Хотя "теплый старт" потенциально может быть полезен, если вы вручную пишете весь алгоритм, вам все равно обычно требуется несколько шагов Ньютона, так что выигрыш не так уж значителен. Преимущество теплого старта заключается в таких методах, как активные наборы, которые в основном используются только для LP.