The Role of Structure in Optimization and Control: How to Detect It, and How to Exploit It

Abstract

In many application domains, including systems and control theory, the optimization problems that appear are seldom "generic" but instead they often have well-defined structural features. Depending on the situation, such structure may be described algebraically (e.g., by transformations under which the problem is invariant, like linearity or time-invariance), geometrically (by restricting the feasible set to a given manifold/variety), or graphically (e.g., by a graph summarizing the interactions among decision variables). Exploiting this structure is crucial for practical efficiency. In this talk we will provide a gentle introduction to these ideas, surveying the basic notions as well as describing algorithmic techniques to detect and exploit these properties. In particular, we will discuss some recent developments, including dimension/symmetry reduction techniques for SDPs, and chordal networks. As we will illustrate through applications, algorithms that automatically exploit structure can significantly outperform existing techniques.