2
$\begingroup$

Hi,
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.

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.

Thanks
I

Improve this question
$\endgroup$
7
  • $\begingroup$ Have you looked over the different representations here and found them lacking? en.wikipedia.org/wiki/Convex_polytope $\endgroup$
    – j.c.
    Commented Sep 27, 2010 at 20:58
  • $\begingroup$ Do you mean a representation of convex sets that are not necessarily polytopes? $\endgroup$
    – Deane Yang
    Commented Sep 27, 2010 at 21:52
  • $\begingroup$ Thanks for the comments. Yes I actually mean a representation of convex sets that is not necessarily polytopes. $\endgroup$
    – Injun Joe
    Commented Sep 28, 2010 at 6:39
  • $\begingroup$ I'm not sure what you mean by a "system of algebra", but does the support function meet your needs? It is nice in the sense that adding two support functions corresponds to pointwise addition of the corresponding convex sets. Also, the support function of the polar convex set is the homogeneous Legendre transform of the support function of the original body. $\endgroup$
    – Deane Yang
    Commented Sep 28, 2010 at 14:25
  • $\begingroup$ By 'system of algebra', I meant that like geometric algebra is much more elegant while modeling points in space and associated geometric transformations instead of representations like vector space or quaternions - Whether there was something similar for convex sets. Is there a straightforward way to go from a linear matrix inequality to a support function (I would be able to represent my sets of norm inequalities into a linear matrix inequality)? $\endgroup$
    – Injun Joe
    Commented Sep 28, 2010 at 15:17

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .