Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k ?a _k (▽U(X _k ) + ξ_k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ? ^d , {ξ_k} is a sequence of ? ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), {ξ _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.     

sensitivity minimization for delay systems

This paper announces results on the problem of feedback compensator design for ^∞ norm weighted sensitivity minimization when the plant contains a delay in the input. A complete solution is presented for the case of one pole/zero weighting function and a single-input/single-output plant for stable minimum-phase rational part. Generalizations and proofs will be published elsewhere.     

The conjugate gradient method for optimal control problems

This paper extends the conjugate gradient minimization method of Fletcher and Reeves to optimal control problems. The technique is directly applicable only to unconstrained problems; if terminal conditions and inequality constraints are present, the problem must be converted to an unconstrained form; e.g., by penalty functions. Only the gradient trajectory, its norm, and one additional trajectory, the actual direction of search, need be stored. These search directions are generated from past and present values of the objective and its gradient. Successive points are determined by linear minimization down these directions, which are always directions of descent. Thus, the method tends to converge, even from poor approximations to the minimum. Since, near its minimum, a general nonlinear problem can be approximated by one with a linear system and quadratic objective, the rate of convergence is studied by considering this case. Here, the directions of search are conjugate and hence the objective is minimized over an expanding sequence of sets. Also, the distance from the current point to the miminum is reduced at each step. Three examples are presented to compare the method with the method of steepest descent. Convergence of the proposed method is much more rapid in all cases. A comparison with a second variational technique is also given in Example 3.     

Hierarchical Image Segmentation—Part I: Detection of Regular Curves in a Vector Graph

The problem of edge detection is viewed as a hierarchy of detection problems where the geometric objects to be detected (e.g., edge points, curves, regions) have increasing complexity and spatial extent. An early stage of the proposed hierarchy consists in detecting the regular portions of the visible edges. The input to this stage is given by a graph whose vertices are tangent vectors representing local and uncertain information about the edges. A model relating the input vector graph to the curves to be detected is proposed. An algorithm with linear time complexity is described which solves the corresponding detection problem in a worst-case scenario. The stability of curve reconstruction in the presence of uncertain information and multiple responses to the same edge is analyzed and addressed explicitly by the proposed algorithm.     

A unified framework for hybrid control: model and optimal controltheory

We propose a very general framework that systematizes the notion of a hybrid system, combining differential equations and automata, governed by a hybrid controller that issues continuous-variable commands and makes logical decisions. We first identify the phenomena that arise in real-world hybrid systems. Then, we introduce a mathematical model of hybrid systems as interacting collections of dynamical systems, evolving on continuous-variable state spaces and subject to continuous controls and discrete transitions. The model captures the identified phenomena, subsumes previous models, yet retains enough structure to pose and solve meaningful control problems. We develop a theory for synthesizing hybrid controllers for hybrid plants in all optimal control framework. In particular, we demonstrate the existence of optimal (relaxed) and near-optimal (precise) controls and derive “generalized quasi-variational inequalities” that the associated value function satisfies. We summarize algorithms for solving these inequalities based on a generalized Bellman equation, impulse control, and linear programming     

Bioremediation of direct dyes in simulated textile effluents by a paramorphogenic form of Aspergillus oryzae

Azo dyes are extensively used for coloring textiles, paper, food, leather, drinks, pharmaceutical products, cosmetics and inks. The textile industry consumes the largest amount of azo dyes, and it is estimated that approximately 10-15% of dyes used for coloring textiles may be lost in waste streams. Almost all azo dyes are synthetic and resist biodegradation, however, they can readily be reduced by a number of chemical and biological reducing systems. Biological treatment has advantages over physical and chemical methods due to lower costs and minimal environmental effect. This research focuses on the utilization of Aspergillus oryzae to remove some types of azo dyes from aqueous solutions. The fungus, physically induced in its paramorphogenic form (called 'pellets'), was used in the dye biosorption studies with both non-autoclaved and autoclaved hyphae, at different pH values. The goals were the removal of dyes by biosorption and the decrease of their toxicity. The dyes used were Direct Red 23 and Direct Violet 51. Their spectral stability (325-700 nm) was analyzed at different pH values (2.50, 4.50 and 6.50). The best biosorptive pH value and the toxicity limit, (which is given by the lethal concentration (LC(100)), were then determined. Each dye showed the same spectrum at different pH values. The best biosorptive pH was 2.50, for both non- autoclaved and autoclaved hyphae of A. oryzae. The toxicity level of the dyes was determined using the Trimmed Spearman-Karber Method, with Daphnia similis in all bioassays. The Direct Violet 51 (LC(100) 400 mg · mL(-1)) was found to be the most toxic dye, followed by the Direct Red 23 (LC(100) 900 mg · mL(-1)). The toxicity bioassays for each dye have shown that it is possible to decrease the toxicity level to zero by adding a small quantity of biomass from A. oryzae in its paramorphogenic form. The autoclaved biomass had a higher biosorptive capacity for the dye than the non-autoclaved biomass. The results show that bioremediation occurs with A. oryzae in its paramorphogenic form, and it can be used as a biosorptive substrate for treatment of industrial waste water containing azo dyes.     

Simulated annealing type algorithms for multivariate optimization

We study the convergence of a class of discrete-time continuous-state simulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the formX _k +1 =X _k –a _k (U(X _k ) + _k) +b _k W _k . HereU(·) is a smooth function on a compact subset of ^d , {_k} is a sequence of ^d -valued random variables, {W _k } is a sequence of independent standardd-dimensional Gaussian random variables, and {a _k }, {b _k } are sequences of positive numbers which tend to zero. These algorithms arise by adding decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show under suitable conditions onU(·), { _k }, {a _k }, and {b _k } thatX _k converges in probability to the set of global minima ofU(·). A careful treatment of howX _k is restricted to a compact set and its effect on convergence is given.Research supported by the Air Force Office of Scientific Research contract 89-0276B, and the Army Research Office contract DAAL03-86-K-0171 (Center for Intelligent Control Systems).     

The Solution of Linear Probabilistic Recurrence Relations

Linear probabilistic divide-and-conquer recurrence relations arise when analyzing the running time of divide-and-conquer randomized algorithms. We consider first the problem of finding the expected value of the random process T(x) , described as the output of a randomized recursive algorithm T . On input x , T generates a sample (h1,···,hk) from a given probability distribution on [0,1]k and recurses by returning g(x) + Σi=1kciT(hi x) until a constant is returned when x becomes less than a given number. Under some minor assumptions on the problem parameters, we present a closed-form asymptotic solution of the expected value of T(x) . We show that E[T(x)] = Θ( xp + xp∈t1x(g(u)/ up+1 ) du) , where p is the nonnegative unique solution of the equation Σi=1kciE[hip] = 1 . This generalizes the result in [1] where we considered the deterministic version of the recurrence. Then, following [2], we argue that the solution holds under a broad class of perturbations including floors and ceilings that usually accompany the recurrences that arise when analyzing randomized divide-and-conquer algorithms.