Combinatorial conditions for low rank solutions in semidefinite programming

A. Varvitsiotis

Research output: ThesisDoctoral Thesis

638 Downloads (Pure)

Abstract

In this thesis we investigate combinatorial conditions that guarantee the existence of low-rank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the low-rank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a well-known spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closed-form formula for the Grothendieck constant of graphs with noK_5-minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of low-rank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rank-constrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidth-like parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • Laurent, Monique, Promotor
Award date25 Nov 2013
Place of PublicationTilburg
Publisher
Print ISBNs9789056683719
Publication statusPublished - 2013

Fingerprint

Semidefinite Programming
Graph in graph theory
Semidefinite Program
Extremes
Forbidden Minor
Minor
Positive Semidefinite Matrix
Optimal Solution
Monotone
Matrix Completion Problem
Partial Matrix
Semidefinite Relaxation
Geometric Representation
Treewidth
Positive semidefinite
Diagonal matrix
Sparsity
Graph theory
Polyhedron
Completion

Cite this

Varvitsiotis, A. (2013). Combinatorial conditions for low rank solutions in semidefinite programming. Tilburg: CentER, Center for Economic Research.
Varvitsiotis, A.. / Combinatorial conditions for low rank solutions in semidefinite programming. Tilburg : CentER, Center for Economic Research, 2013. 168 p.
@phdthesis{d0fcc572daaf4bd995db1365ade9fc53,
title = "Combinatorial conditions for low rank solutions in semidefinite programming",
abstract = "In this thesis we investigate combinatorial conditions that guarantee the existence of low-rank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the low-rank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a well-known spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closed-form formula for the Grothendieck constant of graphs with noK_5-minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of low-rank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rank-constrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidth-like parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.",
author = "A. Varvitsiotis",
year = "2013",
language = "English",
isbn = "9789056683719",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

Varvitsiotis, A 2013, 'Combinatorial conditions for low rank solutions in semidefinite programming', Doctor of Philosophy, Tilburg University, Tilburg.

Combinatorial conditions for low rank solutions in semidefinite programming. / Varvitsiotis, A.

Tilburg : CentER, Center for Economic Research, 2013. 168 p.

Research output: ThesisDoctoral Thesis

TY - THES

T1 - Combinatorial conditions for low rank solutions in semidefinite programming

AU - Varvitsiotis, A.

PY - 2013

Y1 - 2013

N2 - In this thesis we investigate combinatorial conditions that guarantee the existence of low-rank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the low-rank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a well-known spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closed-form formula for the Grothendieck constant of graphs with noK_5-minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of low-rank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rank-constrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidth-like parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.

AB - In this thesis we investigate combinatorial conditions that guarantee the existence of low-rank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the low-rank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a well-known spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closed-form formula for the Grothendieck constant of graphs with noK_5-minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of low-rank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rank-constrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidth-like parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.

M3 - Doctoral Thesis

SN - 9789056683719

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

Varvitsiotis A. Combinatorial conditions for low rank solutions in semidefinite programming. Tilburg: CentER, Center for Economic Research, 2013. 168 p. (CentER Dissertation Series).