Stackelberg–Nash exact controllability for the Kuramoto–Sivashinsky equation

This paper deals with a hierarchical control problem for the Kuramoto–Sivashinsky equation following a Stackelberg–Nash strategy. We assume that there is a main control, called the leader, and two secondary controls, called the followers. The leader tries to drive the solution to a prescribed target and the followers intend to be a Nash equilibrium for given functionals. It is known that this problem is equivalent to a null controllability result for an optimality system consisting of three non-linear equations. One of the novelties is a new Carleman estimate for a fourth-order equation with right-hand sides in Sobolev spaces of negative order, which allows to relax some geometric conditions for the observation sets for the followers.     

Searching for a set of correlated patterns

New algorithms for searching simultaneously for a set of patterns in a text are suggested, for the special case where these patterns are correlated and have a common substring. This is then extended to the case where it could be more profitable to look for more than a single overlap, and a problem related to the generalization of this idea is shown to be NP-complete. Experimental results suggest that for this particular application, the suggested algorithm yields significant improvements over previous methods.     

Necessary and Sufficient Conditions for Mcshane’s Identity and Variations

Greg McShane introduced a remarkable identity for lengths of simple closed geodesics on the once punctured torus with a complete, finite volume hyperbolic structure. Bowditch later generalized this and gave sufficient conditions for the identity to hold for general type-preserving representations of a free group on two generators Γ to SL(2,C), this was further generalized by the authors to obtain sufficient conditions for a generalized McShane’s identity to hold for arbitrary (not necessarily type-preserving) non-reducible representations in Tan et al. (Submitted). Here we extend the above by giving necessary and sufficient conditions for the generalized McShane identity to hold (Akiyoshi, Miyachi and Sakuma had proved it for type-preserving representations). We also give a version of Bowditch’s variation of McShane’s identity to once-punctured torus bundles, in the case where the monodromy is generated by a reducible element, and provide necessary and sufficient conditions for the variations to hold.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

有横贯的Hall-型判定定理

给出了任意集上的一个集族有横贯的一些Hall-型判定定理,回答了Welsh关于相应的无限情形的公开问题,即对于无限情况,找到一个集族有横贯的充要条件.     

An Itô formula for a family of stochastic integrals and related Wong–Zakai theorems

The aim of this paper is to generalize two important results known for the Stratonovich and Itô integrals to any stochastic integral obtained as limit of Riemann sums with arbitrary evaluating point: the ordinary chain rule for certain nonlinear functions of the Brownian motion and the Wong–Zakai approximation theorem. To this scope we begin by introducing a new family of products for smooth random variables which reduces for specific choices of a parameter to the pointwise and to the Wick products. We show that each product in that family is related in a natural way to a precise choice of the evaluating point in the above mentioned Riemann sums and hence to a certain notion of stochastic integral. Our chain rule relies on a new probabilistic representation for the solution of the heat equation while the Wong–Zakai type theorem follows from a reduction method for quasi-linear SDEs together with a formula of Gjessing’s type.     

Optimal Control and Stabilization for Some Fisher-Like Models

This article concerns optimal control and stabilization for some Fisher-like models with control acting in a subdomain ω. We investigate the optimal position of ω for some optimal harvesting problems. First, we refer to a logistic model with diffusion. We remember the necessary optimality conditions, and then obtain an iterative method to improve the position of ω for the optimal harvesting effort (for a simplified model without logistic term). Next, we consider the null stabilization for a controlled Fisher model and obtain a descent method to improve the position of ω in order to get a faster stabilization to zero. Numerical tests illustrating the effect of the last method are given. We also studied the null stabilization for a prey-predator system and have reduced it to the study of the null stabilizability for a related Fisher model.     

A minimization method for the sum of a convex function and a continuously differentiable function

This paper presents a method for finding the minimum for a class of nonconvex and nondifferentiable functions consisting of the sum of a convex function and a continuously differentiable function. The algorithm is a descent method which generates successive search directions by solving successive convex subproblems. The algorithm is shown to converge to a critical point.The authors wish to express their appreciation to the referees for their careful review and helpful comments.     

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.      

Proper exhausters and coexhausters in nonsmooth analysis

There exist many tools to analyze nonsmooth functions. For convex and max-type functions, the notion of subdifferential is used, for quasidifferentiable functions – that of quasidifferential. By means of these tools, one is able to solve, e.g. the following problems: to get an approximation of the increment of a functional, to formulate conditions for an extremum, to find steepest descent and ascent directions and to construct numerical methods. For arbitrary directionally differentiable functions, these problems are solved by employing the notions of upper and lower exhausters and coexhausters, which are generalizations of such notions of nonsmooth analysis as sub- and superdifferentials, quasidifferentials and codifferentials. Exhausters allow one to construct homogeneous approximations of the increment of a functional while coexhausters provide nonhomogeneous approximations. It became possible to formulate conditions for an extremum in terms of exhausters and coexhausters. It turns out that conditions for a minimum are expressed by an upper exhauster, and conditions for a maximum are formulated via a lower one. This is why an upper exhauster is called a proper one for the minimization problem (and adjoint for the maximization problem) while a lower exhauster is called a proper one for the maximization problem (and adjoint for the minimization problem). The conditions obtained provide a simple geometric interpretation and allow one to find steepest descent and ascent directions. In this article, optimization problems are treated by means of proper exhausters and coexhausters.     

Repeated Richardson extrapolation applied to the two-dimensional Laplace equation using triangular and square grids

The focus of this work is to verify the efficiency of the Repeated Richardson Extrapolation (RRE) to reduce the discretization error in a triangular grid and to compare the result to the one obtained for a square grid for the two-dimensional Laplace equation. Two different geometries were employed: the first one, a unitary square domain, was discretized into a square or triangular grid; and the second, a half square triangle, was discretized into a triangular grid. The methodology employed used the following conditions: the finite volume method, uniform grids, second-order accurate approximations, several variables of interest, Dirichlet boundary conditions, grids with up to 16,777,216 nodes for the square domain and up to 2097,152 nodes for the half square triangle domain, multigrid method, double precision, up to eleven Richardson extrapolations for the first domain and up to ten Richardson extrapolations for the second domain. It was verified that (1) RRE is efficient in reducing the discretization error in a triangular grid, achieving an effective order of approximately 11 for all the variables of interest for the first geometry; (2) for the same number of nodes and with or without RRE, the discretization error is smaller in a square grid than in a triangular grid; and (3) the magnitude of the numerical error reduction depends on, among other factors, the variable of interest and the domain geometry.     

Structural models in consumer credit

We propose a structural credit risk model for consumer lending using option theory and the concept of the value of the consumer’s reputation. Using Brazilian empirical data and a credit bureau score as proxy for creditworthiness we compare a number of alternative models before suggesting one that leads to a simple analytical solution for the probability of default. We apply the proposed model to portfolios of consumer loans introducing a factor to account for the mean influence of systemic economic factors on individuals. This results in a hybrid structural-reduced-form model. And comparisons are made with the Basel II approach. Our conclusions partially support that approach for modelling the credit risk of portfolios of retail credit.     

A necessary and sufficient condition for Pareto-optimal security strategies in multicriteria matrix games

In this paper, a scalar game is derived from a zero-sum multicriteria matrix game, and it is proved that the solution of the new game with strictly positive scalarization is a necessary and sufficient condition for a strategy to be a Pareto-optimal security strategy (POSS) for one of the players in the original game. This is done by proving that a certain set, which is the extension of the set of security level vectors in the criterion function space, is convex and polyhedral. It is also established that only a finite number of scalarizations are necessary to obtain all the POSS for a player. An example is included to illustrate the main steps in the proof.This work was done while the author was a Research Associate in the Department of Electrical Engineering at the Indian Institute of Science and was financially supported by the Council of Scientific and Industrial Research, Delhi, India.The author wishes to express his gratefulness to Professor U. R. Prasad for helpful discussions and to two anonymous referees for suggestions which led to an improved presentation.     

The asymptotic variance of a time average in a birth-death process

The variance of a time average is important for planning, running and interpreting experiments. This paper derives a simple method to find this variance for the case of a Markov process. This method is then applied to obtain the variance of a time average for the case of a birth-death process.     

Supporting offshoring and nearshoring decisions for mass customization manufacturing processes

Offshore countries attract companies for a possible relocation of production processes through extremely low worker wages. Particularly, mass production processes seem to be highly appropriate for a relocation. However, while the impact of wage reductions can be directly estimated, an appropriate determination of additional cost consequences proves to be a complex task. For instance, on account of lower education standards and higher fluctuation rates, the average worker skills in offshore countries are often significantly lower than in high-wage countries like the United States. In order to appropriately analyze and evaluate the resulting tradeoff between wages and worker skills for mass customization manufacturing systems, this paper introduces a new approach that comprises a detailed mixed-model assembly line balancing. This approach provides a direct comparison of the estimated variable manufacturing costs by generating a country-dependent line layout for all competing locations. In order to validate the efficiency of the balancing approach and, in particular, derive general implications for management, several test series with various country configurations were executed. First, by attaining improvement rates of up to 40%, the capability of a generated Tabu Search procedure for finding appropriate line layouts was proven. Second, as the main result, the complexity of the variant program was identified as a crucial factor for offshoring decisions since it substantially affects variable manufacturing costs. This was particularly proven for countries with low worker skills, which attract offshoring/nearshoring through exceptionally low labor costs. Hence, companies that consider outsourcing production systems to those countries are strongly hold to examine these decisive effects thoroughly. Regarding this, offshoring becomes very promising for manufacturing processes characterized by a moderate variant complexity level.     

Propagation of a plane wave to a materially uniform but inhomogeneous body

We produce the equations of small deformations superimposed upon large for materially uniform but inhomogeneous bodies and specialize to an isotropic material and to a homogeneous finite elastic deformation. By assuming the small deformation to be a plane wave, a set of equations for the amplitude of the wave is produced which is accompanied by an additional set of conditions. By requiring a non-trivial solution for the amplitude, we obtain the secular equation and from it a set of necessary and sufficient conditions for having a real wave speed. The second set of conditions that have to be satisfied is due to the materials inhomogeneity. Essentially, the present analysis enhances the approach of Hayes and Rivlin for materially uniform but inhomogeneous bodies. The outcome is that for such bodies the restrictions on the constitutive law for having real wave speeds for an isotropic material subjected to a pure homogeneous deformation involves the field of the inhomogeneity as well.     

A sufficient condition and a necessary condition for the diffusion approximations of multiclass queueing networks under priority service disciplines

We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition.     

The Size of a Political Club

We investigate the size of a political club that admits new members according to a rule that if only a few members vote against admission the candidate joins, but the members who voted against admission leave. For the simplest ergodic case, we use a modified Bessel function to give the generating function for the invariant distribution of the club size. This also allows us to give asymptotics for the moments as the probability of voting for admission approaches 1 and to prove global and local central limit theorems. We also calculate the mean recurrent time and determine formulas for calculating first passage times. We then show that for an expanded set of cases the club size process approaches the Ornstein-Uhlenbeck process as the probability of voting for admission approaches 1. This means that the club size will approach a Gaussian distribution for a wide set of formal and informal admission rules. Finally, we show a comparison between theoretical results and simulation runs for two cases.     

Cooperative facility location games

The location of facilities in order to provide service for customers is a well-studied problem in the operations research literature. In the basic model, there is a predefined cost for opening a facility and also for connecting a customer to a facility, the goal being to minimize the total cost. Often, both in the case of public facilities (such as libraries, municipal swimming pools, fire stations, … ) and private facilities (such as distribution centers, switching stations, … ), we may want to find a ‘fair’ allocation of the total cost to the customers—this is known as the cost allocation problem. A central question in cooperative game theory is whether the total cost can be allocated to the customers such that no coalition of customers has any incentive to build their own facility or to ask a competitor to service them. We establish strong connections between fair cost allocations and linear programming relaxations for several variants of the facility location problem. In particular, we show that a fair cost allocation exists if and only if there is no integrality gap for a corresponding linear programming relaxation; this was only known for the simplest unconstrained variant of the facility location problem. Moreover, we introduce a subtle variant of randomized rounding and derive new proofs for the existence of fair cost allocations for several classes of instances. We also show that it is in general NP-complete to decide whether a fair cost allocation exists and whether a given allocation is fair.     

Multiround Unconditionally Secure Authentication

Authentication codes are used to protect communication against a malicious adversary. In this paper we investigate unconditionally secure multiround authentication schemes. In a multiround scheme a message is authenticated by passing back and forth several codewords between the sender and receiver. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. We prove the security for a 3-round scheme and give a construction for the 3-round scheme based on Reed-Solomom codes. This construction has a very small key size for even extremely large messages. Furthermore, a secure scheme for an arbitrary number of rounds is given. We give a new upper bound for the keys size of an n-round scheme.