most recent 30 from http://mathoverflow.net 2013-05-24T10:48:44Z http://mathoverflow.net/feeds/question/40208 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/40208/a-different-algebra-representation-for-convex-sets Injun Joe 2010-09-27T20:45:15Z 2010-09-27T21:52:09Z

<p>Hi,<br> I was dealing with finding a feasible region for a set of norm inequalities and the feasible region is convex. The question is not about how to find the feasible region but how to represent the final feasible region.</p> <p>At the risk of sounding vague, my question is - Is there a system of algebra which is better in representing higher dimensional convex sets. So that if the feasible region is not a convex polytope but something else, we can still obtain a closed form representation of the feasible region.</p> <p>Thanks<br> I</p>

http://mathoverflow.net/questions/40208/a-different-algebra-representation-for-convex-sets/40214#40214 Tony Huynh 2010-09-27T20:56:45Z 2010-09-27T20:56:45Z

<p>This question is a bit vague, but you may be looking for Motzkin's decomposition theorem. This theorem says that any polyhedral convex set can be expressed as the Minkowski sum of a polytope and a polyhedral convex cone. In particular, this shows that a bounded polyhedron is in fact a polytope. </p>

http://mathoverflow.net/questions/40208/a-different-algebra-representation-for-convex-sets/40215#40215 Noah Stein 2010-09-27T20:58:02Z 2010-09-27T20:58:02Z

<p>Of course it's hard to say without any information, but linear matrix inequalities may be what you're looking for. They are to semidefinite programs what linear inequalities are to linear programs. There are a variety of inequalities relating norms, eigenvalues, singular values, etc. which can be written using these. The resulting feasible sets are convex and semialgebraic (given by polynomial inequalities) but need not be polyhedral. See the overview article "Semidefinite Programming" by Vandenberghe and Boyd for lots of examples and more information.</p>

http://mathoverflow.net/questions/40208/a-different-algebra-representation-for-convex-sets/40224#40224 Brian Borchers 2010-09-27T21:52:09Z 2010-09-27T21:52:09Z

<p>These kinds of feasible sets can often be written in terms of second order cone programming and/or semidefinite programming constraints. If that's the case, then optimizing over the feasible set is relatively easy. Techniques for rewriting norm constraints in this way are discussed in the textbook "Convex Optimization" by van den Berghe and Boyd. </p>