3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you show more details of how you go from the SDP formulation to the rank-1 solution? $\endgroup$ – Mark L. Stone Jun 22 at 12:47
  • $\begingroup$ 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$. $\endgroup$ – Antonio Albanese Jun 22 at 13:12
  • $\begingroup$ How are you solving the SDP relaxation? You should all all these details to the question itself, not just in comments. $\endgroup$ – Mark L. Stone Jun 22 at 14:01
  • $\begingroup$ 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). $\endgroup$ – Ryan Cory-Wright Jun 22 at 22:21
  • $\begingroup$ @MarkL.Stone I've added more details to the solution. $\endgroup$ – Antonio Albanese Jun 23 at 7:20

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.