| In this dissertation, we construct methods for solving challenging optimization problems. These methods result in simpler “surrogate” problems for which the solutions are obtained easily. In some cases these solutions can recover those of the original problem, while in others they provide good approximations. In particular, we propose two methodologies; the surrogate problem method for stochastic discrete optimization problems, and the hierarchical decomposition method for optimization problems of deterministic hybrid systems, namely systems where time-driven and event-driven dynamics interact. The first part of this dissertation discusses an on-line control method that constructs a surrogate continuous optimization problem from the actual discrete optimization problem. This method then solves the former using standard gradient-based approaches while simultaneously updating both actual and surrogate system states. It is shown that, under certain conditions, the solution of the original problem is recovered as an element of the discrete state neighborhood of the optimal surrogate state. Convergence of the proposed method is established under standard technical conditions and numerical results are included to illustrate the fast convergence properties of this approach. In the second part, we study optimization problems of deterministic hybrid systems consisting of a lower-level component with time-driven dynamics interacting with a higher-level component with event-driven dynamics. These typically arise in manufacturing environments where the lower-level component represents physical processes and the higher-level component represents events related to these processes. A common problem manufacturing organizations face is how to manufacture high quality products at low cost and within reasonable time. We formulate a deterministic optimization problem that captures this trade-off, which, under certain assumptions, can be decomposed into a set of simpler lower-level problems and a higher-level problem. We then present a hybrid controller that jointly optimizes the performance of both hierarchical components. The methods presented in this dissertation contribute towards the real-time optimization of complex systems, a task that was considered intractable until recently. |
