Optimistic optimization for continuous nonconvex piecewise affine functions. (English) Zbl 1464.90069

Xu, Jia; van den Boom, Ton; De Schutter, Bart

Automatica 125, Article ID 109466, 7 p. (2021).

Summary: This paper considers global optimization of a continuous nonconvex piecewise affine (PWA) function over a polytope. This type of optimization problem often arises in the context of control of continuous PWA systems. In literature, it has been shown that the given problem can be formulated as a mixed integer linear programming (MILP) problem, the worst-case complexity of which grows exponentially with the number of polyhedral subregions in the domain of the PWA function. In this paper, we propose a solution approach that is more efficient for continuous PWA functions with a large number of polyhedral subregions. The proposed approach is based on optimistic optimization, which uses hierarchical partitioning of the feasible set and which can guarantee bounds on the suboptimality of the returned solution with respect to the global optimum given a prespecified finite number of iterations. Since the function domain is a polytope with arbitrary shape, we introduce a partitioning approach by employing Delaunay triangulation and edgewise subdivision. Moreover, we derive the analytic expressions for the core parameters required by optimistic optimization for continuous PWA functions. The numerical example shows that the resulting algorithm is faster than MILP solvers for PWA functions with a large number of polyhedral subregions.

MSC:

90C26

Nonconvex programming, global optimization

Keywords:

piecewise affine function; optimistic optimization; simplicial subdivision

References:

[1]	Azuma, S.; Imura, J.; Sugie, T., Lebesgue piecewise affine approximation of nonlinear systems, Nonlinear Analysis. Hybrid Systems, 4, 1, 92-102 (2010) · Zbl 1179.93051
[2]	Bemporad, A.; Morari, M., Control of systems integrating logic, dynamics, and constraints, Automatica, 35, 3, 407-427 (1999) · Zbl 1049.93514
[3]	Bey, J., Simplicial grid refinement: On Freudenthal’s algorithm and the optimal number of congruence classes, Numerische Mathematik, 85, 1, 1-29 (2000) · Zbl 0949.65128
[4]	Borrelli, F., Constrained Optimal Control of Linear and Hybrid Systems (2003), Springer: Springer Berlin · Zbl 1030.49036
[5]	Breschi, V.; Piga, D.; Bemporad, A., Piecewise affine regression via recursive multiple least squares and multicategory discrimination, Automatica, 73, 155-162 (2016) · Zbl 1372.93221
[6]	Cheng, S.-W.; Dey, T. K.; Shewchuk, J. R., Delaunay Mesh Generation (2012), CRC Press
[7]	Croxton, K. L.; Gendron, B.; Magnanti, T. L., A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems, Management Science, 49, 9, 1268-1273 (2003) · Zbl 1232.90311
[8]	Croxton, K. L.; Gendron, B.; Magnanti, T. L., Models and methods for merge-in-transit operations, Transportation Science, 37, 1, 1-22 (2003)
[9]	Edelsbrunner, H.; Grayson, D. R., Edgewise subdivision of a simplex, Discrete & Computational Geometry, 24, 4, 707-719 (2000) · Zbl 0968.51016
[10]	Fujisawa, T.; Kuh, E. S., Piecewise-linear theory of nonlinear networks, SIAM Journal of Applied Mathematics, 22, 2, 307-328 (1972) · Zbl 0239.94033
[11]	Gonçalves, E. N.; Palhares, R. M.; Takahashi, R. H.C.; Mesquita, R. C., New approach to robust \(\mathcal{D} \)-stability analysis of linear time-invariant systems with polytope-bounded uncertainty, IEEE Transactions on Automatic Control, 51, 10, 1709-1714 (2006) · Zbl 1366.93462
[12]	Grill, J.-B.; Valko, M.; Munos, R., Black-box optimization of noisy functions with unknown smoothness, (Advances in Neural Information Processing Systems 28 (2015)), 667-675
[13]	Jones, D. R.; Perttunen, C. D.; Stuckman, B. E., Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 79, 1, 157-181 (1993) · Zbl 0796.49032
[14]	Munos, R. (2011). Optimistic optimization of a deterministic function without the knowledge of its smoothness. In 25th Annual Conference on Neural Information Processing Systems Granada, Spain: (pp. 783-791).
[15]	Munos, R., From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning, Foundations and Trends in Machine Learning, 7, 1, 1-130 (2014) · Zbl 1296.91086
[16]	Piga, D.; Bemporad, A.; Benavoli, A., Rao-Blackwellized sampling for batch and recursive Bayesian inference of Piecewise Affine models, Automatica, 117, Article 109002 pp. (2020) · Zbl 1442.93039
[17]	Preparata, F. P.; Shamos, M. I., Computational Geometry: An Introduction (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0759.68037
[18]	Rizk, N.; Martel, A.; Ramudhin, A., A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs, International Journal of Production Economics, 102, 2, 344-357 (2006)
[19]	Sridhar, S.; Linderoth, J.; Luedtke, J., Models and solution techniques for production planning problems with increasing byproducts, Journal of Global Optimization, 59, 2-3, 597-631 (2014) · Zbl 1301.90065
[20]	Valko, M., Carpentier, A., & Munos, R. Stochastic simultaneous optimistic optimization. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), Vol. 28 Atlanta, Georgia, USA: (pp. 19-27).
[21]	Vielma, J. P.; Ahmed, S.; Nemhauser, G., Mixed-integer models for nonseparable piecewise-linear optimization: Unifying framework and extensions, Operations Research, 58, 2, 303-315 (2010) · Zbl 1226.90046
[22]	Xu, J., van den Boom, T. J. J., Buşoniu, L., & De Schutter, B. (2016). Model predictive control for continuous piecewise affine systems using optimistic optimization. In 2016 American Control Conference Boston, Massachusetts: (pp. 4482-4487).
[23]	Xu, J.; van den Boom, T.; De Schutter, B., Optimistic optimization for model predictive control of max-plus linear systems, Automatica, 74, 16-22 (2016) · Zbl 1348.93192