Bipartite Locating Array

As a special case of experimental design,locating array is useful for locating interaction faults in component-based systems.In this paper,bipartite locating array is proposed to locate interaction faults between two specific groups.Such arrays are especially suitable for antagonism tests.Based on the definition of bipartite locating array,the lower bound on run sizes are established to measure the optimality for specific parameters.When a single fault is to be located,optimal bipartite locating arrays are proved to be equivalent to certain specific combinatorial configurations.As a result,approaches to constructing optimal bipartite locating arrays are proposed and some infinite classes of optimal bipartite locating arrays are obtained using the corresponding construction met hod.     

Optimum detecting arrays for independent interaction faults

The use of detecting arrays (DTAs) is motivated by the need to locate and detect interaction faults arising between the factors in a component-based system in software testing. The optimality and construction of DTAs have been investigated in depth for the case in which all the interaction faults are assumed to have the same strength; however, as a practical concern, the strengths of these faults are not always identical. For real world applications, it would be desirable for a DTA to be able to identify and detect faulty interactions of a strength equal to or less than a specified value under the assumption that the faulty interactions are independent from one another. To the best of our knowledge, the optimality and construction of DTAs for independent interaction faults have not been studied systematically before. In this paper, we establish a general lower bound on the size of DTAs for independent interaction faults and explore the combinatorial feature that enable these DTAs to meet the lower bound. Taking advantage of this combinatorial characterization, several classes of optimum DTAs meeting the lower bound are presented.     

Detecting arrays and their optimality

Detecting arrays were proposed by Colbourn and McClary in 2008, which are of interest in generating software test suites to cover all t-sets of component interactions and detect interaction faults in component-based systems. So far, optimality and constructions of detecting arrays have not been studied systematically. Indeed, no useful benchmark to measure the optimality of detecting arrays has previously been given, and only some sporadic examples of optimal detecting arrays have been found. This paper tries to take the first step by presenting a lower bound on the size of detecting arrays and some methods of constructing optimal detecting arrays. A number of infinite series of optimal detecting arrays are then obtained.     

Optimal design of efficient acoustic antenna arrays

Minimax optimal design of sonar transducer arrays can be formulated as a nonlinear program with many convex quadratic constraints and a nonconvex quadratic efficiency constraint. The variables of this problem are a scaling and phase shift applied to the output of each sensor. This problem is solved by applying Lagrangian relaxation to the convex quadratic constraints. Extensive computational experience shows that this approach can efficiently find near-optimal solutions of problems with up to 391 variables and 579 constraints. This work was supported by ONR Contracts N00014-83-C-0437 and N00014-82-C-824.     

Intertwining unisolvent arrays for multivariate Lagrange interpolation

Generalizing a classical idea of Biermann, we study a way of constructing a unisolvent array for Lagrange interpolation in C^n+m out of two suitably ordered unisolvent arrays respectively in Cⁿ and C^m. For this new array, important objects of Lagrange interpolation theory (fundamental Lagrange polynomials, Newton polynomials, divided difference operator, vandermondian, etc.) are computed. AMS subject classification 41A05, 41A63     

Optimal control in nonlinear infinite-dimensional systems with nondifferentiability of two types

We consider the optimal control problem for systems described by nonlinear equations of elliptic type. If the nonlinear term in the equation is smooth and the nonlinearity increases at a comparatively low rate of growth, then necessary conditions for optimality can be obtained by well-known methods. For small values of the nonlinearity exponent in the smooth case, we propose to approximate the state operator by a certain differentiable operator. We show that the solution of the approximate problem obtained by standard methods ensures that the optimality criterion for the initial problem is close to its minimal value. For sufficiently large values of the nonlinearity exponent, the dependence of the state function on the control is nondifferentiable even under smoothness conditions for the operator. But this dependence becomes differentiable in a certain extended sense, which is sufficient for obtaining necessary conditions for optimality. Finally, if there is no smoothness and no restrictions are imposed on the nonlinearity exponent of the equation, then a smooth approximation of the state operator is possible. Next, we obtain necessary conditions for optimality of the approximate problem using the notion of extended differentiability of the solution of the equation approximated with respect to the control, and then we show that the optimal control of the approximated extremum problem minimizes the original functional with arbitrary accuracy.     

Simultaneous Optimal Controls for Non-Stationary Stokes Systems

This paper deal with optimal control problems for a non-stationary Stokes system. We study a simultaneous distributed-boundary optimal control problem with distributed observation. We prove the existence and uniqueness of a simultaneous optimal control and we give the first order optimality condition for this problem. We also consider a distributed optimal control problem and a boundary optimal control problem and we obtain estimations between the simultaneous optimal control and the optimal controls of these last ones. Finally, some regularity results are presented.     

Optimality Conditions for Nonregular Optimal Control Problems and Duality

We define a new class of optimal control problems and show that this class is the largest one of control problems where every admissible process that satisfies the Extended Pontryaguin Maximum Principle is an optimal solution of nonregular optimal control problems. In this class of problems the local and global minimum coincide. A dual problem is also proposed, which may be seen as a generalization of the Mond–Weir-type dual problem, and it is shown that the 2-invexity notion is a necessary and su?cient condition to establish weak, strong, and converse duality results between a nonregular optimal control problem and its dual problem. We also present an example to illustrate our results.     

Optimal control problems with terminal functionals represented as the difference of two convex functions

Two control problems for a state-linear control system are considered: the minimization of a terminal functional representable as the difference of two convex functions (d.c. functions) and the minimization of a convex terminal functional with a d.c. terminal inequality contraint. Necessary and sufficient global optimality conditions are proved for problems in which the Pontryagin and Bellman maximum principles do not distinguish between locally and globally optimal processes. The efficiency of the approach is illustrated by examples.     

On Global Optimality Conditions for Nonlinear Optimal Control Problems

Let a trajectory and control pair maximize globally the functional g(x(T)) in the basic optimal control problem. Then (evidently) any pair (x,u) from the level set of the functional g corresponding to the value g( (T)) is also globally optimal and satisfies the Pontryagin maximum principle. It is shown that this necessary condition for global optimality of turns out to be a sufficient one under the additional assumption of nondegeneracy of the maximum principle for every pair (x,u) from the above-mentioned level set. In particular, if the pair satisfies the Pontryagin maximum principle which is nondegenerate in the sense that for the Hamiltonian H, we have along the pair on [0,T], and if there is no another pair (x,u) such that g(x(T))=g( (T)), then is a global maximizer.     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

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

讨论了用两台装置搜索两个不合格品的“糖果厂”模型Ｃ２：ΦΦ｜Φｘ,Φｙ,Φｘｙ,ｙｘ｜ｘΦ,ｙΦ,ｘｙΦ,ｘｙ,给出了一个测试过程ｔ,其与理论上的最优测试过程至多相差一次测试,从而较好地解决了文［１］提出的问题     

A linear-time algorithm for finding an edge-partition with max-min ratio at most two

Given a positive integer $k$ and an undirected edge-weighted connected simple graph $G$ with at least $k$ edges of positive weight, we wish to partition the graph into $k$ edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible.     

Variance minimization for continuous-time Markov decision processes: two approaches

This paper studies the limit average variance criterion for continuous-time Markov decision processes in Polish spaces. Based on two approaches, this paper proves not only the existence of solutions to the variance minimization optimality equation and the existence of a variance minimal policy that is canonical, but also the existence of solutions to the two variance minimization optimality inequalities and the existence of a variance minimal policy which may not be canonical. An example is given to illustrate all of our conditions.     

On laplace continued fraction for the normal integral

The Laplace continued fraction is derived through a power series. It provides both upper bounds and lower bounds of the normal tail probability % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiqbfA6agzaaraaaaa!3DC0!\[\bar \Phi\](x), it is simple, it converges for x>0, and it is by far the best approximation for x3. The Laplace continued fraction is rederived as an extreme case of admissible bounds of the Mills' ratio, % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXafv3ySLgzGmvETj2BSbqefm0B1jxALjhiov2D% aebbfv3ySLgzGueE0jxyaibaiGc9yrFr0xXdbba91rFfpec8Eeeu0x% Xdbba9frFj0-OqFfea0dXdd9vqaq-JfrVkFHe9pgea0dXdar-Jb9hs% 0dXdbPYxe9vr0-vr0-vqpWqaaeaabiGaciaacaqabeaadaqaaqGaaO% qaaiqbfA6agzaaraaaaa!3DC0!\[\bar \Phi\](x)/(x), in the family of ratios of two polynomials subject to a monotone decreasing absolute error. However, it is not optimal at any finite x. Convergence at the origin and local optimality of a subclass of admissible bounds are investigated. A modified continued fraction is proposed. It is the sharpest tail bound of the Mills' ratio, it has a satisfactory convergence rate for x1 and it is recommended for the entire range of x if a maximum absolute error of 10^-4 is required.The efforts of the author were supported by the NSERC of Canada.     

Pattern-forming systems for control of large arrays of actuators

Summary. We consider an approach for coordinating the activity of a large array of microactuators via diffusive (i.e., nearest-neighbor) coupling combined with reactive growth and decay, implemented via interconnection templates which have been artificially engineered into the system (for example, in collocated microelectronic circuitry, or through the formulation of active material layers). Such coupled systems can support interesting spatiotemporal patterns, which in turn determine the actuation patterns. Generating such spatiotemporal patterns typically involves stressing the interconnections by raising or lowering a parameter resulting in the crossing of stability thresholds. The possibility of making such parametric adjustments via feedback on a slower timescale offers a solution to the problem of communicating effectively within a large array: The communication is achieved through the interconnection template. The mathematics behind this idea leads us into the rich domain of nonlinear partial differential equations (PDEs) with spatiotemporal pattern solutions. We present a global nonlinear stability analysis that applies to certain model pattern-forming systems. The nonlinear stability analysis could serve as a starting point for control system design for systems containing large microactuator arrays. Received August 1, 2000; accepted August 16, 2001 Online publication November 5, 2001