Search

International audience; We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum. We show how certain alternative neighborhoods can locate the global more readily, but disclose that each of these approaches encounters serious difficulties by slightly changing the problem formulation. We also identify other possible approaches that seem at first to be promising but turn out to have deficiencies. Finally, we observe that a strategic oscillation approach for transitioning between feasible and infeasible space overcomes these difficulties, reinforcing recent published observations about the utility of solution trajectories that alternate between feasibility and infeasibility. We also sketch features of such an approach that have implications for future research.

The recently introduced family of natural evolution strategies (NES), a novel stochastic descent method employing the natural gradient, is providing a more principled alternative to the well-known covariance matrix adaptation evolution strategy (CMA-ES). Until now, NES could only be used for single-objective optimization. This paper extends the approach to the multi-objective case, by first deriving a (1+1) hillclimber version of NES which is then used as the core component of a multi-objective optimization algorithm. We empirically evaluate the approach on a battery of benchmark functions and find it to be competitive with the state-of-the-art.

Sized types are a modular and theoretically well-understood tool for checking termination of recursive and productivity of corecursive definitions. The essential idea is to track structural descent and guardedness in the type system to make termination checking robust and suitable for strong abstractions like higher-order functions and polymorphism. To study the application of sized types to proof assistants and programming languages based on dependent type theory, we have implemented a core language, MiniAgda, with explicit handling of sizes. New considerations were necessary to soundly integrate sized types with dependencies and pattern matching, which was made possible by concepts such as inaccessible patterns and parametric function spaces. This paper provides an introduction to MiniAgda by example and informal explanations of the underlying principles., Comment: In Proceedings PAR 2010, arXiv:1012.4555

Although many pattern classifiers based on artificial neural networks have been vigorous-ly studied, they are still inadequate from a viewpoint of classifyingdynamic (variable-and unspecified-duration) speech patterns. To cope with this problem, the generalized probabilistic descent method (GPD) has recently been proposed. GPD not only allows one to train a discriminative system to classify dynamic patterns, but also possesses a remarkable advantage, namely guaranteeing the learning optimality (in the sense of a probabilistic descent search). A practical implementation of this theory, however, remains to be evaluated. In this light, we particularly focus on evaluating GPD in designing a widely-used speech recognizer based on dynamic time warping distance-measurement. We also show that the design algorithm appraised in this paper can be considered a new version of learning vector quantization, which is incorporated with the dynamic programming. Experimental evaluation results in tasks of classifying syllables and phonemes clearly demonstrate GPD's superiority.

This note discusses certain aspects of computational solution of optimal control problems for fluid systems. We focus on approaches in which the steepest descent direction of the cost functional is determined using the adjoint equations. In the first part we review the classical formulation by presenting it in the context of Nonlinear Programming. In the second part we show some new results concerning determination of descent directions in general Banach spaces without Hilbert structure. The proposed approach is illustrated with computational examples concerning a state estimation problem for the 1D Kuramoto-Sivashinsky equation.

We turn now to a description of the basic techniques used for iteratively solving unconstrained minimization problems. These techniques are, of course, important for practical application since they often offer the simplest, most direct alternatives for obtaining solutions; but perhaps their greatest importance is that they establish certain reference plateaus with respect to difficulty of implementation and speed of convergence. Thus in later chapters as more efficient techniques and techniques capable of handling constraints are developed, reference is continually made to the basic techniques of this chapter both for guidance and as points of comparison.

We use an hybrid approach based on a genetic algorithm and on the gradient descent method in order to decompose an image. In the pre-processing phase the genetic algorithm is used for finding two suitable initial families of fuzzy sets that decompose R in accordance to the well known concept of Schein rank. These fuzzy sets are successively used in the descent gradient algorithm which determines the final fuzzy sets, useful for the reconstruction of the image. The experiments are executed on some images extracted from the the SIDBA standard image database.Abstract. We use an hybrid approach based on a genetic algorithm and on the gradient descent method in order to decompose an image. In the pre-processing phase the genetic algorithm is used for finding two suitable initial families of fuzzy sets that decompose R in accordance to the well known concept of Schein rank. These fuzzy sets are successively used in the descent gradient algorithm which determines the final fuzzy sets, useful for the reconstruction of the image. The experiments are executed on some images extracted from the the SIDBA standard image database.

Learning from examples is the process of taking input-output examples of an unknown function ƒ and infering an implementation of ƒ. Learning from hints allows for general information about ƒ to be used instead of just input-output examples. We introduce a method for incorporating any invariance hint about ƒ in any descent method for learning from examples. We also show that learning in a neural network remains NP-complete with a certain, biologically plausible, hint about the network. We discuss the information value and the complexity value of hibts.

A recursive relational database structure, called the two-path structure, is proposed for holding data about the properties and structure of molecules. The two-path database approach solves certain severe restriction problems by providing two pathways to the structure of complex chemical entities. One pathway permits a fast descent to the atomic structure in terms of correct IUPAC carbon atom occurrence numbers. The other pathway descends through the molecular substructures, which can be referenced at any level in retrievals. The database appears to be capable of faithfully recording the structure of all chemical entities, including proteins and enzymes.

I describe a modification of the Barnes-Hut tree algorithm together with a series of numerical tests of this method. The basic idea is to improve the performance of the code on heavily vector-oriented machines such as the Cyber 205 by exploiting the fact that nearby particles tend to have very similar interaction lists. By building an interaction list good everywhere within a cell containing a modest number of particles and reusing this interaction list for each particle in the cell in turn, the balance of computation can be shifted from recursive descent to force summation. Instead of vectorizing tree descent, this scheme simply avoids it in favor of force summation, which is quite easy to vectorize. A welcome side-effect of this modification is that the force calculation, which now treats a larger fraction of the local interactions exactly, is significantly more accurate than the unmodified method.

Current classification systems for protein structure show many inconsistencies both within and between systems. The metafold concept was introduced to identify fold similarities by consensus and thus provide a more unified view of fold space. Using cradle-loop barrels as an example, we propose to use the metafold as the next hierarchical level above the fold, encompassing a group of topologically related folds for which a homologous relationship has been substantiated. We see this as an important step on the way to a classification of proteins by natural descent.

If we wish to find out more about the origins of our family, the obvious way is to try and find the links between previous generations and set up a family tree. This is not always an easy task as it can be difficult to trace specific generations, but at least we know that a set pattern of descent exists and it is a question of finding the information which can fill in the missing links.

Determining linear separability is an important way to understand structures present in data.We review the behavior of several classical descent procedures for determining linear separability and training linear classifiers in the presence of linearly nonseparable input. We compare the adaptive procedures to linear programming methods using many pairwise discrimination problems from a public database. We found that the adaptive procedures have serious implementational problems that make them less preferable than linear programming.

In this paper we give an Inexact Interior Point method to solve finitedimensional variational inequality problems for monotone functions and polyhedral sets. At each iteration the linear system that determines the search direction is solved inexactly, by using a linear iterative solver with an ad hoc stopping criterion. We discuss algorithmic issues concerning the solution of several subproblems arising in the formulation of the method, including: form of the linear systems to be solved, choice of the accuracy in the solution of these systems, strategy for satisfying centering and descent conditions. Not surprisingly, all these choices can affect the actual performance of the method, both in terms of reliability and efficiency. We describe the practical and theoretical considerations behind the decisions included in our implementation. Results of the numerical experimentation on several well known test problems are given. They confirm the effectiveness of the proposed algorithm.

Some computable schemes for descent methods without line search are proposed. Convergence properties are presented. Numerical experiments concerning large scale unconstrained minimization problems are reported.

In the exploration of the other planets of our solar system, images taken during a lander's descent to the surface of a planet provide a critical link between orbital images and surface images. The descent images not only allow us to locate the landing site in a global coordinate frame, but also provide progressively higher-resolution maps for mission planning. The paper addresses the generation of depth maps from the descent images. Our approach has two steps: motion refinement and depth recovery. During motion refinement, we use an initial motion estimate in order to avoid the intrinsic ambiguity in descending motions. The objective of the motion refinement step is to adjust the motion parameters such that the epipolar constraints are valid between adjacent frames. The depth recovery step correlates adjacent frames to match pixels for triangulation. Due to the descending motion, the conventional rectification process is replaced by a set of anti-aliasing image warpings corresponding to a set of virtual parallel planes. We demonstrate experimental results on synthetic and real descent images.

In a prior paper, we described a haptic rendering algorithm for arbitrary polygonal models using a six degree-of-freedom haptic interface. In that paper, global search for local minimum distances provided repulsive forces between models. This paper augments that system with a local tracking algorithm that quickly updates and maintains globally computed minima. The global search continuously adds and deletes local minimum distance pairs being updated by the local search. This new system supports higher haptic interaction rates on more complex scenes than the previous approach.

In ski racing, the objective is to minimize the time of descent through a prescribed course delineated by poles, or gates, around which the skier must turn. Segments of the course consist of direct paths from one gate to the next, which are usually placed in a regular array at some distance down and across the slope from each other. Finding the path of quickest descent between such pairs of gates is not done simply by following a straight line between them. This problem, known as the brachistochrone problem, requires finding the stationary value of the integral of a function for different paths between two fixed points. It is treated by the calculus of variations and is discussed in any of a number of texts on mathematical physics or mechanics [1].

Piecewise-linear (PWL) neural networks are networks with piecewise-linear node functions. They have attractive features, such as speed of training and amenability to digital VISI implementation. The paper presents an algorithm for training PWL networks. The algorithm is general in that it can be used for the optimization of general PWL functions. It is based on moving from one linear region to the next. This is achieved by exploring 2N specific directions along the boundaries between the linear regions (N is the dimension), and moving along the direction that achieves a descent in the objective function. Convergence to the local minimum is proved, and simulation results confirm the computational efficiency of the algorithm.

In this paper we apply to a few new problems some of the techniques we have developed over the years for optimal shape design. These include optimality conditions, automatic differentiation and the appropriate descent methods.

This chapter is dedicated to the numerical approximation of Optimal Control Problems. The algorithms are based on the necessary conditions for optimality which allow us to use a descent method for the minimization of the cost functional.

In the congested cities of today, congestion pricing is a tempting alternative. With a single user class, already Beckmann et al. showed that “system optimal” traffic flows can be achieved by social marginal cost (SMC) pricing. However, different user classes can have wildly differing time values. Hence, when introducing tolls, one should consider multi-class user quilibria, where the classes have different time values. With SMC pricing, Netter claims that multi-class equilibrium problems cannot be stated as an optimization problems. We show that, depending on the formulation, the multi-class SMC-pricing equilibrium problem (with different time values) can be stated either as an asymmetric or as a symmetric equilibrium problem. In the latter case, the corresponding optimization problem is in general non-convex. For this non-convex problem, we devise descent methods of Frank-Wolfe type. We apply the methods and study a synthetic case based on Sioux Falls.

The presence of speckle in ultrasound images makes it hard to segment them using active contours. Speckle causes the energy function of the active contours to have many local minima, and the gradient descent procedure used for evolving the contour gets trapped in these minima.

An efficient parallel processing multi-coordinate descent method with line search is proposed for the large-scale unconstrained optimization problems with sparse structure. Its convergence is proved, and it is noted that its efficiency is obvious from its inherent properties. A trivial application of the proposed algorithm is the large-scale power system static-state estimation problem. >

Gradient descent algorithms with Armijo stepsizes are adapted to simulation-based optimization of queuing networks. The cost function was evaluated by Monte Carlo simulation, and its gradient was estimated by infinitesimal perturbation analysis. The Armijo stepsize routine requires multiple function evaluations, which are simultaneously performed by finite perturbation analysis (FPA) in one simulation run. Two kinds of FPA estimators are considered: one is precise, but time consuming, and the other is approximate, but faster. Numerical examples show the validity of the proposed algorithm. >

Generalized competitive learning algorithms are described. These algorithms comprise competition handicaps, cooperation and multiply descent cost property. Applications are made on single processing and combinatorial optimizations. Parallel computation of the algorithms presented is discussed. >

Summary form only given, as follows. An energy-ascent dynamics has been defined for the Hopfield-style network with properties complementary to the energy-descent dynamics. The Hopfield-style network energy descent/ascent dynamics was extended with a backtracking algorithm that visits a stable state and then backtracks from it to visit other stable states also reachable from the same initial state via energy descent/ascent. This algorithm was applied to information retrieval to retrieve all answers (network stable states) to one question (initial state). It was also shown how it can be used to solve binary constraint satisfaction problems. Experiments on using it to solve the N-queens problem were carried out. >

We propose a method for sound monitoring, which enables one to selectively detect unexpected irregular sounds and ignore the other sounds, i.e., regular sounds. The proposed method is based on the generalized probabilistic descent (GPD) method, which was originally developed as a general concept for the discriminative design of pattern recognizers, and is referred to as minimum detection error (MDE) training. The formulation and implementation of MDE training are described in detail, and its utility is demonstrated in a task of detecting irregular events; more specifically, sounds due to the mis-operation of a tool in a noisy environment.

In this paper we propose a novel approach to the detection of acoustic irregular signals using minimum detection error (MDE) training. The MDE training is based on the generalized probabilistic descent method, which was originally developed as a general concept for a discriminative pattern recognizer design. We demonstrate its fundamental utility by experiments in which several acoustic events are detected in a noisy environment.

In order to construct a fuzzy system with a learning function, numerous studies combining fuzzy systems and neural networks (or descent method) are being carried out. The self-tuning method using the descent method has been proposed by Ichihashi et al. (1991) and it is known that the constructive method is more powerful than other methods using neural networks (or descent method). But this method does not have a sufficient generalization capability or an expressing capability for the acquired knowledge. In this paper, we propose a new learning method called a destructive method of fuzzy inference rules by the descent method. And we show that the destructive method is superior in the number of rules and inference errors but inferior in learning speed to the constructive one. Further more, in order to improve learning speed, we propose a learning method combining the constructive and the destructive methods. Some numerical examples are given to show the validity of the proposed methods, and applications of these methods to the obstacle avoidance problem are shown. >

Since the theoretical basis for the method of feasible directions (MFD) was originally developed by Zoutendijk in 1960’s, several basic variations and modifications of MFD were proposed and investigated. Even though faster algorithms for solving nonlinear programming problems exist, MFD has never been abandoned because of several important advantages such as the descent property, feasibility of all iterates, conceptual simplicity and overall computational efficiency. In fact, MFD is especially popular in the engineering community where it is heavily used in structural optimization and other engineering design optimization. In engineering design, it is extremely important to end up with a design which satisfies the hard specifications expressed by a set of inequalities. This paper reviews several typical methods of feasible directions and their variants: Zoutendijk’s MFD, Topkis — Veinott’s MFD, Pironneau — Polak’s MFD, Wiest — Polak’s MFD, Cawood — Kostreva’s MFD, Panier — Tits’ FSQP and a modified MFD. Then, the performances of three MFD: Pironneau — Polak’s MFD, Cawood — Kostreva’s MFD and the modified MFD are compared numerically and graphically. The results suggest that the modified MFD is more efficient than the other two MFD.

If we assume that all present living things descend from a single ancient species, we still have many intriguing problems to solve. In particular, there are heated debates on the nature of that ancient species and on the first descent lineages which directly derived from it. To put some order in these debates, we have better address the points step by step, according to the temporal order of the evolutionary process. But first of all, we should become a little familiar with the dendrograms, i.e., the tree-shaped graphs which represent the derivation of the species.

On-line learning is one of the leading training techniques for neural networks. In this paper we will review recent theoretical approaches, based on methods from non-equilibrium statistical mechanics, for analysing on-line learning in multilayer neural network, concentrating on new approaches for defining optimal learning parameters or rules and on incorporating second order information into the learning process using natural gradient descent.

In this work a novel approach to the training of recurrent neural nets is presented. The algorithm exploits the separability of each neuron into its linear and nonlinear part. Each Iteration of the learning consists of two steps: first the descent of the error functional in the space of the linear outputs of the neurons is performed (descent in the neuron space);then the weights are updated by solving a linear system with a Recursive Least Squares technique.

Continuously operated autonomous processes governed by hereditary state equations are considered. The problem of improving of the optimal steady-state solution by periodic variations of control and state variables is discussed. A new formulation of the periodic hereditary control problem exploiting the heredity shift operator is presented, and its advantages are pointed out. This problem is solved iteratively by descent methods using variable metric ideas and implemented with the help of the Mathematica system. The proposed approach is illustrated by a simple example of ecological hereditary system.

Quasidifferentiable and codifferentiable optimization algorithms are based on gradientlike, descent, iterative techniques whereas gradient information is replaced by the setvalued quasidifferential or the codifferential. Then the steepest descent finding subproblems are appropriately replaced by quadratic programming subproblems with a polyhedral approximation of the aforementioned set—valued quantities. Since supergradients (resp. hyperdifferentials) pose a combinatorial problem in the descent direction finding subproblem, which can effectively be treated after making the polyhedral approximation by repeated solution of a number of similar subproblems or simply by solving one of them (supergradient—like technique), the basic methods used are the ones of hypodifferential optimization. These techniques will be described in the sequel (for more details we refer to [3], [9], [5]). It should be mentioned here that first order quasidifferential and codifferential optimization schemes treat more effectively, in a correct way vertical branches of laws and boundary conditions in mechanical problems, or equivalently, the nonsmoothness of the respective potentials. If at a neighbourhood of the solution the problem is essentially smooth, i.e. the solution lies far away from a point of nondifferentiability, classical methods of nonlinear computational mechanics (e.g. Newton—type methods and its derivates) can be used for the refinement of the accuracy and for speeding up the rate of convergence. Nevertheless if multiple points of nondifferentiability (cusps) have to be passed along a given loading path the general methods presented here must be used (see also Chapter 8).

This paper deals with optimal periodic control problems for distributed-parameter systems with many kinds of controls (lumped and distributed). Descent optimization methods reduced to the control space are proposed. The formulas of partial gradients with respect to lumped and distributed controls are derived and their applicability to technological and biological problems is pointed-out.

Mathematica is a symbolic manipulator with graphical capabilities. During the fall 1990 semester, I used Mathematica on my NeXT workstation to create graphics for teaching the method of steepest descents. This required level curve plots and surface plots for the real or imaginary part of functions of a complex variable. By the end of this topic in the course, I was doing near- research-level analysis of complex valued functions. The response of my class was also very positive. In this paper, I describe some of the more elementary examples discussed in the class. In Part II, I will describe the steepest descent analysis for the Lamb problem as a representative of research level application and utility of Mathematica for this type of analysis. This is the easiest example demonstrating how refracted and evanescent waves in a layered medium are treated by the method of steepest descents with the additional enhancement of Mathematica.

Although several kinds of discriminative training methods based on artificial neural networks have been vigorously tested, the pursuit of highly capable classification of variable-duration speech patterns has been unsatisfactory. In this light, the authors evaluate a generalized probabilistic descent method (GPD) in designing a speech recognizer incorporated with the dynamic time warping methodology. The algorithm can be viewed as generalized learning vector quantization suited to the dynamic programming-based time warping. Experiments were conducted on two tasks: English syllable classification and Japanese phoneme classification. Results clearly demonstrate that GPD can be a viable candidate for a method to realize a high-performance speech recognizer. >

Multiple descent cost competitive learning simultaneously generates two types of feature maps by self-organization. One is a grouped pattern of atomic data elements; the other is a geometric structure on the set of neural weight vectors. In the case of images, the grouped pattern is a set of nonoverlapping quadrilaterals. Each quadrilateral is associated with a neural weight vector, i.e., an image patch. Then, control of the grouped pattern based on external intelligence creates new images. By this method, generation of new emotional features on facial images is attempted. Thus, the feature map of the multiple descent cost competitive learning is not used for recognition but is utilized for creation of new patterns by incorporating additional information. >

Non-backtracking recursive descent parsers are easy to create but suffer from the disadvantage that they are limited to the relatively small LL(κ) class of grammars. Recursive ascent parsers can be built for the much larger LR(κ) class of grammars, but they are likely be too large to be useful and manual insertion of semantic action code into the parsers would require considerable skill. A composite approach, dubbed ‘recursive ascent-descent parsing’ or XLC(1) parsing, and which is related to left-corner parsing, solves all the problems. The parser has two parts — a top-down part and a bottom-up part. Either or both parts may be implemented as a collection of recursive functions or by a table-driven parsing algorithm. When a table-driven implementation of the bottom-up part is used, any syntax error recovery scheme applicable to LR parsers can be employed. Small, fast, implementations of the parsers are possible.

Stochastic approximation procedures, e.g. stochastic gradient methods, for solving stochastic optimization problems, can be accelerated considerably by using deterministic descent directions or more exact gradient estimations at certain iteration points. Several methods for the computation of more exact gradient estimators and deterministic (feasible) descent directions are presented.

Steve Jones Little, Brown, £14.99, pp 256 ISBN 0 316 856150 Rating: ![Graphic][1] ![Graphic][2] Steve Jones, professor of genetics at University College London, has achieved minor cult status in the world of popular science. His reputation as an amusing and fluent TV boffin led me to expect Y: The Descent of Men to be a ripping good yarn. I was disappointed, because it turned out to be an incongruous mixture of pop science, serious science, and tabloid trivia. It is a 260 page, brightly illuminated cornucopian essay on men, biology, penises, genetics, masculinity, and many other related topics. … [1]: /embed/inline-graphic-1.gif [2]: /embed/inline-graphic-2.gif

Poor convergence of existing training algorithms prevents wide applications of backpropagation neural networks. Several new training algorithms with very fast convergence are presented. They all use derivative information to efficiently estimate the optimal descent factors, thus providing the fastest descent of the mean squared error in the descent directions that characterise the algorithms. Simulation results are illustrated.

For discrete stratification and allocation problems several procedures based on the concept of feasible directions are proposed. A comparison of the procedures using an example from literature shows that surprisingly the variant affording the lowest computational effort produces the best results. It should be stressed that stratification and allocation techniques are of great practical importance e.g. within the context of stocktaking.

Summary Kidd et al. (1980) studied the allelic origins of a recessive trait in an extensive and complex genealogy. Due to computational limitations, the hypotheses they could consider were limited, and the dependencies in descent from alternative ancestors and to different sibships were not considered. Karigl (1981) developed a recursive algorithm for the computation of multiple kinship coefficients. Here we show that very similar algorithms apply to probabilities of the joint descent of multiple genes from specified ancestral genes. This makes possible a far more extensive analysis of hypotheses of allelic origins in a genealogy.

1 Cherry, G. W., "A Class of Unified Explicit Methods for Steering Throttleable and Fixed-Thrust Rockets," R-417 Rev. Jan. 1964, MIT Instrumentation Lab., Cambridge, Mass. 2 Bond, V. R., "Linear Acceleration Guidance Scheme for Landing and Launch Trajectories in a Vacuum," TN D-2684, 1965, NASA. 3 Jezewski, D. J., Three-Dimensional Guidance Equations for Quasi-Optimum Space Maneuvers, XV IAF Congress, Vol. I, Gauthier-Villars, Paris PWN-Polish Scientific Publishers, Warsaw, 1965. 4 Lawden, D. F., Optimal Trajectories for Space Navigation, Butterworths, London, 1963, p. 56. 5 Fletcher, R. and Powell, M. J. D., "A Rapidly Convergent Descent Method for Minimization," The Computer Journal, Vol. 6, No. 2, July 1963, pp. 163-168. 6 Breakwell, J. V., "The Optimization of Trajectories," Journal of the Society for Industrial and Applied Mathematics, Vol. 7, No. 2, June 1959. 7 Peirce, B. O., A Short Table of Integrals, 4th ed., Blaisdell, Waltham, Mass., 1956.