Having the following optimization problem that models $\sum_i\min(c_i, C)$: $$ \min_{\mathbf{Y},\,\,\{x_i\}_i} \sum_i^{n} c_ix_i + C(1-x_i) $$ and where
- $C$ is a positive constant,
- each $x_i$ is a binary variable that can take values in $\{0, 1\}$,
- $c_i\in\mathbb{R}$ is variable whose square $c_i^2$ is constrained by the linear equality: $$c_i^2 = \text{trace}(\mathbf{A}_i\mathbf{Y}),$$ with $\mathbf{Y}$ being a symmetric PSD matrix and $\mathbf{A}_i$ a symmetric real matrix.
Since the number of binary variables $x_i$ can be quite large (more than 100), I have experimented with a semidefinite (SDP) relaxation that drops the binary constraint of each $x_i$. Specifically, I am optimizing $n$ 3x3 PSD matrices $\mathbf{X}_i$ that have the following desired rank-1 global optimum (which I am not currently achieving): $$ \mathbf{X}_i = \begin{bmatrix} x_i^2 & x_ic_i & x_i \\ & c_i^2 & c_i \\ & & 1 \end{bmatrix} $$ Besides the equality constraints that fix the values of $c_i^2$ and $1$, I also impose the binary constraint $x_i^2 - x_i = 0$. However, these constraints are not enough since the trivial solution $c_ix_i=0$ and $x_i=x_i^2=1$ remains feasible regardless of the value of $c_i^2$.
Since my problem is bounded $c_i^2,C<M$, for any possible value of $c_i$ and $C$, a stronger relaxation can be achieved using the big-M method as explained here for a LP problem. However, I am still unable to achieve the desired rank-1 matrix solution $\mathbf{X}_i$ of above.
The result from Exact SDP Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems states:
For binary polynomial optimization problems (POPs) of degree $d$ with $n$ variables, we prove that the $[(n + d − 1)/2]$th semidefinite (SDP) relaxation in Lasserre’s hierarchy of the SDP relaxations provides the exact optimal value.
seems relevant. However I think it is not applicable to my problem, since my problem also involves the continuous variable $c_i^2 = \text{trace}(\mathbf{A}_i\mathbf{Y})$.
Is it possible that achieving the desired rank-1 matrices is impossible due to the strong non-convexity induced by the binary variables?
