UC San Diego

Recent work has shown that by considering an optimization perspective of the eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, we present efficient methods for solving general quadratic programs with nonconvex constraints in the context of very-large-scale integration (VLSI) computer-aided design (CAD) and graph-based semi-supervised learning problems.

We propose a general framework for matrix quadratic programming with nonconvex constraints, which is motivated by classic algorithms for solving trust-region subproblems. We introduce approximate and iterative methods with derived convergence guarantees.

We demonstrate the effectiveness of our framework on large-scale numerical test cases, specifically real-world benchmarks. By leveraging analytical VLSI and PCB layout engines, we show that effective initialization using our method consistently improves a variety of pre- and post-detailed placement metrics. Additionally, we introduce a graph semi-supervised learning algorithm based on this framework, which yields strong results across a wide spectrum of label rates.