Simultaneous Perturbation Newton Algorithms for Simulation Optimization

We present a new Hessian estimator based on the simultaneous perturbation procedure, that requires three system simulations regardless of the parameter dimension. We then present two Newton-based simulation optimization algorithms that incorporate this Hessian estimator. The two algorithms differ primarily in the manner in which the Hessian estimate is used. Both our algorithms do not compute the inverse Hessian explicitly, thereby saving on computational effort. While our first algorithm directly obtains the product of the inverse Hessian with the gradient of the objective, our second algorithm makes use of the Sherman-Morrison matrix inversion lemma to recursively estimate the inverse Hessian. We provide proofs of convergence for both our algorithms. Next, we consider an interesting application of our algorithms on a problem of road traffic control. Our algorithms are seen to exhibit better performance than two Newton algorithms from a recent prior work.

The Tetrablock as a Spectral Set

The tetrablock, roughly speaking, is the set of all linear fractional maps that map the open unit disc to itself. A formal definition of this inhomogeneous domain is given below. This paper considers triples of commuting bounded operators (A,B,P) that have the tetrablock as a spectral set. Such a triple is named a tetrablock contraction. The motivation comes from the success of model theory in another inhomogeneous domain, namely, the symmetrized bidisc F. A pair of commuting bounded operators (S,P) with Gamma as a spectral set is called a Gamma-contraction, and always has a dilation. The two domains are related intricately as the Lemma 3.2 below shows. Given a triple (A, B, P) as above, we associate with it a pair (F-1, F-2), called its fundamental operators. We show that (A,B,P) dilates if the fundamental operators F-1 and F-2 satisfy certain commutativity conditions. Moreover, the dilation space is no bigger than the minimal isometric dilation space of the contraction P. Whether these commutativity conditions are necessary, too, is not known. what we have shown is that if there is a tetrablock isometric dilation on the minimal isometric dilation space of P. then those commutativity conditions necessarily get imposed on the fundamental operators. En route, we decipher the structure of a tetrablock unitary (this is the candidate as the dilation triple) and a tertrablock isometry (the restriction of a tetrablock unitary to a joint invariant sub-space). We derive new results about r-contractions and apply them to tetrablock contractions. The methods applied are motivated by 11]. Although the calculations are lengthy and more complicated, they beautifully reveal that the dilation depends on the mutual relationship of the two fundamental operators, so that certain conditions need to be satisfied. The question of whether all tetrablock contractions dilate or not is unresolved.

A Closer Look at Multiple Forking: Leveraging (In)Dependence for a Tighter Bound

Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of , where denotes the upper bound on the underlying random oracle calls and , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of `dependence' and `independence' conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of . By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.

EUSMT: incorporating linguistic information to SMT for a morphologically rich language. Its use in SMT-RBMT-EBMT hybridation

148 p.: graf.

A Direct Approach to Robustness Optimization

This dissertation reformulates and streamlines the core tools of robustness analysis for linear time invariant systems using now-standard methods in convex optimization. In particular, robust performance analysis can be formulated as a primal convex optimization in the form of a semidefinite program using a semidefinite representation of a set of Gramians. The same approach with semidefinite programming duality is applied to develop a linear matrix inequality test for well-connectedness analysis, and many existing results such as the Kalman-Yakubovich--Popov lemma and various scaled small gain tests are derived in an elegant fashion. More importantly, unlike the classical approach, a decision variable in this novel optimization framework contains all inner products of signals in a system, and an algorithm for constructing an input and state pair of a system corresponding to the optimal solution of robustness optimization is presented based on this information. This insight may open up new research directions, and as one such example, this dissertation proposes a semidefinite programming relaxation of a cardinality constrained variant of the H ∞ norm, which we term sparse H ∞ analysis, where an adversarial disturbance can use only a limited number of channels. Finally, sparse H ∞ analysis is applied to the linearized swing dynamics in order to detect potential vulnerable spots in power networks.

Rings faithfully represented on their left socle

In 1964 A. W. Goldie [1] posed the problem of determining all rings with identity and minimal condition on left ideals which are faithfully represented on the right side of their left socle. Goldie showed that such a ring which is indecomposable and in which the left and right principal indecomposable ideals have, respectively, unique left and unique right composition series is a complete blocked triangular matrix ring over a skewfield. The general problem suggested above is very difficult. We obtain results under certain natural restrictions which are much weaker than the restrictive assumptions made by Goldie.

We characterize those rings in which the principal indecomposable left ideals each contain a unique minimal left ideal (Theorem (4.2)). It is sufficient to handle indecomposable rings (Lemma (1.4)). Such a ring is also a blocked triangular matrix ring. There exist r positive integers K₁,..., K_r such that the i,j^th block of a typical matrix is a K_i x K_j matrix with arbitrary entries in a subgroup D_ij of the additive group of a fixed skewfield D. Each D_ii is a sub-skewfield of D and D_ri = D for all i. Conversely, every matrix ring which has this form is indecomposable, faithfully represented on the right side of its left socle, and possesses the property that every principal indecomposable left ideal contains a unique minimal left ideal.

The principal indecomposable left ideals may have unique composition series even though the ring does not have minimal condition on right ideals. We characterize this situation by defining a partial ordering ρ on {i, 2,...,r} where we set iρj if D_ij ≠ 0. Every principal indecomposable left ideal has a unique composition series if and only if the diagram of ρ is an inverted tree and every D_ij is a one-dimensional left vector space over D_ii (Theorem (5.4)).

We show (Theorem (2.2)) that every ring A of the type we are studying is a unique subdirect sum of less complex rings A₁,...,A_s of the same type. Namely, each A_i has only one isomorphism class of minimal left ideals and the minimal left ideals of different A_i are non-isomorphic as left A-modules. We give (Theorem (2.1)) necessary and sufficient conditions for a ring which is a subdirect sum of rings A_i having these properties to be faithfully represented on the right side of its left socle. We show ((4.F), p. 42) that up to technical trivia the rings A_i are matrix rings of the form

[...]. Each Q_j comes from the faithful irreducible matrix representation of a certain skewfield over a fixed skewfield D. The bottom row is filled in by arbitrary elements of D.

In Part V we construct an interesting class of rings faithfully represented on their left socle from a given partial ordering on a finite set, given skewfields, and given additive groups. This class of rings contains the ones in which every principal indecomposable left ideal has a unique minimal left ideal. We identify the uniquely determined subdirect summands mentioned above in terms of the given partial ordering (Proposition (5.2)). We conjecture that this technique serves to construct all the rings which are a unique subdirect sum of rings each having the property that every principal-indecomposable left ideal contains a unique minimal left ideal.

Stability of parametrically excited differential equations

Sufficient stability criteria for classes of parametrically excited differential equations are developed and applied to example problems of a dynamical nature.

Stability requirements are presented in terms of 1) the modulus of the amplitude of the parametric terms, 2) the modulus of the integral of the parametric terms and 3) the modulus of the derivative of the parametric terms.

The methods employed to show stability are Liapunov’s Direct Method and the Gronwall Lemma. The type of stability is generally referred to as asymptotic stability in the sense of Liapunov.

The results indicate that if the equation of the system with the parametric terms set equal to zero exhibits stability and possesses bounded operators, then the system will be stable under sufficiently small modulus of the parametric terms or sufficiently small modulus of the integral of the parametric terms (high frequency). On the other hand, if the equation of the system exhibits individual stability for all values that the parameter assumes in the time interval, then the actual system will be stable under sufficiently small modulus of the derivative of the parametric terms (slowly varying).

Some theorems in classical elastodynamic

This investigation is concerned with various fundamental aspects of the linearized dynamical theory for mechanically homogeneous and isotropic elastic solids. First, the uniqueness and reciprocal theorems of dynamic elasticity are extended to unbounded domains with the aid of a generalized energy identity and a lemma on the prolonged quiescence of the far field, which are established for this purpose. Next, the basic singular solutions of elastodynamics are studied and used to generate systematically Love's integral identity for the displacement field, as well as an associated identity for the field of stress. These results, in conjunction with suitably defined Green's functions, are applied to the construction of integral representations for the solution of the first and second boundary-initial value problem. Finally, a uniqueness theorem for dynamic concentrated-load problems is obtained.

Improving statistical machine translation by classifying and generalizing inflected verb forms

This paper introduces a rule-based classification of single-word and compound verbs into a statistical machine translation approach. By substituting verb forms by the lemma of their head verb, the data sparseness problem caused by highly-inflected languages can be successfully addressed. On the other hand, the information of seen verb forms can be used to generate new translations for unseen verb forms. Translation results for an English to Spanish task are reported, producing a significant performance improvement.

可满足性问题研究

数理逻辑是计算机科学的基础，而逻辑公式的可满足性问题是计算机科学和人工智能领域中的一个著名而又重要的问题。它在计算机科学和人工智能研究中有广泛的应用。本文将重点介绍实际可用的判定算法及其相关技术。 本文的研究分两大方向，分别是命题逻辑的可满足性问题研究和一阶逻辑的可满足性问题研究。命题逻辑的可满足性问题（Satisfiability Problem）是一个历史悠久的问题，一般简称为 SAT问题。SAT 问题的求解算法有两大类，分别是确定性算法和非确定性算法。本文只研究确定性算法的相关内容，尤其是如何进行剪枝。我们充分调研了SAT求解算法和求解工具的相关知识，在此基础上，提出了local Lemma 这个剪枝技术，该技术可以更加充分地挖掘剪枝信息，达到进行更多剪枝的目的。 在一阶逻辑的可满足性问题研究方面，本文采取直接搜索可行的一阶逻辑模型的方法研究有限论域上的一阶逻辑的可满足性问题。该方法本质上就是深度优先的回溯搜索。因此，我们的研究重点就是如何找到问题的更高效的一阶逻辑的表示以及如何采用启发式的方式进行剪枝。在这个问题上，我的主要工作有两个：一个是模型搜索中适用于谓词的同构消去技术，包括Row by Row策略和Ramsey Number 策略两个技术；另一个是 DASH（Decision Assignment Scheme Heuristic），用来在生成有限模型的时候边搜索边消除同构子空间。DASH 能用近乎零代价保证输出的模型都是互不同构的。这两个技术都是基于有限论域中的元素的固有对称性，换言之，就是需要有限论域中的元素是两两可交换的。 在已有的成果的基础上，我们又尝试使用它们去求解一些数学中的实际问题，如拟群拉丁方，有限射影平面，正交拉丁方（组）等。我们给出了在这几个方面的一些尝试和初步结果，包括一个重要的定理和若干效率提高了几个数量级的改进。 值得一提的是，和马菲菲共同提出的横截矩阵（Transversal Matrix）概念是一个新颖的成果，使得正交拉丁方的表示和求解取得了明显的改进。在这个概念的基础上，进一步给出了几个定理，进行了理论上的拓展。实验数据表明，我们的求解途径和技术能有效解决拉丁方相关的问题。

SAT和DSOLS问题的研究

约束可满足性问题（Constraint Satisfaction Problem,CSP）是在人工智能领域被广泛研究的一类问题。对CSP问题的研究有两种重要的思路：一种思路是用统一的模型来表示CSP，然后用针对这个统一模型的通用工具进行求解；另外一种思路是针对不同的CSP问题开发专门工具，设计不同的算法和数据结构来求解。 本文研究了两个CSP问题：SAT(SATisfiability problem)和DSOLS(DoublySelf-Orthogonal Latin Squares)。CSP可以方便的转换为SAT来求解，因此对SAT的研究对很多问题具有重大意义。本文介绍了当前流行的SAT solver的一些技术，也提出一种新的搜索空间裁剪策略Local Lemma。DSOLS是一种具有特定性质的拉丁方，本文对它的研究不仅仅因为它的应用意义。更重要的是它作为一个特定的CSP问题，可以用来比较通用工具和专门工具的优劣。本文尝试了把DSOLS转化为SAT求解，也试过用一般CSP的思路来求解，最后提出了一种针对性的高效算法并开发了一个专门工具DSOLver，用这个工具证明了一个开放问题：DSOLS(10)不存在。

Tripogon debilis (Poaceae), a new species from western China

A new species of Tripogon from western China (Sichuan Province), T. debilis L. B. Cai, is described and illustrated. This species is similar to both T. chinensis (Franchet) Hackel and T sichuanicus S. M. Phillips & S. L. Chen, but distinguished from these two species by its pendent pi spikes, relatively tong glumes and lemma awns, denticulate upper glumes, and its paleas strikingly shorter than the lemmas.

Robust Identification of Shared Losses Using End-to-End Unicast Probes

ERRATA: We present corrections to Fact 3 and (as a consequence) to Lemma 1 of BUCS Technical Report BUCS-TR-2000-013 (also published in IEEE INCP'2000)[1]. These corrections result in slight changes to the formulae used for the identifications of shared losses, which we quantify.

Toxicity of manufactured nano-ZnO to Lemna minor

The rapid development of nanotechnology has led to a rise in the large-scale production and commercial use of engineered nano-ZnO. Engineered/manufactured nano-ZnO are applied in a broad range of products such as drugs, paints, cosmetics, abrasive agents and insulators. This can result in the unintended exposure of human beings to nano-ZnO and will inevitably result in the release of nano-ZnO in to the environment. Thus, it is necessary to assess the risk of nano-ZnO to the environment. In this thesis the toxicity of nano-ZnO was analysed using the aquatic, primary producer lesser duckweed (Lemna minor), and the mechanism of toxicity was analysed. Both short-term (one week) and long-term (six weeks) toxicity of nano-ZnO (uncoated) were determined. Results show that the toxicity of nano-ZnO added to the aquatic growth medium increases with increasing concentration and that toxicity accumulates with exposure time. A study of nano-ZnO dissolution reveals that the main reason for nano-ZnO toxicity on Lemna minor is the release of Zn ions. Nano-ZnO dissolution is pH dependent, and toxicity matches the release of Zn2+. Functional coating materials are commonly added to nano-ZnO particles to improve specific industrial applications. To test if coating materials contribute to nano-ZnO toxicity on lesser duckweed, the effect of silane coupling agent (KH550) coated nano-ZnO on Lemma minor was investigated. Results show that coating can decrease the release of Zn ions, which reduces toxicity to Lemna minor, in contrast to uncoated particles. Another commonly hypothesized reason for nano-ZnO toxicity is the formation of Reactive Oxygen Species (ROS) on the particles surface. As part of this thesis, the ROS formation induced by nano-ZnO was studied. Results show that nano-ZnO catalyse ROS formation and this can negatively affect duckweed growth. In conclusion, this work has detailed potentially toxic effects of nano-ZnO on Lemna minor. This study has also provides references for future research, and informs regulatory testing for nanoparticle toxicity. Specifically, the outcomes of this study emphasize the importance of exposure time, environmental parameters and coating material when analysing NPs toxicity. Firstly, impacts of longer exposure time should be studied. Secondly, environmental parameters such as pH and medium-composition need to be considered when investigating NPs toxicity. Lastly, coating of NPs should always be considered in the context of NPs toxicity, and similar NPs with different coatings require separate toxicity tests.

A theory of hypoellipticity and unique ergodicity for semilinear stochastic PDEs

We present a theory of hypoellipticity and unique ergodicity for semilinear parabolic stochastic PDEs with "polynomial" nonlinearities and additive noise, considered as abstract evolution equations in some Hilbert space. It is shown that if Hörmander's bracket condition holds at every point of this Hilbert space, then a lower bound on the Malliavin covariance operatorμt can be obtained. Informally, this bound can be read as "Fix any finite-dimensional projection on a subspace of sufficiently regular functions. Then the eigenfunctions of μt with small eigenvalues have only a very small component in the image of Π." We also show how to use a priori bounds on the solutions to the equation to obtain good control on the dependency of the bounds on the Malliavin matrix on the initial condition. These bounds are sufficient in many cases to obtain the asymptotic strong Feller property introduced in [HM06]. One of the main novel technical tools is an almost sure bound from below on the size of "Wiener polynomials," where the coefficients are possibly non-adapted stochastic processes satisfying a Lips chitz condition. By exploiting the polynomial structure of the equations, this result can be used to replace Norris' lemma, which is unavailable in the present context. We conclude by showing that the two-dimensional stochastic Navier-Stokes equations and a large class of reaction-diffusion equations fit the framework of our theory.