Paper Info
Title
Optimistic optimization for continuous nonconvex piecewise affine functions
Abstract
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.
Year
DOI
Venue
2021
10.1016/j.automatica.2020.109476
Automatica
Keywords
DocType
Volume
Piecewise affine function,Optimistic optimization,Simplicial subdivision
Journal
125
Issue
ISSN
Citations 
1
0005-1098
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Jia Xu129836.94
Ton J. J. van den Boom210320.98
Hans Hellendoorn31673220.44