Я работаю с выпуклым QCQP следующим образом:
Min e'Ie
z'Iz=n
[some linear equalities and inequalities that contain variables w,z, and e]
w>=0, z in [0,1]^n
Таким образом, задача имеет только одно квадратичное ограничение, кроме целевого, а некоторые переменные неотрицательны. Матрицы обеих квадратичных форм являются единичными матрицами, поэтому являются положительно определенными.
Я могу переместить квадратное ограничение в цель, но оно должно иметь отрицательный знак, чтобы задача была невыпуклой:
min e'Ie-z'Iz
Размер задачи может достигать 10 000 линейных ограничений со 100 неотрицательными переменными и почти таким же количеством других переменных.
Задачу можно переписать и в виде MIQP, так как z_i может быть бинарным, а z'Iz=n можно удалить. До сих пор я работал с CPLEX через AIMMS для MIQP, и это очень медленно для этой проблемы. Использование версии задачи QCQP с CPLEX, MINOS, SNOPT и CONOPT безнадежно, так как они либо не могут найти решение, либо решение даже близко не соответствует тому приближению, которое я знаю априори.
Теперь у меня три вопроса:
Знаете ли вы какой-либо метод/прием, позволяющий избавиться от квадратичного ограничения в виде этой формы, не переходя к MIQP?
Есть ли «хороший» решатель для этого QCQP? под хорошим я подразумеваю решатель, который эффективно находит глобальный оптимум за разумное время.
Как вы думаете, может ли использование SDP-релаксации решить эту проблему? Я никогда не решал проблему SDP в реальности, поэтому не знаю, насколько эффективной может быть версия SDP. Любой совет?
Спасибо.
z
являются двоичными, то у вас есть MIP с квадратичной целевой функцией, а не задача с квадратичными ограничениями. Что вы подразумеваете под z_i может быть двоичным. - person David Nehme   schedule 17.12.2014