Non-Submodular Combinatorial Optimization in Control Systems: Efficient Algorithms with Provable Bounds

Hou, Qiqiang

Etd

Non-Submodular Combinatorial Optimization in Control Systems: Efficient Algorithms with Provable Bounds

Public

A variety of control-theoretic problems are equivalent to selecting a subset of discrete elements to maximize a performance metric, making them inherently combinatorial in nature. Such problems are computationally intractable in the worst case because the number of possible sets is exponential in the number of elements. An alternative approach is to choose a suboptimal set using an efficient heuristic algorithm. Of particular interest are problem structures that lead to provable optimality bounds for such heuristics. One such problem structure with numerous applications in dynamics and control is submodularity, which is a diminishing returns property of discrete functions. However, not all combinatorial problems are submodular. For example, the convergence rate of leader-follower systems is known to be determined by the smallest eigenvalue of the graph Laplacian, which is known to be not submodular as a function of the leader set. In systems with parameter uncertainty, it may be desirable to maximize the worst-case performance over a set of parameter values. However, even if the objective function is submodular for a given parameter value, the minimum of a set of submodular functions is generally not submodular. Problems such as sensor placement over infinite-dimensional systems described by partial differential equations (PDEs) require selecting a finite subset of elements from an infinite set, and thus cannot be solved by submodular optimization algorithms that implicitly assume a finite ground set. In this thesis, we solve these three combinatorial problems by developing new analytical approaches. We first consider the problem of selecting a largest principal submatrix from a graph Laplacian such that the smallest eigenvalue of the selected submatrix is positive. We prove that the positivity of the eigenvalues of a submatrix can be characterized using the probability distribution of the quadratic form induced by the submatrix. By exploiting this connection, we show that positive-definiteness of a submatrix can be expressed as a constraint on a submodular function. We then exploit the Greedy algorithm to maximize the submodular function by removing rows and columns from the graph Laplacian until the smallest eigenvalue of the remaining matrix is positive. We prove that our approach is with polynomial-time complexity and the size of the remaining submatrix is lower bounded. We also generalize our approach to conditions where the original matrix is non-symmetric and determinant respectively. Our theoretical result is applicable to stabilize the networked system containing negative interactions by selecting a minimum number of nodes to exert external actuation. We investigate the linear quadratic control problem over infinite time interval in systems described by partial differential equations (PDEs). It has been proved that the optimal control strategy is achieved by a linear full state feedback operator. As it is impossible to obtain the full state, we intend to place a finite number of sensors in the PDE system to minimize the deviation between our finite state feedback controller and the desired infinite-dimensional feedback controller. In this thesis, we propose a greedy algorithm as well as its simplified version for sensor placement. We analyze the performance of our approaches under two scenarios. In the case where the sensor placements are constrained such that the detection radii of each pair of sensors do not overlap, we show that the two algorithms are equivalent and achieve a 1/2 ratio with respect to the performance metric of optimal sensor position set. When overlaps exist between sensor detection areas, we derive a optimality bound for the simplified algorithm. The value of the optimality bound is determined by the sensor model, cardinality of sensor set and the allowed minimum sensor distance. In the third problem solved in this thesis, we look into maximizing the minimum of a set of submodular functions. We consider scenarios where the set of objective functions are correlated. These correlations may arise from the problem structure. For example, when the submodular functions are formulated based on the same graph with varying edge weights or a small set of edge deletions, each function corresponds to one possible graph, the operation of assigning leader nodes to maximize one function will also influence the value of other functions. We propose two algorithms to select elements under cardinality and matroid constraints respectively. The optimality bounds of our algorithms are derived with our defined correlation ratio. As a case study, we consider the problem of minimizing the largest effective resistance of multiple leader-follower systems by assigning common leader nodes. The lower bound of the correlation ratio is computed using the graphs' spectrum.

Creator