Any recommended solver? Objective function involves max operator and polynomials of power 3, linear constraints

[Jinyu Xie]

Hi folks,

The optimization problem is quite typical, which is as follows:

where a, b, c, d, q are constant.

The objective function inside of the summation is convex, and I have plotted here:

I tried Sedumi, which run intio numerical problem, but it gave a solution. 

I tried SDPT, but throwed me error. 

I tried fmincon, which took super long and freezed my computer.

Any other suggestions on solver? Or perhaps my problem is ill-conditioned?

I have attached the code and state matrices. 

Thanks very much!

Jinyu

[Johan Löfberg]

Look like you really haven't thought through the analysis here and you just tried to throw a solver at it. Have you done convexity propagation to see that max(0,.^3) actually is convex.

Luckily, it is convex, and more importantly obeys simple convexity propagation rules, and is SOCP representable. Hence sedumi is applicable. You can not simply throw a power on it though. YALMIP has to be told to do convex modelling on the polynomial, max(0,c*cpower(d - BG,3))

[Jinyu Xie]

Thank you for the quick reply! I don't have too much background of convex programming. Does the "convexity propagation" mean that you pick a bunch of x1, x2 and see whether f(x1 + lambda*x2) >= f(x1) + lambda*f(x2), lambda in (0, 1)? What is the definition of "simple convexity propagation rules"? Is there any book or resources I can refer to? 

Thank you very much!

Jinyu

[Johan Löfberg]

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.GraphRepresentations

[Johan Löfberg]

model is probably not want you want, as cpower requires/adds d - BG>=0 to ensure convexity

[Johan Löfberg]

Although, if you minimize max(0,x^3), you can replace it with max(0,e^3) s.t e>=x. Hence use cpower with new variable, and the added positivity will not effect the underlying variable, but the optimal value of the objective will be tight

[Jinyu Xie]

Thank you for your link. I don't want to restrict BG so that BG <=d. 

The idea of this objective function is that

1) When d - BG < 0, the objective function becomes a*BG + b, which is linear. 

2) When d - BG >= 0, the objective function becomes a*BG + b + c*(d - BG)^3, which is still convex. And the cost when BG is close to 0 will become very high.

Is there any way to invoke cpower correctly?

Thank you very much!

[Johan Löfberg]

As I said, the convex operator max(0,x^3) is SOCP representable when used in a convexity preserving fashion, as max(0,cpower(e,3)) with constraint e>=x (if you try to push down this function, you will have e trying to be as close as x as possible, hence for positive x, e=x and the cost will be x^3 When x is negative, e will stop at e=0 and the cost will be 0)

For simplicity, I added an operator. Place it in yalmip/operators

[Jinyu Xie]

Thank you very much! I used hinge instead. Sedumi didn't run into numerical problem this time.