DocumentCode :
115032
Title :
A Newton algorithm for distributed Semi-Definite Programs using the primal-dual interior-point method
Author :
Gros, Sebastien
Author_Institution :
Chalmers Univ. of Tech, Gothenburg, Sweden
fYear :
2014
fDate :
15-17 Dec. 2014
Firstpage :
3222
Lastpage :
3227
Abstract :
This paper considers the problem of solving convex decomposable Semi-Definite Programs (SDPs) in a distributed fashion. The SDP subproblems are solved locally, while the constraints coupling the different local problems are introduced in the local cost functions using a Lagrange relaxation. The local problems are solved via the primal-dual interior-point method, taking steps along the Nesterov-Todd directions, while the feasibility of the coupling constraints is improved along the central path by taking Newton iterations on the multipliers associated to the Lagrange relaxation. The local factorisations involved in computing the Nesterov-Todd directions are re-used to construct gradients and Hessians for the Lagrange multipliers. The local factorisations are also re-used to construct linear predictors for both the local primal-dual variables and the multipliers, which improve significantly the tracking of the central path.
Keywords :
Newton method; mathematical programming; Lagrange relaxation; Nesterov-Todd direction; Newton algorithm; SDP; cost function; coupling constraint; distributed semidefinite program; linear predictors; primal-dual interior-point method; primal-dual variables; Algorithm design and analysis; Convergence; Couplings; Lagrangian functions; Prediction algorithms; Sensitivity; Symmetric matrices;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on
Conference_Location :
Los Angeles, CA
Print_ISBN :
978-1-4799-7746-8
Type :
conf
DOI :
10.1109/CDC.2014.7039887
Filename :
7039887
Link To Document :
بازگشت