# Simplification of a Quadratically constrained, Quadratic objective (to apply Semidefinite relaxation)

I came up with the following optimization problem:

$$\arg\max_{G_i} \quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$ subject to: $$\|G_i\|_2^2=1 \quad \forall i$$ $$\|G_i-G_{o_i}\|_2^2\leq c \quad \forall i$$ $$|G_i^TG_j|\leq\epsilon \quad \forall i,j,i\neq j \quad$$ $$\sum_{j=1}^{n} G_i(j)=0 \quad \forall i,j,i\neq j \quad$$ where $$G_i \in R^n$$.

Is there any way to somehow factor out $$I^TI$$ and convert it to semidefinite programming problem? how could I use semidefinite Relaxation for this problem?

I tried to use semidefinite relaxation, but the second and third constraints are hard to deal with for me:

Let: $$C=I^TI, X_i=G_iG_i^T$$

Now we can rewrite the problem as: $$\arg\max_{X_i} \quad \sum_{i=1}^{N} tr(CX_i)$$ subject to: $$tr(X_i)=1 \quad \forall i$$ $$X_i\succeq 0 \quad \forall i$$ $$Rank(X_i)=1 \quad \forall i$$ $$\|G_i-G_{o_i}\|_2^2\leq c \quad \forall i$$ $$|G_i^TG_j|\leq\epsilon \quad \forall i,j,i\neq j \quad$$ $$\sum_{j=1}^{n} G_i(j)=0 \quad \forall i,j,i\neq j \quad$$

But I don't know how to rewrite last two constraints based on $$X_i$$. Update: Let $$[G_i\;1]^T$$ as the new variable for the problem, the second constraint could be homogenized. But still the third and forth constraints, I don't know how to write them based on new variable.

Update:

Let $$x_m = \begin{pmatrix} G_m \\ t_m \end{pmatrix}$$ and $$X_m=x_mx_m^T$$, now we can rewrite the problem as follows: $$$$\operatorname*{argmax}_{X_m} \sum_{m=1}^{M}tr(CX_m)$$$$ subject to: $$$$tr(X_m)=2 \;\; \forall m$$$$ $$$$Rank(X_m)=1 \;\; \forall m$$$$ $$$$X_m \succeq 0 \;\; \forall m$$$$ $$$$tr(\begin{pmatrix} I & G_{0m} \\ G_{0m}^T & 0 \end{pmatrix} X_m) \leq c(epochs)-G_{0m}^TG_{0m} \;\; \forall m$$$$

$$$$tr(\begin{pmatrix} \mathbf{0} & \frac{I}{2} \\ \frac{I}{2} & 0 \end{pmatrix} X_m)=0 \;\; \forall m$$$$

$$$$tr(\begin{pmatrix} \mathbf{0} & \mathbf{0} \\ \mathbf{0} & 1 \end{pmatrix} X_m)=1 \;\; \forall m$$$$

Now Just the orthogonality constraint remains. In fact, I don't need $$G_i$$s to be orthogonal, I just want they are different.

• What exactly is $I$? – Rodrigo de Azevedo Apr 9 at 8:00
• Your problem is the nonconvex quadratic equality constraint and the final nonconvex bilinear constraint, not the objective which is a convex quadratic – Johan Löfberg Apr 9 at 10:27
• @RodrigodeAzevedo $I$ is a $m*n$ matrix, so $I^TI$ has the dimension $n*n$ – Panda Apr 9 at 13:37
• Draw the feasible set for the constraint $x^2 = 1$ where $x$ is a scalar... – Johan Löfberg Apr 9 at 14:15
• and no, these are intrinsically nonconvex sets – Johan Löfberg Apr 9 at 14:16