New Efficient Methods for Challenging Computational Optimization Problems

解决计算优化问题的有效新方法

• 批准号: 327684-2012
• 负责人: Coleman, Thomas
• 金额: $ 1.82万
• 依托单位: 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=572099
• 关键词: New; Efficient; Methods; Challenging; Computational

There is a growing interest in, and demand for, efficient and practical computational optimization methods in numerous application domains. Our proposed research will develop methodology, and theoretical underpinnings and understanding, for three such problems in computational optimization. All three problems are hard, and computationally demanding, but progress on developing effective solutions will have broad impact not only in the field of optimization but across scientific computing and applications more generally. The first problem is to develop methods to find efficiency-enhancing structure in a user objective function code to allow for the efficient application of automatic differentiation (AD), applied in a structured way, to compute first and possibly second derivatives. This proposed effort builds on our previous work on AD for sparse problems, but the idea here is to find structure beyond sparsity. Our proposed technique involves understanding and manipulating the underlying computational graph (available through the use of 'reverse mode' AD). The second problem is to develop an effective procedure to find sparse solutions to optimization problems (the optimization themselves may or may not be sparse). This is an important problem because sparse solutions, in turn, yield efficient and robust models for various application modeling problems. Our approach is very novel but is related to a technique developed by the author (and colleagues) in the area of index tracking in finance. A sequence of approximations is created and optimization solutions are tracked from one approximation to the subsequent approximation. The final problem is similar but also different. It is to develop an effective optimization procedure for effective 'feature selection' in the support vector machine area. Effective feature selection can improve model interpretability and robustness. Our approach to 'feature selection' will draw heavily on previous work on piecewise differentiable problems, and problems with box constraints.

许多应用领域对高效实用的计算优化方法的兴趣和需求日益增长。我们提出的研究将为计算优化中的三个此类问题开发方法论、理论基础和理解。这三个问题都很困难，而且计算要求很高，但开发有效解决方案的进展不仅会在优化领域产生广泛影响，而且会在科学计算和更广泛的应用领域产生广泛影响。 第一个问题是开发在用户目标函数代码中找到提高效率的结构的方法，以允许以结构化方式有效应用自动微分（AD）来计算一阶导数和可能的二阶导数。这项提议的工作建立在我们之前针对稀疏问题的 AD 工作的基础上，但这里的想法是找到稀疏性之外的结构。我们提出的技术涉及理解和操作底层计算图（可通过使用“反向模式”AD 获得）。 第二个问题是开发一个有效的过程来找到优化问题的稀疏解（优化本身可能是稀疏的，也可能不是稀疏的）。这是一个重要的问题，因为稀疏解决方案反过来会为各种应用程序建模问题产生高效且稳健的模型。我们的方法非常新颖，但与作者（和同事）在金融指数跟踪领域开发的技术相关。创建一系列近似值，并从一个近似值到下一个近似值跟踪优化解决方案。 最后的问题相似但又不同。它旨在开发一种有效的优化程序，以在支持向量机领域进行有效的“特征选择”。有效的特征选择可以提高模型的可解释性和鲁棒性。我们的“特征选择”方法将大量借鉴先前关于分段可微问题和框约束问题的工作。