Esta dissertação busca aproveitar os métodos de penalidades exatas diferenciáveis de programação não-linear para resolver problemas de desigualdades variacionais. Problemas desse tipo têm recebido grande atenção na literatura recentemente e possuem aplicações em diversas áreas como Engenharia, Física e Economia. Métodos de penalidades exatas diferenciáveis foram desenvolvidos nos anos 70 e 80 para resolver problemas de otimização com restrições por meio da solução de problemas irrestritos. Esses problemas são tais que, com uma escolha apropriada do parâmetro de penalização, uma solução do problema original é recuperada após a resolução de um único problema irrestrito. A função a ser minimizada é semelhante a um lagrangiano aumentado clássico, porém uma estimativa do multiplicador é automaticamente calculada a partir do ponto primal. Nesse trabalho, mostramos como acoplar a estimativa de multiplicadores sugerida por Glad e Polak [27] ao lagrangiano aumentado clássico para desigualdades variacionais sugerido por Auslender e Teboulle. Obtivemos assim uma penalidade exata para problemas de desigualdades variacionais. Os resultados mais finos de exatidão foram obtidos no caso de problemas de complementaridade não-linear. Uma característica importante da penalidade proposta é que ela não envolve informações de segunda ordem das funções que definem a desigualdade variacional. Além desses resultados, que formam o núcleo da dissertação, apresentamos uma breve revisão de penalidades não-exatas diferenciáveis , exatas não-diferenciáveis e exatas diferenciáveis em otimização. / This work intends to build upon differentiable exact penalty methods for nonlinear programming, using them to solve variational inequality problems. Such problems have been given a lot of attention in the literature lately and have applications to diverse areas of knowledge such as Engineering, Physics and Economics. Differentiable exact penalty methods were developed during the 70s and 80s to solve constrained optimization problems by means of the solution of unconstrained problems. Those problems are such that, with an appropriate choice of the penalty parameter, one finds a solution of the original constrained problem by solving only one unconstrained problem. The function which is minimized is similar to the classic augmented lagrangian, but an estimate of the multiplier is automatically calculated from the primal point. In this thesis we show how to couple Glad and Polak?s multiplier estimate, with the classic augmented lagrangian of a variational inequality developed by Auslender and Teboulle. This allowed us to obtain an exact penalty function for variational inequality problems. The best exactness results were obtained in the particular case of nonlinear complementarity problems. An important characteristic of the proposed penalty is that it doesn?t involve second order information of any of the functions which compose the variational inequality. In addition to those results, which are the core of this work, we also present a brief review of inexact differentiable penalties, exact nondifferentiable penalties and differentiable exact penalties in optimization.

Esta dissertação busca aproveitar os métodos de penalidades exatas diferenciáveis de programação não-linear para resolver problemas de desigualdades variacionais. Problemas desse tipo têm recebido grande atenção na literatura recentemente e possuem aplicações em diversas áreas como Engenharia, Física e Economia. Métodos de penalidades exatas diferenciáveis foram desenvolvidos nos anos 70 e 80 para resolver problemas de otimização com restrições por meio da solução de problemas irrestritos. Esses problemas são tais que, com uma escolha apropriada do parâmetro de penalização, uma solução do problema original é recuperada após a resolução de um único problema irrestrito. A função a ser minimizada é semelhante a um lagrangiano aumentado clássico, porém uma estimativa do multiplicador é automaticamente calculada a partir do ponto primal. Nesse trabalho, mostramos como acoplar a estimativa de multiplicadores sugerida por Glad e Polak [27] ao lagrangiano aumentado clássico para desigualdades variacionais sugerido por Auslender e Teboulle. Obtivemos assim uma penalidade exata para problemas de desigualdades variacionais. Os resultados mais finos de exatidão foram obtidos no caso de problemas de complementaridade não-linear. Uma característica importante da penalidade proposta é que ela não envolve informações de segunda ordem das funções que definem a desigualdade variacional. Além desses resultados, que formam o núcleo da dissertação, apresentamos uma breve revisão de penalidades não-exatas diferenciáveis , exatas não-diferenciáveis e exatas diferenciáveis em otimização. / This work intends to build upon differentiable exact penalty methods for nonlinear programming, using them to solve variational inequality problems. Such problems have been given a lot of attention in the literature lately and have applications to diverse areas of knowledge such as Engineering, Physics and Economics. Differentiable exact penalty methods were developed during the 70s and 80s to solve constrained optimization problems by means of the solution of unconstrained problems. Those problems are such that, with an appropriate choice of the penalty parameter, one finds a solution of the original constrained problem by solving only one unconstrained problem. The function which is minimized is similar to the classic augmented lagrangian, but an estimate of the multiplier is automatically calculated from the primal point. In this thesis we show how to couple Glad and Polak?s multiplier estimate, with the classic augmented lagrangian of a variational inequality developed by Auslender and Teboulle. This allowed us to obtain an exact penalty function for variational inequality problems. The best exactness results were obtained in the particular case of nonlinear complementarity problems. An important characteristic of the proposed penalty is that it doesn?t involve second order information of any of the functions which compose the variational inequality. In addition to those results, which are the core of this work, we also present a brief review of inexact differentiable penalties, exact nondifferentiable penalties and differentiable exact penalties in optimization.

Esta tese é um estudo acerca da análise de convergência de vários métodos numéricos de primeira e de segunda ordem para resolver problemas de programação matemática e as condições de otimalidade associadas. Nossas principais ferramentas são as condições sequenciais de otimalidade. As condições sequenciais de otimalidade oferecem um quadro teórico para a análise de convergência para várias famílias de métodos de primeira ordem sob condições de qualificações fracas. Nesta tese, apresentamos, para cada condição sequencial de otimalidade, a condição de qualificação mínima associada e mostramos as relações com outras condições de qualificação conhecidas. Este fato tem implicações práticas, uma vez que enfraquece as hipóteses requeridas para a convergência de vários métodos numéricos cujos critérios de paradas estão associados às condições sequenciais de otimalidade. Ainda mais, esse tipo de resultado não pode ser melhorado usando outras condições de qualificações. Nós estendemos a noção de condições sequenciais de otimalidade de primeira ordem, para incorporar informações de segunda ordem. Apresentamos, segundo nosso conhecimento, a primeira condição sequencial de otimalidade de segunda ordem, adequada para a análise de convergência de vários métodos numéricos com convergência a pontos estacionários de segunda ordem, como por exemplo métodos baseados no Lagrangeano aumentado, regiões de confiança e SQP regularizado. Associada com a nova condição sequencial de segunda ordem, temos uma nova condição de qualificação, mais fraca que as outras condições de qualificações utilizadas para a análise de convergência para métodos numéricos de segunda ordem. Nós situamos essa nova condição de qualificação com respeito a outras condições de qualificação usadas em análise de convergência. Finalmente apresentamos outra razão pela qual a condição fraca necessária de segunda ordem é a condição de segunda ordem adequada quando lidarmos com a convergência de algoritmos práticos / This thesis deals with the convergence analysis for several rst-and-second-order numerical methods used to solve mathematical programming problems. Our main tools are the sequential optimality conditions. First-order sequential optimality conditions oer a framework to the study of the convergence analysis of several families of rst-order methods, under weak constraint qualications. In this thesis, we will introduce, for each sequential optimality condition the minimal constraint qualications associated with it and we will show their relationships with other constraint qualications. This fact has a practical aspect, since, we improve the convergence analysis of practical methods with stopping criteria associated with sequential optimality conditions. This results can not be improved by using another weak constraint qualications. We will extend the notion of rst-order sequential optimality conditions to incorporate secondorder information. We will introduce, to the best of our knowledge, the rst second-order sequential optimality condition, suitable to the study of the convergence analysis of several second-order methods including methods based on the augmented lagrangian, trust-region and regularized SQP. Associated with the second-order sequential optimality condition, we have a new constraint qualication weaker than all constraint qualications used for the convergence analysis of second-order methods. We show the relationships of this new constraint qualications with other constraint qualications used for algorithmic purposes. We will also present a new reason why the weak secondorder necessary condition is the natural second-order condition when we are dealing with practical numerical methods

Esta tese é um estudo acerca da análise de convergência de vários métodos numéricos de primeira e de segunda ordem para resolver problemas de programação matemática e as condições de otimalidade associadas. Nossas principais ferramentas são as condições sequenciais de otimalidade. As condições sequenciais de otimalidade oferecem um quadro teórico para a análise de convergência para várias famílias de métodos de primeira ordem sob condições de qualificações fracas. Nesta tese, apresentamos, para cada condição sequencial de otimalidade, a condição de qualificação mínima associada e mostramos as relações com outras condições de qualificação conhecidas. Este fato tem implicações práticas, uma vez que enfraquece as hipóteses requeridas para a convergência de vários métodos numéricos cujos critérios de paradas estão associados às condições sequenciais de otimalidade. Ainda mais, esse tipo de resultado não pode ser melhorado usando outras condições de qualificações. Nós estendemos a noção de condições sequenciais de otimalidade de primeira ordem, para incorporar informações de segunda ordem. Apresentamos, segundo nosso conhecimento, a primeira condição sequencial de otimalidade de segunda ordem, adequada para a análise de convergência de vários métodos numéricos com convergência a pontos estacionários de segunda ordem, como por exemplo métodos baseados no Lagrangeano aumentado, regiões de confiança e SQP regularizado. Associada com a nova condição sequencial de segunda ordem, temos uma nova condição de qualificação, mais fraca que as outras condições de qualificações utilizadas para a análise de convergência para métodos numéricos de segunda ordem. Nós situamos essa nova condição de qualificação com respeito a outras condições de qualificação usadas em análise de convergência. Finalmente apresentamos outra razão pela qual a condição fraca necessária de segunda ordem é a condição de segunda ordem adequada quando lidarmos com a convergência de algoritmos práticos / This thesis deals with the convergence analysis for several rst-and-second-order numerical methods used to solve mathematical programming problems. Our main tools are the sequential optimality conditions. First-order sequential optimality conditions oer a framework to the study of the convergence analysis of several families of rst-order methods, under weak constraint qualications. In this thesis, we will introduce, for each sequential optimality condition the minimal constraint qualications associated with it and we will show their relationships with other constraint qualications. This fact has a practical aspect, since, we improve the convergence analysis of practical methods with stopping criteria associated with sequential optimality conditions. This results can not be improved by using another weak constraint qualications. We will extend the notion of rst-order sequential optimality conditions to incorporate secondorder information. We will introduce, to the best of our knowledge, the rst second-order sequential optimality condition, suitable to the study of the convergence analysis of several second-order methods including methods based on the augmented lagrangian, trust-region and regularized SQP. Associated with the second-order sequential optimality condition, we have a new constraint qualication weaker than all constraint qualications used for the convergence analysis of second-order methods. We show the relationships of this new constraint qualications with other constraint qualications used for algorithmic purposes. We will also present a new reason why the weak secondorder necessary condition is the natural second-order condition when we are dealing with practical numerical methods

Durante as décadas de 70 e 80, desenvolveram-se métodos baseados em penalidades exatas diferenciáveis para resolver problemas de otimização não linear com restrições. Uma desvantagem dessas penalidades é que seus gradientes contêm termos de segunda ordem em suas fórmulas, o que impede a utilização de métodos do tipo Newton para resolver o problema. Para contornar essa dificuldade, utilizamos uma ideia de construção de penalidade exata para desigualdades variacionais, introduzida recentemente por André e Silva. Essa construção consiste em incorporar um estimador de multiplicadores, proposto por Glad e Polak, no lagrangiano aumentado para desigualdades variacionais. Nesse trabalho, estendemos o estimador de multiplicadores para restrições gerais de igualdade e desigualdade, e enfraquecemos a hipótese de regularidade. Como resultado, obtemos uma função penalidade exata continuamente diferenciável e uma nova reformulação do sistema KKT associado a problemas não lineares. A estrutura dessa reformulação permite a utilização do método de Newton semi-suave, e a taxa de convergência local superlinear pode ser provada. Além disso, verificamos que a penalidade exata construída pode ser usada para globalizar o método, levando a uma abordagem do tipo Gauss-Newton. Por fim, realizamos experimentos numéricos baseando-se na coleção CUTE de problemas de teste. / During the 1970\'s and 1980\'s, methods based on differentiable exact penalty functions were developed to solve constrained optimization problems. One drawback of these functions is that they contain second-order terms in their gradient\'s formula, which do not allow the use of Newton-type methods. To overcome such difficulty, we use an idea for construction of exact penalties for variational inequalities, introduced recently by André and Silva. This construction consists on incorporating a multipliers estimate, proposed by Glad and Polak, in the augmented Lagrangian function for variational inequalities. In this work, we extend the multipliers estimate to deal with both equality and inequality constraints and we weaken the regularity assumption. As a result, we obtain a continuous differentiable exact penalty function and a new equation reformulation of the KKT system associated to nonlinear problems. The formula of such reformulation allows the use of semismooth Newton method, and the local superlinear convergence rate can be also proved. Besides, we note that the exact penalty function can be used to globalize the method, resulting in a Gauss-Newton-type approach. We conclude with some numerical experiments using the collection of test problems CUTE.

Em um problema de natureza hierárquica, o nível mais influente toma certas decisões que afetam o comportamento dos níveis inferiores. Cada decisão do nível mais influente é considerada como fixa pelos níveis inferiores, que, com tais informações, tomam decisões que maximizam seus objetivos. Essas decisões podem influenciar os resultados obtidos pelo nível superior, que, por sua vez, também anseia pela decisão ótima. Em programação matemática, este problema é modelado como um problema de programação em níveis. Neste trabalho, consideramos uma classe particular de problemas de programação em níveis: os problemas de programação matemática em dois níveis. Estudamos uma técnica de resolução que consiste em substituir o problema do nível inferior por suas condições necessárias de primeira ordem, que podem ser formuladas de diversas maneiras, conforme as restrições de complementaridade são modificadas. O novo problema torna-se um problema de programação não linear e pode ser resolvido com algoritmos clássicos de otimização. Com o auxílio de condições de otimalidade de primeira e segunda ordem mostramos as relações entre o problema original e o problema reformulado. Aplicamos a técnica a problemas encontrados na literatura, analisamos o seu comportamento e apresentamos estratégias para eliminar certos inconvenientes encontrados. / In problems of hierarchical nature, the choices made by the most influential level - the so-called leader - affect the behavior of the lower levels. For each one of the leader\'s decisions there is a response from the lower levels, which maximizes the value of their respective objectives. These optimal choices, in return, may have influence in the results achieved by the leader, which also wants to make the optimal choices. In mathematical programming, this kind of problem is described as a multilevel programming problem. The present work considers a specific kind of multilevel problem: the bilevel mathematical problem. We study a resolution technique which consists in replacing the lower level problem by its necessary first order conditions, which can be formulated in various ways, as complementarity constraints occur and are modified. The new reformulated problem is a nonlinear programming problem which can be solved by classical optimization methods. Using first and second order optimality conditions, we show the relations between the original bilevel problem and the reformulated problem. We apply the described technique to solve a set of bilevel problems taken from the literature, analyse their behavior and discuss strategies to prevent undesirable difficulties that may arise.

The presented thesis discusses bilevel programming problems with the focus on solution algorithms. Bilevel programming problem is a hierarchical programming problem, where constraints contain another programming problem. We formulate basic bilevel optimization theory and describe three types of so- lution algorithms for bilevel programming problems: Algorithms based on KKT reformulation where the lower level is replaced by its KKT conditions, algorithms based on optimal value function where the bilevel programming problem is re- duced to a single level problem using the optimal value function of the lower level problem, and algorithms solving linear bilevel programming problems. Using real data for portfolio optimization bilevel programming problems, we compare ability to solve the problems and computing time of some of the pre- sented algorithms. 1

Durante as décadas de 70 e 80, desenvolveram-se métodos baseados em penalidades exatas diferenciáveis para resolver problemas de otimização não linear com restrições. Uma desvantagem dessas penalidades é que seus gradientes contêm termos de segunda ordem em suas fórmulas, o que impede a utilização de métodos do tipo Newton para resolver o problema. Para contornar essa dificuldade, utilizamos uma ideia de construção de penalidade exata para desigualdades variacionais, introduzida recentemente por André e Silva. Essa construção consiste em incorporar um estimador de multiplicadores, proposto por Glad e Polak, no lagrangiano aumentado para desigualdades variacionais. Nesse trabalho, estendemos o estimador de multiplicadores para restrições gerais de igualdade e desigualdade, e enfraquecemos a hipótese de regularidade. Como resultado, obtemos uma função penalidade exata continuamente diferenciável e uma nova reformulação do sistema KKT associado a problemas não lineares. A estrutura dessa reformulação permite a utilização do método de Newton semi-suave, e a taxa de convergência local superlinear pode ser provada. Além disso, verificamos que a penalidade exata construída pode ser usada para globalizar o método, levando a uma abordagem do tipo Gauss-Newton. Por fim, realizamos experimentos numéricos baseando-se na coleção CUTE de problemas de teste. / During the 1970\'s and 1980\'s, methods based on differentiable exact penalty functions were developed to solve constrained optimization problems. One drawback of these functions is that they contain second-order terms in their gradient\'s formula, which do not allow the use of Newton-type methods. To overcome such difficulty, we use an idea for construction of exact penalties for variational inequalities, introduced recently by André and Silva. This construction consists on incorporating a multipliers estimate, proposed by Glad and Polak, in the augmented Lagrangian function for variational inequalities. In this work, we extend the multipliers estimate to deal with both equality and inequality constraints and we weaken the regularity assumption. As a result, we obtain a continuous differentiable exact penalty function and a new equation reformulation of the KKT system associated to nonlinear problems. The formula of such reformulation allows the use of semismooth Newton method, and the local superlinear convergence rate can be also proved. Besides, we note that the exact penalty function can be used to globalize the method, resulting in a Gauss-Newton-type approach. We conclude with some numerical experiments using the collection of test problems CUTE.

Em um problema de natureza hierárquica, o nível mais influente toma certas decisões que afetam o comportamento dos níveis inferiores. Cada decisão do nível mais influente é considerada como fixa pelos níveis inferiores, que, com tais informações, tomam decisões que maximizam seus objetivos. Essas decisões podem influenciar os resultados obtidos pelo nível superior, que, por sua vez, também anseia pela decisão ótima. Em programação matemática, este problema é modelado como um problema de programação em níveis. Neste trabalho, consideramos uma classe particular de problemas de programação em níveis: os problemas de programação matemática em dois níveis. Estudamos uma técnica de resolução que consiste em substituir o problema do nível inferior por suas condições necessárias de primeira ordem, que podem ser formuladas de diversas maneiras, conforme as restrições de complementaridade são modificadas. O novo problema torna-se um problema de programação não linear e pode ser resolvido com algoritmos clássicos de otimização. Com o auxílio de condições de otimalidade de primeira e segunda ordem mostramos as relações entre o problema original e o problema reformulado. Aplicamos a técnica a problemas encontrados na literatura, analisamos o seu comportamento e apresentamos estratégias para eliminar certos inconvenientes encontrados. / In problems of hierarchical nature, the choices made by the most influential level - the so-called leader - affect the behavior of the lower levels. For each one of the leader\'s decisions there is a response from the lower levels, which maximizes the value of their respective objectives. These optimal choices, in return, may have influence in the results achieved by the leader, which also wants to make the optimal choices. In mathematical programming, this kind of problem is described as a multilevel programming problem. The present work considers a specific kind of multilevel problem: the bilevel mathematical problem. We study a resolution technique which consists in replacing the lower level problem by its necessary first order conditions, which can be formulated in various ways, as complementarity constraints occur and are modified. The new reformulated problem is a nonlinear programming problem which can be solved by classical optimization methods. Using first and second order optimality conditions, we show the relations between the original bilevel problem and the reformulated problem. We apply the described technique to solve a set of bilevel problems taken from the literature, analyse their behavior and discuss strategies to prevent undesirable difficulties that may arise.

In conventional wireless channel models, there is no control on the gains of different subchannels. In such channels, the transmitted signal undergoes attenuation and phase shift and is subject to multi-path propagation effects. We herein refer to such channels as passive channels. In this dissertation, we study the problem of joint power allocation and channel design for a parallel channel which conveys information from a source to a destination through multiple orthogonal subchannels. In such a link, the power over each subchannel can be adjusted not only at the source but also at each subchannel. We refer to this link as an active parallel channel. For such a channel, we study the problem of sum-rate maximization under the assumption that the source power as well as the energy of the active channel are constrained. This problem is investigated for equal and unequal noise power at different subchannels. For equal noise power over different subchannels, although the sum-rate maximization problem is not convex, we propose a closed-form solution to this maximization problem. An interesting aspect of this solution is that it requires only a subset of the subchannels to be active and the remaining subchannels should be switched off. This is in contrast with passive parallel channels with equal subchannel signal-tonoise- ratios (SNRs), where water-filling solution to the sum-rate maximization under a total source power constraint leads to an equal power allocation among all subchannels. Furthermore, we prove that the number of active channels depends on the product of the source and channel powers. We also prove that if the total power available to the source and to the channel is limited, then in order to maximize the sum-rate via optimal power allocation to the source and to the active channel, half viii ix of the total available power should be allocated to the source and the remaining half should be allocated to the active channel. We extend our analysis to the case where the noise powers are unequal over different subchannels. we show that the sum-rate maximization problem is not convex. Nevertheless, with the aid of Karush-Kuhn-Tucker (KKT) conditions, we propose a computationally efficient algorithm for optimal source and channel power allocation. To this end, first, we obtain the feasible number of active subchannels. Then, we show that the optimal solution can be obtained by comparing a finite number of points in the feasible set and by choosing the best point which yields the best sum-rate performance. The worst-case computational complexity of this solution is linear in terms of number of subchannels. / UOIT