Inscribe a polytope in an ellipsoid

[Cristina Magnetti Gisolo]

Hello, 

thank you for opening this conversation.

I have an ellipsoid 

where n = 43, and I want to find the maximum volume symmetric polytope 

inscribed in that ellipsoid. I would like to have all equal rho1(i) for the first 21 variables of x and, in general, another rho2(i) equal for the last 22 variables of x. 

rho1 and rho2 are independent from one another, so I start computing rho1 and find the first 21 components of the polytope.

To inscribe the polytope in the ellipsoid, I define the following LMIs

where Q has 21 rows and Qx is a vector with the first 21 x variables on the rows. 

To maximize the polytope, I would maximize rho1, but then the matrix inequality would be bilinear. So, I define rho1^2 as variable and choose to maximize rho1^2.

I get an 'Unbounded objective function' error message, but the ellipsoid is finite... If I project it on a subspace generated by the first two variables (x1,x2), the ellipse is finite and it is the same for any choice of (x_i,x_j) with i,j = 1,..,21. 

Moreover, if I minimize rho1^2, I get that rho1^2 = 3.9707, so rho1 = 1.9927. But, from the definition of the polyotope, it means that 

x1 <= 1.9927

and it is clearly not contained in the ellipsoid. 

So I don't think I'm inscribing a polytope in that ellipsoid... 

I can't figure out what's wrong in what I'm doing. Maybe there's another way? A simpler method? 

Thank you in advance

[Cristina Magnetti Gisolo]

*Forgot the script 

[Cristina Magnetti Gisolo]

And the P matrix 

[Johan Löfberg]

I have no idea where you got that model from. It is pretty obviously wrong as setting rho^2 to inf will make the semidefinite constraint feasible for any Q

Also, the representation of the polytope is bad as it is homogenuous is Q and rho, meaning that rho cannot be a measure of the size, becuase if it is, then you can make it 10 times larger by simply replacing (Q,rho) with  (Q*10,rho*10) which doesn't make sense since that still represents the same feasible space du to the homogenuous form

Finally, the general problem of finding the smallest possible elliposid inscribing a polytope in H-represenation (which would be somewhat like largest possible polytope in ellipsoid) is hard. I don't know of any nice representations of that problem. Smallest possible ellipsoid when polytope is in V-representation is easy, and largest possible ellipsoid inside a polytope in H-representation is easy.

[Cristina Magnetti Gisolo]

I computed P from another optimization problem and the LMIs that ensure the inclusion of the polytope in an ellipsoid are defined in "Stability and Stabilization of Linear Systems

with Saturating Actuators" by S. Tarbouriech. 

There's no way to find the maximum volume polytope in an ellipsoid then? 

[Cristina Magnetti Gisolo]

Neither fixing rho and definining a scale factor for Q and minimizing this factor?

[Johan Löfberg]

Already the "simple" act of computing the volume of a polytope is hard (as in computationally intractable in theory). Maybe you've got some special structure on your which could make it tractable, but I doubt that, and then the next step is to formulate that into an optimization problem so you can optimize that volume

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.42.7953

https://en.wikipedia.org/wiki/Convex_volume_approximation

[Cristina Magnetti Gisolo]

Ok, thank you. 

[Cristina Magnetti Gisolo]

Even if I don't maximize the volume of the polytope and I get any matrix Q and vector rho, is there a way to define the polytope and represent its projections on a 2D subspace?

[Johan Löfberg]

Given a polytope A[x;y]<=b, it is a classical problem to compute the projection to x. It is, as many other problems in polytopic geometry, a very hard problem but there are packages which are focused on this. In matlab MPT for instance. Whether it can compute an exact  projection from R^43 to R^2 is another question though...

Optimizing over the projection is trivial though as it simply means the constraint must hold, and numerically plotting an approximation means you maximize c'*x over A[x;y]<=b for a large number of directions c and plot the solutions which all will be on the border of the projection

[Cristina Magnetti Gisolo]

Thank you very much