No description available.

Multi-scale wave propagation problems are computationally costly to    solve by traditional techniques because the smallest scales must be    represented over a domain determined by the largest scales of the    problem.  We have developed new numerical methods for multi-scale wave    propagation in the framework of heterogeneous multi-scale methods.  The    numerical methods couples simulations on macro and micro scales with    data exchange between models of different scales.  With the new method    we are able to consider a general class of problems including some    problems where a homogenized equation is unknown.  We show that the    complexity of the new method is significantly lower than that of    traditional techniques.  Numerical results are presented from problems    in one, two and three dimensional and for finite and long time.  We also    analyze the method, in one and several dimensions and for finite time,    using Fourier analysis.

There are several benefits of taking the Hessian of the objective function into account when designing optimization algorithms. Compared to using strictly gradient-based algorithms, Hessian-based algorithms usually require fewer iterations to converge. They are generally less sensitive to tuning of parameters and can better handle ill-conditioned problems. Yet, they are not universally used, due to there being several challenges associated with adapting them to various challenging settings. This thesis deals with Hessian-based optimization algorithms for large-scale, distributed and zeroth-order problems. For the large-scale setting, we contribute with a new way of deriving limited memory quasi-Newton methods, which we show can achieve better results than traditional limited memory quasi-Newton methods with less memory for some logistic and linear regression problems. For the distributed setting, we perform an analysis of how the error of a Newton-step is affected by the condition number and the number of iterations of a consensus-algorithm based on averaging, We show that the number of iterations needed to solve a quadratic problem with relative error less than ε grows logarithmically with 1/ε and also with the condition number of the Hessian of the centralized problem. For the zeroth order setting, we exploit the fact that a finite difference estimate of the directional derivative works as an approximate sketching technique, and use this to propose a zeroth order extension of a sketched Newton method that has been developed to solve large-scale problems. With the extension of this method to the zeroth order setting, we address the combined challenge of large-scale and zeroth order problems. / <p>QC 20220120</p>

This thesis aims at research in the field of combinatorial optimization. Problems within this field often posses special structures allowing them to be decomposed into more easily solved subproblems, which can be exploited in solution methods. These structures appear frequently in applications. We contribute with both re-search on the development of decomposition principles and on applications. The thesis consists of an introduction and three papers.  In Paper I, we develop a Lagrangian meta-heuristic principle, which is founded on a primal-dual global optimality condition for discrete and non-convex optimization problems. This condition characterizes (near-)optimal solutions in terms of near-optimality and near-complementarity measures for Lagrangian relaxed solutions. The meta-heuristic principle amounts to constructing a weighted combination of these measures, thus creating a parametric auxiliary objective function (which is a close relative to a Lagrangian function), and embedding a Lagrangian heuristic in a search procedure in the space of the weight parameters. We illustrate and assess the Lagrangian meta-heuristic principle by applying it to the generalized assignment problem and to the set covering problem. Our computational experience shows that the meta-heuristic extension of a standard Lagrangian heuristic principle can significantly improve upon the solution quality.  In Paper II, we study the duality gap for set covering problems. Such problems sometimes have large duality gaps, which make them computationally challenging. The duality gap is dissected with the purpose of understanding its relationship to problem characteristics, such as problem shape and density. The means for doing this is the above-mentioned optimality condition, which is used to decompose the duality gap into terms describing near-optimality in a Lagrangian relaxation and near-complementarity in the relaxed constraints. We analyse these terms for numerous problem instances, including some large real-life instances, and conclude that when the duality gap is large, the near-complementarity term is typically large and the near-optimality term small. The large violation of complementarity is due to extensive over-coverage. Our observations have implications for the design of solution methods, especially for the design of core problems.  In Paper III, we study a bi-objective covering problem stemming from a real-world application concerning the design of camera surveillance systems for large-scale outdoor areas. It is prohibitively costly to surveil the entire area, and therefore relevant to be able to present a decision-maker with trade-offs between total cost and the portion of the area that is surveilled. The problem is stated as a set covering problem with two objectives, describing cost and portion of covering constraints that are fulfilled, respectively. Finding the Pareto frontier for these objectives is very computationally demanding and we therefore develop a method for finding a good approximate frontier in a reasonable computing time. The method is based on the ε−constraint reformulation, an established heuristic for set covering problems, and subgradient optimization. / Denna avhandling behandlar lösningsmetoder för stora och komplexa kombinatoriska optimeringsproblem. Sådana problem har ofta speciella strukturer som gör att de kan dekomponeras i en uppsättning mindre delproblem, vilket kan utnyttjas för konstruktion av effektiva lösningsmetoder. Avhandlingen omfattar både grundforskning inom utvecklingen av dekompositionsprinciper för kombinatorisk optimering och forskning på tillämpningar inom detta område. Avhandlingen består av en introduktion och tre artiklar.  I den första artikeln utvecklar vi en “Lagrange-meta-heuristik-princip”. Principen bygger på primal-duala globala optimalitetsvillkor för diskreta och icke-konvexa optimeringsproblem. Dessa optimalitetsvillkor beskriver (när)optimala lösningar i termer av när-optimalitet och när-komplementaritet för Lagrange-relaxerade lösningar. Den meta-heuristiska principen bygger på en ihopviktning av dessa storheter vilket skapar en parametrisk hjälpmålfunktion, som har stora likheter med en Lagrange-funktion, varefter en traditionell Lagrange-heuristik används för olika värden på viktparametrarna, vilka avsöks med en meta-heuristik. Vi illustrerar och utvärderar denna meta-heuristiska princip genom att tillämpa den på det generaliserade tillordningsproblemet och övertäckningsproblemet, vilka båda är välkända och svårlösta kombinatoriska optimeringsproblem. Våra beräkningsresultat visar att denna meta-heuristiska utvidgning av en vanlig Lagrange-heuristik kan förbättra lösningskvaliteten avsevärt.  I den andra artikeln studerar vi egenskaper hos övertäckningsproblem. Denna typ av optimeringsproblem har ibland stora dual-gap, vilket gör dem beräkningskrävande. Dual-gapet analyseras därför med syfte att förstå dess relation till problemegenskaper, såsom problemstorlek och täthet. Medlet för att göra detta är de ovan nämnda primal-duala globala optimalitetsvillkoren för diskreta och icke-konvexa optimeringsproblem. Dessa delar upp dual-gapet i två termer, som är när-optimalitet i en Lagrange-relaxation och när-komplementaritet i de relaxerade bivillkoren, och vi analyserar dessa termer för ett stort antal probleminstanser, däribland några storskaliga praktiska problem. Vi drar slutsatsen att när dualgapet är stort är vanligen den när-komplementära termen stor och den när-optimala termen liten. Vidare obseveras att när den när-komplementära termen är stor så beror det på en stor överflödig övertäckning. Denna förståelse för problemets inneboende egenskaper går att använda vid utformningen av lösningsmetoder för övertäckningsproblem, och speciellt för konstruktion av så kallade kärnproblem.  I den tredje artikeln studeras tvåmålsproblem som uppstår vid utformningen av ett kameraövervakningssystem för stora områden utomhus. Det är i denna tillämpning alltför kostsamt att övervaka hela området och problemet modelleras därför som ett övertäckningsproblem med två mål, där ett mål beskriver totalkostnaden och ett mål beskriver hur stor del av området som övervakas. Man önskar därefter kunna skapa flera lösningar som har olika avvägningar mellan total kostnad och hur stor del av området som övervakas. Detta är dock mycket beräkningskrävande och vi utvecklar därför en metod för att hitta bra approximationer av sådana lösningar inom rimlig beräkningstid.

No description available.

There are many regularization parameter selection methods that can be used when solving inverse problems, but it is not clear which one is best suited for the inverse dispersion problem. The suitability of three different methods for solving the inverse dispersion problem are evaluated here in order to pick a suitable method for these kinds of problems in the future. The regularization parameter selection methods are used to solve the separable non-linear inverse dispersion problem which is adjusted and solved as a linear inverse problem. It is solved with Tikhonov regularization and the model is a time integrated Gaussian puff model. The dispersion problem is used with different settings and is solved with the three methods. The three methods are generalized cross-validation, L-curve method and quasi-optimality criterion. They produce rather different solutions and the results show that generalized cross-validation is the best choice. The other methods are less stable and the errors are sometimes orders of magnitude larger than the errors from generalized cross-validation.

I detta projekt undersöktes hur numeriska lösningar till PDEer beter sig då randvillkor ges med metoder som används i dagens väder- och klimatsimuleringar, så kallat Daviesrelaxering vilket gör att problemet inte är maximalt semibegränsat. Advektionsekvationen och de linjäriserade Eulerekvationerna löstes numeriskt enligt vedertagen matematisk metodik (maximalt semibegränsat) och jämfördes med lösningar då Daviesrelaxering (inte maximalt semibegränsat) användes. Det visade sig att lösningar till advektionsekvationen blir fel, och resultaten tyder på att de linjäriserade Eulerekvationerna blir fel då Daviesrelaxering används.

No description available.

We propose three models to study morphology formations in interacting ternary mixtures with the evaporation of one component. Our models involve three distinct length scales: microscopic, mesoscopic, and respectively, macroscopic. The real-world application we have in mind concerns charge transport through the heterogeneous structures arising in the fabrication of organic solar cells. As first model, we propose a microscopic 3-spins lattice dynamics with short-range interactions between the considered species. This microscopic model is approximated numerically via a Monte Carlo Metropolis-based algorithm. We explore the effect of the model parameters (volatility of the solvent, system's temperature, and interaction strengths) on the structure of the formed morphologies. Our second model is built upon the first one, by introducing a new mesoscale corresponding to the size of block spins. The link between these two models as well as between the effects of the model parameters and formed morphologies are studied in detail. These two models offer insight into cross-sections of the modeling box. Our third model encodes a macroscopic view of the evaporating mixture. We investigate its capability to lead to internal coherent structures. We propose a macroscopic system of nonlinearly coupled Cahn-Hilliard equations to capture numerical results for a top view of the modeling box. Effects of effective evaporation rates, effective interaction energy parameters, and degree of polymerization on the wanted morphology formation are explored via the computational platform FEniCS using a FEM approximation of a suitably linearized system. High-performance computing resources and Python-based parallel implementations have been used to facilitate the numerical approximation of the three models.

In this thesis we study the Cauchy problem for elliptic equations. It arises in many areas of application in science and engineering as a problem of reconstruction of solutions to elliptic equations in a domain from boundary measurements taken on a part of the boundary of this domain. The Cauchy problem for elliptic equations is known to be ill-posed. We use an iterative regularization method based on alternatively solving a sequence of well-posed mixed boundary value problems for the same elliptic equation. This method, based on iterations between Dirichlet-Neumann and Neumann-Dirichlet mixed boundary value problems was first proposed by Kozlov and Maz’ya [13] for Laplace equation and Lame’ system but not Helmholtz-type equations. As a result different modifications of this original regularization method have been proposed in literature. We consider the Robin-Dirichlet iterative method proposed by Mpinganzima et.al [3] for the Cauchy problem for the Helmholtz equation in bounded domains. We demonstrate that the Robin-Dirichlet iterative procedure is convergent for second order elliptic equations with variable coefficients provided the parameter in the Robin condition is appropriately chosen. We further investigate the convergence of the Robin-Dirichlet iterative procedure for the Cauchy problem for the Helmholtz equation in a an unbounded domain. We derive and analyse the necessary conditions needed for the convergence of the procedure. In the numerical experiments, the precise behaviour of the procedure for different values of k2 in the Helmholtz equation is investigated and the results show that the speed of convergence depends on the choice of the Robin parameters, μ0 and μ1. In the unbounded domain case, the numerical experiments demonstrate that the procedure is convergent provided that the domain is truncated appropriately and the Robin parameters, μ0 and μ1 are also chosen appropriately. / <p>Funding Agencies: International Science Programme (ISP) and the Eastern Africa Universities Mathematics Programme (EAUMP).</p>