Coordinate shadows of semi-definite and Euclidean distance matrices

Autor:	Drusvyatskiy, D., Pataki, G., Wolkowicz, H.
Rok vydání:	2014
Předmět:	Mathematics - Optimization and Control 90C22 90C46 52A99
Druh dokumentu:	Working Paper
Popis:	We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We classify when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. In particular, we show that under a chordality assumption, the "minimal cones" of these problems admit combinatorial characterizations. As a byproduct, we record a striking relationship between the complexity of the general facial reduction algorithm (singularity degree) and facial exposedness of conic images under a linear mapping. Comment: 21 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1405.2037 Zobrazit plný text záznamu View this record from Arxiv