求解一类特殊二次规划问题的分布式牛顿算法  

Distributed Newton Algorithm for a Special Quadratic Programming Problem

作　　者：王永丽[1] 王栋[1] 贺国平[1,2] 胡运红[3] 

机构地区：[1]山东科技大学数学与系统科学学院,山东青岛266590 [2]山东省科学院计算中心,山东济南250000 [3]运城学院应用数学系,山西运城044000

出　　处：《数学的实践与认识》2015年第5期209-218,共10页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10971122;11241005)

摘　　要：针对二次规划问题,现有的基于对偶分解和梯度方法的分布式算法由于没有充分利用目标函数的二阶信息,算法并不高效.针对一类特殊二次规划问题提出分布式牛顿算法,算法在计算对偶向量时使用Jacobi迭代,使算法不仅能够分布式执行并且可以并行运算.通过证明Jacobi矩阵的谱半径小于1保证了迭代的收敛性.最后通过数值实验说明分布式牛顿算法在运行时间上的高效性.Most existing work uses dual decomposition and gradient methods to solve quadratic programming（QP） problem in a distributed manner. These methods are ineffi- cient because lack of the second-order result of the objective function. This paper develops a distributed Newton algorithm for solving QP problems with special objective functions. By using Jacobian iteration in dual updates, both primal and dual variables can be solved in a decentralized parallel manner. The key is whether the Jacobian iteration converges to ＂the optimal solution. We can ensure its convergence through proving the spectral radius of Ja- cobian matrix less than 1. Simulation results demonstrate the performance of the proposed distributed Newton algorithm outperform the distributed incremental gradient algorithm.

关 键 词：二次规划 分布式 牛顿算法 JACOBI迭代 并行计算 

分 类 号：O221.2[理学—运筹学与控制论]