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 作为一种预处理技术，并展示其数学优雅、几何透明度和计算潜力。