Exploiting Structure and Hidden Convexity in Hard, Large Scale Numerical Optimization

点击翻译按钮获取中文摘要

My research aims to apply continuous optimization relaxations and to exploit structure in order to derive practical algorithms that efficiently and accurately solve large scale hard numerical problems. These problems arise in data science and are generally non-convex and intractable. One well known application is the low-rank matrix completion (LRMC) problem, such as the netflix movie ratings problem, i.e., one can fill missing entries in order to make good recommendations to customers. Other applications include: hard discrete optimization problems that model scheduling and location problems such as the quadratic assignment problem; robust principal component analysis that includes recovery of measurements from highly corrupted surveillance data; molecular conformation and protein folding sensor network localization and real solutions of polynomial equations. Throughout I emphasize specific applications with extensive numerical tests.Many current optimization modelling and convex relaxations for hard non-convex problems typically result in loss of strict feasibility, interior, of the feasible set. This can result in both theoretical and numerical difficulties. Rather than being a disadvantage, we turn this loss of regularity to a great advantage using a technique called facial reduction (FR). In particular, this has resulted in extremely efficient algorithms for many intractable problems. The result is that we can solve huge problems often without the need of a numerical optimization solver. For matrix completion type problems, in the noiseless case one gets extremely high accuracy. In the noisy case, one can use the notion of exposing vectors of the faces to avoid build up of round-off error and obtain solutions within the order of the noise. In addition, the FR technique appears to fit perfectly with first order methods as one can maintain two sets of variables and alternate projections between them. The work I am doing has many applications to the data science and machine learning areas in computer science and to operations research. In particular, the loss of regularity, strict feasibility, appears in surprisingly many applications as mentioned above. The FR techniques allow for more accurate solutions of larger problems than have currently been handled. The novelty of our approach is we can exploit the structures of problems to identify loss of regularity and then use this loss to our advantage to obtain a reformulation that is both stable and reduces the size. We emphasize FR as a preprocessing technique and display its mathematical elegance, geometric transparency and computational potential.