On a decision rule using dichotomies for identifying the nonnegligible parameter in certain linear models

Consider the class of linear models (with uncorrelated observation, each having variance σ²), in which it is known that at most k (location) parameters are negligible, but it is not known which are negligible. The problem is to identify the nonnegligible parameters. In this paper, for k = 1, and under certain restrictions on the model, a technique is developed for solving this problem, which has the feature of requiring (in an information theoretic sense) the minimum amount of computation. (It can “search through” 2^m objects, using m “steps.”) The technique consists of dichotomizing the set of parameters (one known subset possibly containing the nonnegligible element, and the other not), using chi-square variables. A method for computing the probability that the correct parameter is identified, is presented, and an important application to factorial search designs is established.     

A minimalist two-level foundation for constructive mathematics

We present a two-level theory to formalize constructive mathematics as advocated in a previous paper with G. Sambin.One level is given by an intensional type theory, called Minimal type theory. This theory extends a previous version with collections.The other level is given by an extensional set theory that is interpreted in the first one by means of a quotient model.This two-level theory has two main features: it is minimal among the most relevant foundations for constructive mathematics; it is constructive thanks to the way the extensional level is linked to the intensional one which fulfills the “proofs-as-programs” paradigm and acts as a programming language.     

Applying fuzzy weighted average approach to evaluate office layouts with Feng–Shui consideration

Office layout is an important issue, especially in China and the Asian countries, where the Feng–Shui theory frequently plays a vital role. Yet, in the literature, Feng–Shui theory has seldom been discussed. Another problem is the imprecise or vague satisfaction level of the linguistic expression used in this theory. In this article, the fuzzy set theory is applied to deal with this aspect of the problem. Using an improved and efficient fuzzy weighted average (EFWA) algorithm, which has been shown to be more advantageous than the existing FWA algorithms, an empirical study of an office-layout design problem with the consideration of Feng–Shui is presented to illustrate the EFWA approach. The results and the criteria developed, based on the interpretation of the Form school concept of the Feng–Shui are reported.     

On factoring an operator using elements of its kernel

A well-known theorem factors a scalar coefficient differential operator given a linearly independent set of functions in its kernel. The goal of this paper is to generalize this useful result to other types of operators. In place of the derivation ? acting on some ring of functions, this paper considers the more general situation of an endomorphism 𝔇 acting on a unital associative algebra. The operators considered, analogous to differential operators, are those which can be written as a finite sum of powers of 𝔇 followed by left multiplication by elements of the algebra. Assume that the set of such operators is closed under multiplication and that a Wronski-like matrix produced from some finite list of elements of the algebra is invertible (analogous to the linear independence condition). Then, it is shown that the set of operators whose kernels contain all of those elements is the left ideal generated by an explicitly given operator. In other words, an operator has those elements in its kernel if and only if it has that generator as a right factor. Three examples demonstrate the application of this result in different contexts, including one in which 𝔇 is an automorphism of finite order.     

Bidders and dispenser: manipulative hypergames in a multinational context

The object of this paper is to present an introduction to the basic ideas of Hypergame Analysis, and to illustrate these by building some models of a particular type of situation.Hypergame Analysis is an extension of the Game-theoretic framework, the purpose of which is to enable one to model situations in which the various parties are not well-informed of each other's preferences and strategies. we take as a basic structure not a single game, but a linked set of ‘perceived’ games: this, in essence, is what constitutes a Hypergame. Misperceptions may arise accidentally or be deliberately induced. Thus, a player may be acting ‘rationally’ relative to the game he perceives, but this game itself may have been ‘set up’ to suit the interests of some other party.The technique is used to explore situations in which several parties (the ‘bidders’) negotiate competitively with another (the ‘dispenser’) who is able to accept whichever bidder's offer is most advantageous to him. In particular, the ability of the dispenser to ‘play off’ one bidder against another is examined. This is related to an account of the siting of new plant by a Multi-National Corporation. Some general implications are suggested: especially, it is argued that to have a reasonable chance of producing adequate forecasts in such difficult situations, modelling techniques must embody at least this degree of conceptual complexity.     

Triangular Matrix Representations

In this paper we develop the theory of generalized triangular matrix representation in an abstract setting. This is accomplished by introducing the concept of a set of left triangulating idempotents. These idempotents determine a generalized triangular matrix representation for an algebra. The existence of a set of left triangulating idempotents does not depend on any specific conditions on the algebras; however, if the algebra satisfies a mild finiteness condition, then such a set can be refined to a “complete” set of left triangulating idempotents in which each “diagonal” subalgebra has no nontrivial generalized triangular matrix representation. We then apply our theory to obtain new results on generalized triangular matrix representations, including extensions of several well known results.     

Local decision making and decision fusion in hierarchical levels

Hierarchical problem solving is preferred when the problem is overwhelmingly complicated. In such a case, the problem should better be analyzed in hierarchical levels. At each level, some temporary solutions are obtained; then a suitable decision fusion technique is used to merge the temporary solutions for the next level. The hierarchical framework proposed in this study depends on reutilization or elimination of previous level local agents that together perform the decisions due to a decision-fusion technique: a performance criterion is set for local agents. The criterion checks the success of agents in their local regions. An agent satisfying this criterion is reutilized in the next level, whereas an agent not successful enough is removed from the agent pool in the next level. In place of a removed agent, a number of new local agents are developed. This framework is applied on a fault detection problem.      

On the Complexity of Equalizing Inequalities

We study two approaches to replace a finite mathematical programming problem with inequality constraints by a problem that contains only equality constraints. The first approach lifts the feasible set into a high-dimensional space by the introduction of quadratic slack variables. We show that then not only the number of critical points but also the topological complexity of the feasible set grow exponentially. On the other hand, the second approach bases on an interior point technique and lifts an approximation of the feasible set into a space with only one additional dimension. Here only Karush–Kuhn–Tucker points with respect to the positive and negative objective function in the original problem give rise to critical points of the smoothed problem, so that the number of critical points as well as the topological complexity can at most double.     

Batched dynamic solutions to decomposable searching problems

The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlog^d−1n + k) time using only O(n) space.     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times

In this work a new heuristic solution technique for the Resource-Constrained Project Scheduling Problem (RCPSP) is proposed. This technique is a hybrid multi-pass method that combines random sampling procedures with a backward–forward method. The impact of each component of the algorithm is evaluated through a step-wise computational analysis which in addition permits the value of their parameters to be specified. Furthermore, the performance of the new technique is evaluated against the best currently available heuristics using a well known set of instances. The results obtained point out that the new technique greatly outperforms both the heuristics and metaheuristics currently available for the RCPSP being thus competitive with the best heuristic solution techniques for this problem.     

The segment projection method for interface tracking

There has recently been important progress in the development of front tracking and level set methods for the numerical simulation of moving interfaces. The segment projection method is a new technique for computational geometry. It can be seen as a compromise between front tracking and level set methods. It is based on the regular mathematical representation of a manifold as an atlas of charts. Each chart or segment is evolved independently by a partial differential equation that is discretized on an Eulerian grid. The connectivity of the segments is handled by an appropriate data structure and by numerical interpolation. The method is presented and its properties are analyzed. Applications to multiphase flow, epitaxial growth, and high‐frequency wave propagation are given. © 2002 Wiley Periodicals, Inc.     

Partitions of a Polytope and Mappings of a Point Set to Facets

Three theorems of this paper generalize previous results of the author on conjectures of A. Bezdek and V.V. Proizvolov. They show the existence of mappings from a given point set to the set of facets of a given polytope that satistfy some special conditions. Developing the same technique, some results on convex polytope partitions are presented, two of them dealing with partitions with prescribed measures of parts. Then we prove a corollary on the existence of a possibly nonconvex polytope with a given set of vertices, containing given points in its interior. We also consider problems of the following type: find an assignment of vectors from a given set to the parts of a given convex partition of ℝⁿ so that the shifts of the parts by their corresponding vectors either do not intersect by interior points or cover ℝⁿ     

A repairing technique for the local search of the job-shop problem

The local search technique has become a widely used tool for solving many combinatorial optimization problems. In the case of the job-shop the implementation of such a technique is not straightforward at all due to the existence of the technological constraints among the operations that belong to the same job. Their presence renders a certain set of schedules infeasible. Consequently, special attention is required when defining optimization algorithms to prevent the possibility of reaching an infeasible schedule during execution. Traditionally, the problem is tackled on the neighborhood level by using only a limited set of moves for which feasibility inherently holds. This paper proposes an alternative way to avoid infeasibility by incorporating a repairing technique into the mechanism for applying moves to a schedule. Whenever an infeasible move is being applied, a repairing mechanism rearranges the underlying schedule in such a way that the feasibility of the move is restored. The possibility of reaching infeasible solutions is, therefore, eliminated on the lowest possible conceptual level. Consequently, neighborhood functions need not to be constrained to a limited set of feasible moves any more.     

On the Asymptotics of Trimmed Best k-Nets

Trimmed best k-nets were introduced in J. A. Cuesta-Albertos, A. Gordaliza and C. Matrán (1998, Statist. Probab. Lett.36, 401–413) as a robustified L_∞-based quantization procedure. This paper focuses on the asymptotics of this procedure. Also, some possible applications are briefly sketched to motivate the interest of this technique. Consistency and weak limit law are obtained in the multivariate setting. Consistency holds for absolutely continuous distributions without the (artificial) requirement of a trimming level varying with the sample size as in J. A. Cuesta-Albertos, A. Gordaliza and C. Matrán (1998, Statist. Probab. Lett.36, 401–413). The weak convergence will be stated toward a non-normal limit law at a O_P(n^−1/3) rate of convergence. An algorithm for computing trimmed best k-nets is proposed. Also a procedure is given in order to choose an appropriate number of centers, k, for a given data set.     

A shape and topology optimization technique for solving a class of linear complementarity problems in function space

A shape and topology optimization driven solution technique for a class of linear complementarity problems (LCPs) in function space is considered. The main motivating application is given by obstacle problems. Based on the LCP together with its corresponding interface conditions on the boundary between the coincidence or active set and the inactive set, the original problem is reformulated as a shape optimization problem. The topological sensitivity of the new objective functional is used to estimate the “topology” of the active set. Then, for local correction purposes near the interface, a level set based shape sensitivity technique is employed. A numerical algorithm is devised, and a report on numerical test runs ends the paper.     

Resolving degeneracy in quadratic programming

A technique for the resolution of degeneracy in an Active Set Method for Quadratic Programming is described. The approach generalises Fletcher's method [2] which applies to the LP case. The method is described in terms of an LCP tableau, which is seen to provide useful insights. It is shown that the degeneracy procedure only needs to operate when the degenerate constraints are linearly dependent on those in the active set. No significant overheads are incurred by the degeneracy procedure. It is readily implemented in a null space format, and no complications in the matrix algebra are introduced.The guarantees of termination provided by [2], extending in particular to the case where round-off error is present, are preserved in the QP case. It is argued that the technique gives stronger guarantees than are available with other popular methods such as Wolfe's method [11] or the method of Goldfarb and Idnani [7].Presented at the 14th International Symposium on Mathematical Programming, Amsterdam, August 5–9, 1991.     

Associative memory approach to the identification of structural and mechanical systems

This paper presents a new method for identification of parameters in nonlinear structural and mechanical systems in which the initial guesses of the unknown parameter vectors may be far from their true values. The method uses notions from the field of artificial neural nets and, using an initial set of training parameter vectors, generates in an adaptive fashion other relevant training vectors to yield identification of the parameter vector in a recursive fashion. The simplicity and power of the technique are illustrated by considering three highly nonlinear systems. It is shown that the technique presented here yields excellent estimates with only a limited amount of response data, even when each element of the set comprising the initial training parameter vectors is far from its true value—in fact, sufficiently far that the usual recursive identification schemes fail to converge.     

Computing tournament solutions using relation algebra and RelView

We describe a simple computing technique for the tournament choice problem. It rests upon relational modeling and uses the BDD-based computer system RelView for the evaluation of the relation-algebraic expressions that specify the solutions and for the visualization of the computed results. The Copeland set can immediately be identified using RelView’s labeling feature. Relation-algebraic specifications of the Condorcet non-losers, the Schwartz set, the top cycle, the uncovered set, the minimal covering set, the Banks set, and the tournament equilibrium set are delivered. We present an example of a tournament on a small set of alternatives, for which the above choice sets are computed and visualized via RelView. The technique described in this paper is very flexible and especially appropriate for prototyping and experimentation, and as such very instructive for educational purposes. It can easily be applied to other problems of social choice and game theory.     

Optimal Covering of Plane Domains by Circles Via Hyperbolic Smoothing

We consider the problem of optimally covering plane domains by a given number of circles. The mathematical modeling of this problem leads to a min–max–min formulation which, in addition to its intrinsic multi-level nature, has the significant characteristic of being non-differentiable. In order to overcome these difficulties, we have developed a smoothing strategy using a special class C^∞ smoothing function. The final solution is obtained by solving a sequence of differentiable subproblems which gradually approach the original problem. The use of this technique, called Hyperbolic Smoothing, allows the main difficulties presented by the original problem to be overcome. A simplified algorithm containing only the essential of the method is presented. For the purpose of illustrating both the actual working and the potentialities of the method, a set of computational results is presented.