How to write this Norm constraint effieiciently?

MIDCP
1

I have a known Binary Matrix \bf A of size M\times N.
Let \bf B (also a binary matrix of the same size) be an optimization variable.

I want \bf B to be as close as possible. The difference between \bf A and \bf B should be minimal.

The following constraint is working and giving me the desired output. First I vectorize the matrices and use the following constraint.

       norm (A(:)-B(:),1)<=4;

But the problem is that CVX is taking much longer time to give me the output.

How can I resolve this issue? Can I impose the constraint in different ways so that it is efficiently solved?

2

Well it is a binary optimization, so that can potentially be very time consuming to solve - in the worst case, for n not very large, it may not complete before the sun dies. I believe CVX presents this problem to the solver as a Binary ILinear programming problem, which is a type of MILP, Are there any constraints (other than binary restriction)? If so, does the solver have difficulty finding a feasible solution or difficulty closing the MIP gap to optimality?

.Options I can think of are

  1. Use this norm and consider changing solver options using cvx_solver_settings http://cvxr.com/cvx/doc/solver.html#advanced-solver-settings. Thus could be adjusting parameters which control solution strategy, or specifying a larger than default MIP gap

  2. Try another solver. I think your choices under CVX are Gurobi and Mosek.

  3. Try a different norm, such as ‘fro’ or ‘inf’

  4. Choose a means of accessing the solver which allows you to specify an initial (starting) value.for the optimization variable. CVX does not let you do this. Perhaps this will help if you know a good, but not optimal solution. Or if there are constraints, and the solver called by CVX is having difficulty finding any feasible solution.

1 Like
3

Different norms does not provide the expected results. Gurobi is solving much faster! However, is there any other way (formulation) I can define the same constraint, minimizing the mismatch between two matrices?

4

Changing the norm changes the measure of closeness being optimized. it is up to you to decide what is a good measure of closeness for your purposes.