‘Shear’ convex polyhedra: solution

Here I describe the solution to the problem from the last post. Spoilers!

As  P_n one may take the simplex 0 \le x_1 \le\, ...\, \le x_n \le 1.  Personally, I think about it as follows: start at the origin, then go to the point  (1, 0,\, ...,\, 0),  then to  (1, 1, 0,\, ...,\, 0),  etc. Finally take the convex hull of all the  n+1  vertices to obtain the simplex. The intuition is that each time forming a new vertex, we go out of the subspace spanned by all previous ones.

Obviously,  W^*(P_n) = n.  On the other hand, It is easy to obtain by some low-level convex optimization reasoning (it’s a good exercise though!) that  w^*(P_n) = 2  and in fact it is attained at any vertex.

Advertisements

About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.
This entry was posted in Pretty little things and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s