Max(abs(x) - abs(y)) does not follow DCP rules

1

Hi,

Love this website, just discovered it!
Is there any way to reformulate the following maximization problem in a way that does not violate DCP?

Maximize(abs(x) - abs(y)) where x and y lie in [-100, 100]

Its easy to see that the maximum should be x = 100, y = 0, but the curvature is problematic for cvx:
https://dcp.stanford.edu/analyzer?expr=abs(x)%20-%20abs(y)

Any help/input is greatly appreciated.

Thanks and Regards

2

abs(x) is convex, and -abs(y) is concave. Therefore, abs(x) - abs(y) is neither convex nor concave; therefore can not be handled as is by CVX.

To reformulate for CVX, binary variables must be introduced to “linearize” abs(x) using Big M. You can look up on the internet how to do that. The result will be an MIDCP, presuming CVX’s other rules are followed.

You can leave -abs(y) as is in this example, because it is concave, and therefore can be maximized, and still will be so when the linearization of abs(x) is included.

3

Hi Mark,

Thank-you for your help with this. Followed the binary method here https://orinanobworld.blogspot.com/2012/07/modeling-absolute-values.html with success.

Really makes you wish this was an inbuilt reduction for abs(x) in cvxpy if the original formulation failed DCP.

4

Just as a reminder, this is the CVX forum. CVXPY is a different product.

YALMIP (under MATLAB) will automcatcally do Big M for you, including for non-convex occurrence of abs.CVX makes you do all your Big M modeling manually.