Signal modeling using the gradient search

This letter presents a new method for continuous signal modeling. Firstly, the continuous signal can be represented as a function of the trigonometric functional extension (Fourier series). Fourier series of the signal are parameterized by the fundamental frequency and unknown parameters. Then, the gradient-based iterative identification algorithm is derived, for estimating parameters of the signal model with known and unknown frequencies, separately. Finally, the simulation results indicate that the proposed algorithm is effective.     

A quadratic programming algorithm using conjugate search directions

A quadratic programming algorithm is presented, resembling Beale's 1955 quadratic programming algorithm and Wolfe's Reduced Gradient method. It uses conjugate search directions. The algorithm is conceived as being particularly appropriate for problems with a large Hessian matrix. An experimental computer program has been written to validate the concepts, and has performed adequately, although it has not been used on very large problems. An outline of the solution to the quadratic capacity-constrained transportation problem using the above method is also presented.While engaged in this research the author had a part-time post with the Manpower Services Commission.     

Conjugate gradient methods based on secant conditions that generate descent search directions for unconstrained optimization

Conjugate gradient methods have been paid attention to, because they can be directly applied to large-scale unconstrained optimization problems. In order to incorporate second order information of the objective function into conjugate gradient methods, Dai and Liao (2001) proposed a conjugate gradient method based on the secant condition. However, their method does not necessarily generate a descent search direction. On the other hand, Hager and Zhang (2005) proposed another conjugate gradient method which always generates a descent search direction.     

Slow motion of gradient flows

We present sufficient conditions on an energy landscape in order for the associated gradient flow to exhibit slow motion or “dynamic metastability.” The first condition is a weak form of convexity transverse to the so-called slow manifold, N. The second condition is that the energy restricted to N is Lipschitz with a constant δ?1. One feature of the abstract result that makes it of broader interest is that it does not rely on maximum principles.As an application, we give a new proof of the exponentially slow motion of transition layers in the one-dimensional Allen-Cahn equation. The analysis is more nonlinear than previous work: It relies on the nonlinear convexity condition or “energy-energy-dissipation inequality.” (Although we do use the maximum principle for convenience in the application, we believe it may be removed with additional work.) Our result demonstrates that a broad class of initial data relaxes with an exponential rate into a δ-neighborhood of the slow manifold, where it is then trapped for an exponentially long time.     

On search directions for minimization algorithms

Some examples are given of differentiable functions of three variables, having the property that if they are treated by the minimization algorithm that searches along the coordinate directions in sequence, then the search path tends to a closed loop. On this loop the gradient of the objective function is bounded away from zero. We discuss the relevance of these examples to the problem of proving general convergence theorems for minimization algorithms that use search directions.     

On the convergence of a class of algorithms using linearly independent search directions

Powell has shown that the cyclic coordinate method with exact searches may not converge to a stationary point. In this note we consider a more general class of algorithms for unconstrained minimization, and establish their convergence under the assumption that the objective function has a unique minimum along any line.     

A variational principle for gradient flows

We verify – after appropriate modifications – an old conjecture of Brezis-Ekeland ([3], [4]) concerning the feasibility of a global variational approach to the problems of existence and uniqueness of gradient flows for convex energy functionals. Our approach is based on a concept of self-duality inherent in many parabolic evolution equations, and motivated by Bolza-type problems in the classical calculus of variations. The modified principle allows to identify the extremal value –which was the missing ingredient in [3]– and so it can now be used to give variational proofs for the existence and uniqueness of solutions for the heat equation (of course) but also for quasi-linear parabolic equations, porous media, fast diffusion and more general dissipative evolution equations.Both authors were partially supported by a grant from the Natural Science and Engineering Research Council of Canada.This paper is part of this authors Masters thesis under the supervision of the first named author.Revised version: 31 March 2004     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

Combining and scaling descent and negative curvature directions

The aim of this paper is the study of different approaches to combine and scale, in an efficient manner, descent information for the solution of unconstrained optimization problems. We consider the situation in which different directions are available in a given iteration, and we wish to analyze how to combine these directions in order to provide a method more efficient and robust than the standard Newton approach. In particular, we will focus on the scaling process that should be carried out before combining the directions. We derive some theoretical results regarding the conditions necessary to ensure the convergence of combination procedures following schemes similar to our proposals. Finally, we conduct some computational experiments to compare these proposals with a modified Newton??s method and other procedures in the literature for the combination of information.     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.     

Combining simulated annealing with local search heuristics

We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality, improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities, in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems, we obtain new best heuristics.     

A convexity theorem for noncommutative gradient flows

In this survey we shall prove a convexity theorem for gradient actions of reductive Lie groups on Riemannian symmetric spaces. After studying general properties of gradient maps, this proof is established by (1) an explicit calculation on the hyperbolic plane followed by a transfer of the results to general reductive Lie groups, (2) a reduction to a problem on abelian spaces using Kostant's Convexity Theorem, (3) an application of Fenchel's Convexity Theorem. In the final section the theorem is applied to gradient actions on other homogeneous spaces and we show, that Hilgert's Convexity Theorem for moment maps can be derived from the results.     

Accelerated gradient descent methods with line search

We introduced an algorithm for unconstrained optimization based on the transformation of the Newton method with the line search into a gradient descent method. Main idea used in the algorithm construction is approximation of the Hessian by an appropriate diagonal matrix. The steplength calculation algorithm is based on the Taylor’s development in two successive iterative points and the backtracking line search procedure. The linear convergence of the algorithm is proved for uniformly convex functions and strictly convex quadratic functions satisfying specified conditions.     

On the asymptotic directions of thes-dimensional optimum gradient method

The optimums-gradient method for minimizing a positive definite quadratic functionf(x) onE _n has long been known to converge fors ≧+1. For theses the author studies the directions from which the iteratesx _k approach their limit, and extends tos>1 a theory proved byAkaike fors=1. It is shown thatf (x _k ) can never converge to its minimum value faster than linearly, except in degenerate cases where it attains the minimum in one step. Research sponsored by the U.S. Office of Naval Research under project NR 044211. Dedicated to ProfessorHeinrich Brinkmann for his seventieth birthday.     

On the uniqueness of search directions in variable-metric algorithms

Generalized variable-metric algorithms presented in Ref. 1 produce a unique search direction independently of parameters in the algorithms under several conditions. They generate a unique sequence of minimizing points for the given initial conditions if the objective function is quadratic.     

Global attractors for gradient flows in metric spaces

We develop the long-time analysis for gradient flow equations in metric spaces. In particular, we consider two notions of solutions for metric gradient flows, namely energy and generalized solutions. While the former concept coincides with the notion of curves of maximal slope of Ambrosio et al. (2005) [5], we introduce the latter to include limits of time-incremental approximations constructed via the Minimizing Movements approach (De Giorgi, 1993; Ambrosio, 1995 [3], [15]).For both notions of solutions we prove the existence of the global attractor. Since the evolutionary problems we consider may lack uniqueness, we rely on the theory of generalized semiflows introduced in Ball (1997) [7].The notions of generalized and energy solutions are quite flexible, and can be used to address gradient flows in a variety of contexts, ranging from Banach spaces, to Wasserstein spaces of probability measures. We present applications of our abstract results, by proving the existence of the global attractor for the energy solutions, both of abstract doubly nonlinear evolution equations in reflexive Banach spaces, and of a class of evolution equations in Wasserstein spaces, as well as for the generalized solutions of some phase-change evolutions driven by mean curvature.     

Matrix representation and gradient flows for NP-hard problems

Over the past decade, a number of connections between continuous flows and numerical algorithms were established. Recently, Brockett and Wong reported a connection between gradient flows on the special orthogonal groupLO(n) and local search solutions for the assignment problem. In this paper, we describe a uniform formulation for certain NP-hard combinatorial optimization problems in matrix form and examine their connection with gradient flows onLO(n). For these problems, there is a correspondence between the so-called 2-opt solutions and asymptotically stable critical points of an associated gradient flow.     

On the search for singularities in incompressible flows

In these notes we give some examples of the interaction of mathematics with experiments and numerical simulations on the search for singularities.     

Combining evolutionary and stochastic gradient techniques for system identification

In the present contribution, a novel method combining evolutionary and stochastic gradient techniques for system identification is presented. The method attempts to solve the AutoRegressive Moving Average (ARMA) system identification problem using a hybrid evolutionary algorithm which combines Genetic Algorithms (GAs) and the Least Mean Squares LMS algorithm. More precisely, LMS is used in the step of the evaluation of the fitness function in order to enhance the chromosomes produced by the GA. Experimental results demonstrate that the proposed method manages to identify unknown systems, even in cases with high additive noise. Furthermore, it is observed that, in most cases, the proposed method finds the correct order of the unknown system without using a lot of a priori information, compared to other system identification methods presented in the literature. So, the proposed hybrid evolutionary algorithm builds models that not only have small MSE, but also are very similar to the real systems. Except for that, all models derived from the proposed algorithm are stable.     

Constructing composite search directions with parameters in quadratic interpolation models

In this paper, we introduce the weighted composite search directions to develop the quadratic approximation methods. The purpose is to make fully use of the information disclosed by the former steps to construct possibly more promising directions. Firstly, we obtain these composite directions based on the properties of simplex methods and use them to construct trust region subproblems. Then, these subproblems are solved in the algorithm to find solutions of some benchmark optimization problems. The computation results show that for most tested problems, the improved quadratic approximation methods can obviously reduce the number of function evaluations compared with the existing ones. Finally, we conclude that the algorithm will perform better if the composite directions approach the previous steepest descent direction of the sub-simplex so far. We also point out the potential applications of this improved quadratic interpolation method in business intelligence systems.