I want to solve this Quadratic Assignment Interger Programming Problem by CVX. The mosek can not solve it directly if m=1008,n=29, (the size of X is large). so I solve the relaxing problem, 0<=X<=1, all entries of X in [0,1], each sum of row of X is 1. I penalty the X_i,j= 0 or 1 by X_ij(1-X_ij), To make the problem convex, I introduce an auxiliary variable Y, where X and Y are equal.
clc;
clear;
rng(123);
%parameter
n = 3;
m = 4;
A = randn(n);
A = A*A'+eye(n);
% Set a positive define matrix
w1=1;
%oldID=readmatrix('30changeablesubsample.xlsx', 'Range', 'C2:C30')';
%O= get_IDmatrix(n,oldID);
pho=100;
M=5;
%%
cvx_begin
% variable
variable X(n,m)
variable Y(n,m)
%objective
objectiveA = 0;
b=0;
for j = 1:m
objectiveA = objectiveA + w1 * quad_form(X(:, j), A);
end
for i=1:n
for j = 1:m
objectiveA = objectiveA + X(i,j) * (Y(i,j)-1);
end
end
a1=ones(n,1);
a2=ones(m,1);
minimize(objectiveA)
%constrit
subject to
0 <= X <= 1
X*a2 == a1
0 <= Y <= 1
Y*a2 == a1
X == Y
cvx_end
However, it is worry.
警告: A non-empty cvx problem already
exists in this scope.
It is being overwritten.
位置：cvxprob (第 28 行)
位置: cvx_begin (第 41 行)
位置: example (第 28 行)
错误使用 .*
Disciplined convex programming error:
Invalid quadratic form(s): not a
square.
出错 * (第 36 行)
z = feval( oper, x, y );
出错 example (第 46 行)
objectiveA = objectiveA + X(i,j) * (Y(i,j)-1);
Your attempted convexification doesn’t make sense.
However, trace(X'*A*X) can be reformulated as square_pos(norm(sqrtm(A)*X,'fro')), which complies with CVX’s rules.
Given that it is the only term in the objective function, there is no need for the squaring (use of square_pos).
Similarly, the last constraint can be reformulated as
norm(X-O,'fro') <= sqrt(2*M)
Thank you. I have a question: how can I deal with the constraint of X_i,j=0 or 1. Why is there wrong for X_i,j*(Y_i,j-1) ? I think it is linear for X_i,j and Y_i,j, respectively.
it is not jointly linear, or jointly convex or concave. “Separately” (respectively) doesn’t count. When anything in CVX is required to be affine, or convex, or concave, that must hold jointly for all CVX (optimization) variables, not separately per variable
X = 0 or 1 can be handled by declaring X as binary:
variable X(m,n) binary
and then don’t include the relaxation 0 <= X <= 1.
Of course, it is then a possibly difficult to solve MISOCP., which the QAP is. The relaxed version should be fast to solve, although its results might be garbage, other than providing a (possibly not very tight) lower bound on the optimal objective value.
Before proceeding, please carefully read
Why isn't CVX accepting my model? READ THIS FIRST!
Thank you. Can I change my variable to x_i,j？ For example,
variable x_1,1
variable x_1,2
variable x_1,3 …
variable x_1,m
like this form.
Not with commas.
But anyhow, I don’t know why you want to do that. An n by m array (matrix) should be convenient, and also lends itself to vectorization of the CVX formulation, which at least reduces model formulation time, even though it might not help with solver time.
I suggest you carefully read the entirety of the CVX Users’ Guide.
If you are going to try to solve the QAP, start with small values of m and n.
I have a question, how does x*ln(x) be expressed in CVX?
Hello, in my thesis derivation, I used a similar form when dealing with binary variables. However, I noticed that you introduced the term X_i,j * (Y_i,j - 1) . Is this term intended to restrict X to be 0 or 1? If so, why is there no penalty coefficient in front of X_i,j * (Y_i,j - 1) ? Have you resolved this part of the problem? I would like to discuss the approach for handling this part. If possible, please contact me at 3217894389@qq.com.
