article

An Alternating Trust Region Algorithm for Distributed Linearly Constrained Nonlinear Programs, Application to the Optimal Power Flow Problem

Authors:

Jean-Hubert Hours,

Colin N. JonesAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 173, Issue 3

Pages 844 - 877

https://doi.org/10.1007/s10957-015-0853-2

Published: 01 June 2017 Publication History

Abstract

A novel trust region method for solving linearly constrained nonlinear programs is presented. The proposed technique is amenable to a distributed implementation, as its salient ingredient is an alternating projected gradient sweep in place of the Cauchy point computation. It is proven that the algorithm yields a sequence that globally converges to a critical point. As a result of some changes to the standard trust region method, namely a proximal regularisation of the trust region subproblem, it is shown that the local convergence rate is linear with an arbitrarily small ratio. Thus, convergence is locally almost superlinear, under standard regularity assumptions. The proposed method is successfully applied to compute local solutions to alternating current optimal power flow problems in transmission and distribution networks. Moreover, the new mechanism for computing a Cauchy point compares favourably against the standard projected search, as for its activity detection properties.

References

[1]

Necoara, I., Savorgnan, C., Tran Dinh, Q., Suykens, J., Diehl, M.: Distributed nonlinear optimal control using sequential convex programming and smoothing techniques. In: Proceedings of the $$48^{\text{th}}$$48th Conference on Decision and Control (2009)

[2]

Kim, B.H., Baldick, R.: Coarse-grained distributed optimal power flow. IEEE Trans. Power Syst. 12(2), 932---939 (1997)

[3]

Chiang, M., Low, S., Calderbank, A., Doyle, J.: Layering as optimization decomposition: a mathematical theory of network architectures. Proc. IEEE 95(1), 255---312 (2007)

[4]

Hours, J.-H., Jones, C.N.: A parametric non-convex decomposition algorithm for real-time and distributed NMPC. IEEE Trans. Autom. Control 61(2), 287---302 (2016)

[5]

Gan, L., Li, N., Topcu, U., Low, S.H.: Exact convex relaxation of optimal power flow in radial network. IEEE Trans. Autom. Control 60, 72---87 (2014)

[6]

Zavala, V.M., Laird, C.D., Biegler, L.T.: Interior-point decomposition approaches for parallel solution of large-scale nonlinear parameter estimation problems. Chem. Eng. Sci. 63, 4834---4845 (2008)

[7]

Fei, Y., Guodong, R., Wang, B., Wang, W.: Parallel L-BFGS-B algorithm on GPU. Comput. Graph. 40, 1---9 (2014)

Digital Library

[8]

Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont (1997)

Digital Library

[9]

Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25---57 (2006)

Digital Library

[10]

Tran-Dinh, Q., Savorgnan, C., Diehl, M.: Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems. Comput. Optim. Appl. 55(1), 75---111 (2013)

Digital Library

[11]

Cohen, G.: Auxiliary problem principle and decomposition of optimization problems. J. Optim. Theory Appl. 32(3), 277---305 (1980)

[12]

Hamdi, A., Mishra, S.K.: Decomposition methods based on augmented Lagrangian: a survey. In: Topics in Nonconvex Optimization. Mishra, S.K. (2011)

[13]

Hours, J.-H., Jones, C.N.: An augmented Lagrangian coordination---decomposition algorithm for solving distributed non-convex programs. In: Proceedings of the 2014 American Control Conference, pp. 4312---4317 (2014)

[14]

Tran Dinh, Q., Necoara, I., Diehl, M.: A dual decomposition algorithm for separable nonconvex optimization using the penalty framework. In: Proceedings of the $$52^{\text{ nd }}$$52nd Conference on Decision and Control (2013)

[15]

Conn, A., Gould, N.I.M., Toint, P.L.: A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545---572 (1991)

Digital Library

[16]

Fernández, D., Solodov, M.V.: Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition. SIAM J. Optim. 22(2), 384---407 (2012)

[17]

Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1---2), 459---494 (2014)

Digital Library

[18]

Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. Society for Industrial and Applied Mathematics, Philadelphia (2000)

Digital Library

[19]

Zavala, V.M., Anitescu, M.: Scalable nonlinear programming via exact differentiable penalty functions and trust-region Newton methods. SIAM J. Optim. 24(1), 528---558 (2014)

Digital Library

[20]

D'Azevedo, E., Eijkhout, V., Romine, C.: LAPACK Working Note 56: Reducing communication costs in the conjugate gradient algorithm on distributed memory multiprocessors. Technical report, University of Tennessee, Knoxville, TN (1993)

Digital Library

[21]

Verschoor, M., Jalba, A.C.: Analysis and performance estimation of the conjugate gradient method on multiple GPUs. Parallel Comput. 38(10---11), 552---575 (2012)

Digital Library

[22]

Conn, A.R., Gould, N.I.M., Toint, P.L.: Global convergence of a class of trust region algorithms for optimization with simple bounds. SIAM J. Numer. Anal. 25(2) (1988)

Digital Library

[23]

Xue, D., Sun, W., Qi, L.: An alternating structured trust-region algorithm for separable optimization problems with nonconvex constraints. Comput. Optim. Appl. 57, 365---386 (2014)

Digital Library

[24]

Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (2009)

[25]

Moreau, J.: Décomposition orthogonale d'un espace hilbertien selon deux cônes mutuellement polaires. C.R. Acad. Sci. 255, 238---240 (1962)

[26]

Burke, J., Moré, J., Toraldo, G.: Convergence properties of trust region methods for linear and convex constraints. Math. Program. 47, 305---336 (1990)

Digital Library

[27]

Moré, J.J.: Trust regions and projected gradients. In: Lecture Notes in Control and Information Sciences, vol. 113. Springer, Berlin (1988)

[28]

Steihaug, T.: The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20, 626---637 (1983)

Digital Library

[29]

Nocedal, J., Wright, S.: Numerical Optimization. Springer, New-York (2006)

[30]

Yamashita, N.: Sparse quasi-Newton updates with positive definite matrix completion. Math. Program. 115(1), 1---30 (2008)

Digital Library

[31]

Curtis, F.E., Gould, N.I.M., Jiang, H., Robinson, D.P.: Adaptive augmented Lagrangian methods: algorithms and practical numerical experience. Technical report 14T-006, COR@L Laboratory, Department of ISE, Lehigh University (2014. To appear in Optimization Methods and Software). http://coral.ie.lehigh.edu/~frankecurtis/wp-content/papers/CurtGoulJianRobi14.pdf

[32]

Lam, A.Y.S., Zhang, B., Tse, D.N.: Distributed algorithms for optimal power flow. In: Proceedings of the 51st Conference on Decision and Control, pp. 430---437 (2012)

[33]

Bukhsh, W.A., Grothey, A., McKinnon, K.I.M., Trodden, P.A.: Local solutions of the optimal power flow problem. IEEE Trans. Power Syst. 28(4) (2013)

[34]

Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Belmont (1982)

[35]

Zhu, J.: Optimization of Power System Operation. IEEE Press, Piscataway (2009)

[36]

http://www.maths.ed.ac.uk/optenergy/LocalOpt/

Cited By

Khodayifar SRaayatpanah MRabiee ARahimian HPardalos P(2018)Optimal Long-Term Distributed Generation Planning and Reconfiguration of Distribution SystemsJournal of Optimization Theory and Applications10.1007/s10957-018-1367-5179:1(283-310)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10957-018-1367-5

An Alternating Trust Region Algorithm for Distributed Linearly Constrained Nonlinear Programs, Application to the Optimal Power Flow Problem
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A coordinate gradient descent method for nonsmooth separable minimization

We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with ℓ1-regularization. We propose a (block) coordinate ...
Primal-Dual Active-Set Methods for Large-Scale Optimization

In this paper, we introduce two primal-dual active-set methods for solving large-scale constrained optimization problems. The first method minimizes a sequence of primal-dual augmented Lagrangian functions subject to bounds on the primal variables and ...
A proximal trust-region method for nonsmooth optimization with inexact function and gradient evaluations
Abstract
Many applications require minimizing the sum of smooth and nonsmooth functions. For example, basis pursuit denoising problems in data science require minimizing a measure of data misfit plus an $ℓ^{1}$ -regularizer. Similar problems arise in the optimal ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 173, Issue 3

June 2017

344 pages

ISSN:0022-3239

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Plenum Press

United States

Publication History

Published: 01 June 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khodayifar SRaayatpanah MRabiee ARahimian HPardalos P(2018)Optimal Long-Term Distributed Generation Planning and Reconfiguration of Distribution SystemsJournal of Optimization Theory and Applications10.1007/s10957-018-1367-5179:1(283-310)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10957-018-1367-5

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents