On Algorithms for Nonlinear Minimax and Min-Max-Min Problems and Their Efficiency
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
This dissertation approaches the solution of optimization models with uncertain parameters by considering the worst-case value of the uncertain parameters during optimization. We consider three problems resulting from this approach a finite minimax problem FMX, a semi-infinite minimax problem SMX, and a semi-infinite min-max-min problem MXM. In all problems, we consider nonlinear functions with continuous variables. We find that smoothing algorithms for FMX may only have sublinear rates of convergence, but their complexity in the number of functions is competitive with other algorithms. We present two new smoothing algorithms with novel precision-adjustment schemes for FMX. For SMX algorithms, we present a novel way of expressing rate of convergence in terms of computational work instead of the typical number of iterations, and show how the new way allows for a fairer comparison of different algorithms. We propose a new approach to solve MXM, based on discretization and reformulation of MXM as a constrained finite minimax problem. Our approach is the first to solve MXM in the general case where the innermost feasible region depends on the variables in the outer problems. We conduct numerical studies for all three problems.
- Numerical Mathematics