Element Wise Division in Inequality Constraints ( Not solvable by CVX. Cause DCP Error)

[Avinash Modi]

Hi All,

I want to solve a minimization problem, which has element wise division as constraints. I have tried to use CVX but the CVX caused DCP (Disciplined Convex Programming) error. Although, the constraint is convex. Is there any other way/library/solver that I can use to solve.

The problem is as follows:

min ||x||_1 such that ((y-Ax).^2)./Ax \leq \epsilon

./ is element wise division.

Thanks

[Johan Löfberg]

It is not a convex constraint, as it depends on the sign of the denominators

If you know Ax>0 (which would be the convex case) it is simply (y-A*x).^2 <= epsilon *A*x

In general, it would be the MISOCP represenatable set (Ax < 0) or (Ax>0  &   (y-A*x).^2 <= epsilon *A*x) which would be easily represented using two implies operator

[Avinash Modi]

Thanks Johan.

Yes Ax>0 indeed in my case(sorry for not mentioning before). But the problem comes when we use following minimization problem

min ||x||_1 such that norm((y-Ax)./sqrt(Ax), 2) \leq \epsilon

I dont see if there is any way i can take denominator to Right hand side. Is there any workaroud/suggestions.

Any suggestion/help would be welcomed.

Thanks again.

[Johan Löfberg]

So you have a completely different problem compared to the one you asked about...

sqrt( (y1/sqrt(x1)) ^2+ (y2/sqrt(x2)^2) <= eps

would be equivalent to

(y1/sqrt(x1)) ^2 + (y2/sqrt(x2)^2)  <= eps^2

which woukld be equivalent to 

z1^2 + z2^2 <= eps^2

y1^2/x1 <= z1

y2^2/x2 <= z2

which is

z1^2 + z2^2 <= eps^2

y1^2 <= z1*x1

y2^2 <= z2*x2

which is a combination of a quadratic constraints and rotated SOCP constraints, i.e. easily SOCP representable