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

在困难的大规模数值优化中利用结构和隐藏凸性

• 批准号: RGPIN-2018-04028
• 负责人: Wolkowicz, Henry
• 金额: $ 4.01万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=690567
• 关键词: Exploiting; Structure; Hidden; Convexity; Hard

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.

我的研究旨在应用持续的优化放松并利用结构，以得出有效，准确地解决大规模硬数值问题的实用算法。这些问题在数据科学中出现，通常是非凸面和棘手的。一个众所周知的应用程序是低级矩阵完成（LRMC）问题，例如Netflix电影评分问题，即，可以填写缺失的条目，以便向客户提出好建议。其他应用程序包括：建模计划和位置问题（例如二次分配问题）的硬离散优化问题； 强大的主成分分析，包括从高度损坏的监视数据中恢复测量；分子构象和蛋白质折叠传感器网络的定位以及多项式方程的实际解。 在整个过程中，我强调了通过广泛的数值测试的特定应用。这可能会导致理论和数值困难。我们将这种规律性的丧失变为巨大的优势，而不是作为劣势，而是使用称为面部减少（FR）的技术。特别是，这导致了许多棘手问题的极有效算法。结果是，我们可以经常解决巨大的问题，而无需数值优化求解器。对于矩阵完成类型问题，在无声的情况下，一个人的精度极高。在嘈杂的情况下，人们可以使用暴露面部向量的概念来避免产生圆形错误并在噪声顺序中获得解决方案。此外，FR技术似乎完全符合一阶方法，因为可以维护两组变量和它们之间的替代投影。 ***我正在做的工作在计算机科学和运营研究中的数据科学和机器学习领域有许多应用程序。特别是，在许多应用程序中出现了许多规律性，严格的可行性，如上所述。与目前处理的技术相比，FR技术允许更准确地解决更大的问题。我们方法的新颖性是我们可以利用问题结构来确定丧失规律性的丧失，然后利用这种损失来获得既稳定又降低规模的重新印象。我们强调FR是一种预处理技术，并显示其数学优雅，几何透明度和计算潜力。