Mathematical Sciences: Algorithms for Large Scale Optimization

本文将研究多变量非光滑复合函数的最小化算法。这类函数的实例有可积和有界数据拟合，以及非线性规划的惩罚函数。一般的方法是使用可信域框架和迭代方法，本着梯度投影法的精神，在每次迭代中求解子问题。它的目的是使算法最适合于非线性问题，其中的约束是部分可分离的（即约束导数矩阵具有块对角结构）。这类问题的重要例子包括约束离散最优控制和多商品网络流。将特别注意在并行计算机架构上的算法实现。大规模线性规划问题的迭代求解方法也将被研究。这些方法将一些成熟的一般约束优化技术作为框架，其优点是不需要对约束矩阵进行因式分解。相反，迭代方法（如连续过度松弛或梯度投影/共轭梯度技术）用于在每次迭代中求解凸二次规划子问题。将在矢量/并行处理器上实现这些不同的算法，以确定底层方法的有效性，以及计算机体系结构可以利用的程度。

Research will be carried out into algorithms for minimizing nonsmooth composite functions of many variables. Instances of such functions are integrable and bounded data fitting, and penalty functions for nonlinear programming. The general approach is to use a trust-region framework, and iterative methods, in the spirit of gradient projection methods, to solve the subproblem at each iteration. It is intended that the algorithms will be most suitable for nonlinear problems in which the constraints are partially separable (i.e. the contraint derivative matrix has a block-diagonal structure). Important examples of such problems include constrained discrete optimal control, and multicommodity network flow. Particular attention will be given to implementation of the algorithms on parallel computer architectures. Iterative solution methods for large-scale linear programming problems will also be investigated. These methods, which use as a framework some well-established techniques for general constrained optimization, have the advantage that factorization of the constraint matrix is never required. Instead, iterative methods (such as successive over-relaxation or a gradient projection/conjugate gradient technique) are used to solve the convex quadratic programming subproblems at each iteration. Implementation of these various algorithms on vector/parallel processors will be carried out, to determine both the effectiveness of the underlying approach, and the extent to which computer architectures can be utilized.