State estimation is an important tool for continuously monitoring the power system and aims to recover the underlying system voltage phasors, given supervisory control and data acquisition (SCADA) measurements and a model that encompasses the system topology and specifications. To ensure an accurate state estimation, it is essential to have the capability of detecting bad data. Assuming that the network parameters are known and the measurement devices are correctly calibrated, the main source of bad data is topological errors in the model. In this dissertation, we propose a methodology for robust power system state estimation (PSSE) modeled by AC power flow equations when there exists a small number of topological errors. The developed technique utilizes the availability of a large number of SCADA measurements and minimizes the L-1 norm of nonconvex residuals augmented by a nonlinear, but convex, regularizer. Representing the power network by a graph, we first study the properties of the solution obtained from the proposed NLAV estimator and demonstrate that, under mild conditions, this solution identifies a small subgraph of the network that contains the topological errors in the model used for the state estimation problem. Then, we introduce a method that can efficiently detect the topological errors by searching over the identified subgraph. In addition, we develop a theoretical upper bound on the state estimation error to guarantee the accuracy of the proposed state estimation technique.

The power flow equations are nonlinear, and may admit multiple solutions. In the past, the conventional wisdom was to assume that the solution becomes unique by restricting it to "realistic'' or "physically realizable'' values. However, various examples in the literature show that multiple solutions may persist even after restricting either voltage magnitudes or phase angle differences to "physically realizable'' values. This dissertation establishes sufficient conditions for the uniqueness of AC power flow solutions via the monotonic relationship between real power flow and the phase angle difference. More specifically, we prove that the P-Theta power flow problem has at most one solution for any acyclic or GSP graph. In addition, for arbitrary cyclic power networks, we show that multiple distinct solutions cannot exist under the assumption that angle differences across the lines are bounded by some limit related to the maximal girth of the network. We also introduce a series-parallel operator and show that this operator obtains a reduced and easier-to-analyze model for the power system without changing the uniqueness of power flow solutions.

In the next part of this dissertation, the above work is extended and we establish general necessary and sufficient conditions for the uniqueness of P-Theta power flow solutions in an AC power system using properties of the monotone regime and the power network topology. We show that the necessary and sufficient conditions can lead to tighter sufficient conditions for the uniqueness in several special cases. Our results are based on the previously introduced notion of maximal girth and a new notion of maximal eye. Moreover, we develop a series-parallel reduction method and search-based algorithms for computing the maximal eye and maximal girth, which are necessary for the uniqueness analysis. Reduction to a single line using the proposed reduction method is guaranteed for 2-vertex-connected Series-Parallel graphs.

In the final part of this dissertation, we present a methodology based on homotopy to find the globally optimal solutions of nonconvex optimization problems. Optimal power flow (OPF) is a fundamental problem in power systems analysis for determining the steady-state operating point of a power network that minimizes the generation cost. In anticipation of component failures, such as transmission line or generator outages, it is also important to find optimal corrective actions for the power flow distribution over the network. The problem of finding these post-contingency solutions to the OPF problem is challenging due to the nonconvexity of the power flow equations and the large number of contingency cases in practice. In this paper, we introduce a homotopy method to solve for the post-contingency actions, which involves a series of intermediate optimization problems that gradually transform the original OPF problem into each contingency-OPF problem. We show that given a global solution to the original OPF problem, a global solution to the contingency problem can be obtained using this homotopy method, under some conditions. With simulations on Polish and other European networks, we demonstrate that the effectiveness of the proposed homotopy method is dependent on the choice of the homotopy path and that homotopy yields an improved solution in many cases.

Mathematical optimization is the cornerstone for the data-driven design and exploitation of various large-scale cyber-physical and information systems. The generic off-the-shelf tools for guaranteed global optimization used today often have a prohibitively high computational complexity on practical instances, preventing their convergence within a reasonable time. Instead, highly-scalable heuristics are utilized with no guarantee of global optimality of their result, which poses a problem in the analysis of complex safety-critical systems. Thus, specialized highly-scalable algorithms that come with a guarantee of their performance are required. These can be constructed by providing guarantees and limits of applicability for the well-performing heuristics. In this dissertation, we study how to leverage system-specific characteristics to analyze computational heuristics leading to guarantees of global optimality of their outputs. A prominent example of a large-scale safety-critical system that we consider throughout the first part of the dissertation is the sensor network within the measurement system of an electrical power grid. It is known that the associated generic problem of recovery of the state of a power system is computationally complex yet critical. The three main ways to reduce the complexity of computation associated with a sensor network are to increase the density of sensors, place them strategically, or enhance their security and accuracy to limit the set of possible errors and faults of measurement. All three of these paths are investigated within the first part of this dissertation. We provide numerical quantification to the computation complexity of inverse problems depending on the total number of measurements, the properties of the graph structure of the measurement network, and the signal-to-noise ratio measured as the ratio between the numbers of good and bad measurements. We address both the computational complexity and the matter of constructing a suitable, efficient algorithm in each of the three scenarios. Our results offer implications that should be considered at multiple stages throughout the life cycle of a system, starting from the design of the sensing mechanisms to ensure robustness and security of operation both in normal conditions and in situations of an emergency such as during a cyber-attack.

In the second part of this dissertation, we present a pioneering work considering an automatic approach toward selecting the most suitable efficient heuristic algorithm for an optimization problem at hand. We focus on a machine learning technique that can be adopted for heuristic selection and investigate its properties and the guarantees of its performance from the perspective of mathematical optimization. We conclude that adopting this machine learning technique in its original form would not result in guaranteed optimal heuristic selection even in a benign scenario, propose modifications and outline future work toward the automatic selection of heuristics.

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.

Decision-makers often face environments which vary over time and deal with uncertainty as a result. Problems with temporal variation differ based on how frequently they are solved and what information about the present or future is available to the decision-maker; each class of problem poses distinct challenges and requires tailored solutions. In this dissertation, we design and analyze methods to support decision-makers in these settings, with an emphasis on applications in electric power systems.

Online optimization, in which a player makes a sequence of decisions aimed at minimizing the damage inflicted by their adversary, is the first class of problems considered. Here, we shed light on online nonconvex optimization problems in which algorithms are evaluated against the optimal decision at each time using the notion of dynamic regret. The adversary's loss functions are arbitrarily nonconvex but have global solutions that are slowly time-varying. To address this problem we first analyze the region around the global solutions to define time-varying target sets. Then, we introduce two algorithms and prove that the dynamic regret for each algorithm is bounded by a function of the temporal variation in the optimal decision. The first algorithm assumes the decision-maker has some prior knowledge about the initial loss function. The second algorithm makes no assumption about prior knowledge, and instead it relies on random sampling and memory to find and then track the target sets over time. In this case, the landscape of the loss functions determines the likelihood that the dynamic regret will be small. Numerical experiments validate these theoretical results and highlight the impact of a single low-complexity problem early in the sequence.

Time-varying optimization, in which a series of linked problems are solved sequentially using information about past decisions, but not considering the future, is the second class of problems considered. Specifically, we analyze the optimality behavior of solution trajectories for optimal power flow (OPF) with time-varying load. Despite its nonlinearity, time-varying OPF is commonly solved every 5-15 minutes using local-search algorithms. Failing to obtain the globally optimal solution of power optimization problems jeopardizes the grid’s reliability and causes poor financial and environmental outcomes. An empirical study on California data shows that, with enough variation in the data, local search methods can solve OPF to global optimality, even if the problem has many local minima. To explain this phenomenon, we introduce a backward mapping that relates the time-varying OPF’s global solution at a given time to a set of desirable initial points. We show that this mapping could act as a stochastic gradient ascent algorithm on an implicitly convexified formulation of OPF, justifying the escape of poor solutions over time. This work is the first to mathematically explain how temporal data variation affects the complexity of solving power operational problems.

Multi-period optimization under uncertainty, in which decisions for the entire time horizon are made at once, is the third and final class of problems considered. Within this class, we focus on the decision-making problem facing hybrid power plant operators when participating in wholesale electricity markets with the goal of enabling researchers to accurately incorporate these resources into simulations of future electricity systems. To this end, a stochastic optimization model is developed to maximize the revenue of the plant, which consists of a renewable generator and an energy storage resource that appear as a single, combined unit to the market, while limiting risk due to uncertainty in market prices and generation levels, through price-quantity bid curves. The uncertainty is represented by scenarios, and a detailed methodology is provided for creating scenarios which both reflect the type of information a hybrid operator would have and only require the limited data which is available in simulation settings. This work advances existing models by allowing greater cooperation between the generator and storage components while also enforcing market limits on bid curves' complexity. Further, the approach ensures economically-sound behavior even when faced with unforeseen events.

Despite several progresses of control-theoretic techniques in the past decade, these methods still struggle to bridge the widening gap between theory and reality, which is exacerbated by the increasing complexity, uncertainty, and safety requirements. Consequently, the creation of online control algorithms for safety-critical applications in non-stationary environments could pave the way for a new chapter in modern control theory, substantially enhancing the reliability of intelligent systems as they function in dynamic, uncertain, and potentially hostile conditions subject to physical and computational limitations. Safe non-stationary decision-making not only encompasses the core challenges of traditional decision-making but also presents new hurdles, such as (i) fast adaptation under the non-stationary environments, (ii) global optimality convergence of the non-convex optimization, (iii) continual balancing of objective and constraints. The above challenges go beyond current capabilities in computation and theory and manifest in various aspects of practical and theoretical interests, from sample complexity and non-convergence issues to computational tractability and enforcement of safety constraints for real-time control. This thesis aims to pioneer system operation at the nexus of reinforcement learning, online learning, statistical learning, and nonlinear optimization. The design of provably efficient and safe online decision-making algorithms that exploit prediction and prior knowledge while grappling with the effects of dynamic feedback and non-stationary environment will push the frontiers of computational verification and synthesis of control policies for safety-critical systems.

To overcome these challenges and realize the full potential of online decision-making approaches for adaptability and performance gains, this thesis aims to extend the foundational knowledge in systems and control and broaden our understanding of performance limits and engineering trade-offs when the system must operate outside of the assumptions of known models and needs to adapt to its environment in real-time. In particular, we develop a new mathematical foundation and a set of computational tools for the design of safe online decision-making algorithms that can be deployed in environments that undergo changes. Along this line, we will address the following objectives: (i) escaping spurious local minimum trajectories in online time-varying non-convex optimization, (ii) provably efficient primal-dual reinforcement learning for CMDPs with non-stationary objectives and constraints, (iii) non-stationary risk-sensitive reinforcement learning with near-optimal dynamic regret, adaptive detection, and separation design.

Within the realm of computational methods, there has been a long-standing trade-off between the scalability of different techniques and their optimality guarantees. However, most of today’s systems—such as transportation, power, and brain networks—are large-scale and safety-critical, thereby requiring both scalability and optimality guarantees. To address these challenges, in this dissertation we develop structure-aware, scalable, and guaranteed computational methods for the learning, optimization, and control of safety-critical systems.

In the first part of the dissertation, we consider two classes of machine learning problems, namely graphical model inference and robust matrix recovery. First, we provide a massively-scalable algorithm for the graphical model inference, where the goal is to reveal hidden correlation structures of high-dimensional datasets. We introduce a graph-based method that is capable of solving instances with billions of variables in less than an hour, significantly outperforming other state-of-the-art methods. Next, we consider a class of nonconvex and nonsmooth optimization problems in safe machine learning. We show that, despite their nonconvexity, a large class of problems in robust matrix recovery is devoid of spurious and sub-optimal solutions, thereby leading to the guaranteed success of fast local-search algorithms.

The second part of the dissertation is devoted to different classes of network optimization problems. In particular, we consider a class of generalized network flow problems that are at the backbone of many modern interconnected systems, such as power, water, and gas networks. Unlike many of its classical counterparts, the generalized network flow problem is highly nonconvex due to the incorporation of nonlinear losses in its formulation. To address this issue, we propose an efficient convex relaxation of the problem, and provide conditions under which the proposed relaxation is exact. Next, we focus on a specialized network optimization problem in power systems, namely optimal transmission switching, where the goal is to find the optimal topology of a power grid to minimize its cost of operation, while satisfying operational and security constraints in the network. The optimal transmission switching is a NP-hard optimization problem with mixed-integer variables. However, by exploiting the tree-like structure of realistic power grids, we introduce an strengthened formulation of the problem that can be solved efficiently in practice.

The third part of the dissertation is concerned with the design of robust and distributed control policies for dynamical systems with uncertain models. To this end, first we propose a sparsity-exploiting technique for the efficient learning of a structured dynamical system, based on a limited number of collected input-output sample trajectories from the system. In particular, we quantify the sample complexity of the sparse system identification problem in a high-dimensional setting, where the dimension of the system is significantly greater than the number of available data samples. Given the estimated dynamics, our next goal is to design a robust and distributed control policy for the system by taking into account the uncertainty of its estimated model. We show that near-optimal distributed controllers can be learned with logarithmic sample complexity and computed with near-linear time complexity.