Computational and Mathematical Investigations in 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.