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.

The objective of this paper is to provide a concise introduction to the max-plus algebra and to max-plus linear discrete-event systems. We present the basic concepts of the max-plus algebra and explain how it can be used to model a specific class of discrete-event systems with synchronization but no concurrency. Such systems are called max-plus linear discrete-event systems because they can be described by a model that is “linear” in the max-plus algebra. We discuss some key properties of the max-plus algebra and indicate how these properties can be used to analyze the behavior of max-plus linear discrete-event systems. Next, some control approaches for max-plus linear discrete-event systems, including residuation-based control and model predictive control, are presented briefly. Finally, we discuss some extensions of the max-plus algebra and of max-plus linear systems.

The topic of this paper is model predictive control (MPC) for max-plus linear systems with stochastic uncertainties the distribution of which is supposed to be known. We consider linear constraints on the inputs and the outputs. Due to the uncertainties, these linear constraints are formulated as probabilistic or chance constraints, i.e., the constraints are required to be satisfied with a predefined probability level. The proposed chance constraints can be equivalently rewritten into a max-affine (i.e., the maximum of affine terms) form if the linear constraints are monotonically nondecreasing as a function of the outputs. Based on the resulting max-affine form, two methods are developed for solving the chance-constrained MPC problem for stochastic max-plus linear systems. Method 1 uses Boole's inequality to convert the multivariate chance constraint into univariate chance constraints for which the probability can be computed more efficiently. Method 2 employs Chebyshev's inequality and transforms the chance constraint into linear constraints on the inputs. The simulation results for a production system example show that the two proposed methods are faster than the Monte Carlo simulation method and yield lower closed-loop costs than the nominal MPC method.

We consider the infinite-horizon optimal control of discrete-time, Lipschitz continuous piecewise affine systems with a single input. Stage costs are discounted, bounded, and use a 1 or ∞-norm. Rather than using the usual fixed-horizon approach from model-predictive control, we tailor an adaptive-horizon method called optimistic planning for continuous actions (OPC) to solve the piecewise affine control problem in receding horizon. The main advantage is the ability to solve problems requiring arbitrarily long horizons. Furthermore, we introduce a novel extension that provides guarantees on the closed-loop performance, by reusing data (“learning”) across different steps. This extension is general and works for a large class of nonlinear dynamics. In experiments with piecewise affine systems, OPC improves performance compared to a fixed-horizon approach, while the data-reuse approach yields further improvements.