VERTICES OF SPECTRAHEDRA ARISING FROM THE ELLIPTOPE, THE THETA BODY, AND THEIR RELATIVES

Autor(es)

de Carli Silva, Marcel K. ^[1] ; Tuncel, Levent ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Comp Sci, Inst Math & Stat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Waterloo, Fac Math, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1 - Canada

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON OPTIMIZATION; v. 25, n. 1, p. 295-316, 2015.
• Citações Web of Science: 2

Resumo

Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from the Lovasz theta body, generalizations of the elliptope, and related convex sets. Our results generalize vertex characterizations due to Laurent and Poljak in the 1990s. Our approach, focused on the dimension of the normal cone, also leads us to nice characterizations of strict complementarity and to connections with some of the related literature. (AU)

• Processo FAPESP: 13/20740-9 - Aplicações de Programação Semidefinida em Otimização Combinatória
• Beneficiário: Marcel Kenji de Carli Silva
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado