# SDP relaxation with greater-than and less-than inequalities at the same time

I am dealing with the following nonconvex fractional quadratic optimization problem

\begin{align} & \min_{\boldsymbol{x}} && \max_{t \in \mathcal{T}} \frac{\boldsymbol{a}_t^T \boldsymbol{x}}{\boldsymbol{x}^T \boldsymbol{Q}_t\boldsymbol{x}}& \\ & && x_j\in\{0,1\}, & j = 1,\dots,N \end{align}

where $$\boldsymbol{x}=[x_1,\dots,x_N]^T$$, $$\boldsymbol{a}_t = [a_{1t},\dots,a_{Nt}]^T\, \forall t \in \mathcal{T}$$ and $$\boldsymbol{Q}_t \in \mathbb{R}_+^{N \times N} \, \forall t \in \mathcal{T}$$ is a stricly lower triangular (positive semidefinite) matrix. By applying the SDP relaxation together with the linearization of the binary constraint, I get the following

\begin{align} & \min_{\boldsymbol{X}} && \max_{t \in \mathcal{T}} \frac{\text{Tr}(\boldsymbol{X} \odot \text{diag}(\boldsymbol{a}_t))} {\text{Tr}(\boldsymbol{Q}_t\boldsymbol{X})} & \\ & && \boldsymbol{X} \succeq \boldsymbol{x}\boldsymbol{x}^T\\ & && X_{jj} \in [0, 1] & j = 1,\dots,N \end{align}

with $$\text{Tr}$$ being the trace of a square matrix, $$\text{diag}$$ indicating a diagonal matrix whose diagonal is made out of the function argument and $$\odot$$ denoting the Hadamard product. To write the numerator, I exploit the property $$X_{jj} = x_j$$, being $$x_j$$ binary in the original problem.

The relaxed problem can be solved by means of the bisection method, so I can write a series of feasibility problems for decreasing values of a predefined threshold $$z$$ and solve them until the problem gets infeasible. I use CVX for this task.

\begin{align} & \text{Find} && \boldsymbol{X} && \\ & && \text{Tr}(\boldsymbol{X} \odot \text{diag}(\boldsymbol{a}_t)) \leq z\, \text{Tr}(\boldsymbol{Q}_t\boldsymbol{X}) & \forall t \in \mathcal{T}\\ & && \boldsymbol{X} \succeq \boldsymbol{x}\boldsymbol{x}^T\\ & && X_{jj} \in [0, 1] & j = 1,\dots,N \end{align}

I pick the last feasible solution $$\boldsymbol{X}^*$$ as solution of the SDP relaxation. For simplicity, I use the Eigenvalue Decomposition (EVD) procedure to derive a rank-1 solution $$\hat{\boldsymbol{x}}$$ from $$\boldsymbol{X}^*$$. In particular, after approximating $$\boldsymbol{X}^*$$ as $$\lambda_1 \boldsymbol{q}_1 \boldsymbol{q}_1^T$$, where $$\lambda_1$$ is its highest eigenvalue and $$\boldsymbol{q}_1$$ the corresponding eigenvector, I set $$\hat{\boldsymbol{x}} = \sqrt{\lambda_1}\boldsymbol{q}_1$$.

To enforce constraints $$x_j < 1$$, I would perform the normalization $$\hat{\boldsymbol{x}}/\max_j \sqrt{|\hat{x_j}|}$$ and then obtain a binary solution $$\boldsymbol{x}^*$$ by quantization.

It is not clear to me if I am ignoring constraints $$x_j > 0$$ or if not, why. Moreover, in another version of this problem, I have a constraint of type $$\text{Tr}(\boldsymbol{X}) \ge n, \, k\in \mathbb{N}$$, which is a greater-than constraint. How is it to be treated with respect to the other constraints? How would you treat greater-than and less-than constraints if present at the same time? Thank you.

• Can you show more details of how you go from the SDP formulation to the rank-1 solution? – Mark L. Stone Jun 22 '20 at 12:47
• Sure. I perform the Eigenvalue Decomposition of the solution of the SDP relaxation $\boldsymbol{X}^*$. Then, I approximate it as $\boldsymbol{X}^* \approx \lambda_1 \boldsymbol{q}_1 \boldsymbol{q}_1^T$, where $\lambda_1$ is the highest eigenvalue and $\boldsymbol{q}_1$ is the corresponding eigenvector. Finally, I set $\hat{\boldsymbol{x}} = \sqrt{\lambda_1} \boldsymbol{q}_1$. – Antonio Albanese Jun 22 '20 at 13:12
• How are you solving the SDP relaxation? You should all all these details to the question itself, not just in comments. – Mark L. Stone Jun 22 '20 at 14:01
• Are you enforcing $X_{i,i}=x_i$? Also, if your rounded solution has negative coefficients, you could try a doubly non-negative relaxation instead of the usual SDP relaxation (i.e. adding the constraint $X \geq 0$ elementwise). – Ryan Cory-Wright Jun 22 '20 at 22:21
• @MarkL.Stone I've added more details to the solution. – Antonio Albanese Jun 23 '20 at 7:20