Convergence of Mixed-Integer ALADIN
Pages 51 - 54
Abstract
The mixed-integer extension of the well-known Augmented Lagrangian Alternating Direction Inexact Newton (ALADIN) method has been shown to have favourable results for a number of different problems from battery scheduling to reactive power dispatch. Despite the demonstrated convergence for these problems, a general convergence proof has thus far been an open question. To this effect, the present paper proves limited convergence properties for the mixed-integer ALADIN algorithm and provides a new algorithm for detecting a class of problems for which convergence is not possible.
References
[1]
B. Houska, J. Frasch and M. Diehl, "An Augmented Lagrangian Based Algorithm for Distributed NonConvex Optimization," SIAM J. Optim, vol. 26, no. 2, p. 1101--1127, Jan 2016.
[2]
A. Murray, T. Faulwasser and V. Hagenmeyer, "Assessment of a multi-agent mixed-integer optimization algorithm for battery scheduling," Proceedings of the Ninth International Conference on Future Energy Systems, pp. 453--455, 2018.
[3]
A. Murray, A. Engelmann and V. Hagenmeyer, "Hierarchical Distributed Mixed-Integer Optimization for Reactive Power Dispatch," in 10th Symposium on Control of Power and Energy Systems, 2018.
[4]
A. Murray, T. Faulwasser and V. Hagenmeyer, "Mixed-integer vs. real-valued formulations of distributed battery scheduling problems," 10th Symposium on Control of Power and Energy Systems (CPES 2018), vol. 51, p. 350{355, 2018.
[5]
R. Takapoui, N. Moehle, S. Boyd and A. Bemporad, "A simple effective heuristic for mixed-integer programming," International Journal of Control, vol. 93, pp. 2--12, 2020.
[6]
M. Tawarmalani and N. Sahinidis, "A polyhedral branch-and-cut approach to global optimization," Mathematical Programming, vol. 103, pp. 225--249, 2005.
[7]
T. Achterberg, "SCIP: solving constraint integer programs," Mathematical Programming Computation, vol. 1, pp. 1--41, 2009.
[8]
P. Bonami, L. Biegler, A. Conn, G. Cornuejols, I. Grossmann, C. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya and A. Wächter, "An algorithmic framework for convex mixed integer nonlinear programs," Discrete Optimization, vol. 5, pp. 186--204, 2008.
[9]
A. Wächter and L. Biegler, "On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming," Mathematical Programming, vol. 106, no. 1, pp. 25--57, 2005.
[10]
R. Scattolini, "Architectures for distributed and hierarchical model predictive control - a review," Journal of Process Control, vol. 19, pp. 723--731, 2009.
[11]
B. Houska, D. Kouzoupis, Y. Jiang and M. Diehl, "Convex optimization with ALADIN," Math. Program., pp. 1--22, 2018.
[12]
L. Bertacco, M. Fischetti and A. Lodi, "A feasibility pump heuristic for general mixed-integer problems," Discrete Optimization, vol. 4, pp. 63--76, 2007.
[13]
M. Fischetti and A. Lodi, "Heuristics in mixed integer programming," Wiley Encyclopedia of Operations Research and Management Science, 2010.
[14]
M. Frumkin, "Polynomial time algorithms in the theory of linear diophantine equations," International Conference on Fundamentals of Computation Theory, pp. 386--392, 1977.
[15]
E. Gilbert, D. Johnson and S. Keerthi, "A fast procedure for computing the distance between complex objects in three-dimensional space," IEEE Journal on Robotics and Automation, vol. 4, no. 2, pp. 193--203, 1988.
[16]
C. Papadimitriou and K. Steiglitz, "Combinatorial optimization: algorithms and complexity," Prentice Hall, 1982.
[17]
N. Azizan-Ruhi, F. Lahouti, A. Avestimehr and B. Hassibi, "Distributed solution of large-scale linear systems via accelerated projection-based consensus," IEEE Transactions on Signal Processing, vol. 67, no. 14, pp. 3806--3817, 2019.
Index Terms
- Convergence of Mixed-Integer ALADIN
Recommendations
Method for solving generalized convex nonsmooth mixed-integer nonlinear programming problems
In this paper, we generalize the extended supporting hyperplane algorithm for a convex continuously differentiable mixed-integer nonlinear programming problem to solve a wider class of nonsmooth problems. The generalization is made by using the ...
Inexact feasibility pump for mixed integer nonlinear programming
The mixed integer nonlinear programming (MINLP) problem as an optimization problem involves both continuous and discrete variables. Moreover, at least one of the functions defining the objective function or the constraints must be nonlinear. Because of ...
Conic mixed-integer rounding cuts
A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2020
109 pages
ISBN:9781450377324
DOI:10.1145/3423390
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- University of Thessaly: University of Thessaly, Volos, Greece
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 November 2020
Check for updates
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- helmholtz-gemeinschaft
Conference
ICACS'20
ICACS'20: 2020 4th International Conference on Algorithms, Computing and Systems
January 6 - 8, 2020
Rabat, Morocco
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 63Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)1
Reflects downloads up to 19 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in