# Inference and Optimization for Engineering and Physical Systems

arXiv: https://arxiv.org/abs/2208.13880 · HTML: https://mlsanity.com/paper/2208.13880/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 113 references that are in the map.
- First posted on arXiv 29 Aug 2022.

## Builds on (most cited first, 26 of 26)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Self-Training: A Survey](https://mlsanity.com/paper/2202.12040/) (2022)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications](https://mlsanity.com/paper/1810.05186/) (2018)
- [Rademacher Complexity Bounds for a Penalized Multiclass Semi-Supervised Algorithm](https://mlsanity.com/paper/1607.00567/) (2016)
- [Representation Learning and Pairwise Ranking for Implicit Feedback in Recommendation Systems](https://mlsanity.com/paper/1705.00105/) (2017)
- [Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality](https://mlsanity.com/paper/1703.08729/) (2017)
- [A Time-dependent SIR model for COVID-19 with Undetectable Infected Persons](https://mlsanity.com/paper/2003.00122/) (2020)
- [Semidefinite approximations of the matrix logarithm](https://mlsanity.com/paper/1705.00812/) (2017)
- [Convergence Rate of Block-Coordinate Maximization Burer-Monteiro Method for Solving Large SDPs](https://mlsanity.com/paper/1807.04428/) (2018)
- [Large-scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications](https://mlsanity.com/paper/1411.7564/) (2014)
- [Importance sampling approach to chance-constrained DC optimal power flow](https://mlsanity.com/paper/2111.11729/) (2021)
- [Power Grid Reliability Estimation via Adaptive Importance Sampling](https://mlsanity.com/paper/2105.08753/) (2021)
- [Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank](https://mlsanity.com/paper/1508.07607/) (2015)
- [Inference in Graphical Models via Semidefinite Programming Hierarchies](https://mlsanity.com/paper/1709.06525/) (2017)
- [Entropy Penalized Semidefinite Programming](https://mlsanity.com/paper/1802.04332/) (2018)
- [Gauges, Loops, and Polynomials for Partition Functions of Graphical Models](https://mlsanity.com/paper/1811.04713/) (2018)
- [Learning a Generator Model from Terminal Bus Data](https://mlsanity.com/paper/1901.00781/) (2019)
- [Optimal Power Flow as a Polynomial Optimization Problem](https://mlsanity.com/paper/1404.3626/) (2014)
- [A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow](https://mlsanity.com/paper/1506.08568/) (2015)
- [Inference and Sampling of K33-free Ising Models](https://mlsanity.com/paper/1812.09587/) (2018)
- [A Bayesian Framework for Power System Components Identification](https://mlsanity.com/paper/2001.06704/) (2020)
- [Prediction and Prevention of Pandemics via Graphical Model Inference and Convex Programming](https://mlsanity.com/paper/2109.04517/) (2021)
- [Efficient Rank Minimization to Tighten Semidefinite Programming for Unconstrained Binary Quadratic Optimization](https://mlsanity.com/paper/1708.01690/) (2017)
- [A New Family of Tractable Ising Models](https://mlsanity.com/paper/1906.06431/) (2019)
- [Tractable Minor-free Generalization of Planar Zero-field Ising Models](https://mlsanity.com/paper/1910.11142/) (2019)

## Abstract (arXiv)

The central object of this PhD thesis is known under different names in the fields of computer science and statistical mechanics. In computer science, it is called the Maximum Cut problem, one of the famous twenty-one Karp's original NP-hard problems, while the same object from Physics is called the Ising Spin Glass model. This model of a rich structure often appears as a reduction or reformulation of real-world problems from computer science, physics and engineering. However, solving this model exactly (finding the maximal cut or the ground state) is likely to stay an intractable problem (unless textitP = textitNP) and requires the development of ad-hoc heuristics for every particular family of instances. One of the bright and beautiful connections between discrete and continuous optimization is a Semidefinite Programming-based rounding scheme for Maximum Cut. This procedure allows us to find a provably near-optimal solution; moreover, this method is conjectured to be the best possible in polynomial time. In the first two chapters of this thesis, we investigate local non-convex heuristics intended to improve the rounding scheme. In the last chapter of this thesis, we make one step further and aim to control the solution of the problem we wanted to solve in previous chapters. We formulate a bi-level optimization problem over the Ising model where we want to tweak the interactions as little as possible so that the ground state of the resulting Ising model satisfies the desired criteria. This kind of problem arises in pandemic modeling. We show that when the interactions are non-negative, our bi-level optimization is solvable in polynomial time using convex programming.