基于牛顿法的并行优化算法

Parallel optimization algorithm based on Newton method

针对非线性数值优化问题,提出一种在分布式环境下的基于牛顿法的并行算法。引入松弛变量,将不等式约束转换为等式约束,利用广义拉格朗日乘子将约束优化问题转换为无约束子优化问题。为了并行地求解这些子优化问题,将Newton迭代法中的Hessian矩阵进行适当的分裂,采用简单迭代法求解Newton法中的线性方程组。在理论上对该算法进行了收敛性分析。在HP rx2600集群上进行的数值实验结果表明并行效率达90%以上。

This paper presented a parallel algorithm for solving nonlinear optimization problem on distributed-memory multi-computers.It converted optimization problem that contains inequality constraints to a problem with equality constraints by introducing slack variables.Replaced the equality constrained problem by a sequence of unconstrained sub-problems by augmented Lagrangian method.To parallelly solve the nonlinear unconstrained sub-optimization problem,properly splitted Hessian matrix in Newton method.It solved the linear equation in Newton method by simple iterative method.In theory,gave analysis of convergence about this algorithm.Some numerical results on HP rx2600 cluster show that the algorithm＇s parallel efficiency exceeds 90%.