比利时vs摩洛哥足彩
,
university of california san diego
****************************
math and mae colloquium
pablo a. parrilo
eth zurich
symmetry groups, semidefinite programs, and sums of squares
abstract:
we explore the geometric, algebraic, and computational implications of thepresence of continuous and discrete symmetries in semidefinite programs(sdps). it is shown that symmetry exploitation allows a significantreduction in both matrix size and number of decision variables. to this end,we define a class of sdps, that are invariant under the action of a finiteor continuous symmetry group. using group averaging and linearrepresentation theory, it is shown that the feasible set can be restrictedto a specific invariant subspace, thus reducing the problem to a collectionof coupled semidefinite programs of smaller dimensions.we focus particularly on sdps arising in the sum ofsquares/positivstellensatz framework, where the group representation isinduced by an action on the space of monomials. it is shown that thecomplexity is significantly reduced, and the techniques are illustrated withnumerous examples. the results, reinterpreted from an invariant-theoreticviewpoint, provide a novel representation of nonnegative symmetricpolynomials. this alternative approach has as attractive features itscomputational efficiency and the natural connections with therepresentation-based approach developed earlier.finally, the computational savings of the techniques are demonstrated insome large-scale problems. it is shown how the symmetry reduction techniquesenable the numerical solution of complicated instances, otherwisecomputationally infeasible to solve.the material in the talk is based on joint work with karin gatermann (zibberlin).
host: bill helton
december 6, 2002
2:00 pm
ap&m 6438
****************************