Convexification by averages - Freitas, Iago Leal de (UFRJ, 2019)
[PT] Essa dissertação é dedicada ao estudo de funções de valor ótimo para pro- gramas estocásticos não convexos e como estas funções podem ser aproximadas por cortes exatos. São estudadas duas maneiras de se medir não convexidade: o gap entre uma função e sua relaxação convexa e a parte negativa da segunda derivada de uma função. Baseando-nos nas semelhanças destes dois operadores, introduzimos o conceito de medida de não convexidade. Estas tem a propriedade de sempre serem reduzidas pela operação de tomar médias. Diversos destes resul- tados também continuam valendo para o gap ao substituir-se a média por uma medida de risco coerente qualquer. Esses resultados são aplicados à aproximação de programas estocásticos multiestágio não convexos por cortes válidos ao consi- derarmos a diferença entre encontrar um corte médio através de uma formulação decomposta ou conjunta para os cenários.[EN] This dissertation is dedicated to the study of optimal value function for non- convex stochastic programs and how these functions can be approximated by tight cuts. Two ways to measure non-convexity are studied in this work: the gap between a function and its convex relaxation, and the negative part of a function’s second derivative. Influenced by the similarities between these two operators, we introduce the concept of a non-convexity measure. These have the property of being reduced by the operation of taking averages. Many of these results also hold for the gap when considering an arbitrary risk measure instead of the expected value. Theses results can be applied for approximating non-convex multi-stage stochastic programs by tighter cuts by considering the difference between calculating an average cut via a decomposed or a linked formulation for the scenarios.