<p>We present a detailed study on application of factor<br />graphs and the belief propagation (BP) algorithm to the<br />power system state estimation (SE) problem. We start<br />from the BP solution for the linear DC model, for which<br />we provide a detailed convergence analysis. Using BPbased<br />DC model we propose a fast real-time state<br />estimator for the power system SE. The proposed<br />estimator is easy to distribute and parallelize, thus<br />alleviating computational limitations and allowing for<br />processing measurements in real time. The presented<br />algorithm may run as a continuous process, with each<br />new measurement being seamlessly processed by the<br />distributed state estimator. In contrast to the matrixbased<br />SE methods, the BP approach is robust to illconditioned<br />scenarios caused by significant differences<br />between measurement variances, thus resulting in a<br />solution that eliminates observability analysis. Using the<br />DC model, we numerically demonstrate the performance<br />of the state estimator in a realistic real-time system<br />model with asynchronous measurements. We note that<br />the extension to the non-linear SE is possible within the<br />same framework.<br />Using insights from the DC model, we use two different<br />approaches to derive the BP algorithm for the non-linear<br />model. The first method directly applies BP methodology,<br />however, providing only approximate BP solution for the<br />non-linear model. In the second approach, we make a key<br />further step by providing the solution in which the BP is<br />applied sequentially over the non-linear model, akin to<br />what is done by the Gauss-Newton method. The resulting<br />iterative Gauss-Newton belief propagation (GN-BP)<br />algorithm can be interpreted as a distributed Gauss-<br />Newton method with the same accuracy as the<br />centralized SE, however, introducing a number of<br />advantages of the BP framework. The thesis provides<br />extensive numerical study of the GN-BP algorithm,<br />provides details on its convergence behavior, and gives a<br />number of useful insights for its implementation.<br />Finally, we define the bad data test based on the BP<br />algorithm for the non-linear model. The presented model<br />establishes local criteria to detect and identify bad data<br />measurements. We numerically demonstrate that the<br />BP-based bad data test significantly improves the bad<br />data detection over the largest normalized residual test.</p> / <p>Glavni rezultati ove teze su dizajn i analiza novih<br />algoritama za re&scaron;avanje problema estimacije stanja<br />baziranih na faktor grafovima i &bdquo;Belief Propagation&ldquo; (BP)<br />algoritmu koji se mogu primeniti kao centralizovani ili<br />distribuirani estimatori stanja u elektroenergetskim<br />sistemima. Na samom početku, definisan je postupak za<br />re&scaron;avanje linearnog (DC) problema kori&scaron;ćenjem BP<br />algoritma. Pored samog algoritma data je analiza<br />konvergencije i predloženo je re&scaron;enje za unapređenje<br />konvergencije. Algoritam se može jednostavno<br />distribuirati i paralelizovati, te je pogodan za estimaciju<br />stanja u realnom vremenu, pri čemu se informacije mogu<br />prikupljati na asinhroni način, zaobilazeći neke od<br />postojećih rutina, kao npr. provera observabilnosti<br />sistema. Pro&scaron;irenje algoritma za nelinearnu estimaciju<br />stanja je moguće unutar datog modela.<br />Dalje se predlaže algoritam baziran na probabilističkim<br />grafičkim modelima koji je direktno primenjen na<br />nelinearni problem estimacije stanja, &scaron;to predstavlja<br />logičan korak u tranziciji od linearnog ka nelinearnom<br />modelu. Zbog nelinearnosti funkcija, izrazi za određenu<br />klasu poruka ne mogu se dobiti u zatvorenoj formi, zbog<br />čega rezultujući algoritam predstavlja aproksimativno<br />re&scaron;enje. Nakon toga se predlaže distribuirani Gaus-<br />Njutnov metod baziran na probabilističkim grafičkim<br />modelima i BP algoritmu koji postiže istu tačnost kao i<br />centralizovana verzija Gaus-Njutnovog metoda za<br />estimaciju stanja, te je dat i novi algoritam za otkrivanje<br />nepouzdanih merenja (outliers) prilikom merenja<br />električnih veličina. Predstavljeni algoritam uspostavlja<br />lokalni kriterijum za otkrivanje i identifikaciju<br />nepouzdanih merenja, a numerički je pokazano da<br />algoritam značajno pobolj&scaron;ava detekciju u odnosu na<br />standardne metode.</p>

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.

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.

Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).

The development, analysis, and implementation of efficient methods to solve algebraic systems of equations are main research directions in the field of numerical simulation and are the focus of this thesis. Due to their lesser demands for computer resources, iterative solution methods are the choice to make, when very large scale simulations have to be performed. To improve their efficiency, iterative methods are combined with proper techniques to accelerate convergence. A general technique to do this is to use a so-called preconditioner. Constructing and analysing various preconditioning methods has been an active field of research already for decades. Special attention is devoted to the class of the so-called optimal order preconditioners, that possess both optimal convergence rate and optimal computational complexity. The preconditioning techniques, proposed and studied in this thesis, utilise the block structure of the underlying matrices, and lead to methods that are of optimal order. In the first part of the thesis, we construct an Algebraic MultiLevel Iteration (AMLI) method for systems arising from discretizations of parabolic problems, using Crouzeix-Raviart finite elements. The developed AMLI method is based on an approximated block factorization of the original system matrix, where the partitioning is associated with a sequence of nested discretization meshes. In the second part of the thesis we develop solution methods for the numerical simulation of multiphase flow problems, modelled by the Cahn-Hilliard (C-H) equation. We consider the discrete C-H problem, obtained via finite element discretization in space and implicit schemes in time. We propose techniques to precondition the Jacobian of the discrete nonlinear system, based on its natural two-by-two block structure. The preconditioners are used in the framework of inexact Newton methods. We develop two nonlinear solution algorithms for the Cahn-Hilliard problem. Both lead to efficient optimal order methods. One of the main advantages of the proposed methods is that they are implemented using available software toolboxes for both sequential and distributed execution. The theoretical analysis of the solution methods presented in this thesis is combined with numerical studies that confirm their efficiency.

In this thesis, optimization approaches for intensity-modulated radiation therapy are developed and evaluated with focus on numerical efficiency and treatment delivery aspects. The first two papers deal with strategies for solving fluence map optimization problems efficiently while avoiding solutions with jagged fluence profiles. The last two papers concern optimization of step-and-shoot parameters with emphasis on generating treatment plans that can be delivered efficiently and accurately. In the first paper, the problem dimension of a fluence map optimization problem is reduced through a spectral decomposition of the Hessian of the objective function. The weights of the eigenvectors corresponding to the p largest eigenvalues are introduced as optimization variables, and the impact on the solution of varying p is studied. Including only a few eigenvector weights results in faster initial decrease of the objective value, but with an inferior solution, compared to optimization of the bixel weights. An approach combining eigenvector weights and bixel weights produces improved solutions, but at the expense of the pre-computational time for the spectral decomposition. So-called iterative regularization is performed on fluence map optimization problems in the second paper. The idea is to find regular solutions by utilizing an optimization method that is able to find near-optimal solutions with non-jagged fluence profiles in few iterations. The suitability of a quasi-Newton sequential quadratic programming method is demonstrated by comparing the treatment quality of deliverable step-and-shoot plans, generated through leaf sequencing with a fixed number of segments, for different number of bixel-weight iterations. A conclusion is that over-optimization of the fluence map optimization problem prior to leaf sequencing should be avoided. An approach for dynamically generating multileaf collimator segments using a column generation approach combined with optimization of segment shapes and weights is presented in the third paper. Numerical results demonstrate that the adjustment of leaf positions improves the plan quality and that satisfactory treatment plans are found with few segments. The method provides a tool for exploring the trade-off between plan quality and treatment complexity by generating a sequence of deliverable plans of increasing quality. The final paper is devoted to understanding the ability of the column generation approach in the third paper to find near-optimal solutions with very few columns compared to the problem dimension. The impact of different restrictions on the generated columns is studied, both in terms of numerical behaviour and convergence properties. A bound on the two-norm of the columns results in the conjugate-gradient method. Numerical results indicate that the appealing properties of the conjugate-gradient method on ill-conditioned problems are inherited in the column generation approach of the third paper. / QC 20100709

A class of Lagrange-Newton-SQP methods is investigated for optimal control problems governed by semilinear parabolic initial- boundary value problems. Distributed and boundary controls are given, restricted by pointwise upper and lower bounds. The convergence of the method is discussed in appropriate Banach spaces. Based on a weak second order sufficient optimality condition for the reference solution, local quadratic convergence is proved. The proof is based on the theory of Newton methods for generalized equations in Banach spaces.

A technology for optimization of potential parameters from condensed phase simulations (POP) is discussed and illustrated. It is based on direct calculations of the derivatives of macroscopic observables with respect to the potential parameters. The derivatives are used in a local minimization scheme, comparing simulated and experimental data. In particular, we show that the Newton Trust-Region protocol allows for accurate and robust optimization. POP is illustrated for a toy problem of alanine dipeptide and is applied to folding of the peptide WAAAH. The helix fraction is highly sensitive to the potential parameters while the slope of the melting curve is not. The sensitivity variations make it difficult to satisfy both observations simultaneously. We conjecture that there is no set of parameters that reproduces experimental melting curves of short peptides that are modeled with the usual functional form of a force field. We then apply the newly developed technology to study the liquid mixture of tert-butanol and water. We are able to obtain, after 4 iterations, the correct phase behavior and accurately predict the value of the Kirkwood Buff (KB) integrals. We further illustrate that a potential that is determined solely by KB information, or the pair correlation function, is not necessarily unique. / text

The objective of this PhD research program is to develop an accurate and efficient heterogeneous three-dimensional computational model for simulating the drying of wood at temperatures below the boiling point of water. The complex macroscopic drying equations comprise a coupled and highly nonlinear system of physical laws for liquid and energy conservation. Due to the heterogeneous nature of wood, the physical model parameters strongly depend upon the local pore structure, wood density variation within growth rings and variations in primary and secondary system variables. In order to provide a realistic representation of this behaviour, a set of previously determined parameters derived using sophisticated image analysis methods and homogenisation techniques is embedded within the model. From the literature it is noted that current three-dimensional computational models for wood drying do not take into consideration the heterogeneities of the medium. A significant advance made by the research conducted in this thesis is the development of a three - dimensional computational model that takes into account the heterogeneous board material properties which vary within the transverse plane with respect to the pith position that defines the radial and tangential directions. The development of an accurate and efficient computational model requires the consideration of a number of significant numerical issues, including the virtual board description, an effective mesh design based on triangular prismatic elements, the control volume finite element discretisation process for the cou- pled conservation laws, the derivation of an accurate dux expression based on gradient approximations together with flux limiting, and finally the solution of a large, coupled, nonlinear system using an inexact Newton method with a suitably preconditioned iterative linear solver for computing the Newton correction. This thesis addresses all of these issues for the case of low temperature drying of softwood. Specific case studies are presented that highlight the efficiency of the proposed numerical techniques and illustrate the complex heat and mass transport processes that evolve throughout drying.

Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problème. / Our objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem.