Is this problem solvable in cvx?

MIDCP
1

Hi all,

I have encountered an optimization problem. I want to find a matrix P so that

minimize W||APB||_2, s.t. P is a permutation matrix.
where W, A, B are known matrices given by specific parameters in the problem. The norm here is Euclidean norm.

Can this problem be solved by cvx? If so, how to formulate the constraint? Thanks in advance!

2

If you have a version of CVX and solver which accepts binary variables

cvx_begin
variable P(size(A,2),size(A,2) binary
minimize(W*norm(A*P*B))
sum(P,1) == 1
sum(P,2) == 1
cvx_end

Edit: Of course, if this is the entirety of your problem, you could solve it by brute force enumeration and calculation of the objective value (if N is small enough) for all N! (if P is N by N) possible values of P, and picking the best.

3

Thank you very much! I have applied the Mixed integer Optimizer from MOSEK in cvx (latest version) to try to solve the problem. The number of all enumerations is 23!x33!, very huge… So brute force enumeration may be not suitable for the problem. I’ve tried the Mixed integer Optimizer and it could yield the solution. But there are two problems:

  1. I implemented the same code (and the same data) in two different computers, but for the two computers, the solutions were different when convergence attained.
  2. When the solver attained convergence in solution, I cannot stop the cvx program in MATLAB using Ctrl+C.
    I am curious where does the problem comes from? Thanks!
4

  1. Were the two solutions within optimality gap tolerance of each other in objective value? It’s certainly possible that the optimal solution is not unique, either exactly, or within tolerance.

  2. See Unstoppable mosek .And somewhat related Can I terminate the program after "some threshold time"? .

5

Thanks for your helpful suggestion! The unstoppable problem in mosek really existed for some computers, but not for all. I don’t know why and also don’t know how to solve it after many attempts. Instead I used Gurobi, and found it worked well and there were no such problems. Though it is much slower than mosek.