Практический решатель для выпуклого QCQP?

Я работаю с выпуклым 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 безнадежно, так как они либо не могут найти решение, либо решение даже близко не соответствует тому приближению, которое я знаю априори.

Теперь у меня три вопроса:

  1. Знаете ли вы какой-либо метод/прием, позволяющий избавиться от квадратичного ограничения в виде этой формы, не переходя к MIQP?

  2. Есть ли «хороший» решатель для этого QCQP? под хорошим я подразумеваю решатель, который эффективно находит глобальный оптимум за разумное время.

  3. Как вы думаете, может ли использование SDP-релаксации решить эту проблему? Я никогда не решал проблему SDP в реальности, поэтому не знаю, насколько эффективной может быть версия SDP. Любой совет?

Спасибо.


person Alef    schedule 16.12.2014    source источник
comment
Если в модели нет значительной структуры, которую вы понимаете, как использовать в настройках SDP, используя современную теорию редукции симметрии и т. Д., Подход SDP не продвинет вас дальше. Форма MIQP — это то, с чем вам придется работать. Если ни cplex, ни gurobi, ни mosek не смогут решить эту проблему за приемлемое для вас время, вам придется создавать свой собственный решатель, пытаясь использовать структуру проблемы (эвристики, сокращения и т. д.), и надеяться, что вы нашли что-то умное. MIQP в целом неразрешимы, поэтому может случиться так, что вы не сможете их решить.   -  person Johan Löfberg    schedule 16.12.2014
comment
Ограничения квадратичного равенства приводят к невыпуклым задачам. См. и ранее вопрос.   -  person David Nehme    schedule 17.12.2014
comment
Спасибо @DavidNehme! Правильно, задача невыпуклая. Любая идея для решателя для невыпуклого qp?   -  person Alef    schedule 17.12.2014
comment
Большое спасибо @JohanLöfberg! Из вашего комментария я понял, что SDP не может быть хорошим выбором, если я не могу использовать какую-то конкретную структуру модели. Это правильно? Если это так, то я должен вернуться к MIQP. Просто общий вопрос: с чем проще иметь дело и что лучше иметь в статье с точки зрения читателя: MIQP или QCQP? MIQP, по крайней мере, разрешимы, но мне кажется, что реальный QCQP вообще не разрешим. Верно?   -  person Alef    schedule 17.12.2014
comment
Если переменные z являются двоичными, то у вас есть MIP с квадратичной целевой функцией, а не задача с квадратичными ограничениями. Что вы подразумеваете под z_i может быть двоичным.   -  person David Nehme    schedule 17.12.2014
comment
QCQP, как вы его сформулировали, очень сложный (поскольку ослабление ограничения невыпукло, поскольку у вас есть равенство). Однако любой интеллектуальный решатель поймет, как и вы, что он включает только квадраты членов (без билинейных функций) и, следовательно, может быть записан как линейное равенство, сводя задачу к MIQP. Однако в целях безопасности вы можете явно перейти к форме MIQP. Что касается полуопределенной релаксации, то она плохо масштабируется для общих задач и почти наверняка бесполезна.   -  person Johan Löfberg    schedule 17.12.2014