Scenario Cluster Lagrangian Decomposition in two stage stochastic mixed 0-1 optimization

In this paper we introduce four scenario Cluster based Lagrangian Decomposition (CLD) procedures for obtaining strong lower bounds to the (optimal) solution value of two-stage stochastic mixed 0-1 problems. At each iteration of the Lagrangian based procedures, the traditional aim consists of obtaining the solution value of the corresponding Lagrangian dual via solving scenario submodels once the nonanticipativity constraints have been dualized. Instead of considering a splitting variable representation over the set of scenarios, we propose to decompose the model into a set of scenario clusters. We compare the computational performance of the four Lagrange multiplier updating procedures, namely the Subgradient Method, the Volume Algorithm, the Progressive Hedging Algorithm and the Dynamic Constrained Cutting Plane scheme for different numbers of scenario clusters and different dimensions of the original problem. Our computational experience shows that the CLD bound and its computational effort depend on the number of scenario clusters to consider. In any case, our results show that the CLD procedures outperform the traditional LD scheme for single scenarios both in the quality of the bounds and computational effort. All the procedures have been implemented in a C++ experimental code. A broad computational experience is reported on a test of randomly generated instances by using the MIP solvers COIN-OR and CPLEX for the auxiliary mixed 0-1 cluster submodels, this last solver within the open source engine COIN-OR. We also give computational evidence of the model tightening effect that the preprocessing techniques, cut generation and appending and parallel computing tools have in stochastic integer optimization. Finally, we have observed that the plain use of both solvers does not provide the optimal solution of the instances included in the testbed with which we have experimented but for two toy instances in affordable elapsed time. On the other hand the proposed procedures provide strong lower bounds (or the same solution value) in a considerably shorter elapsed time for the quasi-optimal solution obtained by other means for the original stochastic problem.

A Multiscale-Domain Decomposition Method for High Reynolds Number Flows

The high Reynolds number flow contains a wide range of length and time scales, and the flow domain can be divided into several sub-domains with different characteristic scales. In some sub-domains, the viscosity dissipation scale can only be considered in a certain direction; in some sub-domains, the viscosity dissipation scales need to be considered in all directions; in some sub-domains, the viscosity dissipation scales are unnecessary to be considered at all. For laminar boundary layer region, the characteristic length scales in the streamwise and normal directions are L and L Re-1/ 2 , respectively. The characteristic length scale and the velocity scale in the outer region of the boundary layer are L and U, respectively. In the neighborhood region of the separated point, the length scale l<Euler equations, NS- and diffusion parabolized (DP) NS equations. In this paper, a new multiscale-domain decomposition method is developed for the high Reynolds number flow. First, the whole domain is decomposed to different sub-domains with the different characteristic scales. Then the different dominant equation of all sub-domains is defined according to the diffusion parabolized (DP) theory of viscous flow. Finally these different equations are solved simultaneously in whole computational region. For numerical tests of high Reynolds numerical flows, two-dimensional supersonic flows over rearward and frontward steps as well as an interaction flow between shock wave and boundary layer were solved numerically. The pressure distributions and local coefficients of skin friction on the wall are given. The numerical results obtained by the multiscale-domain decomposition algorithm are well agreement with those by NS equations. Comparing with the usual method of solving the Navier-Stokes equations in the whole flow, under the same numerical accuracy, the present multiscale domain decomposition method decreases CPU consuming about 20% and reflects the physical mechanism of practical flow more accurately.

Geometric integration applied to moving mesh methods and degenerate Lagrangians

Moving mesh methods (also called r-adaptive methods) are space-adaptive strategies used for the numerical simulation of time-dependent partial differential equations. These methods keep the total number of mesh points fixed during the simulation, but redistribute them over time to follow the areas where a higher mesh point density is required. There are a very limited number of moving mesh methods designed for solving field-theoretic partial differential equations, and the numerical analysis of the resulting schemes is challenging. In this thesis we present two ways to construct r-adaptive variational and multisymplectic integrators for (1+1)-dimensional Lagrangian field theories. The first method uses a variational discretization of the physical equations and the mesh equations are then coupled in a way typical of the existing r-adaptive schemes. The second method treats the mesh points as pseudo-particles and incorporates their dynamics directly into the variational principle. A user-specified adaptation strategy is then enforced through Lagrange multipliers as a constraint on the dynamics of both the physical field and the mesh points. We discuss the advantages and limitations of our methods. The proposed methods are readily applicable to (weakly) non-degenerate field theories---numerical results for the Sine-Gordon equation are presented.

In an attempt to extend our approach to degenerate field theories, in the last part of this thesis we construct higher-order variational integrators for a class of degenerate systems described by Lagrangians that are linear in velocities. We analyze the geometry underlying such systems and develop the appropriate theory for variational integration. Our main observation is that the evolution takes place on the primary constraint and the 'Hamiltonian' equations of motion can be formulated as an index 1 differential-algebraic system. We then proceed to construct variational Runge-Kutta methods and analyze their properties. The general properties of Runge-Kutta methods depend on the 'velocity' part of the Lagrangian. If the 'velocity' part is also linear in the position coordinate, then we show that non-partitioned variational Runge-Kutta methods are equivalent to integration of the corresponding first-order Euler-Lagrange equations, which have the form of a Poisson system with a constant structure matrix, and the classical properties of the Runge-Kutta method are retained. If the 'velocity' part is nonlinear in the position coordinate, we observe a reduction of the order of convergence, which is typical of numerical integration of DAEs. We also apply our methods to several models and present the results of our numerical experiments.

Uncovering the Lagrangian from observations of trajectories

We approach the problem of automatically modeling a mechanical system from data about its dynamics, using a method motivated by variational integrators. We write the discrete Lagrangian as a quadratic polynomial with varying coefficients, and then use the discrete Euler-Lagrange equations to numerically solve for the values of these coefficients near the data points. This method correctly modeled the Lagrangian of a simple harmonic oscillator and a simple pendulum, even with significant measurement noise added to the trajectories.

Adjoint linearised Euler solver in the frequency domain for jet noise modelling

The paper is devoted to extending the new efficient frequency-domain method of adjoint Green's function calculation to curvilinear multi-block RANS domains for middle and farfield sound computations. Numerical details of the method such as grids, boundary conditions and convergence acceleration are discussed. Two acoustic source models are considered in conjunction with the method and acoustic modelling results are presented for a benchmark low-Reynolds-number jet case.

Static analysis of Euler-Bernoulli beams with multiple unilateral cracks under combined axial and transverse loads

The paper deals with the static analysis of pre-damaged Euler-Bernoulli beams with any number of unilateral cracks and subjected to tensile or compression forces combined with arbitrary transverse loads. The mathematical representation of cracks with a bilateral behaviour (i.e. always open) via Dirac delta functions is extended by introducing a convenient switching variable, which allows each crack to be open or closed depending on the sign of the axial strain at the crack centre. The proposed model leads to analytical solutions, which depend on four integration constants (to be computed by enforcing the boundary conditions) along with the Boolean switching variables associated with the cracks (whose role is to turn on and off the additional flexibility due to the presence of the cracks). An efficient computational procedure is also presented and numerically validated. For this purpose, the proposed approach is applied to two pre-damaged beams, with different damage and loading conditions, and the results so obtained are compared against those given by a standard finite element code (in which the correct opening of the cracks is pre-assigned), always showing a perfect agreement. © 2013 Elsevier Ltd. All rights reserved.

边坡动力响应分析及应用研究

As a marginal subject, dynamic responses of slopes is not only an important problem of engineering geology (Geotechnical problem), but also of other subjects such as seismology, geophysics, seismic engineering and engineering seismic and so on. Owning to the gulf between different subjects, it is arduous to study dynamic responses of slopes and the study is far from ripeness. Studying on the dynamic responses of slopes is very important in theories as well as practices. Supported by hundreds of bibliographies, this paper systemically details the development process of this subject, introduces main means to analyze this subject, and then gives brief remarks to each means respectively. Engineering geology qualitative analysis is the base of slopes dynamic responses study. Because of complexity of geological conditions, engineering geology qualitative analysis is very important in slopes stability study, especially to rock slopes with complex engineering geology conditions. Based on research fruits of forerunners, this paper summarizes factors influencing slopes dynamic stability into five aspects as geology background, stratums, rock mass structure, and topography as well as hydrogeology condition. Based on rock mass structure controlling theory, engineering geology model of the slope is grouped into two typical classes, one is model with obvious controlling discontinuities, which includes horizontal bedded slope, bedding slope, anti-dip slope, slide as well as slope with base rock and weathered crust; the other is model without obvious controlling discontinuities, which includes homogeneous soil slope, joint rock mass slope. Study on slope failure mechanism under dynamic force, the paper concludes that there are two effects will appear in slope during strong earthquake, one is earthquake inertia force, the other is ultra pore pressure buildup. The two effects lead to failure of the slope. To different types of slope failure, the intensity of two effects acting on the slope is different too. To plastic flow failure, pore pressure buildup is dominant; to falling rock failure and toppling failure, earthquake inertia force is dominant in general. This paper briefly introduces the principle of Lagrangian element method. Through a lot of numerical simulations with FLAC3D, the paper comprehensively studies dynamic responses of slopes, and finds that: if the slope is low, displacement, velocity and acceleration are linear enlarging with elevation increasing in vertical direction; if the slope is high enough, displacement, velocity and acceleration are not linear with elevation any more, on the other hand, they fluctuate with certain rhythm. At the same time, the rhythm appears in the horizontal direction in the certain area near surface of the slope. The distribution form of isoline of displacement, velocity and acceleration in the section of the slope is remarkably affected by the slope angle. In the certain area near the slope surface, isoline of displacement, velocity and acceleration is parallel to the surface of the slope, in the mean time, the strike direction of the extreraum area is parallel to the surface of the slope too. Beyond this area, the isoline direction and the strike direction of the extremum area turn to horizontal with invariable distance. But the rhythm appearing or not has nothing to with the slope angle. The paper defines the high slope effect and the low slope effect of slopes dynamic responses, discusses the threshold height H^t of the dynamic high slope effect, and finds that AW is proportional to square root of the dynamic elastic moduli El P , at the same time, it is proportional to period Tof the dynamic input. Thus, the discriminant of H^t is achieved. The discriminant can tell us that to a slope, if its height is larger than one fifth of the wavelength, its response regular will be the dynamic high slope effect; on the other hand, its response regular will be the dynamic low slope effect. Based on these, the discriminant of different slopes taking on same response under the same dynamic input is put forward in this paper. At the same time, the paper studies distribution law of the rhythm extremum point of displacement, velocity and acceleration, and finds that there exists relationship of N = int among the slope height H, the number of the rhythm extremum VHlhro) point N and ffthre- Furthermore, the paper points out that if N^l, the response of the slope will be dynamic high slope effect; \fN

Fast Geodesic Active Fields for Image Registration Based on Splitting and Augmented Lagrangian Approaches.

In this paper, we present an efficient numerical scheme for the recently introduced geodesic active fields (GAF) framework for geometric image registration. This framework considers the registration task as a weighted minimal surface problem. Hence, the data-term and the regularization-term are combined through multiplication in a single, parametrization invariant and geometric cost functional. The multiplicative coupling provides an intrinsic, spatially varying and data-dependent tuning of the regularization strength, and the parametrization invariance allows working with images of nonflat geometry, generally defined on any smoothly parametrizable manifold. The resulting energy-minimizing flow, however, has poor numerical properties. Here, we provide an efficient numerical scheme that uses a splitting approach; data and regularity terms are optimized over two distinct deformation fields that are constrained to be equal via an augmented Lagrangian approach. Our approach is more flexible than standard Gaussian regularization, since one can interpolate freely between isotropic Gaussian and anisotropic TV-like smoothing. In this paper, we compare the geodesic active fields method with the popular Demons method and three more recent state-of-the-art algorithms: NL-optical flow, MRF image registration, and landmark-enhanced large displacement optical flow. Thus, we can show the advantages of the proposed FastGAF method. It compares favorably against Demons, both in terms of registration speed and quality. Over the range of example applications, it also consistently produces results not far from more dedicated state-of-the-art methods, illustrating the flexibility of the proposed framework.

On some Density Theorems in Number Theory and Group Theory

Gowers, dans son article sur les matrices quasi-aléatoires, étudie la question, posée par Babai et Sos, de l'existence d'une constante $c>0$ telle que tout groupe fini possède un sous-ensemble sans produit de taille supérieure ou égale a $c|G|$. En prouvant que, pour tout nombre premier $p$ assez grand, le groupe $PSL_2(\mathbb{F}_p)$ (d'ordre noté $n$) ne posséde aucun sous-ensemble sans produit de taille $c n^{8/9}$, il y répond par la négative. Nous allons considérer le probléme dans le cas des groupes compacts finis, et plus particuliérement des groupes profinis $SL_k(\mathbb{Z}_p)$ et $Sp_{2k}(\mathbb{Z}_p)$. La premiére partie de cette thése est dédiée à l'obtention de bornes inférieures et supérieures exponentielles pour la mesure suprémale des ensembles sans produit. La preuve nécessite d'établir préalablement une borne inférieure sur la dimension des représentations non-triviales des groupes finis $SL_k(\mathbb{Z}/(p^n\mathbb{Z}))$ et $Sp_{2k}(\mathbb{Z}/(p^n\mathbb{Z}))$. Notre théoréme prolonge le travail de Landazuri et Seitz, qui considérent le degré minimal des représentations pour les groupes de Chevalley sur les corps finis, tout en offrant une preuve plus simple que la leur. La seconde partie de la thése à trait à la théorie algébrique des nombres. Un polynome monogéne $f$ est un polynome unitaire irréductible à coefficients entiers qui endengre un corps de nombres monogéne. Pour un nombre premier $q$ donné, nous allons montrer, en utilisant le théoréme de densité de Tchebotariov, que la densité des nombres premiers $p$ tels que $t^q -p$ soit monogéne est supérieure ou égale à $(q-1)/q$. Nous allons également démontrer que, quand $q=3$, la densité des nombres premiers $p$ tels que $\mathbb{Q}(\sqrt[3]{p})$ soit non monogéne est supérieure ou égale à $1/9$.

Superheavy nuclei in relativistic effective Lagrangian model

Isotopic and isotonic chains of superheavy nuclei are analyzed to search for spherical double shell closures beyond Z=82 and N=126 within the new effective field theory model of Furnstahl, Serot, and Tang for the relativistic nuclear many-body problem. We take into account several indicators to identify the occurrence of possible shell closures, such as two-nucleon separation energies, two-nucleon shell gaps, average pairing gaps, and the shell correction energy. The effective Lagrangian model predicts N=172 and Z=120 and N=258 and Z=120 as spherical doubly magic superheavy nuclei, whereas N=184 and Z=114 show some magic character depending on the parameter set. The magicity of a particular neutron (proton) number in the analyzed mass region is found to depend on the number of protons (neutrons) present in the nucleus.

Ein Algorithmus zur numerischen Verifikation der äquivarianten Tamagawazahlvermutung für eine Familie von Zahlkörpererweiterungen

Sei $N/K$ eine galoissche Zahlkörpererweiterung mit Galoisgruppe $G$, so dass es in $N$ eine Stelle mit voller Zerlegungsgruppe gibt. Die vorliegende Arbeit beschäftigt sich mit Algorithmen, die für das gegebene Fallbeispiel $N/K$, die äquivariante Tamagawazahlvermutung von Burns und Flach für das Paar $(h^0(Spec(N), \mathbb{Z}[G]))$ (numerisch) verifizieren. Grob gesprochen stellt die äquivariante Tamagawazahlvermutung (im Folgenden ETNC) in diesem Spezialfall einen Zusammenhang her zwischen Werten von Artinschen $L$-Reihen zu den absolut irreduziblen Charakteren von $G$ und einer Eulercharakteristik, die man in diesem Fall mit Hilfe einer sogenannten Tatesequenz konstruieren kann. Unter den Voraussetzungen 1. es gibt eine Stelle $v$ von $N$ mit voller Zerlegungsgruppe, 2. jeder irreduzible Charakter $\chi$ von $G$ erfüllt eine der folgenden Bedingungen 2a) $\chi$ ist abelsch, 2b) $\chi(G) \subset \mathbb{Q}$ und $\chi$ ist eine ganzzahlige Linearkombination von induzierten trivialen Charakteren; wird ein Algorithmus entwickelt, der ETNC für jedes Fallbeispiel $N/\mathbb{Q}$ vollständig beweist. Voraussetzung 1. erlaubt es eine Idee von Chinburg ([Chi89]) umzusetzen zur algorithmischen Berechnung von Tatesequenzen. Dabei war es u.a. auch notwendig lokale Fundamentalklassen zu berechnen. Im höchsten zahm verzweigten Fall haben wir hierfür einen Algorithmus entwickelt, der ebenfalls auf den Ideen von Chinburg ([Chi85]) beruht, die auf Arbeiten von Serre [Ser] zurück gehen. Für nicht zahm verzweigte Erweiterungen benutzen wir den von Debeerst ([Deb11]) entwickelten Algorithmus, der ebenfalls auf Serre's Arbeiten beruht. Voraussetzung 2. wird benötigt, um Quotienten aus den $L$-Werten und Regulatoren exakt zu berechnen. Dies gelingt, da wir im Fall von abelschen Charakteren auf die Theorie der zyklotomischen Einheiten zurückgreifen können und im Fall (b) auf die analytische Klassenzahlformel von Zwischenkörpern. Ohne die Voraussetzung 2. liefern die Algorithmen für jedes Fallbeispiel $N/K$ immer noch eine numerische Verifikation bis auf Rechengenauigkeit. Den Algorithmus zur numerischen Verifikation haben wir für $A_4$-Erweiterungen über $\mathbb{Q}$ in das Computeralgebrasystem MAGMA implementiert und für 27 Erweiterungen die äquivariante Tamagawazahlvermutung numerisch verifiziert.

Manifold clustering for motion segmentation

En aquesta tesi s’estudia el problema de la segmentació del moviment. La tesi presenta una revisió dels principals algoritmes de segmentació del moviment, s’analitzen les característiques principals i es proposa una classificació de les tècniques més recents i importants. La segmentació es pot entendre com un problema d’agrupament d’espais (manifold clustering). Aquest estudi aborda alguns dels reptes més difícils de la segmentació de moviment a través l’agrupament d’espais. S’han proposat nous algoritmes per a l’estimació del rang de la matriu de trajectòries, s’ha presenta una mesura de similitud entre subespais, s’han abordat problemes relacionats amb el comportament dels angles canònics i s’ha desenvolupat una eina genèrica per estimar quants moviments apareixen en una seqüència. L´ultima part de l’estudi es dedica a la correcció de l’estimació inicial d’una segmentació. Aquesta correcció es du a terme ajuntant els problemes de la segmentació del moviment i de l’estructura a partir del moviment.

A cell by cell anisotropic adaptive mesh ALE scheme for the numerical solution of the Euler equations

In this paper a cell by cell anisotropic adaptive mesh technique is added to an existing staggered mesh Lagrange plus remap finite element ALE code for the solution of the Euler equations. The quadrilateral finite elements may be subdivided isotropically or anisotropically and a hierarchical data structure is employed. An efficient computational method is proposed, which only solves on the finest level of resolution that exists for each part of the domain with disjoint or hanging nodes being used at resolution transitions. The Lagrangian, equipotential mesh relaxation and advection (solution remapping) steps are generalised so that they may be applied on the dynamic mesh. It is shown that for a radial Sod problem and a two-dimensional Riemann problem the anisotropic adaptive mesh method runs over eight times faster.

Free gravity waves and balanced dynamics

It is shown how a renormalization technique, which is a variant of classical Krylov–Bogolyubov–Mitropol’skii averaging, can be used to obtain slow evolution equations for the vortical and inertia–gravity wave components of the dynamics in a rotating flow. The evolution equations for each component are obtained to second order in the Rossby number, and the nature of the coupling between the two is analyzed carefully. It is also shown how classical balance models such as quasigeostrophic dynamics and its second-order extension appear naturally as a special case of this renormalized system, thereby providing a rigorous basis for the slaving approach where only the fast variables are expanded. It is well known that these balance models correspond to a hypothetical slow manifold of the parent system; the method herein allows the determination of the dynamics in the neighborhood of such solutions. As a concrete illustration, a simple weak-wave model is used, although the method readily applies to more complex rotating fluid models such as the shallow-water, Boussinesq, primitive, and 3D Euler equations.

On Hamiltonian balanced dynamics and the slowest invariant manifold

The concept of a slowest invariant manifold is investigated for the five-component model of Lorenz under conservative dynamics. It is shown that Lorenz's model is a two-degree-of-freedom canonical Hamiltonian system, consisting of a nonlinear vorticity-triad oscillator coupled to a linear gravity wave oscillator, whose solutions consist of regular and chaotic orbits. When either the Rossby number or the rotational Froude number is small, there is a formal separation of timescales, and one can speak of fast and slow motion. In the same regime, the coupling is weak, and the Kolmogorov–Arnold-Moser theorem is shown to apply. The chaotic orbits are inherently unbalanced and are confined to regions sandwiched between invariant tori consisting of quasi-periodic regular orbits. The regular orbits generally contain free fast motion, but a slowest invariant manifold may be geometrically defined as the set of all slow cores of invariant tori (defined by zero fast action) that are smoothly related to such cores in the uncoupled system. This slowest invariant manifold is not global; in fact, its structure is fractal; but it is of nearly full measure in the limit of weak coupling. It is also nonlinearly stable. As the coupling increases, the slowest invariant manifold shrinks until it disappears altogether. The results clarify previous definitions of a slowest invariant manifold and highlight the ambiguity in the definition of “slowness.” An asymptotic procedure, analogous to standard initialization techniques, is found to yield nonzero free fast motion even when the core solutions contain none. A hierarchy of Hamiltonian balanced models preserving the symmetries in the original low-order model is formulated; these models are compared with classic balanced models, asymptotically initialized solutions of the full system and the slowest invariant manifold defined by the core solutions. The analysis suggests that for sufficiently small Rossby or rotational Froude numbers, a stable slowest invariant manifold can be defined for this system, which has zero free gravity wave activity, but it cannot be defined everywhere. The implications of the results for more complex systems are discussed.