The non-convex problem

MIDCP
1

\begin{array}{ll} \text{minimize} &\|A-Dx\|_2 \\ \text{subject to} &x*(x-1)=0 \\ &x_1+x_2+ \cdots + x_{31} + x_{32} = 1 \\ &x_{33}+x_{34}+ \cdots + x_{63} + x_{64} = 1 \\ &\vdots \\ &x_{961}+x_{962}+ \cdots + x_{991} + x_{992} = 1 \\ &x_{993}+x_{992}+ \cdots + x_{1023} + x_{1024} = 1 \end{array}

where \quad x\in\mathbf{R}^{1024}, \quad x=[x_1,x_2,\cdots,x_{1023},x_{1024}]^T,\quad A\in\mathbf{C}^{256}, \quad D\in\mathbf{C}^{256\times1024}, A and D are both known.
I previously attempted to directly declare the variable x as a binary number, making the above problem conform to CVX’s DCPs.

cvx_begin
    cvx_solver MOSEK;
    variable x(1024) binary;
    minimize(norm(A-D*x, 2));
    subject to
        for i = 1:32
            sum(x((i-1)*32+1:i*32)) == 1;
        end
cvx_end

However, it took an extremely long time to solve. Once the dimension of x increases, this approach becomes impractical.
How can I model the above non-convex problem using the CVX? I would greatly appreciate your assistance in resolving this problem.

3

You already formulated it as an MISOCP. As with MILPs, MISOCPs might take a long time to solve, or might not. You can play with solver options, including gap tolerance termination criteria. Gurobi or Mosek can be used with CVX for MISOCP. One solver might potentially be much (orders of magnitude) faster than the other on some binary or integer problems.

But to an extent, you have to be lucky.

4

I tried switching to Gurobi for solving, but it also took too long. Even when I modified the gap tolerance, it only worked when I set it to a very large value, but the results didn’t meet the design requirements. Otherwise, it still took a long time. Therefore, if we don’t consider it from the perspective of integer programming but rather from the perspective of convex programming, the primary reason for the non-convex problem above is the constraint x(x−1)=0. Is there a good way to relax this constraint to make it conform to DCPs?

5

You can relax to x being continuous, with the constraint 0 <= x <= 1. Whether the result is any good is for you to determine. However, I believe that would be the root relaxation, so if you are not satisfied with the MISOCP solution with large gap, I presume you won’t be satisfied, and maybe less so, with the solution to this relaxation.

You are not the first person in history to formulate a MILP or MISOCP for which the solution time does not meet your requirements.

6

Yes, you’re right. I tried relaxing the constraint to '0 <= x <= ', but the results weren’t satisfactory. I’ll try modifying the model again to see if there’s a better way. Thank you for your help.

7

You can try using the Gurobi tuner on a not too large version of the problem, Use cvx_solver_settings to set the needed solver options. Actually, I’ve never tried this using CVX, so not sure whether it works. I have done it using YALMIP by specifying the solver options to invoke the tuner.