A parallelizable augmented Lagrangian method applied to

A Parallelizable Augmented Lagrangian Method Applied To-Free PDF

  • Date:10 Jan 2021
  • Views:0
  • Downloads:0
  • Pages:34
  • Size:474.88 KB

Share Pdf : A Parallelizable Augmented Lagrangian Method Applied To

Download and Preview : A Parallelizable Augmented Lagrangian Method Applied To


Report CopyRight/DMCA Form For : A Parallelizable Augmented Lagrangian Method Applied To


Transcription:

2 Natashia Boland et al, the simplicial decomposition method SDM and the nonlinear block Gauss. Seidel GS method An adaptation of a serious step condition associated with. proximal bundle methods allows for the approximation tolerance to be auto. matically adjusted Under mild conditions optimal dual convergence is proven. and we report computational results on test instances from the stochastic op. timization literature We demonstrate improvement in parallel speedup over a. baseline parallel approach, Keywords augmented Lagrangian method proximal bundle method. nonlinear block Gauss Seidel method simplicial decomposition method. parallel computing, Mathematics Subject Classification 2000 90 08 90C06 90C11. 90C15 90C25 90C26 90C30 90C46,1 Introduction and Background. We develop a dual solution approach to the problem of interest having the. min tf pxq Qx z x P X z P Z u 1, where f is convex and continuously differentiable Q P Rq n is a block diagonal.
matrix determining linear constraints Qx z X Rn is a closed and bounded. set and Z Rq is a linear subspace The vector x P X of decision variables. is derived from the original decisions associated with a problem while the. vector z P Z of auxiliary variables are introduced to effect a decomposable. structure in 1 The block diagonal components of Q are denoted Qi P Rqi ni. i 1 m Problem 1 is general enough to subsume for example the split. variable deterministic reformulation of a stochastic optimization problem with. potentially multiple stages as defined for example in 8 while it can also. model the case where f is nonlinear and convex and or X is any compact. but not necessarily convex set, The Lagrangian dual function resulting from the relaxation of Qx z is. p q min f pxq J pQx z q x P X z PZ 2, Given that X is compact and f is continuous in order for 8 p q to hold. it is necessary and sufficient that the following dual feasibility assumption be. maintained,P Z K P Rq J z 0 for all z P Z 3, either by assumption or by construction Under condition 3 the z term in def. inition 2 vanishes and we may compute p q minx f pxq J Qx x P X. Consequently becomes separable as,p q i p i q,A parallelizable augmented Lagrangian method 3. where i p i q minx fi pxi q iJ Qi xi xi P Xi and p 1 m q P. Rq1 Rqm has a block structure compatible with the block diagonal. structure of Q The Lagrangian dual problem is,LD max p q 4.
In this paper we develop analyze and apply an iterative solution approach. to solving problem 4 subject to the following challenges. Implementability The set X is not convex for example it may have mixed. integer constraints as part of its definition Consequently the augmented. Lagrangian method is not supported by the theory of proximal point meth. Efficiency of parallelization The solution approach should be amenable. to efficient parallel computation in the sense of maximizing the computa. tional work that can be parallelized the memory usage that can be dis. tributed and minimizing the amount of parallel communication. For the Lagrangian dual problem 4 we note that the objective function. is concave even when f and X are not convex We can apply a subgradient. method see e g 56 in textbooks 5 54 for solving 4 in an efficiently. parallelizable manner Such an approach is proposed in 13 However it is. preferable to make use of structural features of 4 that allow for smoothing. or regularization so that better convergence properties are realized For this. reason we consider alternative developments based on proximal point methods. that are modified to address both of the above two challenges. As a starting point we first consider the classical augmented Lagrangian. method based on proximal point methods The augmented Lagrangian AL. method also known as the method of multipliers is developed from proximal. point methods and references include 32 50 4 5 The AL method typically. has favorable convergence properties as a dual solution approach for convex. problems linear convergence rate under certain assumptions see 52 4 and. references cited therein However two issues arise 1 the set X is not convex. and so current theories of convergence are not applicable and 2 the primal. subproblem associated with each iteration of the AL method is not separable. due to the augmented Lagrange term making efficient parallel implementa. tions difficult to develop, We introduce modifications to the AL method that address both of these. issues In order to introduce computational tractability in light of the possible. nonlinearity of f and the nonconvexity of X the modified AL method solves. an alternative dual problem that can provide a weaker dual bound than that. provided by the value of 4 In the case when f is linear the alternative. dual problem is equivalent to 4 This matter is explained in more detail in. Section 3 The method that results from these modifications is most naturally. compared with the proximal bundle method, The proximal bundle method initially appeared in 39 and for a survey. with history see 48 Use of inexact oracles for computing p q and elements of. 4 Natashia Boland et al, the subdifferential set B p q are studied in 48 49 29 and references therein In. its dual form the bundle method may be referred to as the stabilized column. generation method 3 or the proximal simplicial decomposition method 7. In implementation the developed algorithm more closely resembles the latter. For parallelization of the proximal bundle method see 22 and 41 The. approach developed in this paper is most naturally compared with 41 as. both approaches address the manner in which the same continuous master. problem is approximately solved The approach of 22 uses a substantially. different parallel computational paradigm based on subspace optimization. This approach in which solution subspaces are assigned to processors based. on periodically updated global state information is not necessarily based on. the problem s decomposable structure, The proximal bundle method approach requires modification for efficient. parallelization This matter is addressed in 41 where a solution to the con. tinuous master problem is obtained by primal dual interior point methods. that exploit the decomposable structure present in the augmented Lagrangian. term We provide and analyze an alternative approach based on the use of. 1 the simplicial decomposition method SDM 34 59 5 6 which provides an. alternative framework to the proximal bundle method to address the imple. mentability of the proximal point method while allowing for the possibility. that f is nonlinear and, 2 nonlinear block Gauss Seidel GS method 33 60 27 58 11 to approximate.
the solutions to the continuous master problem, Motivated by its constituent parts the algorithm we develop is referred to as. SDM GS ALM, Algorithm SDM GS ALM addresses the solution to an alternative dual. problem which is equivalent to 4 when f is linear but in general provides a. weaker dual bound otherwise This dual problem is used to address the more. general setting where f is convex but possibly nonlinear. In an iteration of SDM GS ALM the analog to the continuous master prob. lem is not solved to near exactness instead approximate solutions based on. possibly just one nonlinear block GS iteration are used Due to the underlying. need for convexification of the non relaxed constraint set implementability re. quires that the nonlinear block GS method must be integrated with the SDM. so that optimal convergence of the resulting iterations can be established In. this way a serious step condition similar to that used in proximal bundle meth. ods is eventually satisfied after a finite number of such integrated SDM GS. iterations and analogous dual optimal convergence of our approach is recov. ered even with the deviations from the proximal bundle method In summary. we algorithmically integrate the AL method the SDM nonlinear block GS. iterations and the proximal bundle method serious step condition A conver. gence analysis is also provided for SDM GS ALM Such an integration allows. for a considerable improvement in parallel efficiency with respect to maximiz. A parallelizable augmented Lagrangian method 5, ing the computational work that can be parallelized the memory usage that. can be distributed and minimizing the amount of parallel communication. Other methods developed in the past that are related to aspects of our. contribution include the following In terms of approximating within the AL. method we include reference to 17 19 where the research goal of developing. implementable approximation criteria is addressed The separable augmented. Lagrangian SALA method 28 which is an application of the alternating di. rection method of multipliers ADMM 26 23 12 with a form of resource allo. cation decomposition and incorporates separability into the AL method Other. approaches to introducing separability into the AL method include 14 57 Ja. cobi iterate approaches applied within either a proximal bundle method or an. AL method framework are considered in 45 55 the accelerated distributed. augmented Lagrangian method ADAL developed in 14 is like a Jacobi. iterate analogue of ADMM with supporting convergence analysis Other ap. proaches to incorporating separability are found in the alternating linearization. approaches 37 40 and the predictor corrector proximal multiplier PCPM. methods 15 31 All of these methods provide implementable mechanisms for. approximating primal subproblem solutions and effecting parallelism in a set. ting where X is convex However they are not practically implementable in. our setting where X is not convex and its convex hull convpX q is not given. beforehand in a computationally useful closed form description. Another recently developed algorithm referred to as FW PH 10 is closely. related to the SDM GS ALM algorithm developed in this paper In terms of. functionality both appear as modifications to ADMM with inner approxi. mated subproblem solutions While the algorithms differ only slightly in terms. of functionality there are substantial differences in the motivation and the. convergence analysis The convergence analysis of FW PH interfaces with the. convergence analysis for ADMM which is most naturally developed in the. context of the theory of maximal monotone operators and Douglas Rachford. splitting methods 18 20 or as the proximal decomposition of the graph of. a maximal monotone operator 43 In contrast the convergence analysis of. SDM GS ALM naturally reflects its synthesis of SDM the nonlinear block GS. method the proximal bundle method and the AL method The convergence. analysis of SDM GS ALM follows under more general assumptions than that. for FW PH In particular the convergence analysis of SDM GS ALM allows. for trimming of the inner approximations and it does not require the warm. starting required by FW PH The most important difference in functionality. is due to the influence of ideas from proximal bundle methods in SDM GS. ALM where updates of are taken conditionally at each iteration while such. updates are taken unconditionally at each iteration of FW PH We shall see. that these conditional updates help to mitigate performance problems that. arise due to the seemingly inevitable use of suboptimal algorithm parameters. In papers such as 24 21 ADMM is applied directly to the primal prob. lem 1 In both works it is acknowledged that ADMM is not theoretically. supported in optimal convergence due to the lack of convexity of X Neverthe. less 24 reports the potential for Lagrangian dual bounds to be recovered at. 6 Natashia Boland et al, each iteration of ADMM even though it is applied to 1 In 21 where ADMM. is applied to nonconvex decentralized unit commitment problems heuristic im. provements to ADMM are introduced to address the lack of convexity due to. the mixed integer constraints In contrast to both of these approaches where. ADMM is applied directly to the primal problem 1 the approach devel. oped in this paper and its related approach 10 both resemble ADMM but. with application to a primal characterization of the dual problem In these. two approaches the challenge of not having an explicit form for this primal. characterization is addressed, The remainder of the paper is organized as follows In Section 2 a general.
algorithmic framework based on the AL method with approximate subproblem. solutions is developed and analyzed In Section 3 a specific implementation. of the Section 2 framework is posed based on the integration of SDM and GS. methods which addresses the aforementioned issues of implementability and. efficiency of parallelization In Section 4 computational experiments and their. outcomes are described and interpreted And at last Section 5 concludes the. paper and provides avenues for future work,2 An alternative AL approximation approach. In the following development we address the solution of a slightly different. dual problem,CLD max C p q 5, based on the dual function C p q minx f pxq J Qx x P convpX q The. only difference between C and is the use of constraint set convpX q in the. former versus the use of X in the latter We assume as before that P Z K. Remark 1 Under the assumption that convpX q is not known beforehand by. any characterization direct evaluation of C or any of its subgradients at any. P Z K is not possible This dual function is not used in the proximal bundle. A parallelizable augmented Lagrangian method applied to large scale non convex constrained optimization problems Natashia Boland Je rey Christiansen Brian Dandurand Andrew Eberhard Fabricio Oliveira Received date Accepted date Abstract We contribute improvements to a Lagrangian dual solution ap proach applied to large scale optimization problems whose objective functions are convex

Related Books