No description available.

No description available.

No description available.

Orientador: Luiz Carlos Matioli / Dissertaçao (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia. Defesa: Curitiba, 2004 / Inclui bibliografia / Área de concentraçao: Programaçao matemática / Resumo: Neste trabalho, serão utilizadas duas metodologias para construção de funções de penalização para algoritmos de Lagrangeano Aumentado, aplicados a problemas de programação convexa comrestrições. Métodos de Lagrangeano Aumentado partem normalmente de funções de penalização ? : R ? R, estritamente convexas e crescentes, que são combinadas com multiplicadores de Lagrange para compor termos de penalização com os formatos: (y, ?) ? R×R++ 7?? p(y, u) = ??(y) e (y, ?) ? R×R++ 7?? p(y, u) = ?(?y). Propõe-se uma função de penalização ? a ser usada no algoritmo de Lagrangeano Aumentado, definida por y ? R 7?? ?(y) = 1 2 y2 + y, sendo ? estritamente convexa, porém nãocrescente em todo o seu domínio. Neste caso, em que as penalidades são quadráticas, os multiplicadores gerados pelo algoritmo de Lagrangeano Aumentado podem ser negativos, pois a derivada da função não é crescente em todo o seu domínio. Este problema é contornado aumentando-se o parâmetro de penalidade, conforme relações mostradas no Capítulo 2, entre os métodos de Ponto Proximal e Região de Confiança. Implementam-se os algoritmos de Lagrangeano Aumentado para problemas com restrições de desigualdades, utilizando duas metodologias para construção das funções de penalidades quadrática e m2b. Os resultados numéricos obtidos em Matlab ilustram a eficiência da penalidade quadrática. / Abstract: In this work, two methodologies are used for constructing penalization functions of Augmented Lagrangian algorithms, solving convex programming problems with constraints. Augmented Lagrangian methods are usually built from strictly convex and increasing penalization functions ? : R ? R, combined with Lagrange multipliers ? to compose penalization terms: (y, ?) ? R × R++ 7?? p(y, u) = ??(y) and (y, ?) ? R × R++ 7?? p(y, u) = ?(?y). The penalization function ?, defined by y ? R 7?? ?(y) = 1 2 y2 + y, is ? strictly convex, but non-increasing in all its domain. In this case, the multipliers generated by the Augmented Lagrangian algorithm can be negative. Therefore the derivative of the function is not increasing in all its domain. This problem has been turned around by increasing the penalty parameter, according to relations shown in chapter 2, between the Proximal Point and Trust-Region methods. Augmented Lagrangian algorithms are implemented and tested for problems with inequality constraints, using the quadratic and m2b penalty functions. The numeric results obtained in Matlab illustrate the efficiency of the quadratic penalty.

- / -

Cette thèse a pour objet la résolution exacte d’un problème d’optimisation des flux de puissance (OPF) dans un réseau électrique. Dans l’OPF, on doit planifier la production et la répartition des flux de puissances électriques permettant de couvrir, à un coût minimal, la consommation en différents points du réseau. Trois variantes du problème de l’OPF sont étudiées dans ce manuscrit. Nous nous concentrerons principalement sur la résolution exacte des deux problèmes (OPF − L) et (OPF − Q), puis nous montrerons comment notre approche peut naturellement s’´étendre à la troisième variante (OPF − UC). Cette thèse propose de résoudre ces derniers à l’aide d’une méthode de reformulation que l’on appelle RC-OPF. La contribution principale de cette thèse réside dans l’étude, le développement et l’utilisation de notre méthode de résolution exacte RC-OPF sur les trois variantes d’OPF. RC-OPF utilise également des techniques de contractions de bornes, et nous montrons comment ces techniques classiques peuvent être renforcées en utilisant des résultats issus de notre reformulation optimale. / Alternative Current Optimal Power Flow (ACOPF) is naturally formulated as a non-convex problem. In that context, solving (ACOPF) to global optimality remains a challenge when classic convex relaxations are not exact. We use semidefinite programming to build a quadratic convex relaxation of (ACOPF). We show that this quadratic convex relaxation has the same optimal value as the classical semidefinite relaxation of (ACOPF) which is known to be tight. In that context, we build a spatial branch-and-bound algorithm to solve (ACOPF) to global optimality that is based on a quadratic convex programming bound.

Dans cette thèse, nous nous étudions des algorithmes d’optimisation non linéaire. D’une part nous proposons des techniques de détection rapide de la non-réalisabilité d’un problème à résoudre. D’autre part, nous analysons le comportement local des algorithmes pour la résolution de problèmes singuliers. Dans la première partie, nous présentons une modification d’un algorithme de lagrangien augmenté pour l’optimisation avec contraintes d’égalité. La convergence quadratique du nouvel algorithme dans le cas non-réalisable est démontrée théoriquement et numériquement. La seconde partie est dédiée à l’extension du résultat précédent aux problèmes d’optimisation non linéaire généraux avec contraintes d’égalité et d’inégalité. Nous proposons une modification d’un algorithme de pénalisation mixte basé sur un lagrangien augmenté et une barrière logarithmique. Les résultats théoriques de l’analyse de convergence et quelques tests numériques montrent l’avantage du nouvel algorithme dans la détection de la non-réalisabilité. La troisième partie est consacrée à étudier le comportement local d’un algorithme primal-dual de points intérieurs pour l’optimisation sous contraintes de borne. L’analyse locale est effectuée sans l’hypothèse classique des conditions suffisantes d’optimalité de second ordre. Celle-ci est remplacée par une hypothèse plus faible basée sur la notion de borne d’erreur locale. Nous proposons une technique de régularisation de la jacobienne du système d’optimalité à résoudre. Nous démontrons ensuite des propriétés de bornitude de l’inverse de ces matrices régularisées, ce qui nous permet de montrer la convergence superlinéaire de l’algorithme. La dernière partie est consacrée à l’analyse de convergence locale de l’algorithme primal-dual qui est utilisé dans les deux premières parties de la thèse. En pratique, il a été observé que cet algorithme converge rapidement même dans le cas où les contraintes ne vérifient l’hypothèse de qualification de Mangasarian-Fromovitz. Nous démontrons la convergence superlinéaire et quadratique de cet algorithme, sans hypothèse de qualification des contraintes. / This thesis is devoted to the study of numerical algorithms for nonlinear optimization. On the one hand, we propose new strategies for the rapid infeasibility detection. On the other hand, we analyze the local behavior of primal-dual algorithms for the solution of singular problems. In the first part, we present a modification of an augmented Lagrangian algorithm for equality constrained optimization. The quadratic convergence of the new algorithm in the infeasible case is theoretically and numerically demonstrated. The second part is dedicated to extending the previous result to the solution of general nonlinear optimization problems with equality and inequality constraints. We propose a modification of a mixed logarithmic barrier-augmented Lagrangian algorithm. The theoretical convergence results and the numerical experiments show the advantage of the new algorithm for the infeasibility detection. In the third part, we study the local behavior of a primal-dual interior point algorithm for bound constrained optimization. The local analysis is done without the standard assumption of the second-order sufficient optimality conditions. These conditions are replaced by a weaker assumption based on a local error bound condition. We propose a regularization technique of the Jacobian matrix of the optimality system. We then demonstrate some boundedness properties of the inverse of these regularized matrices, which allow us to prove the superlinear convergence of our algorithm. The last part is devoted to the local convergence analysis of the primal-dual algorithm used in the first two parts of this thesis. In practice, it has been observed that this algorithm converges rapidly even in the case where the constraints do not satisfy the Mangasarian-Fromovitz constraint qualification. We demonstrate the superlinear and quadratic convergence of this algorithm without any assumption of constraint qualification.