Reference
J. Xu, T. van den Boom, and B. De Schutter, "Optimistic optimization for
continuous nonconvex piecewise affine functions,"
Automatica, Mar. 2021. Article 109476.
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.
Publisher page
Downloads
BibTeX
@article{Xuvan:15-030,
author = {Xu, Jia and van den Boom, Ton and De Schutter, Bart},
title = {Optimistic Optimization for Continuous Nonconvex Piecewise Affine
Functions},
journal = {Automatica},
month = mar,
year = {2021},
note = {Article 109476}
}