Outer-approximation algorithms for nonsmooth convex MINLP problems with chance constraints
| Autor: | Delfino, Adriano Rodrigo, 1984 |
|---|---|
| Přispěvatelé: | Oliveira, Welington Luis de, Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Matemática, Yuan Jin-Yun |
| Jazyk: | portugalština |
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | Repositório Institucional da UFPR Universidade Federal do Paraná (UFPR) instacron:UFPR |
| Popis: | Orientador: Prof. Dr. Yuan Jin Yun Coorientador: Prof. Dr. Welington Luis de Oliveira Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa : Curitiba, 13/04/2018 Inclui referências: p.82-88 Resumo: As restri?c˜oes de probabilidade desempenham um papel fundamental nos problemas de otimiza?c˜ao envolvendo incertezas. Essas restri?c˜oes exigem que um sistema de desigualdade dependendo de um vetor aleat'orio tenha que ser satisfeito com uma probabilidade suficientemente alta. Neste trabalho, lidamos com problemas de otimiza?c˜ao com restri?c˜oes de probabilidades envolvendo vari'aveis inteiras. Assumimos que as fun?c˜oes envolvidas s˜ao convexas e a restri?c˜ao de probabilidade tenha propriedade generalizada de convexidade. Para lidar com problemas de otimiza?c˜ao desse tipo, combinamos o algoritmo de aproxima ?c˜ao externa (OA) e o algoritmo de feixes. Os algoritmos OA tem sido aplicado para problemas su'aveis e para uma pequena classe limitada de problemas n˜ao-su'aveis. Neste trabalho, estendemos o algoritmo OA para lidar com problemas mais gerais n˜ao-su'aveis. Al'em disso, mostramos que quando os subproblemas n˜ao-lineares resultantes do algoritmo OA s˜ao resolvidos por um m'etodo de feixes, ent˜ao os subgradientes que satisfazem as condi?c˜oes de Karush Kuhn Tucker (KKT) est˜ao prontamente dispon'?veis independentemente da estrutura das fun?c˜oes convexas n˜ao-su'aveis. Esta propriedade 'e crucial para provar a convergˆencia (finita) do algoritmo OA. Problemas com restri?c˜oes probabil'?sticas aparecem, por exemplo, em modelos de energia (estoc'asticos). No contexto de interesse, pelo menos uma das restri?c˜oes n˜ao lineares envolve uma fun?c˜ao de probabilidade P[h(x, y) ? ?], onde h 'e uma fun?c˜ao cˆoncava e ? ? Rm 'e um vetor aleat'orio. Em geral, uma integra?c˜ao num'erica multidimensional 'e empregada para avaliar essa fun?c˜ao de probabilidade. Como uma alternativa para lidar com restri?c˜oes de probabilidades (que 'e muito cara computacionalmente), propomos a aproxima?c˜ao da medida de probabilidade P por uma c'opula apropriada. N'os investigamos uma fam'?lia de c'opulas n˜ao-su'aveis e fornecemos algumas propriedades generalizadas de convexidade novas e 'uteis. Em particular, provamos que a fam'?lia de c'opulas de Zhang 'e ??cˆoncava para todo ? ? 0. Esse resultado nos permite aproximar as restri?c˜oes probabil'?sticas por restri?c˜oes muito mais simples envolvendo c'opulas. Avaliamos numericamente as abordagens dadas em duas classe de problemas provenientes do gerenciamento do sistema de energia el'etrica. Palavras-chave: Otimiza¸c˜ao n˜ao-linear inteira, Otimiza¸c˜ao Estoc'astica, Restri¸c˜oes Probabil '?sticas. Abstract: Probability constraints play a key role in optimization problems involving uncertainties. These constraints (also known as chance constraints) require that an inequality system depending on a random vector has to be satisfied with high enough probability. In this work we deal with chance-constrained optimization problems having mixed-integer variables. We assume that the involved functions are convex and the probability constraint has generalized convexity properties. In order to deal with optimization problems of this type, we combine outer-approximation (OA) and bundle method algorithms. OA algorithms have been applied to smooth problems and to a small class of nonsmooth problems. In this work we extend the OA to handle more general nonsmooth problems. Moreover, we show that when the resulting OA's nonlinear subproblems are solved by a bundle method, then subgradients satisfying the Karush-Kuhn-Tucker (KKT) conditions are readily available regardless the structure of the nonsmooth convex functions. This property is crucial for proving (finite) convergence of the OA algorithm. Chance-constrained problems appear, for instance, in (stochastic) energy models. In the context of interest, at least one nonlinear constraint models the probability function P[h(x, y) ? ?], where h is a concave map and ? ? Rm is a random vector. In general, multidimensional numerical integration is employed to evaluate this probability function. As an alternative to deal with probability constraints (which is very expensive computationally), we propose approximating the probability measure P with a suitable copula. We investigate a family of nonsmooth copulae and provide some new and useful generalized convexity properties. In particular, we prove that Zhang's copulae are ?-concave for all ? ? 0. This result allows us to approximate chance-constrained programs by much simpler copula-constrained ones. We assess numerically the given approaches on two classes of problems coming from power system management. Keywords: Mixed-Integer Nonlinear Optimization, Stochastic Optimization, Chance constraints. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|