On algorithms for nonlinear minimax and min-max-min problems and their efficiency

Abstract

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 minmax-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.