Adding a binarization penalty term

1

Hello guys,

First of all: I am an absolute beginner in terms of convex optimization and DCP.

I am using CVX to solve the following problem:

variable x(n)
minimize: norm(A*x - b)
subject to: 0 <= x <= 1

Being a part of an iterative algorithm I try to introduce some kind of penalty Term to get the elements of x to converge to 0 and 1 respectively. The binarization term is meant to have an higher impact by increasing a weighting factor lambda with every iteration. So CVX shall solve the problem in every iteration of the algorithm with an increased value of lambda until x persists only of 0s and 1s.

I can think of various ways to mathematically formulate this but I was unable to translate this into DCP so far.

Can anyone of you help me out with this?

Thank you very much for all replies in advance

2

If you have gurobi or mosek available, you can use CVX’s MIDCP capability by declaring x to be binary.http://cvxr.com/cvx/doc/basics.html#variables and specifying gurobi or mosek as the solver.http://cvxr.com/cvx/doc/solver.html#selecting-a-solver

cvx_begin
variable x(n) binary
minimize: norm(A*x - b)
cvx_end
3

First of all thank you for your reply!

Wouldn’t this enforce x to be purely binary from the very first iteration?
It is important, that I allow x to be continous in the early iterations of the algorithm and then force it to become more and more close to a binary solution.

I’m looking for someething like this (though I don’t know if this is possible):

cvx_begin
variable x(n)
variable x_binary binary
minimize: norm(A*x - b) + norm(x - x_binary)
cvx_end

where x_binary is the binarized version of x using a threshold of 0.5

4

Well, then I don’t understand what you are trying to do.

Presuming the status is reported as solved, the code in my post will result in the solution to your problem, with all elements of x being either zero or one (within integrality tolerance). There may be many iterations performed by the solver CVX calls, but you only need one invocation of CVX, which will produce the desired optimal binary solution. If this does not suit your needs, why not?