How to express (3x^2)/(4+2abs(x)) in CVX

#1

Hi all,

I’ve confirmed that this function is convex for all x in R. I try to use quad_over_lin(Q,L) to express this, where Q = 3x^2, L = 4+2abs(x)
However, CVX told me the second term (L) should be concave. How to fix this problem? Or should I try another way?

(Erling D.Andersen) #2

This

x<=y
-x<=y
L = 4+2*y

will NOT work and hence you should try another way. To me it seems nonconvex.

(Henrik A. Friberg) #3

Erling is right that the presence of |x| in the denominator is only tolerable (i.e., results in a convex expression) because of x^2 in the numerator. In general you’ll find that such strong couplings makes it far trickier to reformulate. In case of
t \geq \frac{3 x^2}{4 + 2 |x|}
it is not too difficult (plot the graphs + trial-and-error) to see that it is equivalent to
t \geq \frac{3 x^2}{4 + 2 x} and t \geq \frac{3 x^2}{4 - 2 x}
but this trick only works on the limited domain -2 \leq x \leq 2 on which both denominators are nonnegative.

If you want the full domain you’ll need to follow the MOSEK cookbook on piecewise functions (https://docs.mosek.com/modeling-cookbook/practical.html#convex-univariate-piecewise-defined-functions) which in case of
t \geq \frac{3 x^2}{4 + 2 |x|}
results in
t = t_1 + t_2,
x = x_1 + x_2,
t_1 \geq \frac{3 x_1^2}{4 + 2 x_1} and t_2 \geq \frac{3 x_2^2}{4 - 2 x_2}.

2 Likes
#4

Thanks for your answer. I expressed my function into a form of minimize t given the condition you provided and successfully got the results from CVX. Thanks again for your help!

2 Likes
(Henrik A. Friberg) #5

As I read your “Thanks for your answer” it immediately popped. It’s symmetric… there should be an alternative representation… Ohhhh…!

t \geq \frac{3 x^2}{4 + 2|x|} = \frac{3 |x|^2}{4 + 2|x|}

so this is the same as

t \geq \frac{3 r^2}{4 + 2r} and r \geq |x|.

You can confirm the validity of the substitution with the composition rules of nested nonlinearity in the cookbook (https://docs.mosek.com/modeling-cookbook/practical.html#nested-nonlinearity). How silly of me not to think of this first :wink:

2 Likes
#6

Compared to the first version, this version looks more efficient and beautiful than the first one. I find it is an art to reformulate a function into a form that CVX can recognize. Also, thanks for your recommendation for that cookbook. It helps me a lot and gives me a guide to deal with more complicated functions. Really thanks for your help.

1 Like
(Erling D.Andersen) #7

Proving convexity is NP hard. Therefore, it is going to be an art to figure the reformulation in some cases.

The upside is a human in the loop is needed.