-

 

 

 




Optimization Online





 

AN INEXACT PERTURBED PATH-FOLLOWING METHOD FOR LAGRANGIAN DECOMPOSITION IN LARGE-SCALE SEPARABLE CONVEX OPTIMIZATION

Quoc Tran Dinh(quoc.trandinh***at***esat.kuleuven.be)
Ion Necoara(ion.necoara***at***acse.pub.ro)
Carlo Savorgnan(carlo.savorgnan***at***esat.kuleuven.be)
Moritz Diehl(moritz.diehl***at***esat.kuleuven.be)

Abstract: This paper studies an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale separable convex programming problems. Unlike the exact versions considered in the literature, we propose to solve the primal subproblems inexactly up to a given accuracy. This leads to an inexactness of the gradient vector and the Hessian matrix of the smoothed dual function. An inexact perturbed algorithm is then applied to minimize the smoothed dual function. The algorithm consists of two phases and both make use of the inexact derivative information of the smoothed dual problem. The convergence of the algorithm is analyzed and the worst-case complexity is estimated. As a special case, an exact path-following decomposition algorithm is obtained and its worst-case complexity is estimated. Implementation details are discussed and preliminary numerical results are reported.

Keywords: Smoothing technique, self-concordant barrier, Lagrangian decomposition, inexact perturbed Newton-type method, separable convex optimization, parallel algorithm.

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Optimization Software and Modeling Systems (Parallel Algorithms )

Citation: SIAM Journal of Optimization, pp. 1-29, in print, 2012.

Download: [PDF]

Entry Submitted: 11/02/2012
Entry Accepted: 11/02/2012
Entry Last Modified: 11/02/2012

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society