Is there a way to expedite the solver for this MIDCP

MIDCP
1

Screenshot 2023-10-12 at 1.54.26 PM
Screenshot 2023-10-12 at 1.54.26 PM892×398 14.8 KB

I have a convex optimization problem as shown above. b is a binary vector. G is a matrix with a size of n by m. g is a vector with a size of n. h_i is i-th row vector of H. h_ij is j-th element of h_i. I used Mosek to solve this problem completely. It takes about 30 seconds. The MATLAB code I used as shown below,

x_max = x_prior + 200;
x_min = x_prior - 200;
% n=14, m=58.
% H matrix is n by m
% diagRs is the sigma vector
cvx_begin
variable x(n)
variable b(m) binary
variable v(n,m)
% Objective function
objf = quad_form(x-x_prior, P);
for i=1:m,
objf = objf + square((y(i)*b(i)-H(i,:)*v(:,i))/diagRs(i));
end
minimize(objf)
subject to
G*b >= g
x_min <= x <= x_max
for j=1:n,
-v(j,:)'+x_max(j)*b >= zeros(m,1);
v(j,:)'-ones(m,1)*x(j)-x_max(j)*b >= -x_max(j)*ones(m,1);
v(j,:)'-x_min(j)*b >= zeros(m,1);
-v(j,:)'+ones(m,1)*x(j)+x_min(j)*b >= x_min(j)*ones(m,1);
end
cvx_end

Is there a way to accelerate the computation? Or break down it into subproblems using BCD. Since this non-linear convex problem can be decomposed into 3 sub-problems:

  1. Quadratic in x
  2. Linear in b (any b_i^2 = b_i)
  3. Quadratic in v
2

I would start by doing the following:

  • Post the optimizer log output.
  • Make sure I use Mosek version 10.1.
  • Maybe relax the stopping criteria. Could be that a 5% optimal solution is good enough. (Cannot say whether this will help since you did not post the log output.)

Also make the objective separable might help.

I would replace

square((y(i)*b(i)-H(i,:)*v(:,i))/diagRs(i));

by

square(t(i));

and the constraint

t(i) = (y(i)*b(i)-H(i,:)*v(:,i))/diagRs(i)

See

for further info.

3

Hi, Thank you so much for the suggestions. Sorry, I didn’t realize that there was a response in my post. If I understand your idea correctly, would the formulation be like as follows?

cvx_begin
variable x(n)
variable b(m) binary
variable v(n,m)
variable h(m)
% Objective function
objf = quad_form(x-x_prior, P) + sum(h);

minimize(objf)
subject to
for i=1:m,
    h(i) = square(y(i)*b(i)-H(i,:)*v(:,i))/diagR(i);
end
G*b >= g
x_min <= x <= x_max
for j=1:n,
-v(j,:)'+x_max(j)*b >= zeros(m,1);
v(j,:)'-ones(m,1)*x(j)-x_max(j)*b >= -x_max(j)*ones(m,1);
v(j,:)'-x_min(j)*b >= zeros(m,1);
-v(j,:)'+ones(m,1)*x(j)+x_min(j)*b >= x_min(j)*ones(m,1);
end
cvx_end
4

Your problem seems to have changed.

@Erling was suggesting replacing

for ...
 ... + `square((y(i)*b(i)-H(i,:)*v(:,i))/diagRs(i));`
end

with

variable t(n)
for ...
 ... + square(t(i))
t(i) == y(i)*b(i)-H(i,:)*v(:,i))/diagRs(i))
end

Note that an equality constraint, which uses
==
is different than assignment to an expression, which uses
=