## Research## Robust Low-Rank Optimization
In [1], we considered an important class of such problems, namely
1- S. Fattahi and S. Sojoudi, Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysis, Journal of Machine Learning Research, 2020. ## Graphical Model Inference
In a series of papers [1-4], we provided an affirmative answer to this question. In particular, we showed that, under mild assumptions, a simple thresholding operation on the sample covariance matrix reveals the sparsity pattern of the inverse covariance matrix. By building upon this result, we proved that sparse inverse covariance estimation can be solved to near-optimality in O(n^2).
Furthermore, we showed the graceful scalability of the proposed method on massive-scale datasets, including real-life functional MRI data and traffic flows for transportation networks.
In practice, our proposed method obtained accurate estimates of inverse covariance matrix for instances with more than 3.2 billion variables in less than 30 minutes on a normal laptop computer, while other methods did not converge within 4 hours on a server with 32 CPU cores.
1- S. Fattahi and S. Sojoudi, Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions, Journal of Machine Learning Research (JMLR), 2019 - 2- R. Y. Zhang, S. Fattahi, and S. Sojoudi, Large-Scale Sparse Inverse Covariance Estimation via Thresholding and Max-Det Matrix Completion, International Conference on Machine Learning (ICML), 2018 3- S. Fattahi, R. Y. Zhang and S. Sojoudi, Sparse Inverse Covariance Estimation for Chordal Structures, European Control Conference (ECC), 2018 4- S. Fattahi and S. Sojoudi, Graphical Lasso: Sparsity Path and Closed-Form Solution, American Control Conference (ACC), 2018 - ## Nonconvex Online Optimization
To answer this question, we considered the OPF problem with the California load profile in [1] and empirically showed that, despite having multiple local solutions at every time step, simple ‘‘short-sighted’’ algorithms can avoid them. Inspired by this observation, we introduced the notion of
1- S. Fattahi, C. Josz, R. Mohammadi, J. Lavaei, and S. Sojoudi, Absence of Spurious Local Trajectories in Time-varying Optimization, submitted for journal publication, 2019 ## Learning-Based System Identification and Distributed Control
1- S. Fattahi and S. Sojoudi, Data-Driven Sparse System Identification, Annual Allerton Conference on Communication, Control, and Computing, 2018 2- Salar Fattahi and Somayeh Sojoudi, Sample Complexity of Sparse System Identification Problem, submitted to IEEE Transactions on Automatic Control, 2019 3- S. Fattahi, N. Matni, and S. Sojoudi, Learning Sparse Dynamical Systems from a Single Sample Trajectory, to appear in IEEE Conference on Decision and Control (CDC), 2019 4- S. Fattahi, N. Matni, and S. Sojoudi, Efficient Learning of Distributed Linear-Quadratic Controllers, submitted to SIAM Journal on Optimization and Control, 2019 ## Nonlinear Network Optimization
In particular, we proved that, under practical conditions, the globally optimal cost and nodal injections can be efficiently obtained by simply relaxing the nonconvex equality constraints to convex inequalities. Unlike the computationally-expensive convexification techniques — such as sum-of-squares (SOS) — that are based on lifting the problem to a higher dimension, our proposed convex relaxation is defined over the original space of variables, making it suitable for the real-time operation of lossy networks in realistic scales.
1- S. Sojoudi, S. Fattahi and J. Lavaei, Convexification of Generalized Network Flow Problem, Mathematical Programming, 2019 2- S. Fattahi and J. Lavaei, Convex Analysis of Generalized Flow Networks, IEEE Conference on Decision and Control (CDC), 2015 ## Real-Time scheduling of Power Systems
Next, we studied the optimal transmission switching (OTS) problem for power systems, where certain lines are fixed (uncontrollable) and the remaining ones are controllable via flexible switches. The goal was to identify a topology of the power grid that minimizes the cost of the system operation while satisfying the physical and operational constraints. Most of the existing methods for the problem are based on first converting the OTS into a mixed-integer linear program (MILP) or mixed-integer quadratic program (MIQP), and then iteratively solving a series of convex relaxations. The performance of these methods depends heavily on the strength of the MILP or MIQP formulations. Here, we showed that finding MILP or MIQP formulation of the OTS is NP-hard. Furthermore, we proved that there is no constant-factor approximation algorithm for constructing these variable bounds. Despite the inherent difficulty of obtaining the strongest bounds in general, we presented a simple bound strengthening method to strengthen the convex relaxation of the problem. The proposed method can be treated as a preprocessing step and can be carried out offline before initiating any off-the-shelf solver. A remarkable speedup in the runtime of the mixed-integer solvers is obtained using the proposed bound strengthening method for medium- and large-scale real world systems [2,3].
1- S. Fattahi, M. Ashraphijou, J. Lavaei and A. Atamturk, Conic Relaxation of the Unit Commitment Problem, Energy, 2017 2- S. Fattahi, J. Lavaei and A. Atamturk, A Bound Strengthening Method for Optimal Transmission Switching in Power Systems, IEEE Transactions on Power Systems, 2018. 3- S. Fattahi, J. Lavaei and A. Atamturk, Promises of Conic Relaxations in Optimal Transmission Switching of Power Systems, IEEE Conference on Decision and Control (CDC), 2017 4- M. Ashraphijou, S. Fattahi, J. Lavaei and A. Atamturk, A Strong Semidefinite Programming Relaxation of the Unit Commitment Problem, IEEE Conference on Decision and Control (CDC), 2016 ## Distributed Control Policies in Large-Scale Dynamical Systems
In [4], we targeted the theoretical complexity of solving stochastic optimal distributed control problem. We showed that if either the measurement noise covariance or the input weighting matrix is not too small, the problem is locally convex. Under such circumstances, the design of a decentralized controller with a bounded norm subject to an arbitrary sparsity pattern is naturally a convex problem.
1- S. Fattahi, G. Fazelnia and J. Lavaei, Transformation of Optimal Centralized Controllers Into Near-Global Static Distributed Controllers, IEEE Transactions on Automatic Control, 2018 2- G. Darivianakis, S. Fattahi, J. Lygeros and J. Lavaei, High-Performance Cooperative Distributed Model Predictive Control for Linear Systems, American Control Conference (ACC), 2018 3- S. Fattahi, J. Lavaei and M. Arcak, A Scalable Method for Designing Distributed Controllers for Systems with Unknown Initial States, IEEE Conference on Decision and Control (CDC), 2017 4- S. Fattahi and J. Lavaei, On the Convexity of Optimal Decentralized Control Problem and Sparsity Path, American Control Conference (ACC), pp. 3359-3366, 2017 5- S. Fattahi, J. Lavaei, Theoretical Guarantees for the Design of Near Globally Optimal Static, 54th Annual Allerton Conference on Communication, Control, and Computing, 2016 6- S. Fattahi, G. Fazelnia and J. Lavaei, Transformation of Optimal Centralized Controllers Into Near-Global Static Distributed Controllers, IEEE Conference on Decision and Control (CDC), 2015 |