Defesa de Tese.

Banca examinadora: Mikhail Solodov - Advisor - IMPA Claudia Sagastizabal - Co-Orientadora - UNICAMP Alfredo Iusem - IMPA Leo Liberti - École Polytechnique, France Sandra Santos - MECC INICAMP Juan Pablo Luna - UFRJ/COPPE

Abstract: Hierarchical optimization problems are those whose feasible sets and/or objective function involve solution map-pings and/or value functions of other optimization problems. Such problems appear naturally when one is mod-eling games or defining decomposition algorithms for non-convex large-scale optimization. Hierarchical problems have peculiar features that make them hard to solve with classical optimization because assumptions that are usually employed in the convergence analysis of algorithms are not satisfied in the hierarchical setting. For instance, neither convexity nor standard constraint qualification conditions can be relied upon. Also, smoothness of problem data cannot be assumed because value functions or solution mappings are not smooth for most of the cases of interest. Moreover, in general there are no explicit formulas for value functions or solution mappings, which makes the calculation of generalized derivatives harder or impossible with current results available in the literature. An essential question that arises when trying to deal with hierarchical problems is the one of computing variations for value functions and solutions mappings in such a way that these variations can be put into an algorithmic pattern that actually solves the problem in practice. Given that high-quality and reliable optimization software is hard to develop, it would be better if we could solve these hierarchical problems as limits of classical problems or by extensions of classical techniques to leverage on existing high-quality classical methods. The first part of this thesis approximates some hierarchical problems as limits of classical problems via a smoothing technique, which is applied for the solution of non-convex two-stage stochastic programs and for decomposing a class of stochastic equilibrium problems. The smoothing method is analyzed theoretically and compared numerically against state-of-the-art techniques. The second part proposes an extension of the classical Benders cuts, termed free floating cuts, that are used to compute variations for value functions of multistage stochastic optimization problems. Such floating cuts are employed to evaluate efficiently the sensitivity of these multistage stochastic programs with respect to right-hand side uncertainty and with respect to the decisions of other players in a multistage stochastic game. The corresponding cuts are employed in a sequential sampling procedure and in a best-response algorithm for the stochastic game. Moreover, a solution technique for a deterministic trilevel game motivating the stochastic game is developed. The approaches are satisfactorily applied to the management of a cascade of water reservoirs used to produce electricity .