Computational and Mathematical Investigations in Optimization

优化中的计算和数学研究

• 批准号: 9805602
• 负责人: Michael Todd
• 金额: $ 36万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-07-15 至 2002-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9805602&HistoricalAwards=false
• 关键词: Computational; Mathematical; Investigations; Optimization

9805602ToddThe goal of this project is to continue a broad set of ongoing studies concerning optimization algorithms and the mathematical theory underlying them. The project covers continuous and discrete optimization algorithms, both exact and approximate, their computational complexity, practical large-scale implementation, performance guarantees (in the case of approximate algorithms), and applications in such areas as crew-scheduling, image-processing, facility location, financial modeling, electrical power systems, and statistical learning theory.The research to be conducted can be roughly grouped into three areas. The first is interior-point methods, including the study of: semidefinite programming, algorithm design and analysis; infeasible-interior-point methods for both linear and convex programming, including detection of infeasibility; the complexity of target-following methods and of semidefinite programming; and methods for large-scale nonlinear problems arising in image-processing, financial modeling, and statistical learning theory. The second area of research is combinatorial optimization, encompassing: investigation of stable-set and crew-scheduling problems; the study of linear congruence relations and their use in branch-and-cut methods; analysis of inconsistent linear inequality systems, with applications in computer vision, data compression, and statistical discriminant analysis; and design of approximation algorithms for facility location problems. The third is concerned with numerical linear algebra, and will study: methods to solve the linear systems that arise at each iteration of an interior-point semidefinite programming algorithm in a stable manner; and special methods for obtaining accurate solutions to ill-conditioned linear systems arising in electrical power systems.This research will lead to improved algorithms to find exact or approximate solutions to large-scale optimization problems arising in industry, finance, the military, science, and engineering. Emphasis is placed on the interplay between practice and theory.

9805602 Todd这个项目的目标是继续一系列正在进行的关于优化算法和数学理论的研究。 本项目的研究内容包括连续和离散优化算法（精确和近似）、计算复杂性、实际大规模实现、性能保证（近似算法）以及在机组调度、图像处理、设施定位、金融建模、电力系统和统计学习理论等领域的应用。 首先是边界点方法，包括研究：半定规划，算法设计和分析;线性和凸规划的不可行内点方法，包括不可行性的检测;目标跟踪方法和半定规划的复杂性;以及图像处理，金融建模和统计学习理论中出现的大规模非线性问题的方法。 第二个研究领域是组合优化，包括：稳定集和机组调度问题的调查;线性同余关系的研究及其在分支和切割方法中的应用;不一致线性不等式系统的分析，在计算机视觉，数据压缩和统计判别分析中的应用;以及设施定位问题的近似算法的设计。 第三是关于数值线性代数，并将研究：方法来解决线性系统出现在每一次迭代的一个临界点半定规划算法在一个稳定的方式;以及求解电力系统中病态线性系统的精确解的特殊方法。在工业、金融、军事、科学和工程中出现的规模优化问题。 重点放在实践和理论之间的相互作用。