Theory and Efficient Algorithms for Hard, Large Scale, Numerical Optimization

大规模硬数值优化的理论和高效算法

• 批准号: 9161-2013
• 负责人: Wolkowicz, Henry
• 金额: $ 2.48万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568649
• 关键词: Theory; Efficient; Algorithms; Hard; Large

The focus of my research will be the proper modelling of hard problems, and the design and implementation of efficient and robust numerical algorithms for large scale, hard, optimization problems. The problems I will deal with arise in many important applications, e.g. molecular conformation (MC), sensor network localization (SNL), inverse imaging and machine learning. In particular, many of these problems arise in the relaxations of hard combinatorial optimization problems. In many instances, the usual modelling approaches result in problems that are both large scale and ill-posed. Therefore, they are hard to solve numerically. Rather than being a disadvantage, one can often take advantage of the ill-posedness to get both a stable problem and one that is smaller in size. In particular, for problems such as SNL one can solve huge problems to high accuracy by exploiting the hidden degeneracy. I plan on applying this technique to MC problems with noisy data as well as to protein design problems. The techniques that I use involve continuous optimization, nonlinear programming (NLP) and in particular, semidefinite programming (SDP). For SDP, my research contributions involve theory, algorithms, and applications, i.e., they include strong duality results, stable algorithms, and the study of relaxations for various applications. Some of the codes that I have designed for the standard form Linear Programming (LP) model have already been implemented in MAPLE. I plan to implement algorithms for more general LP models that include both upper and lower bounds on the variables. As well I plan on implementing codes that solve more general NLP problems. For the NLP problems, I use algorithms for generalized trust region problems to solve large scale unconstrained minimization, as well as solve general NLP using stable sequential quadratic programming methods. The success of these implementations means that researchers in my field will have access to stable, high accuracy, algorithms.

我的研究重点是对困难问题进行正确建模，以及针对大规模困难优化问题设计和实现高效且鲁棒的数值算法。我将处理的问题出现在许多重要的应用中，例如分子构象（MC）、传感器网络定位（SNL）、逆向成像和机器学习。特别是，许多这样的问题出现在硬组合优化问题的松弛中。在许多情况下，通常的建模方法会导致大规模且不适定的问题。因此，它们很难用数值方法求解。人们通常可以利用不适定性来获得稳定的问题和规模较小的问题，而不是成为一种劣势。 特别是，对于 SNL 这样的问题，人们可以通过利用隐藏的简并性来高精度地解决巨大的问题。我计划将此技术应用于带有噪声数据的 MC 问题以及蛋白质设计问题。 我使用的技术涉及连续优化、非线性规划 (NLP)，特别是半定规划 (SDP)。 对于SDP，我的研究贡献涉及理论、算法和应用，即包括强对偶性结果、稳定算法以及各种应用的松弛研究。我为标准形式线性规划 (LP) 模型设计的一些代码已经在 MAPLE 中实现。我计划为更通用的 LP 模型实现算法，其中包括变量的上限和下限。我还计划实现解决更一般 NLP 问题的代码。对于 NLP 问题，我使用广义信赖域问题的算法来解决大规模无约束最小化问题，并使用稳定的顺序二次规划方法来解决一般 NLP。这些实现的成功意味着我所在领域的研究人员将能够获得稳定、高精度的算法。