2
$\begingroup$

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: \begin{equation} \operatorname*{argmax}_{X_m} \sum_{m=1}^{M}tr(CX_m) \end{equation} subject to: \begin{equation} tr(X_m)=2 \;\; \forall m \end{equation} \begin{equation} Rank(X_m)=1 \;\; \forall m \end{equation} \begin{equation} X_m \succeq 0 \;\; \forall m \end{equation} \begin{equation} tr(\begin{pmatrix} I & G_{0m} \\ G_{0m}^T & 0 \end{pmatrix} X_m) \leq c(epochs)-G_{0m}^TG_{0m} \;\; \forall m \end{equation}

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.