·¬ÇÑÉçÇø

Topic

Invariant conic optimization with basis-dependent cones: scaled diagonally dominant matrices and real *-algebra decomposition

Department of Mathematics and Statistics

Date & location

• Wednesday, July 17, 2024

• 9:00 A.M.

• Engineering & Computer Science Building

• Room 130

Reviewers

Supervisory Committee

• Dr. David Goluskin, Department of Mathematics and Statistics, ·¬ÇÑÉçÇø (Supervisor)

• Dr. Heath Emerson, Department of Mathematics and Statistics, UVic (Member) 

External Examiner

• Dr. Cordian Riener, Department of Mathematics and Statistics, University of Tromsø 

Chair of Oral Examination

• Dr. Violeta Iosub, Department of Chemistry, UVic

   

Abstract

Symmetry reduction for a semidefinite program (SDP) with symmetries makes computational solution of the SDP easier by decomposing the semidefiniteness constraint into multiple smaller semidefineness constraints. This decomposition requires changing to a symmetry-adapted basis that block diagonalizes the matrix variable, but this does not change the optimum value of the SDP because the semidefinite cone is basis-independent. For other cones that are basis-dependent, if optimization problems over those cones have symmetries one can still change to a symmetry-adapted basis that block diagonalizes the matrix. However, this change of basis generally changes the constraint cone and can change the optimum. In this thesis we develop a framework for determining when symmetry reduction for basis-dependent conic optimization makes the optimum increase, decrease, or stay the same. The aim is to determine this using general features such as the symmetry group of the optimization problem, without having to solve the problem computationally. We then use our framework to prove various results of this type for scaled diagonally dominant programs (SDDPs), which are convex optimization problems over the cone of scaled diagonally dominant matrices. These results depend on the orbital structure of the underlying representation of invariant SDDPs. Using the regular representation, we demonstrate that analysis of SDDPs of any size can be confined to a smaller SDDP that is invariant under a particular representation. Our approach uses real *-algebra decomposition of equivariant maps, which is not needed for existing symmetry reduction of SDPs. Because polynomial optimization problems with sum-of-squares and sum-of-binomial-squares can be represented as SDPs and SDDPs, respectively, our results on SDDPs have implications for polynomial optimization. Using several polynomial optimization problems as examples, we give computational results that illustrate our theorems. For polynomial optimization subject to sum-of-binomial-squares, our examples included cases in which symmetry reduction causes the optimum to increase, decrease, or stay the same.