Computational and Mathematical Investigations in Optimization

9805602 todd这个项目的目标是继续进行一系列关于优化算法及其背后的数学理论的广泛研究。该项目涵盖连续和离散优化算法，包括精确和近似，其计算复杂性，实际大规模实施，性能保证（在近似算法的情况下），以及在船员调度，图像处理，设施定位，金融建模，电力系统和统计学习理论等领域的应用。要进行的研究大致可以分为三个方面。首先是内点法，包括半定规划、算法设计与分析等方面的研究；线性规划和凸规划的不可行的内点方法，包括不可行的检测；目标跟踪方法和半定规划的复杂性以及在图像处理、金融建模和统计学习理论中出现的大规模非线性问题的方法。第二个研究领域是组合优化，包括：稳定集和机组调度问题的研究；线性同余关系及其在支切法中的应用研究不一致线性不等式系统的分析及其在计算机视觉、数据压缩和统计判别分析中的应用；并设计了设施选址问题的近似算法。第三个是关于数值线性代数，并将研究：以稳定的方式求解内点半定规划算法每次迭代时出现的线性系统的方法；对于电力系统中出现的病态线性系统，给出了精确解的特殊方法。这项研究将导致改进算法，以找到工业，金融，军事，科学和工程中出现的大规模优化问题的精确或近似解。重点放在实践和理论之间的相互作用。

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.