J. Xu, T. van den Boom, and B. De Schutter, "Optimistic optimization for continuous nonconvex piecewise affine functions," Automatica, 2017. To appear.
This paper considers the global optimization problem 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 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 founded on optimistic optimization, which is based on hierarchical partitioning of the feasible set and which focuses on the most promising region when searching for the global optimum. The advantage of optimistic optimization is that one can guarantee bounds on the suboptimality with respect to the global optimum given a finite computational budget (e.g. the number of iterations). In particular, the gap between the best value returned by the proposed algorithm and the real optimum can be made arbitrarily small as the computational budget increases. We derive the analytic expressions for the core parameters required by optimistic optimization for continuous PWA functions. The efficiency of the resulting algorithm is illustrated with numerical examples.