On the minimization of quadratic functions with bilinear constraints via augmented Lagrangians

In the present paper, a new set of necessary and sufficient conditions is given for the regulator problem with plant stability in the presence of disturbances. Significant features of these conditions are the simplicity of their statement and the immediacy of their meaning in the context of the geometric approach. The proof is based on arguments which are extensions of those developed in Part 1 for the more restricted problem of disturbance localization by dynamic compensation with stability. The sufficiency of conditions is proved by a constructive procedure, which may be used as part of an actual regulator synthesis method.This research has been supported in part by MPI, Rome, Italy.     

Contact linearization of nondegenerate Monge-Ampère equations

The present paper is devoted to the problem of transforming the classical Monge-Ampère equations to the linear equations by change of variables. The class of Monge-Ampère equations is distinguished from the variety of second-order partial differential equations by the property that this class is closed under contact transformations. This fact was known already to Sophus Lie who studied the Monge-Ampère equations using methods of contact geometry. Therefore it is natural to consider the classification problems for the Monge-Ampère equations with respect to the pseudogroup of contact transformations. In the present paper we give the complete solution to the problem of linearization of regular elliptic and hyperbolic Monge-Ampère equations with respect to contact transformations. In order to solve this problem, we construct invariants of the Monge-Ampère equations and the Laplace differential forms, which involve the classical Laplace invariants as coefficients.     

Revisiting the regulator problem in the geometric approach,part 1, disturbance localization by dynamic compensation

The aim of this paper is to present a new proof of a well-known fundamental set of necessary and sufficient conditions for disturbance localization by dynamic compensation. Due to a more convenient selection of basic definitions and properties, the arguments herein developed are much more concise and straightforward than those already available in the literature. In Part 2 of the paper, the same approach will be extended to the more general problem of regulator synthesis with plant stability, for which necessary and sufficient conditions significantly different from those already known in the literature will be given.This research has been supported in part by MPI, Rome, Italy.     

A note on Marino-Vafa formula

Hodge integrals over moduli spaces of curves appear naturally during the localization procedure in computation of Gromov-Witten invariants. A remarkable formula of Marino-Vafa expresses a generation function of Hodge integrals via some combinatorial and algebraic data seemingly unrelated to these apriori algebraic geometric objects. We prove in this paper by directly expanding the formula and estimating the involved terms carefully that except a specific type all the other Hodge integrals involving up to three Hodge classes can be calculated from this formula. This implies that amazingly rich information about moduli spaces and Gromov-Witten invariants is encoded in this complicated formula. We also give some low genus examples which agree with the previous results in literature. Proofs and calculations are elementary as long as one accepts Mumford relations on the reductions of products of Hodge classes.     

The complexity of the word problems for commutative semigroups and polynomial ideals

Any decision procedure for the word problems for commutative semigroups and polynomial deals inherently requires computational storage space growing exponentially with the size of the problem instance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.     

Conservative finite-difference scheme for the problem of propagation of a femtosecond pulse in a photonic crystal with combined nonlinearity

A conservative finite-difference scheme is constructed for the problem of propagation of a light pulse in a one-dimensional nonlinear photonic crystal with combined nonlinearity. The invariants of the corresponding differential problem and their difference analogues are given. The scheme is compared with those based on the widespread splitting method. For combined cubic and quadratic nonlinearity in photonic crystal layers, it is shown that the classical splitting method is ineffective, since it requires time steps that are smaller by one or more orders of magnitude. The finite-difference scheme proposed conserves the propagation invariants, which cannot be achieved for splitting schemes even on considerably finer grids. Nonreflecting conditions substantially improve the efficiency of conservative finite-difference schemes as applied to the simulation of complex nonlinear effects in photonic crystals, which require much smaller steps in space and time than those used in the case of linear propagation. The simulation is based on the approach proposed by the authors for the given class of problems.     

Inferring null join dependencies in relational databases

The inference problem for data dependencies in relational databases is the problem of deciding whether a set of data dependencies logically implies another data dependency. For join dependencies (JDs), the inference problem has been extensively studied by utilising the well-known chase procedure. We generalise JDs to null join dependencies (NJDs) that hold in relations which may contain null values. In our model for incomplete information we allow only a single unmarked null value denoted bynull. This allows us to solve the inference problem for NJDs by extending the chase procedure to the or-chase procedure. In order to define the or-chase procedure we generalise relations with nulls to or-relations which contain a limited form of disjunctive information. The main result of the paper shows that the inference problem for NJDs, including embedded NJDs (which are a special case of NJDs), is decidable; this is realised via the or-chase procedure.     

Milnor link invariants and quantum 3-manifold invariants

Let be the 3-manifold invariant of Le, Murakami and Ohtsuki. We show that , where denotes terms of degree , if M is a homology 3-sphere obtained from by surgery on an n-component Brunnian link whose Milnor -invariants of length vanish.?We prove a realization theorem which is a partial converse to the above theorem.?Using the Milnor filtration on links, we define a new bifiltration on the vector space with basis the set of oriented diffeomorphism classes of homology 3-spheres. This includes the Milnor level 2 filtration defined by Ohtsuki. We show that the Milnor level 2 and level 3 filtrations coincide after reindexing. Received: October 23, 1998.     

Monodromy Invariants – From Symplectic to Smooth Manifolds

Recently, together with Auroux and Donaldson, we have introduced some new invariants of four-dimensional symplectic manifolds. Building on the Moishezon–Teicher braid factorization techniques, we show how to compute fundamental groups of compliments to a ramification curve of generic projection. We also show that these fundamental groups are only homology invariants and outline the computations in some examples.Demonstrating the ubiquity of algebra, we go further and, using Braid factorization, we compute invariants of a derived category of representations of the quiver associated with the Fukaya–Seidel category of the vanishing cycles of a Lefschetz pencil and a structure of a symplectic four-dimensional manifold. This idea is suggested by the homological mirror symmetry conjecture of Kontsevich. We do not use it in our computations, although everything is explicit. We outline a procedure for finding homeomorphic, nonsymplectomorphic, four-dimensional symplectic manifolds with the same Saiberg–Witten invariants. This procedure defines invariants in the smooth category as well.     

Involutive moving frames II; The Lie-Tresse theorem

This paper continues the project, begun in [1], of harmonizing Cartan's classical equivalence method and the modern equivariant moving frame in a framework dubbed involutive moving frames. As an attestation of the fruitfulness of our framework, we obtain a new, constructive and intuitive proof of the Lie-Tresse theorem (Fundamental basis theorem) and a first general upper bound on the minimal number of generating differential invariants for Lie pseudo-groups. Further, we demonstrate the computational advantages of this framework by studying the equivalence problem for first order PDE in two independent variables and one dependent variable under point transformations.     

糖果厂模型的最优化搜索方法

讨论了用两台装置搜索两个坏硬币的糖果厂模型 C2 ,给出了一个测试过程 t,使之理论上的最优过程最多相差一次测试 .     

糖果厂模型的最优化搜索方法

讨论了用两台装置搜索两个坏硬币的糖果厂模型C2,给出了一个测试过程t,使之与理论上的最优过程最多相差一次测试。     

Error estimates for shooting methods in two-point boundary value problems for second-order equations

This paper is concerned with a procedure for estimating the global discretization error arising when a boundary value problem for a system of second order differential equations is solved by the simple shooting method, without transforming the original problem in an equivalent first order problem. Expressions of the global discretization error are derived for both linear and nonlinear boundary value problems, which reduce the error estimation for a boundary value problem to that for an initial value problem of same dimension. The procedure extends to second order equations a technique for global error estimation given elsewhere for first order equations. As a practical result the accuracy of the estimates for a second order problem is increased compared with the estimates for the equivalent first order problem.     

Embedding learning capability in Lagrangean relaxation: An application to the travelling salesman problem

This paper presents an effective procedure that finds lower bounds for the travelling salesman problem based on the 1-tree using a learning-based Lagrangian relaxation technique. The procedure can dynamically alter its step-size depending upon its previous iterations. Along with having the capability of expansion–contraction, the procedure performs a learning process in which Lagrange multipliers are influenced by a weighted cost function of their neighbouring nodes. In analogy with simulated annealing paradigm, here a learning process is equivalent to escaping local optimality via exploiting the structure of the problem. Computational results conducted on Euclidean benchmarks from the TSPLIB library show that the procedure is very effective.     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

Black and white local invariants of mappings from surfaces into three-space

Goryunov proved that the space of local invariants of Vassiliev type for generic maps from surfaces to three-space is three-dimensional. The basic invariants were the number of pinch points, the number of triple points and one linked to a Rokhlin type invariant. In this paper we show that, by colouring the complement of the image of the map with a chess board pattern, we can produce a six-dimensional space of local invariants. These are essentially black and white versions of the above. Simple examples show how these are more effective. This revised version was published online in August 2006 with corrections to the Cover Date.     

A representation of Bayes invariant procedures in terms of Haar measure

Summary It is shown that under fairly general conditions the Bayes procedure among the class of procedures invariant under a group of transformations which leave the statistical problem invariant, is really a Bayes or formal Bayes procedure with respect to a prior measure which is constructed from the right Haar measure on the group and the specified prior. This result is useful in problems where the principle of invariance is applied. Such cases, involving the two action problem or a selection and ranking problem are given as examples.     

Differential invariants for systems of linear hyperbolic equations

In this paper we consider a general class of systems of two linear hyperbolic equations. Motivated by the existence of the Laplace invariants for the single linear hyperbolic equation, we adopt the problem of finding differential invariants for the system. We derive the equivalence group of transformations for this class of systems. The infinitesimal method, which makes use of the equivalence group, is employed for determining the desired differential invariants. We show that there exist four differential invariants and five semi-invariants of first order. Applications of systems that can be transformed by local mappings to simple forms are provided.     

Primitive idempotents in central simple algebras over Fq(t) with an application to coding theory

We consider the algorithmic problem of computing a primitive idempotent of a central simple algebra over the field of rational functions over a finite field. The algebra is given by a set of structure constants. The problem is reduced to the computation of a division algebra Brauer equivalent to the central simple algebra. This division algebra is constructed as a cyclic algebra, once the Hasse invariants have been computed. We give an application to skew constacyclic convolutional codes.     

Heuristic,meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation

The allocation of fresh produce to shelf space represents a new decision support research area which is motivated by the desire of many retailers to improve their service due to the increasing demand for fresh food. However, automated decision making for fresh produce allocation is challenging because of the very short lifetime of fresh products. This paper considers a recently proposed practical model for the problem which is motivated by our collaboration with Tesco. Moreover, the paper investigates heuristic and meta-heuristic approaches as alternatives for the generalized reduced gradient algorithm, which becomes inefficient when the problem size becomes larger. A simpler single-item inventory problem is firstly studied and solved by a polynomial time bounded procedure. Several dynamic greedy heuristics are then developed for the multi-item problem based on the procedure for the single-item inventory problem. Experimental results show that these greedy heuristics are much more efficient and provide competitive results when compared to those of a multi-start generalized reduced gradient algorithm. In order to further improve the solution, we investigated simulated annealing, a greedy randomized adaptive search procedure and three types of hyper-heuristics. Their performance is tested and compared on a set of problem instances which are made publicly available for the research community.