Nested partitions for global optimization in nonlinear model predictive control

In Nonlinear Model Predictive Control (NMPC), the optimization problem may be nonconvex. It is important to find a global solution since a local solution may not be able to operate the process at desired setpoints. Also the solution must be available before the control input has to be applied to the process. In this paper, a stochastic algorithm called the Nested Partitions Algorithm (NPA) is used for global optimization. The NPA divides the search space into smaller regions and either concentrates search in one of these regions called the most promising region or backtracks to a larger region in the search space based on a performance index. To adapt the NPA to solve dynamic NMPC with continuous variables, a new partitioning scheme is developed that focuses on the first few control moves in the control horizon. The expected number of iterations taken by the NPA is presented. Convergence speed is improved by reducing the size of the starting most promising region based on a good starting point. The discrete sampling nature of the NPA may cause difficulty in finding the global solution in a continuous space. A gradient-based search is used with the NPA to overcome this difficulty. The solution quality is assessed in terms of the error from the actual global minimum. The algorithm is shown to give a feasible solution that provides asymptotic stability. Case studies are used to show the algorithm performance in terms of tracking setpoints, cost, solution quality and convergence time.