Improved penalty algorithm for mixed integer PDE constrained optimization problems
Garmatter D., Porcelli M., Rinaldi F., Stoll M.
Modeling and Simulation 65K05 Computational Mathematics PDE-constrained optimization FOS: Mathematics 90C06 Exact penalty methods Computational Theory and Mathematics 90C51 Mathematics - Numerical Analysis Optimal control 90C11 Optimization and Control (math.OC) Interior point methods Numerical Analysis (math.NA) 93C20 Mathematics - Optimization and Control Mixed integer optimization
Optimal control problems including partial differential equation (PDE) as well as integer constraints merge the combinatorial difficulties of integer programming and the challenges related to large-scale systems resulting from discretized PDEs. So far, the branch-and-bound framework has been the most common solution strategy for such problems. In order to provide an alternative solution approach, especially in a large-scale context, this article investigates penalization techniques. Taking inspiration from a well-known family of existing exact penalty algorithms, a novel improved penalty algorithm is derived, whose key ingredients are a basin hopping strategy and an interior point method, both of which are specialized for the problem class. A thorough numerical investigation is carried out for a standard stationary test problem. Extensions to a convection-diffusion as well as a nonlinear test problem finally demonstrate the versatility of the approach.
Source: Computers & mathematics with applications (1987) 116 (2021): 2–14. doi:10.1016/j.camwa.2021.11.004
Publisher: Pergamon Press., Oxford, Regno Unito
[2] Matlab's fmincon with interior-point. https://www.mathworks.com/help/optim/ug/constrainednonlinear-optimization-algorithms.html#brnpd5f. Accessed: 2019-07-09.
[3] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1-131, 2013.
[4] C. Buchheim, R. Kuhlmann, and C. Meyer. Combinatorial optimal control of semilinear elliptic PDEs. Computational Optimization and Applications, 70(3):641-675, 03 2018.
[5] M. F. P. Costa, A. M. A. C. Rocha, R. B. Francisco, and E. M. G. P. Fernandes. Firefly penalty-based algorithm for bound constrained mixed-integer nonlinear programming. Optimization, 65(5):1085-1104, 01 2016.
[6] M. De Santis and F. Rinaldi. Continuous reformulations for zero-one programming problems. Journal of Optimization Theory and Applications, 153(1):75-84, 2012.
[7] G. Di Pillo, S. Lucidi, and F. Rinaldi. An approach to constrained global optimization based on exact penalty functions. Journal of Global Optimization, 54(2):251-260, 2012.
[8] S. R. Fipke and A. O. Celli. The use of multilateral well designs for improved recovery in heavy-oil reservoirs. In IADC/SPE Drilling Conference. Society of Petroleum Engineers, 2008.
[9] S. Funke, P. Farrell, and M. Piggott. Tidal turbine array optimisation using the adjoint approach. Renewable Energy, 63:658 - 673, 2014.
[10] F. Giannessi and F. Niccolucci. Connections between nonlinear and integer programming problems. In Symposia Mathematica, volume 19, pages 161-176. Academic Press New York, 1976.
[11] F. Giannessi and F. Tardella. Connections between nonlinear programming and discrete optimization. In Handbook of Combinatorial Optimization, pages 149-188. Springer US, 1998.
[12] S. G¨ottlich, A. Potschka, and C. Teuber. A partial outer convexification approach to control transmission lines. Computational Optimization and Applications, 72(2):431-456, 03 2019.
[13] A. Grosso, M. Locatelli, and F. Schoen. A population-based approach for hard global optimization problems based on dissimilarity measures. Math. Program., 110(2):373-404, 2007.
[14] M. Hahn, S. Leyffer, and V. M. Zavala. Mixed-integer pde-constrained optimal control of gas networks. Techreport. url: https://wiki. mcs. anl. gov/leyffer/images/2/27/GasNetMIP. pdf (visited on 06/25/2018), 2017.
[15] J. Larson, S. Leyffer, P. Palkar, and S. M. Wild. A method for convex black-box integer global optimization. arXiv preprint arXiv:1903.11366, 2019.
[16] R. H. Leary. Global optimization on funneling landscapes. J. Global Optim., 18(4):367-383, 2000.
[17] S. Leyffer. Optimization: Applications, algorithms and computations: 24 lectures on nonlinear optimization and beyond, 2016.
[18] M. Locatelli and F. Schoen. Global optimization: theory, algorithms, and applications, volume 15. Siam, 2013.
[19] S. Lucidi and F. Rinaldi. Exact penalty functions for nonlinear integer programming problems. Journal of Optimization Theory and Applications, 145(3):479-488, 04 2010.
[20] S. Lucidi and F. Rinaldi. An exact penalty global optimization approach for mixed-integer programming problems. Optimization Letters, 7(2):297-307, 10 2011.
[21] P. Manns and C. Kirches. Multi-dimensional sum-up rounding for elliptic control systems. DFG Preprint SPP1962-080, 2018.
[22] W. Murray and K.-M. Ng. An algorithm for nonlinear optimization problems with binary variables. Computational Optimization and Applications, 47(2):257-288, 12 2008.
[23] U. Ozdogan and R. N. Horne. Optimization of well placement under time-dependent uncertainty. SPE Reservoir Evaluation & Engineering, 9(02):135-145, 04 2006.
[24] M. E. Pfetsch, A. Fu¨genschuh, B. Geißler, N. Geißler, R. Gollmer, B. Hiller, J. Humpola, T. Koch, T. Lehmann, A. Martin, et al. Validation of nominations in gas network optimization: models, methods, and solutions. Optimization Methods and Software, 30(1):15-53, 2015.
[25] G. D. Pillo, S. Lucidi, and F. Rinaldi. A derivative-free algorithm for constrained global optimization based on exact penalty functions. Journal of Optimization Theory and Applications, 164(3):862-882, 11 2013.
[26] F. Rinaldi. New results on the equivalence between zero-one programming and continuous concave programming. Optimization Letters, 3(3):377-386, 03 2009.
[27] F. Tr¨oltzsch. Optimal control of partial differential equations: theory, methods, and applications, volume 112. American Mathematical Soc., 2010.
[28] C. Wesselhoeft. Mixed-Integer PDE-Constrained Optimization. PhD thesis, Imperial College London, 2017.
[29] P. Y. Zhang, D. A. Romero, J. C. Beck, and C. H. Amon. Solving wind farm layout optimization with mixed integer programs and constraint programs. EURO Journal on Computational Optimization, 2(3):195-219, 08 2014.
[30] W. Zhu. Penalty parameter for linearly constrained 0-1 quadratic programming. Journal of Optimization Theory and Applications, 116(1):229-239, 2003.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:468674,
title = {Improved penalty algorithm for mixed integer PDE constrained optimization problems},
author = {Garmatter D. and Porcelli M. and Rinaldi F. and Stoll M.},
publisher = {Pergamon Press., Oxford, Regno Unito},
doi = {10.1016/j.camwa.2021.11.004 and 10.48550/arxiv.1907.06462},
journal = {Computers \& mathematics with applications (1987)},
volume = {116},
pages = {2–14},
year = {2021}
}
0000-0003-0183-1204ISTI Repository
DOI
10.1016/j.camwa.2021.11.004
10.48550/arxiv.1907.06462
arXiv.org e-Print Archive
Computers & Mathematics with Applications
www.sciencedirect.com