PhD Thesis Defense

This thesis is concerned with presenting convex optimization based tractable solutions for three fundamental problems:

These combinatorial/algebraic problems frequently arise in various application domains such as social networks, computational biology, chemoinformatics and control theory. Nevertheless, exactly solving them in practice is only possible for very small instances due to their notorious difficulty. For each of these problems, we introduce convex relaxations which succeed in providing exact or approximate solutions in a computationally tractable manner. Our relaxations for the two graph problems are based on convex outer-approximations of the set of adjacency matrices representing the underlying graphs. In particular, we investigate a convex outer-approximation that exclusively depends on the graph spectrum for the planted subgraph problem, whereas we additionally consider outer-approximations based on the stability number and the maximum-cut value for the graph edit distance problem. For both of these problems, we identify conditions under which our graph spectrum based relaxations exactly solve the corresponding problem with overwhelming probability. Specifically, we demonstrate that the graph spectrum based relaxations turn out to be particularly effective when the underlying graph has a spectrum comprised of few distinct eigenvalues with high multiplicities. On the other hand, for the inverse eigenvalue problem, we investigate two relaxations arising from a sum of squares hierarchy. These relaxations have different approximation qualities, and accordingly induce different computational costs. We utilize our framework to generate solutions for, or certify unsolvability of the underlying inverse eigenvalue problem.

We particularly emphasize the computational aspect of our relaxations throughout this thesis. We corroborate the utility of our methods with various numerical experiments.