Nonconvex optimization problems arise in many applications such as nonlinear model predictive control and task assignment. For such problems, a local solution may not produce the required results. It is important that the optimization algorithms used to solve such problems have the ability to find a global solution as opposed to a local one. In this thesis, solving the nonlinear model predictive control problem is examined first. Second, the convergence of stochastic optimization methods is analyzed and the analysis is further used to enhance the existing methods.
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 the desired setpoints. Also, the solution must be available before the control input has to be applied to the process. In this thesis, 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. Case studies are used to show the algorithm performance in terms of tracking setpoints, cost, solution quality and convergence time.
Building on the global solution of the nonconvex NMPC problem using NPA, the general use of stochastic optimization algorithms such as genetic algorithm (GA), particle swarm optimization (PSO), estimation of distribution algorithms (EDAs), and nested partitions algorithm (NPA) to solve nonconvex optimization problems is analyzed. Some of these algorithms lack global convergence guarantee such as PSO, or require strict convergence assumptions such as NPA. To enhance these methods in terms of convergence, a novel framework towards unifying the seemingly unrelated methods is established as iterative sampling and updating of a population distribution, and the methods that fit into this framework are called population distribution-based methods. Global convergence conditions for this framework is innovatively developed by building a shadow NPA structure for the population evolution process. The result is generic and is capable of analyzing convergence of many methods including GA, PSO, EDA, and NPA. It is shown that it can be further exploited to modify and improve convergence of these methods. The existing and modified variants of these methods are then applied to the nonlinear model predictive control and task assignment problems.
