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

У меня есть программная формулировка из статьи, и я хочу дать ей инструмент для решения конкретных задач. Авторы заявили, что это пример линейного программирования (LP), однако я не уверен. Формулировка примерно такая:

max x1+x2+x3...

s.t.

x1.x3+x4.x5 <= 10

x2.x5+x3.x7+x1.x9 <=10

...

Я попытался запрограммировать его с помощью функции cplexqcp (из-за квадратичных ограничений, однако ограничения не включают в себя какую-либо переменную x_i^2). Однако я получаю CPLEX Error 5002: Q in %s is not positive semi-definite error. Является ли это примером нелинейного программирования с невыпуклыми ограничениями? Могу ли я решить это с помощью CPLEX или использовать для этого инструмент NLP? Я новичок в персонале LP/NLP (не хожу на курсы по ним), поэтому очень жду помощи в объяснении подробностей ответов на мои вопросы.

Огромное спасибо.


math mathematical-optimization nonlinear-optimization cplex convex
person john m    schedule 10.03.2014    source источник
comment
Возможно, вам больше повезет на scicomp.stackexchange.com.   -  person Ali    schedule 10.03.2014
comment
Этот вопрос кажется не по теме, потому что он касается математического программирования.   -  person Ali    schedule 10.03.2014
comment
Я добавил математическую оптимизацию к ключевым словам.   -  person john m    schedule 10.03.2014

Ответы (1)


arrow_upward
2
arrow_downward

Проблема, которую вы опубликовали, требует некоторой информации о домене переменных x1, x2 и x3.

Если они непрерывны, вашу задачу невозможно выразить в виде линейной программы (ЛП), поскольку поверхность x1*x2 просто нелинейна.

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

Cplex может в основном решать некоторые классы квадратичных задач. Судя по вашему сообщению об ошибке, ваша проблема здесь не при чем. Таким образом, для решения этой проблемы вам, вероятно, потребуется использовать решатель НЛП общего назначения. Примерный список решателей можно найти здесь, все они могут запускаться программным обеспечением AMPL, или можно использовать отдельно. Я не эксперт здесь, поэтому я не могу дать совет, какой решатель следует предпочесть для вашей проблемы.

С уважением, Мартин

person Martin    schedule 12.03.2014
comment
Мартин, большое спасибо за ответ. Это очень полезно. Переменные не являются непрерывными, вместо этого все они являются целыми числами. Так что в этом случае я могу использовать [ссылка] (leandro-coelho.com/linearization -product-variables) ссылку, чтобы сделать их линейными? Однако, насколько я понимаю, мне все еще может понадобиться решатель НЛП, если я получаю ошибку раньше? Итак, шаги, пытающиеся линеаризовать формулировку, если я все еще получаю ошибку, чем использовать решатели НЛП, правильно ли это? - person john m; 12.03.2014
comment
Когда ваши переменные являются целыми, проблема может быть выражена как смешанная целочисленная линейная задача, т. е. все ограничения являются линейными — вы обходите квадратные выражения с помощью условий целочисленности. Таким образом, его можно решить с помощью стандартного cplex (вам не нужен квадратичный решатель) с помощью симплекса и ветвей и границ. Вы не должны получать сообщение об ошибке, когда все продукты линеаризованы, однако может оказаться, что скорость решения неудовлетворительна, в зависимости от размера ваших задач. - person Martin; 12.03.2014
comment
Мартин, линеаризация ссылки на продукт дает подсказки о двоичных переменных, однако переменные в моей модели являются целыми числами (могут быть 3, 4 и т. д.). Есть ли способ линеаризовать и эти условия? - person john m; 13.03.2014
comment
Важно, чтобы каждая из ваших целочисленных переменных была ограничена числом n (я думаю, иначе это не сработает). Затем вы можете воспроизвести каждую целочисленную переменную I серией двоичных переменных x_i, т. е. I = 1x_1+2x_2+ 3x_3 ... + nx_n. Каждое произведение целых чисел является произведением двоичных чисел. Вы можете линеаризовать каждое произведение соответствующих бинарных переменных. Вздутие делает его неэффективным/эффективным для более крупных проблем... - person Martin; 13.03.2014