Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
It is all about symmetry. You can use group theory to reduce the size of your search space. –  Piyush Grover May 15 at 11:22
1  
Please be so polite to give at least links to the other place when posting twice the same question. –  j.p. May 15 at 11:28
1  
This blog post is relevant: quomodocumque.wordpress.com/2014/05/10/… –  Kevin Ventullo May 15 at 12:02
    
Somewhat related Math Overflow post: mathoverflow.net/questions/58721/… –  rnegrinho May 23 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 at 23:10

3 Answers 3

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

share|improve this answer

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.

share|improve this answer
    
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 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 at 12:52
1  
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 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$ !

share|improve this answer
    
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 at 16:38
1  
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 at 16:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.