UC Berkeley

This dissertation focuses on devising innovative approaches to understanding and computing the optimal decision within complex large-scale operational frameworks, such as service networks and power systems. These approaches aim to facilitate interpretable, scalable, and robust decision-making under uncertainty. However, achieving this objective is hindered by the computational hurdle presented by the fact that most practical problems are known to be NP-hard in the worst case. Nevertheless, this dissertation has been primarily inspired by the observation that real-world problem instances often exhibit benign geometric properties, which can be exploited to reduce the computational complexity. By leveraging methodologies from mathematics, statistics, operations research, and machine learning, our goal is to identify and harness these underlying geometric properties to devise algorithms that are demonstrably efficient and resilient, thereby supporting decision-making in large-scale systems.

In the first part of the dissertation, we focus on the low-rank matrix optimization problem, which targets at recovering the underlying low-rank ground truth matrix from a small number of measurements. Various important applications in the fields of machine learning, signal processing, and power systems can be formulated as a low-rank matrix optimization problem. By utilizing the benign optimization landscape around the manifold of low-rank matrices, we establish state-of-the-art theoretical guarantees to the highly efficient non-convex formulation based on the Burer-Monteiro factorization. First, we significantly improve existing sufficient conditions in terms of the Restricted Isometry Property constant, leading to the guaranteed success of local search algorithms for more problem instances. Next, we propose a new complexity metric for the rank-1 generalized matrix completion problem. The new metric has the potential of unifying several existing metrics and provides both sufficient conditions and necessary conditions to the success of local search algorithms. This part serves as a crucial step towards closing the gap between the empirical success and the theoretical understanding of the Burer-Monteiro factorization approach.

The second part of the dissertation is concerned with the discrete optimization via simulation problem. The design of scalable and robust simulation-optimization algorithms plays a vital role in the timely decision-making in large-scale systems with uncertainty, such as the bike-sharing system. Inspired by the marginal decreasing property, we utilize a special structure, named the L-convexity, to develop algorithms with scalability and optimality guarantees. More specifically, we first construct a subgradient estimator based on the Lovasz extension and develop stochastic search algorithms using the subgradient information. We theoretically and empirically illustrate that the proposed algorithms are highly efficient for high-dimensional discrete optimization via simulation problems. Next, by combining the subgradient information with the discrete nature of the problem, we propose the stochastic localization algorithms, which exhibit an improved efficiency on large-scale applications.

In the third part of the dissertation, we focus on the AC power flow problem in power systems. The efficient and reliable control of large-scale power systems, e.g., the dispatch of electricity under safety-critical constraints, is contingent upon developments of advanced computational and analytical tools. In the first chapter, we consider the uniqueness of solutions to the power flow problem. Utilizing properties of the monotone regime and the network topology, stronger necessary conditions and sufficient conditions, based on the maximal girth and the maximal eye, are proposed to guarantee the uniqueness of solutions. We also provide the corresponding reduction algorithms to efficiently estimate these two network parameters. Given the ongoing emergence of intermittent renewable generation, the second chapter is devoted to the design of optimal power flow algorithms that are robust to large generation forecast errors, which plays an essential role in incorporating renewable energy generators into electrical networks. More concretely, we propose a novel distributionally robust optimization formulation for the chance-constrained optimal power flow problem and provide corresponding algorithms to effectively find the robust solution with the minimum generation cost.