printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 278c - optimization and data science

yang zheng

ucsd

chordal graphs, semidefinite optimization, and sum-of-squares matrices

abstract:

semidefinite optimization is a type of convex optimization problems over the cone of positive semidefinite (psd) matrices, and sum-of-squares (sos) optimization is another type of convex optimization problems concerned with the cone of sos polynomials. both semidefinite and sos optimization have found a wide range of applications, including control theory, fluid dynamics, machine learning, and power systems. in theory, they can be solved in polynomial time using interior-point methods, but these methods are only practical for small- to medium-sized problem instances. in this talk, i will introduce decomposition methods for semidefinite optimization and sos optimization with chordal sparsity, which scale more favorably to large-scale problem instances. it is known that chordal decomposition allows one to equivalently decompose a psd cone into a set of smaller and coupled cones. in the first part, i will apply this fact to reformulate a sparse semidefinite program (sdp) into an equivalent sdp with smaller psd constraints that is suitable for the application of first-order operator-splitting methods. the resulting algorithms have been implemented in the open-source solver cdcs. in the second part, i will extend the classical chordal decomposition to the case of sparse polynomial matrices that are positive (semi)definite globally or locally on a semi-algebraic set. the extended decomposition results can be viewed as sparsity-exploiting versions of the hilbert-artin, reznick, putinar, and putinar-vasilescu positivstellensätze. this talk is based on our work: https://arxiv.org/abs/1707.05058 and https://arxiv.org/abs/2007.11410

host: jiawang nie

october 27, 2021

3:00 pm

zoom meeting id: 991 9807 8858 password: 278cfa21

****************************