# Is group theory useful in any way to optimization?

For what I have seen, optimization uses a lot of linear algebra and convex analysis, but I have not seen any group theory being used, so I was curious about it.

Is group theory useful in any way to optimization?

-
It is all about symmetry. You can use group theory to reduce the size of your search space. – Piyush Grover May 15 '14 at 11:22
Please be so polite to give at least links to the other place when posting twice the same question. – j.p. May 15 '14 at 11:28
This blog post is relevant: quomodocumque.wordpress.com/2014/05/10/… – Kevin Ventullo May 15 '14 at 12:02
Somewhat related Math Overflow post: mathoverflow.net/questions/58721/… – rnegrinho May 23 '14 at 16:18
I would like to make this question a community wiki. Do you think it is reasonable to do so? – rnegrinho Jun 18 '14 at 23:10

Symmetry groups are certainly an issue in integer programming. Orbital branching is one way of dealing with it. Core points are another relevant concept.

-

To some extent. Here's some relevant material where group theoretic objects show up in optimization (though a lot of it is convex algebraic geometry).

1. Orbitopes
2. Group majorization and a host of majorization inequalities induced by groups (which we may broadly view as being objects in optimization)
3. Optimization over covariance matrices that exploits some group theory.

There are certainly more examples out there, but these should help you get started.

-
Yes, I'm aware that algebraic geometry is finding its way into optimization. I think it is a fairly recent thing. I know that Pablo Parrilo from MIT and Venkat Chandrasekaran from Caltech have been working on using algebraic geometry in optimization. There are a few papers I can point to here, here and here – rnegrinho May 15 '14 at 12:38
@megrinho: indeed, I am well aware of Pablo's work (and of several others in the area that blends convex algebraic geometry with optimization). – Suvrit May 15 '14 at 12:52
I have also seen some work by Morris Eaton and others about the interplay between group-induced majorizations, reflection groups and cone orderings. The theory in itself is quite interesting but, in most cases, doesn't seem to suggest computational ways to tackle the problem, i.e., to optimize over a set defined by means of group-induced majorization. Would you care to comment on this? – rnegrinho May 15 '14 at 16:53

Just an elementary remark, if the function $f:X\to\mathbb{R}$ is invariant under the action of a $G$ on $X$ (meaning that $f(g\cdot x)=f(x)$ then you can, at least morally, search for your minimum on the quotient space $X/G$, which is smaller. However this quotient might be not as nice as the space $X$ you started with.

I'm not sure if this is directly used in some optimization algorithms, however, it can be used implicitly at the modelization step. For instance if you have a function $f$ on $\mathbb{R}^n$ which is invariant under the orthogonal group $O(n)$, then you know that $f(x)=g(\|x\|)$ for some function $g:\mathbb{R}_+\to\mathbb{R}$, and you'd better optimize $g$ on $\mathbb{R}_+$ instead of $f$ !

-
I would guess this would be something interesting to consider in continuous nonconvex optimization, when the cost function has some set of set of symmetries (e.g. invariant of to some or all permutations of the variables). I've never seen this done though. Probably because, as you say, the quotient space is in general not a nice space to work with. – rnegrinho May 16 '14 at 16:38
This fact can (and has been) used in optimization to reduce dimensionality. In some cases, you can convert an SDP into an LP, which is a huge gain for computational solvers. However, convexity is crucial for rigorously reducing the problem to the quotient space. Here are some notes on how this tool can be applied to SDPs with some underlying symmetry arxiv.org/abs/0809.2017 – Cristóbal Guzmán Jul 9 '14 at 16:25