UC Berkeley

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.