My previous blog item discussed how to represent the set
x^5/3 <= t, x>=0
using linear and quadratic cones. Now the book by Ben-Tal and Nemirovski shows how to represent the set
x^p/q <= t , x>=0 (1)
using conic quadratic cones where p and q are integers and p>=q>=1 which much more general than my example of course. Now the method suggested by Ben-Tal and Nemirovsky is not optimal in a complexity sense. Hence, I do not think it leads to the minimal number of quadratic cones. Therefore, a natural question is: What is the optimal conic quadratic representation of (1)?
Imre Polik wrote to me:
ReplyDeleteThis has also been described in the Alizadeh-Goldfarb SOCP paper (Math. Program., Ser. B 95: 3–51 (2003)). Actually, sums of products of variables with rational powers can be modelled this way. Finding the best representation seems to be a hard problem in this general setting, but maybe (1) is easier. Alizadeh-Goldfarb only note that the representation is not unique
I'd love to know what the answer to this is---because I do some sort of rational decomposition in CVX to convert powers to second-order cones. I try to be as efficient as possible but I do not know if I've succeeded. Check my CVX user guide, Appendix D.2, for a rough description.
ReplyDelete