UC Santa Barbara

Minmax optimization is a powerful framework to model optimization problems for which there is uncertainty with respect to some parameters. In this dissertation we look at new applications of minmax optimization and at new algorithms to solve theoptimizations.

The new applications revolve around a connection we have developed between minmax optimization and the problem of minimizing an expected value with stochastic constraints, known in the literature as stochastic programming. Our approach is based on obtaining sub-optimal solutions to the stochastic program by optimizing bounds for the expected value that are obtained by solving a deterministic minmax optimization problem that uses the probability density function to penalize unlikely values for the random variables. We illustrate this approach in the context of three applications: finite horizon optimal stochastic control, with state or output feedback; parameter estimation with latent variables; and nonlinear Bayesian experiment design.

As for new algorithms, they are aimed at addressing the problem of finding a local solution to a nonconvex-nonconcave minmax optimization. We propose two main algorithms. The first category of algorithms are modified Newton methods for unconstrained and constrained minmax optimization. Our main contribution is to modify the Hessian matrix of these methods such that, at each step, the modified Newton update direction can be seen as the solution to a quadratic program that locally approximates the minmax problem. Moreover, we show that by selecting the modification in an appropriate way, the only stable points of the algorithm’s iterations are local minmax points. The second category of algorithms are a variation of the learning with opponent learning awareness (LOLA) method, which we call Full LOLA. The rationale of (Full) LOLA is to construct algorithms such that the minimizer and maximizer choose their update direction taking into account the response of their adversary to their choice. The relation between our method and LOLA is that the latter can be seen as a first order linearization of the Full LOLA. We show that it is possible to establish asymptotic convergence results for our method both using fix step length and a variation of the Armijo rule.