The Analysis and Design of Gradient Methods for Large-Scale Nonlinear Optimization and Applications

这个项目将开发高效的基于梯度的创新算法和理论来解决大规模的非线性优化问题，包括那些施加和不施加约束的问题。研究内容包括Barizilai-Borwein型梯度法、有界约束优化的有效集技术和有效预条件子空间仿射尺度法、连续背包约束问题的子空间仿射尺度法和一般线性等式约束优化的有效集方法的渐近收敛研究。所有为优化而开发的技术，以及用于预条件和投影器的稀疏矩阵技术将被纳入用于一般大规模非线性优化的活动集算法。基于这一研究的高质量软件将被开发出来。虽然重点是非线性优化，但项目中开发的方法和算法将在计算科学的许多领域产生广泛的影响，这些领域需要解决如此大规模的非线性优化问题。该项目的具体应用包括医学成像中的正电子发射断层扫描(PET)，(2)两种材料混合以优化其电学性能的拓扑优化设计问题，(3)用于模式识别和数据挖掘中的分离和分类问题的支持向量机(SVM)，(4)在算法并行化和稀疏矩阵因式分解的填充降序中出现的图形划分，以及(5)蛋白质折叠，其中蛋白质的结构是根据核磁共振光谱得出的原子间距离重建的。为了最大限度地发挥影响，在该项目中开发的软件将广泛提供。被资助的研究生将接受数学跨学科应用方面的培训。

This project will develop efficient gradient-based innovative algorithms and theory for the solution of large-scale nonlinear optimization problems, including those with and without constraints imposed. The research will include the asymptotic convergence studies of Barizilai-Borwein type gradient methods, active set techniques and efficient preconditioners for bound constrained optimization, subspace affine-scaling methods for problems with continuous knapsack constraints, and active set methods for general nonlinear optimization with linear equality constrained phase. All the techniques developed for the optimization, as well as the sparse matrix technology for preconditioners and projectors will be incorporated into the active set algorithm for general large-scale nonlinear optimization. High quality software based on this research will be developed.Although the focus is nonlinear optimization, the methods and algorithms developed in the project will have broad impact in the many areas of computational science that require the solution of such large-scale nonlinear optimization problems. Specific applications of this project include Positron Emission Tomography (PET) which arises in medical imaging, (2) a design problem in topology optimization where two materials are mixed so as to optimize their electrical properties, (3) Support Vector Machines (SVM) which are used in separation and classification problems in pattern recognition and data mining, (4) graph partitioning which arises in parallelization of algorithms and in fill reducing orderings for sparse matrix factorization, and (5) protein folding where the structure of a protein is reconstructed from inter-atomic distances derived from nuclear magnetic resonance spectroscopy. To maximize the impact,the software developed in this project will be made widely available. The supported graduate student will receive training on interdisciplinary applications of mathematics.