Quadratic equality constraints via SDP

3.3k Views Asked by At

I want to know if it is possible to solve a QCQP problem with quadratic equality constraints in SDP. I know it is possible to convert a QCQP to an SDP by using the Shur complement. The following worked for me thus far: $$ \begin{equation} \begin{array}{cccccc} \underset{x}{\min} & x^{T}Q_{0}x+q_{0}^{T}x+c_{0} & & \underset{t,x}{min} & t\\ s.t & x^{T}Q_{i}x+q_{i}^{T}x+c_{i}\leq0 & \Longleftrightarrow & s.t & \left(\begin{array}{cc} I & M_{0}x\\ x^{T}M_{0}^{T} & -c_{0}-q_{0}^{T}x+t \end{array}\right) & \succeq0\\ & & & & \left(\begin{array}{cc} I & M_{i}x\\ x^{T}M_{i}^{T} & -c_{i}-q_{i}^{T}x \end{array}\right) & \succeq0\\ & i=1,2,\dots,m & & & i=1,2,\dots,m & \end{array} \end{equation} $$

where $M_{j}M_{j}^{T}=Q_{j}$ (eigendecomposition can also be used, thanks Alt)

However it seems this only applies to quadratic inequality constraints.

I considered converting the desired inequality constraints to equalities by using slack variables but I think that technique only works with linear constraints. I also considered having two constraints like: $$ \begin{equation} \begin{array}{c} x^{T}Qx+q^{T}x+c\leq0\\ -(x^{T}Qx+q^{T}x+c)\leq0 \end{array} \end{equation} $$ To force an equality but the second constraint is not convex so it wont work.

So is there another way to do it?

Edit: turns out quadratic equality constraints are non-convex thus cant be solved directly with this approach

2

There are 2 best solutions below

2
On BEST ANSWER

Hint:

You don't need the constraints $M_{j}M_{j}^{T}=Q_{j}$. For example if $UDU^T$ is the eigen decomposition of $Q_j$, Then $M_j=UD^{\frac{1}{2}}$ (if $Q_j$ is symmetric)

Note that if you introduce new variable $M_j$, then the bilinear forms in the constraints make your problem non-convex, (Besides the fact that equality constraints with quadratic form $M_{j}M_{j}^{T}=Q_{j}$that you have to add also makes the problem non-convex.)

3
On

I cannot see why you should convert a QCQP in an SDP problem. You may want instead to move to a SOCP formulation, which is usually more robust and enjoy a simpler duality theory.

Solvers for QCQP are far more efficient and reliable than SDP ones.