Coupled-expanding maps and one-sided symbolic dynamical systems

This paper studies relationships between coupled-expanding maps and one-sided symbolic dynamical systems. The concept of coupled-expanding map is extended to a more general one: coupled-expansion for a transitive matrix. It is found that the subshift for a transitive matrix is strictly coupled-expanding for the matrix in certain disjoint compact subsets; the topological conjugacy of a continuous map in its compact invariant set of a metric space to a subshift for a transitive matrix has a close relationship with that the map is strictly coupled-expanding for the matrix in some disjoint compact subsets. A certain relationship between strictly coupled-expanding maps for a transitive matrix in disjoint bounded and closed subsets of a complete metric space and their topological conjugacy to the subshift for the matrix is also obtained. Dynamical behaviors of subshifts for irreducible matrices are then studied and several equivalent statements to chaos are obtained; especially, chaos in the sense of Li–Yorke is equivalent to chaos in the sense of Devaney for the subshift, and is also equivalent to that the domain of the subshift is infinite. Based on these results, several new criteria of chaos for maps are finally established via strict coupled-expansions for irreducible transitive matrices in compact subsets of metric spaces and in bounded and closed subsets of complete metric spaces, respectively, where their conditions are weaker than those existing in the literature.     

On Primitive Cellular Algebras

First we define and study the exponentiation of a cellular algebra by a permutation group that is similar to the corresponding operation (the wreath product in primitive action) in permutation group theory. Necessary and sufficient conditions for the resulting cellular algebra to be primitive and Schurian are given. This enables us to construct infinite series of primitive non-Schurian algebras. Also we define and study, for cellular algebras, the notion of a base, which is similar to that for permutation groups. We present an upper bound for the size of an irredundant base of a primitive cellular algebra in terms of the parameters of its standard representation. This produces new upper bounds for the order of the automorphism group of such an algebra and in particular for the order of a primitive permutation group. Finally, we generalize to 2-closed primitive algebras some classical theorems for primitive groups and show that the hypothesis for a primitive algebra to be 2-closed is essential. Bibliography: 16 titles.     

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.     

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.     

An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear global optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as in generating surrogate constraints, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find high quality solutions for the NP-hard linear ordering problem, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in the reference set. We also use a tracking process that generates solution statistics disclosing the nature of combinations and the ranks of antecedent solutions that produced the best final solutions. Extensive computational experiments with more than 300 instances establishes the effectiveness of our procedure in relation to approaches previously identified to be best.     

Adjoint Coexhausters in Nonsmooth Analysis and Extremality Conditions

In the classical (“smooth”) mathematical analysis, a differentiable function is studied by means of the derivative (gradient in the multidimensional space). In the case of nondifferentiable functions, the tools of nonsmooth analysis are to be employed. In convex analysis and minimax theory, the corresponding classes of functions are investigated by means of the subdifferential (it is a convex set in the dual space), quasidifferentiable functions are treated via the notion of quasidifferential (which is a pair of sets). To study an arbitrary directionally differentiable function, the notions of upper and lower exhausters (each of them being a family of convex sets) are used. It turns out that conditions for a minimum are described by an upper exhauster, while conditions for a maximum are stated in terms of a lower exhauster. This is why an upper exhauster is called a proper one for the minimization problem (and an adjoint exhauster for the maximization problem) while a lower exhauster will be referred to as a proper one for the maximization problem (and an adjoint exhauster for the minimization problem). The directional derivatives (and hence, exhausters) provide first-order approximations of the increment of the function under study. These approximations are positively homogeneous as functions of direction. They allow one to formulate optimality conditions, to find steepest ascent and descent directions, to construct numerical methods. However, if, for example, the maximizer of the function is to be found, but one has an upper exhauster (which is not proper for the maximization problem), it is required to use a lower exhauster. Instead, one can try to express conditions for a maximum in terms of upper exhauster (which is an adjoint one for the maximization problem). The first to get such conditions was Roshchina. New optimality conditions in terms of adjoint exhausters were recently obtained by Abbasov. The exhauster mappings are, in general, discontinuous in the Hausdorff metric, therefore, computational problems arise. To overcome these difficulties, the notions of upper and lower coexhausters are used. They provide first-order approximations of the increment of the function which are not positively homogeneous any more. These approximations also allow one to formulate optimality conditions, to find ascent and descent directions (but not the steepest ones), to construct numerical methods possessing good convergence properties. Conditions for a minimum are described in terms of an upper coexhauster (which is, therefore, called a proper coexhauster for the minimization problem) while conditions for a maximum are described in terms of a lower coexhauster (which is called a proper one for the maximization problem). In the present paper, we derive optimality conditions in terms of adjoint coexhausters.     

Finite convergence of algorithms for nonlinear programs and variational inequalities

Algorithms for nonlinear programming and variational inequality problems are, in general, only guaranteed to converge in the limit to a Karush-Kuhn-Tucker point, in the case of nonlinear programs, or to a solution in the case of variational inequalities. In this paper, we derive sufficient conditions for nonlinear programs with convex feasible sets such that any convergent algorithm can be modified, by adding a convex subproblem with a linear objective function, to guarantee finite convergence in a generalized sense. When the feasible set is polyhedral, the subproblem is a linear program and finite convergence is obtained. Similar results are also developed for variational inequalities.The research of the first author was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173.The authors are indebted to Professors Olvi Mangasarian, Garth McCormick, Jong-Shi Pang, Hanif Sherali, and Hoang Tuy for helpful comments and suggestions and to two anonymous referees for constructive remarks and for bringing to their attention the results in Refs. 13 and 14.     

The Number 71.428571 in Hindu Cosmology

Zimmer, in his 1962 book, Myths and Symbols in Indian Art and Civilization, speculates that the number 14, used to divide a kalpa into manvantaras, was chosen in an attempt to reconcile a mahayuga chronology with a tradition of flood heroes. Each manvantara was divided by 71 and an unspecified fraction to produce the mahayuga. The purpose of this research was to find this fraction and discover the reason for its use. The repeating cyclic fraction, 1/7, provides a plausible explanation for use of the number 71.428571 (71 and 3/7) in cosmology; for 22/7 as a value forπ and for concepts of time and circle division related to breaths per minute. The discovery of cyclic decimal fractions by Vedic scholars likely contributed to cyclic theories of cosmology and specifically to the concept of infinity in mathematics.     

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.     

A new hybrid method for solving a generalized equilibrium problem, solving a variational inequality problem and obtaining common fixed points in Banach spaces, with applications

The purpose of this paper is to prove by using a new hybrid method a strong convergence theorem for finding a common element of the set of solutions for a generalized equilibrium problem, the set of solutions for a variational inequality problem and the set of common fixed points for a pair of relatively nonexpansive mappings in a Banach space. As applications, we utilize our results to obtain some new results for finding a solution of an equilibrium problem, a fixed point problem and a common zero-point problem for maximal monotone mappings in Banach spaces.     

Where to treat the older patient? Can Markov models help us better understand the relationship between hospital and community care?

We have previously used Markov models to describe movements of patients between hospital states; these may be actual or virtual and described by a phase-type distribution. Here we extend this approach to a Markov reward model for a healthcare system with Poisson admissions and an absorbing state, typically death. The distribution of costs is evaluated for any time and expressions derived for the mean and variances of costs. The average cost at any time is then determined for two scenarios: the Therapeutic and Prosthetic models, respectively. This example is used to illustrate the idea that keeping acute patients longer in hospital to ensure fitness for discharge, may reduce costs by decreasing the number of patients that become long-stay. In addition we develop a Markov Reward Model for a healthcare system including states, where the patient is in hospital, and states, where the patient is in the community. In each case, the length of stay is described by a phase-type distribution, thus enabling the representation of durations and costs in each phase within a Markov framework. The model can be used to determine costs for the entire system thus facilitating a systems approach to the planning of healthcare and a holistic approach to costing. Such models help us to assess the complex relationship between hospital and community care.     

Painlevé analysis of nonlinear evolution equations—an algorithmic method

This paper refines existing techniques into an algorithmic method for deriving the generalization of a Lax Pair directly from a general integrable nonlinear evolution equation via the use of truncated Painlevé expansions. The resulting algorithm is also applicable to multicomponent integrable systems, and is thus expected to be of great value for complicated variants of such systems in various applications areas. Although a related method has existed for simple scalar integrable evolution equations for many years now, nevertheless no systematic procedure has been given that would work in general for scalar as well as for multicomponent systems. The method presented here largely systematizes the necessary operations in applying the Painlevé method to a general integrable evolution equation or system of equations. We demonstrate that by following the concept of enforcing integrability at each step (referred to here as the Principle of Integrability), one is led to an appropriate generalization of a Lax Pair, although perhaps in nonlinear form, called a “Lax Complex”. One new feature of this procedure is that it utilizes, as needed, a technique from the well-known Estabrook–Wahlquist method for determining necessary integrating factors. The end result of this procedure is to obtain a Lax Complex, whose integrability condition will contain the original evolution equation as a necessary condition. This in itself is sufficient to ensure that the Lax Complex may be used to construct Bäcklund solutions of the evolution equation, to obtain Darboux Transformations, and also to obtain Hirota’s tau functions, in a manner analogous to the procedure for single component systems. The additional problem of finding a general procedure for the linearization of any Lax Complex is not treated in this paper. However, we do demonstrate that a particular technique, which can be derived self-consistently from the Painlevé–Bäcklund equations, has proven to be sufficient so far. The Nonlinear Schrödinger equation is used to illustrate the method, and then the method is applied to obtain, for the first time via the Painlevé method, a Lax Complex for the vector Manakov system. Limitations in the algorithm remain, especially for cases with more than one principal branch, and these are briefly mentioned as directions for future work.     

Patterns generated by mth-order Markov chains

We derive an expression for the expected time for a pattern to appear in higher-order Markov chains with and without a starting sequence. This yields a result for directly calculating, the first time one of a collection of patterns appears, in addition to the probability, for each pattern, that it is the first to appear.     

Computer Forecasting of Australian Rules Football for a Daily Newspaper

An exponential smoothing technique operating on the margins of victory was used to predict the results of Australian Rules football matches for a Melbourne daily newspaper from 1981-86 and again for a competitor in 1991-92. An initial ‘quick and dirty’ program used only a factor for team ability and a common home ground advantage to predict winning margins. Probabilities of winning were accumulated to predict a final ladder, with a simulation to predict chances of teams finishing in any position. Changes to the competition forced a more complicated approach, and the current version uses several parameters which allow for ability, team/ground interaction, team interaction, and a tendency for team ability to regress towards the mean between seasons. A power method is used to place greater weight on the errors in closer matches, and errors across the win-lose boundary. While simple methods were used originally, the Hooke and Jeeves method was used in optimizing the parameters of the current model. Both the original model and the improved version performed at the level of expert tipsters.     

A polychromatic inhomogeneity indicator in an unknown medium for an X-ray tomography problem

We pose and study an X-ray tomography problem, which is an inverse problem for the transport differential equation, making account for particle absorption by a medium and single scattering. The statement of the problem corresponds to a stage-by-stage probing of the unknown medium common in practice. Another step towards a more realistic problem is the use of integrals over energy of the density of emanating radiation flux as the known data, in contrast to specifying the flux density for every energy level, as it is customary in tomography. The required objects are the discontinuity surfaces of the coefficients of the equation, which corresponds to searching for the boundaries between various substances contained in the medium. We prove a uniqueness theorem for the solution under quite general assumptions and a condition ensuring the existence of the required surfaces. The proof is rather constructive in character and suitable for creating a numerical algorithm.     

A higher-order Godunov method for modeling finite deformation in elastic-plastic solids

In this paper we develop a first-order system of conservation laws for finite deformation in solids, describe its characteristic structure, and use this analysis to develop a second-order numerical method for problems involving finite deformation and plasticity. The equations of mass, momentum, and energy conservation in Lagrangian and Eulerian frames of reference are combined with kinetic equations of state for the stress and with caloric equations of state for the internal energy, as well as with auxiliary equations representing equality of mixed partial derivatives of the deformation gradient. Particular attention is paid to the influence of a curl constraint on the deformation gradient, so that the characteristic speeds transform properly between the two frames of reference. Next, we consider models in rate-form for isotropic elastic-plastic materials with work-hardening, and examine the circumstances under which these models lead to hyperbolic systems for the equations of motion. In spite of the fact that these models violate thermodynamic principles in such a way that the acoustic tensor becomes nonsymmetric, we still find that the characteristic speeds are always real for elastic behavior, and essentially always real for plastic response. These results allow us to construct a second-order Godunov method for the computation of three-dimensional displacement in a one-dimensional material viewed in the Lagrangian frame of reference. We also describe a technique for the approximate solution of Riemann problems in order to determine numerical fluxes in this algorithm. Finally, we present numerical examples of the results of the algorithm.     

The effect of demand uncertainty in a price-setting newsvendor model

We study the effects of demand uncertainty on optimal decisions and the expected profit of a price-setting newsvendor who faces either additive or multiplicative stochastic demand. Our key findings are as follows. (1) A stochastically larger demand may even lead to a smaller order size and a lower profit when price is endogenous. (2) A stochastically larger demand will lead to a higher selling price in general for the additive demand case but to a lower selling price under certain mild conditions for the multiplicative demand case. Moreover, if the larger demand can be represented by a transformation of the lower one, it will lead to a higher expected profit for both demand cases. However, except for the setting with a zero shortage cost, a larger demand may not necessarily result in a higher expected profit in general. (3) Under mild conditions, a less variable demand will lead to a higher and lower selling price for the additive and multiplicative demand case, respectively, and a higher expected profit for both cases.     

Equilibrium solutions for multiobjective bimatrix games incorporating fuzzy goals

Equilibrium solutions in terms of the degree of attainment of a fuzzy goal for games in fuzzy and multiobjective environments are examined. We introduce a fuzzy goal for a payoff in order to incorporate ambiguity of human judgments and assume that a player tries to maximize his degree of attainment of the fuzzy goal. A fuzzy goal for a payoff and the equilibrium solution with respect to the degree of attainment of a fuzzy goal are defined. Two basic methods, one by weighting coefficients and the other by a minimum component, are employed to aggregate multiple fuzzy goals. When the membership functions are linear, computational methods for the equilibrium solutions are developed. It is shown that the equilibrium solutions are equal to the optimal solutions of mathematical programming problems in both cases. The relations between the equilibrium solutions for multiobjective bimatrix games incorporating fuzzy goals and the Pareto-optimal equilibrium solutions are considered.     

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.     

A unified approach to error bounds for structured convex optimization problems

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.