Finding the stationary points of semiregular functions

The generalized gradient method is applied to find the stationary points of semiregular functions. Conditions are derived when the image of the set of stationary points does not contain nonempty intervals.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 104–110, July–August, 1991.     

云计算环境下负载—功耗特征测试与分析

为了实现云计算数据中心的高效节能的工作负载调度,必须首先研究虚拟机层面不同的工作负载和功率消耗之间的关系.在现有研究的基础上,通过对服务器虚拟机层面的功耗度量与分析,研究多种硬件、软件、负载条件下,虚拟机中不同类型的工作负载对功耗的影响特性,这对于能耗的度量、建模、管理、优化等都具有重要的意义.     

On the existence of stationary points for the Steiglitz-McBridealgorithm

Most convergence results for adaptive identification algorithms have been developed in sufficient order settings, involving an unknown system with known degree. Reduced-order settings, in which the degree of the unknown system is underestimated, are more common, but more difficult to analyze. Deducing stationary points in these cases typically involves solving nonlinear equations, hence the sparseness of results for reduced-order cases. If we allow ourselves the tractable case in which the input to an identification experiment is white noise, we shall show that the Steiglitz-McBride method (1965) indeed admits a stationary point in reduced-order settings for which the resulting model is stable. Our interest in this study stems from a previous result, showing an attractive a priori bound on the mismodeling error at any such stationary point     

MinFinder: Locating all the local minima of a function

A new stochastic clustering algorithm is introduced that aims to locate all the local minima of a multidimensional continuous and differentiable function inside a bounded domain. The accompanying software (MinFinder) is written in ANSI C++. However, the user may code his objective function either in C++, C or Fortran 77. We compare the performance of this new method to the performance of Multistart and Topographical Multilevel Single Linkage Clustering on a set of benchmark problems.

Program summary

Title of program:MinFinderCatalogue identifier:ADWUProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADWUProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer for which the program is designed and others on which is has been tested:The tool is designed to be portable in all systems running the GNU C++ compilerInstallation:University of Ioannina, GreeceProgramming language used:GNU-C++, GNU-C, GNU Fortran 77Memory required to execute with typical data:200 KBNo. of bits in a word:32No. of processors used:1Has the code been vectorized or parallelized?:noNo. of lines in distributed program, including test data, etc.:5797No. of bytes in distributed program, including test data, etc.:588 121Distribution format:gzipped tar fileNature of the physical problem:A multitude of problems in science and engineering are often reduced to minimizing a function of many variables. There are instances that a local optimum does not correspond to the desired physical solution and hence the search for a better solution is required. Local optimization techniques can be trapped in any local minimum. Global optimization is then the appropriate tool. For example, solving a non-linear system of equations via optimization, employing a “least squares” type of objective, one may encounter many local minima that do not correspond to solutions, i.e. they are far from zero.Method of solution:Using a uniform pdf, points are sampled from the rectangular search domain. A clustering technique, based on a typical distance and a gradient criterion, is used to decide from which points a local search should be started. The employed local procedure is a BFGS version due to Powell. Further searching is terminated when all the local minima inside the search domain are thought to be found. This is accomplished via the double-box rule.Typical running time:Depending on the objective function     

Computation of stationary points of distance functions

This paper presents an algorithm for computation of the stationary points of the squared distance functions between two point sets. One point set consists of a single space point, a rational B-spline curve, or a rational B-spline surface. The problem is reformulated in terms of solution of n polynomial equations with n variables expressed in the tensor product Bernstein basis. The solution method is based on subdivision relying on the convex hull property of the n-dimensional Bernstein basis and minimization techniques. We also cover classification of the stationary points of these distance functions, and include a method for tracing curves of stationary points in case the solution set is not zerodimensional. The distance computation problem is shown to be equivalent to the geometrically intuitive problem of computing collinear normal points. Finally, examples illustrate the applicability of the method     

Optimization of rotations of a five-axis milling machine near stationary points

We consider a new algorithm designed for five-axis milling to minimize the kinematics error near the stationary points of the machined surface. Given the tool orientations, the algorithm optimizes the required rotations on the set of the solutions of the corresponding inverse kinematics equations. We solve the problem by means of the shortest path scheme based on minimization of the kinematics error.We present an application of the proposed algorithm to tool-path planning and demonstrate the efficiency of the proposed scheme verified by practical machining.     

Existence of stationary points for pseudo-linear regressionidentification algorithms

The authors prove the existence of a stable transfer function satisfying the nonlinear equations characterizing an asymptotic stationary point, in undermodeled cases, for a class of pseudo-linear regression algorithms, including Landau's algorithm, the Feintuch algorithm, and (S)HARF. The proof applies to all degrees of undermodeling and assumes only that the input power spectral density function is bounded and nonzero for all frequencies, and that the compensation filter is strictly minimum phase. Some connections to previous stability analyses for reduced-order identification in this algorithm class are brought out     

Fuzzy Sarsa Learning and the proof of existence of its stationary points

This paper provides a new Fuzzy Reinforcement Learning (FRL) algorithm based on critic‐only architecture. The proposed algorithm, called Fuzzy Sarsa Learning (FSL), tunes the parameters of conclusion parts of the Fuzzy Inference System (FIS) online. Our FSL is based on Sarsa, which approximates the Action Value Function (AVF) and is an on‐policy method. In each rule, actions are selected according to the proposed modified Softmax action selection so that the final inferred action selection probability in FSL is equivalent to the standard Softmax formula. We prove the existence of fixed points for the proposed Approximate Action Value Iteration (AAVI). Then, we show that FSL satisfies the necessary conditions that guarantee the existence of stationary points for it, which coincide with the fixed points of the AAVI. We prove that the weight vector of FSL with stationary action selection policy converges to a unique value. We also compare by simulation the performance of FSL and Fuzzy Q‐Learning (FQL) in terms of learning speed, and action quality. Moreover, we show by another example the convergence of FSL and the divergence of FQL when both algorithms use a stationary policy. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Locating input and output points in facilities design - acomparison of constructive, evolutionary, and exact methods

This paper formulates and compares four new approaches to optimally locate the input and output station for each department within a facility design such that material handling costs are minimized. This problem is an NP-hard combinatorial problem with many real-life applications of considerable economic consequence. A genetic algorithm (GA) is shown to be an effective and efficient optimization method when compared to integer programming, simulated annealing, and three versions of a greedy constructive heuristic on a suite of test problems of varying size. Seeding versus random initialization of GA populations are compared     

Testing satisfiability of CNF formulas by computing a stable set of points

We show that a conjunctive normal form (CNF) formula F is unsatisfiable if and only if there is a set of points of the Boolean space that is stable with respect to F. So testing the satisfiability of a CNF formula reduces to looking for a stable set of points (SSP). We give some properties of SSPs and describe a simple algorithm for constructing an SSP for a CNF formula. Building an SSP can be viewed as a natural way of search space traversal. This naturalness of search space examination allows one to make use of the regularity of CNF formulas to be checked for satisfiability. We illustrate this point by showing that if a CNF F formula is symmetric with respect to a group of permutations, it is very easy to make use of this symmetry when constructing an SSP. As an example, we show that the unsatisfiability of pigeon-hole CNF formulas can be proven by examining only a set of points whose size is quadratic in the number of holes. Finally, we introduce the notion of an SSP with excluded directions and sketch a procedure of satisfiability testing based on the construction of such SSPs.     

Testing satisfiability of CNF formulas by computing a stable set of points

We show that a conjunctive normal form (CNF) formula F is unsatisfiable if and only if there is a set of points of the Boolean space that is stable with respect to F. So testing the satisfiability of a CNF formula reduces to looking for a stable set of points (SSP). We give some properties of SSPs and describe a simple algorithm for constructing an SSP for a CNF formula. Building an SSP can be viewed as a natural way of search space traversal. This naturalness of search space examination allows one to make use of the regularity of CNF formulas to be checked for satisfiability. We illustrate this point by showing that if a CNF F formula is symmetric with respect to a group of permutations, it is very easy to make use of this symmetry when constructing an SSP. As an example, we show that the unsatisfiability of pigeon-hole CNF formulas can be proven by examining only a set of points whose size is quadratic in the number of holes. Finally, we introduce the notion of an SSP with excluded directions and sketch a procedure of satisfiability testing based on the construction of such SSPs.     

Attraction domains of the stationary points of the difference equation with switchings

Consideration was given to the scalar difference equation of first order which is defined over an interval and has the right-hand side described by different continuous functions to the left and right of the switching point. Each of these functions has one stationary point. The domains of attraction and oscillatory solutions with an infinite number of switchings in the right-hand side were determined subject to the condition that they are attracted and lie to the left of the switching point.     

Relation between powers of factors and the recurrence function characterizing Sturmian words

In this paper we use the relation of the index of an infinite aperiodic word and its recurrence function to give another characterization of Sturmian words. As a by-product, we give a new proof of the theorem describing the index of a Sturmian word in terms of the continued fraction expansion of its slope. This theorem was independently proved in [A. Carpi, A. de Luca, Special factors, periodicity, and an application to Sturmian words, Acta Inform. 36 (2000) 983–1006] and [D. Damanik, D. Lenz, The index of Sturmian sequences, European J. Combin. 23 (2002) 23–29].     

Stochastic approximation algorithms for the local optimization of functions with nonunique stationary points

The aim of this paper is the provision of a framework for a practical stochastic unconstrained optimization theory. The results are based on certain concepts of stochastic approximation, although not restricted to those procedures, and aim at incorporating the great flexibility of currently available deterministic optimization ideas into the stochastic problem, whenever optimization must be done by Monte Carlo or sampling methods. Hills with nonunique stationary points are treated. A framework has been provided, with which convergence of stochastic versions of conjugate gradient, partan, etc., can be discussed and proved.