Is this linearization process (of if constraint) correct?


(Dipak Narayanan) #1

I have a nonlinear constraint as below

\sum_{k=1}^Kx_k||w_k||_2^2\le P

Here, x_k\in\{0,1\} is a binary integer variable and {\bf w}_k\in\mathbb{C}^{N\times 1} is another optimization variable.

I would prefer that when x_k==0, the norm of {\bf w}_k should be zero, and when x_k==1, the norm of {\bf w}_k should be non-zero or >0.

The linearization process:
The nonlinear constraint is linearized by adding these following linear constraints.

||{\bf w}_k||_2+Mx_k==0
||{\bf w}_k||_2+M(1-x_k)>0
\sum_{k=1}^K||w_k||_2^2\le P

M is sufficiently large.

Is this linearization process correct?


(Mark L. Stone) #2

No.

Look at Section 2,8 of “FICO Xpress Optimization Suite MIP formulations and linearizationsQuick reference” https://www.artelys.com/uploads/pdfs/Xpress/mipformref-1.pdf .

And by the way, make M as small as possible, i.e., as tight a bound as possible. A large value of M can cause numerical havoc in the solver.


How to transform this objective function under CVX DCP rules?