Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

On closure properties of GapP

We study the closure properties of the function classes GapP and GapP₊. We characterize the property of GapP₊ being closed under decrement and of GapP being closed under maximum, minimum, median, or division by seemingly implausible collapses among complexity classes, thereby giving evidence that these function classes don't have the stated closure properties.We show a similar result concerning operations we callbit cancellation andbit insertion: Given a functionf GapP and a polynomialtime computable function , we ask whether the functionsf ^* (x) andf ⁺ (x) are in GapP or not, wheref ^* (x) is obtained fromf(x) by cancelling the (x)-th bit in the binary representation off(x), andf ⁺ (x) is obtained fromf(x) by inserting a bit at position (x) in the binary representation off(x). We give necessary and sufficient conditions for GapP being closed under bit cancellation and bit insertion, respectively.     

Global optimization methods for engineering applications: A review

A review of the methods for global optimization reveals that most methods have been developed for unconstrained problems. They need to be extended to general constrained problems because most of the engineering applications have constraints. Some of the methods can be easily extended while others need further work. It is also possible to transform a constrained problem to an unconstrained one by using penalty or augmented Lagrangian methods and solve the problem that way. Some of the global optimization methods find all the local minimum points while others find only a few of them. In any case, all the methods require a very large number of calculations. Therefore, the computational effort to obtain a global solution is generally substantial. The methods for global optimization can be divided into two broad categories: deterministic and stochastic. Some deterministic methods are based on certain assumptions on the cost function that are not easy to check. These methods are not very useful since they are not applicable to general problems. Other deterministic methods are based on certain heuristics which may not lead to the true global solution. Several stochastic methods have been developed as some variation of the pure random search. Some methods are useful for only discrete optimization problems while others can be used for both discrete and continuous problems. Main characteristics of each method are identified and discussed. The selection of a method for a particular application depends on several attributes, such as types of design variables, whether or not all local minima are desired, and availability of gradients of all the functions.Notation Number of equality constraints - () ^T A transpose of a vector - A A hypercubic cell in clustering methods - Distance between two adjacent mesh points - Probability that a uniform sample of sizeN contains at least one point in a subsetA ofS - A(v, x) Aspiration level function - A The set of points with cost function values less thanf(x _G ^* ) +. Same asA _f () - A _f () A set of points at which the cost function value is within off(x _G ^* ) - A () A set of points x with[f(x)] smaller than - A _N The set ofN random points - A _q The set of sample points with the cost function value f _q - _Q The contraction coefficient; –1 _Q 0 - _R The expansion coefficient; _E > 1 - _R The reflection coefficient; 0 < _R 1 - A _x () A set of points that are within the distance from x _G ^* - D Diagonal form of the Hessian matrix - det() Determinant of a matrix - d _j A monotonic function of the number of failed local minimizations - d _t Infinitesimal change in time - d _x Infinitesimal change in design - A small positive constant - (t) A real function called the noise coefficient - ₀ Initial value for(t) - exp() The exponential function - f ^(c) The record; smallest cost function value over X^(C) - [f(x)] Functional for calculating the volume fraction of a subset - Second-order approximation tof(x) - f(x) The cost function - An estimate of the upper bound of global minimum - f ^E The cost function value at x^E - f ^L The cost function value at x^L - f _opt The current best minimum function value - f ^P The cost function value at x ^P - f ^Q The cost function value at x ^Q - f _q A function value used to reduce the random sample - f ^R The cost function value at x ^R - f ^S The cost function value at x^S - f _{T F min} A common minimum cost function value for several trajectories - f _{TF opt} The best current minimum value found so far forf _{TF min} - f ^W The cost function value at x ^W - G Minimum number of points in a cell (A) to be considered full - The gamma function - A factor used to scale the global optimum cost in the zooming method - Minimum distance assumed to exist between two local minimum points - gi(x) Constraints of the optimization problem - H The size of the tabu list - H(x^*) The Hessian matrix of the cost function at x^* - h _j Half side length of a hypercube - h _m Minimum half side lengths of hypercubes in one row - I The unity matrix - ILIM A limit on the number of trials before the temperature is reduced - J The set of active constraints - K Estimate of total number of local minima - k Iteration counter - The number of times a clustering algorithm is executed - L Lipschitz constant, defined in Section 2 - L The number of local searches performed - _i The corresponding pole strengths - log () The natural logarithm - LS Local search procedure - M Number of local minimum points found inL searches - m Total number of constraints - m(t) Mass of a particle as a function of time - m() TheLebesgue measure of thea set - Average cost value for a number of random sample of points inS - N The number of sample points taken from a uniform random distribution - n Number of design variables - n(t) Nonconservative resistance forces - n _c Number of cells;S is divided inton _c cells - NT Number of trajectories - Pi (3.1415926) - P _i ^(j) Hypersphere approximating thej-th cluster at stagei - p(x ⁽ⁱ⁾⁾ Boltzmann-Gibbs distribution; the probability of finding the system in a particular configuration - pg A parameter corresponding to each reduced sample point, defined in (36) - Q An orthogonal matrix used to diagonalize the Hessian matrix - _i (i = 1, K) The relative size of thei-th region of attraction - r _i ^(j) Radius of thej-th hypersp here at stagei - R _x ^* Region of attraction of a local minimum x^* - r _j Radius of a hypersphere - r A critical distance; determines whether a point is linked to a cluster - R ⁿ A set ofn tuples of real numbers - A hyper rectangle set used to approximateS - S The constraint set - A user supplied parameter used to determiner - s The number of failed local minimizations - T The tabu list - t Time - T(x) The tunneling function - T _c (x) The constrained tunneling function - T _i The temperature of a system at a configurationi - TLIMIT A lower limit for the temperature - TR A factor between 0 and 1 used to reduce the temperature - u(x) A unimodal function - V(x) The set of all feasible moves at the current design - v(x) An oscillating small perturbation. - V(y⁽ⁱ⁾) Voronoi cell of the code point y⁽ⁱ⁾ - v^–1 An inverse move - v _k A move; the change from previous to current designs - w(t) Ann-dimensional standard. Wiener process - x Design variable vector of dimensionn - x^# A movable pole used in the tunneling method - x⁽⁰⁾ A starting point for a local search procedure - X^(c) A sequence of feasible points {x⁽¹⁾, x⁽²⁾,,x^(c)} - x(t) Design vector as a function of time - X^* The set of all local minimum points - x^* A local minimum point forf(x) - x^*(i) Poles used in the tunneling method - x _G ^* A global minimum point forf(x) - Transformed design space - The velocity vector of the particle as a function of time - Acceleration vector of the particle as a function of time - x ^C Centroid of the simplex excluding x ^L - x ^c A pole point used in the tunneling method - x ^E An expansion point of x ^R along the direction x ^C x ^R - x ^L The best point of a simplex - x ^P A new trial point - x ^Q A contraction point - x ^R A reflection point; reflection of x ^W on x ^C - x ^S The second worst point of a simplex - x ^W The worst point of a simplex - The reduced sample point with the smallest function value of a full cell - Y The set of code points - y ⁽ⁱ⁾ A code point; a point that represents all the points of thei-th cell - z A random number uniformly distributed in (0,1) - Z ^(c) The set of points x where [f ^(c) – ] is smaller thanf(x) - []₊ Max (0,) - | | Absolute value - The Euclidean norm - f[x(t)] The gradient of the cost function     

Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems

Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O^*(2.179^k) to O^*(2.05^k), or to improve the kernel size from k³ to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples.     

Dynamic Programming for Minimum Steiner Trees

We present a new dynamic programming algorithm that solves the minimum Steiner tree problem on graphs with k terminals in time O^*(c^k) for any c > 2. This improves the running time of the previously fastest parameterized algorithm by Dreyfus-Wagner of order O^*(3^k) and the so-called "full set dynamic programming" algorithm solving rectilinear instances in time O^*(2.38^k).     

A transformation of non-linear dynamical systems with a single singular singularly perturbed differential equation†

Singularly perturbed state differential equations of the form [xdot] = f(x, z, t, ?), x(t₀, ?) = x₀(?); μ(?)? = g(x, z, t, ?), z(t₀ ?) = z₀(?) with lim μ(?) = 0; ?, μ > 0 are considered, where the nominal equation 0 = g(x, z, t, 0)^{? → ∞} does not have to be solvable for z. A fairly general transformation of the above system into a form [xdot]^* = f ^*(x^*, z, t; z(1),...,z^(d?1), ? ); μ^*(?)z^(d)= g^*(x^*. z(⁰),...z^(d?1), t; ?), with dim x^* = dim x ?(d ? 1), d ? 1 is proposed. The transformed system stands a better chance of being analysed by existing methods (especially by those proposed by Hoppensteadt (1971) and Hoppensteadt and Mi ranker (1976)) than the original singular singularly perturbed form. Informative examples are presented.     

Disuguaglianze relative all'approssimazione polinomiale in norma uniforme

Let Π _n denote the space of algebraic polynomials of degreen or less. In this paper we establish the inequality for everyf _∈ C ⁽ⁿ⁻¹⁾ ([−1, 1]) andf ⁽ⁿ⁻¹⁾ absolutely continuous. A way for obtaining similar inequalities forf _∈ C ^(t−1) ([−1, 1]) andf ^(l−1) absolutely continuous is given.

---

---

Ricerca effettuata mentre l'autore fruiva di una Borsa di Studio del C.N.R.     

Realizing Boolean functions on disjoint sets of variables

For switching functions f let C(f) be the combinational complexity of f. We prove that for every ε>0 there are arbitrarily complex functions f:{0,1}ⁿ→{0,1}ⁿ such that C(f×f)? (1+ε)C(f) and arbitrarily complex functions f:{0,1}ⁿ→{0,1} such that C(v°(fxf)? (1+ε)C(f). These results and the techniques developed to obtain them are used to show that Ashenhurst decomposition of switching functions does not always yield optimal circuits, and to prove a new result concerning the gap between circuit size and monotone circuit size.     

Box-Splitting strategies for the interval Gauss-Seidel step in a global optimization method

We consider an algorithm for computing verified enclosures for all global minimizersx ^* and for the global minimum valuef ^*=f(x ^*) of a twice continuously differentiable functionf:? ⁿ →→ within a box [x]∈I→. Our algorithm incorporates the interval Gauss-Seidel step applied to the problem of finding the zeros of the gradient off. Here, we have to deal with the gaps produced by the extended interval division. It is possible to use different box-splitting strategies for handling these gaps, producing different numbers of subboxes. We present results concerning the impact of these strategies on the interval Gauss-Seidel step and therefore on our global optimization method. First, we give an overview of some of the techniques used in our algorithm, and we describe the modifications improving the efficiency of the interval Gauss-Seidel step by applying a special box-splitting strategy. Then, we have a look on special preconditioners for the Gauss-Seidel step, and we investigate the corresponding results for different splitting strategies. Test results for standard global optimization problems are discussed for different variants of our method in its portable PASCAL-XSC implementation. These results demonstrate that there are many cases in which the splitting strategy is more important for the efficiency of the algorithm than the use of preconditioners.     

Finite canonical rewriting systems for congruences generated by concurrency relations

WhenC is a concurrency relation on alphabet , then ^*/= _C is a free partially commutative monoid. Here we show that it is decidable in polynomial time whether or not there exists a finite canonical rewriting systemR on such that the congruences _R ^* generated byR and = _C induced byC coincide. Further, in case such a systemR exists, one such system can be determined in polynomial time.     

Nonlocal quasi-Newton method for solving convex variational inequalities

Conclusion In the optimization problem [f ₀(x)│h_i(x)<-0,i=1,…,l] relaxation of the functionf ₀(x)+Nh⁺(x) does not produce, as we know [6, 7], α_k=1 in Newton's method with the auxiliary problem (5), (6), whereF(x)=f _0′(x). For this reason, Newton type methods based on relaxation off ₀(x)+Nh⁺(x) are not superlinearly convergent (so-called Maratos effect). The results of this article indicate that if (F(x)=f _0′(x), then replacement of the initial optimization problem with a larger equivalent problem (7) eliminates the Maratos effect in the proposed quasi-Newton method. This result is mainly of theoretical interest, because Newton type optimization methods in the space of the variablesx ∈R ⁿ are less complex. However to the best of our knowledge, the difficulties with nonlocal convergence arising in these methods (choice of parameters, etc.) have not been fully resolved [10, 11]. The discussion of these difficulties and comparison with the proposed method fall outside the scope of the present article, which focuses on solution of variational inequalities (1), (2) for the general caseF′(x)≠F′ ^T(x). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 78–91, November–December, 1994.     

Modelisation d'algorithmes d'optimisation a strategie aleatoire

Conceptual algorithms for random search in optimization. I am proposing two conceptual algorithms for extending results about almost certainly convergence of stochastic algorithms for optimization described as follows. Let f be a map from the vector space E to the set of real number R; f is to be minimized; x⁰ is an arbitrary point of E and (ξ ^k ) a family of random vectors, if f(x^k+ξ ^k)≥f(x^k) then x^k+1=x^k or else x^k+1=x^k+ξ ^k. The inspiration for the two conceptual algorithms came from Polak's conceptual algorithm [11] for deterministic search in optimization.      

Improved Approximation Algorithm for Convex Recoloring of Trees

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance. The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring corresponds to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance. We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ²+n(1/ε)²4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem. We also present an algorithm for computing an optimal convex recoloring whose running time is , where n ^* is the number of colors that violate convexity in the input tree, and Δ is the maximum degree of vertices in the tree. The parameterized complexity of this algorithm is O(n ²+n⋅k⋅2 ^k ).     

Lower Bounds on the Randomized Communication Complexity of Read-Once Functions

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae. A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond to variables, and the internal nodes are labeled by binary connectives. Under certain assumptions, this representation is unique. Thus, one can define the depth of a formula as the depth of the tree that represents it. The complexity of the evaluation of general read-once formulae has attracted interest mainly in the decision tree model. In the communication complexity model many interesting results deal with specific read-once formulae, such as DISJOINTNESS and TRIBES. In this paper we use information theory methods to prove lower bounds that hold for any read-once formula. Our lower bounds are of the form n(f)/c^d(f), where n(f) is the number of variables and d(f) is the depth of the formula, and they are optimal up to the constant in the base of the denominator.     

An enlarged family of packing polynomials on multidimensional lattices

HereN = {0, 1, 2, ...}, while a functionf onN ^m or a larger domain is apacking function if its restrictionf|N ^m is a bijection ontoN. (Packing functions generalize Cantor's [1]pairing polynomials, and yield multidimensional-array storage schemes.) We call two functionsequivalent if permuting arguments makes them equal. Alsos(x) =x ₁ + ... +x _m when x = (x ₁,...,x _m); and such anf is adiagonal mapping iff(x) <f(y) whenever x, y εN ^m ands(x) <s(y). Lew [7] composed Skolem's [14], [15] diagonal packing polynomials (essentially one for eachm) to constructc(m) inequivalent nondiagonal packing polynomials on eachN ^m. For eachm > 1 we now construct 2^m−2 inequivalent diagonal packing polynomials. Then, extending the tree arguments of the prior work, we obtaind(m) inequivalent nondiagonal packing polynomials, whered(m)/c(m) → ∞ asm → ∞. Among these we count the polynomials of extremal degree.     

Communication Complexity Under Product and Nonproduct Distributions

We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R_∈(f) and $D^\mu_\in (f)$D^\mu_\in (f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0, 1}ⁿ ×{0, 1}ⁿ ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which max_{μ product} {D^m _? (f)} = Q(1)  but R _? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously posed by the author (2007).     

New Plain-Exponential Time Classes for Graph Homomorphism

A homomorphism from a graph G to a graph H (in this paper, both simple, undirected graphs) is a mapping f:V(G)→V(H) such that if uv∈E(G) then f(u)f(v)∈E(H). The problem Hom (G,H) of deciding whether there is a homomorphism is NP-complete, and in fact the fastest known algorithm for the general case has a running time of O ^*(n(H) ^cn(G)) (the notation O ^*(⋅) signifies that polynomial factors have been ignored) for a constant 0<c<1. In this paper, we consider restrictions on the graphs G and H such that the problem can be solved in plain-exponential time, i.e. in time O ^*(c ^n(G)+n(H)) for some constant c.     

基于DPSO-AO*算法系统测试序列优化问题研究

为了使复杂装备信息处理系统在进行故障定位过程中耗时最少、成本最低,建立了系统测试序列优化问题的数学模型。基于DPSO-AO^*算法的改进,得到信息处理系统的最优测试策略决策树,根据信息处理系统的相关矩阵,按故障概率,随机生成故障,采用相应的测试序列进行测试,最后利用累计测试费用进行比较,从而证明了改进的DPSO-AO^*算法正确有效。     

Birkhoff's ergodic theorem and the piecewise-constant maximum entropy method for Frobenius–Perron operators

Let (X, Σ, σ) be a finite measure space and S: X→X be a nonsingular transformation such that the corresponding Frobenius–Perron operator P _S : L ¹(X)→L ¹(X) has a stationary density f*. We propose a piecewise-constant maximum entropy method for the numerical recovery of f* and give its relation to the classic Birkhoff's individual ergodic theorem. An advantage of the piecewise-constant method over the current maximum entropy method based on polynomial basis functions is that a nonlinear system of equations is not needed for solving the related moment problem. Numerical results are given for several one dimensional test mappings.