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?
$\begingroup$
$\endgroup$
4
-
4$\begingroup$ It is all about symmetry. You can use group theory to reduce the size of your search space. $\endgroup$– Piyush GroverCommented May 15, 2014 at 11:22
-
3$\begingroup$ Please be so polite to give at least links to the other place when posting twice the same question. $\endgroup$– j.p.Commented May 15, 2014 at 11:28
-
1$\begingroup$ This blog post is relevant: quomodocumque.wordpress.com/2014/05/10/… $\endgroup$– Kevin VentulloCommented May 15, 2014 at 12:02
-
$\begingroup$ Somewhat related Math Overflow post: mathoverflow.net/questions/58721/… $\endgroup$– rnegrinhoCommented May 23, 2014 at 16:18
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
Symmetry groups are certainly an issue in integer programming. Orbital branching is one way of dealing with it. Core points are another relevant concept.
$\begingroup$
$\endgroup$
2
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$ !
-
$\begingroup$ 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. $\endgroup$ Commented May 16, 2014 at 16:38
-
2$\begingroup$ 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 $\endgroup$ Commented Jul 9, 2014 at 16:25
$\begingroup$
$\endgroup$
3
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).
- Orbitopes
- Group majorization and a host of majorization inequalities induced by groups (which we may broadly view as being objects in optimization)
- Optimization over covariance matrices that exploits some group theory.
There are certainly more examples out there, but these should help you get started.
-
$\begingroup$ 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 $\endgroup$ Commented May 15, 2014 at 12:38
-
$\begingroup$ @megrinho: indeed, I am well aware of Pablo's work (and of several others in the area that blends convex algebraic geometry with optimization). $\endgroup$– SuvritCommented May 15, 2014 at 12:52
-
1$\begingroup$ 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? $\endgroup$ Commented May 15, 2014 at 16:53
$\begingroup$
$\endgroup$
Do you count problems from shape analysis to be a relevant optimisation problem? Here you try to find for example the distance between shapes (=unparametrised curves) in euclidean space to each other. This is implemented by looking at immersions modulo the orientation preserving diffeomorphisms (quotienting out all possible reparametrisations). A lot in this geometric theory depends on understanding the diffeomorphism groups or working with Riemannian metrics which are right invariant under the action of the diffeomorphisms. There is a lot of literature on this, but maybe the somewhat dated overview https://arxiv.org/pdf/1305.1150.pdf can get you started.
Also we recently wrote a nice little paper on deep neural networks on diffeomorphism groups for the reparametrisation task in shape analysis. There the algorithms exploit the Lie group structure of the diffeomorphisms and in particular there is a chapter deducing (rough) a priori estimates for Lipschitz constants on iterated compositions of diffeomorphism group elements. All of this yields a framework to find the optimal alignment of two curves (one of the basic shape analysis problems). The arXiv version of that paper can be found here: https://arxiv.org/pdf/2207.11141.pdf