Perspectives on self-scaling variable metric algorithms

Recent attempts to assess the performance of SSVM algorithms for unconstrained minimization problems differ in their evaluations from earlier assessments. Nevertheless, the new experiments confirm earlier observations that, on certain types of problems, the SSVM algorithms are far superior to other variable metric methods. This paper presents a critical review of these recent assessments and discusses some current interpretations advanced to explain the behavior of SSVM methods. The paper examines the new empirical results, in light of the original self-scaling theory, and introduces a new interpretation of these methods based on anL-function model of the objective function. This interpretation sheds new light on the performance characteristics of the SSVM methods, which contributes to the understanding of their behavior and helps in characterizing classes of problems which can benefit from the self-scaling approach.The subject of this paper was presented at the ORSA/TIMS National Meeting in New York, 1978.This work was done while the author was with the Analysis Research Group, Xerox Palo Alto Research Center, Palo Alto, California.     

On variable dimension algorithms and algorithms using primitive sets

We discuss the basic scheme and convergence conditions of variable dimension algorithms for computing fixed points and show the analogy of the recent algorithm of van der Laan and Talman with a restart) algorithm using primitive sets that was devel-oped earlier by Tuy-Thoai-Muu. Furthermore, we show that to each algorithm of the class developed by van der Laan and Talman one can associate an algorithm using primi-tive sets wnich proceeds according to the same scheme but with a different triangulation.     

Analysis of a self-scaling quasi-Newton method

We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately.This work was supported by National Science Foundation Grant CCR-9101359, and by the Department of Energy Grant DE-FG02-87ER25047.This work was performed while the author was visiting Northwestern University.     

Global Optimal Solutions of Noncyclic Mappings in Metric Spaces

We study some minimization problems for noncyclic mappings in metric spaces. We then apply the solution to obtain some results in the theory of analytic functions.     

Parallel variable metric algorithms for unconstrained optimization

We classify Straeter's ideas for parallel unconstrained optimization and apply them to Huang's class of updating formulas. Straeter's rank-one updating formula appears to be the only parallel extension within Huang's class with the property of quadratic termination. We also develop a parallel extension of Broyden's (1965) rank-one updating formula and prove quadratic termination. Finally, we present numerical results, obtained by testing the algorithms on several standard example problems.     

Optimal mutation probability for genetic algorithms

We derive the value of the mutation probability which maximizes the probability that the genetic algorithm finds the optimum value of the objective function under simple assumptions. This value is compared with the optimum mutation probability derived in other studies. An empirical study shows that this value, when used with a larger scaling factor in linear scaling, improves the performance of the genetic algorithm. This feature is then added to a model developed by Hinton and Nowlan which allows certain bits to be guessed in an effort to increase the probability of finding the optimum solution.     

Optimal algorithms for iterated numerical integration

Iterated (repeated, successive) integration is used for integrating functions satisfying the Lipschitz condition. To construct an optimal (minimax) algorithm, it is necessary to integrate optimally functions evaluated with indefinite errors. Such a problem is solved by generalization of an algorithm from Ref. 1 which is sequentially optimal for one-dimensional problems.     

On some conditioning results in the probabilistic analysis of algorithms

A simple combinatorial approach is given for handling certain conditioning problems that arise in the probabilistic analysis of graph algorithms.     

Fast algorithms for designing variable FIR notch filters

The paper presents fast algorithms for designing finite impulse response (FIR) notch filters. The aim is to design a digital FIR notch filter so that the magnitude of the filter has a deep notch at a specified frequency, and as the notch frequency changes, the filter coefficients should be able to track the notch fast in real time. The filter design problem is first converted into a convex optimization problem in the autocorrelation domain. The frequency response of the autocorrelation of the filter impulse response is compared with the desired filter response and the integral square error is minimized with respect to the unknown autocorrelation coefficients. Spectral factorization is used to calculate the coefficients of the filter. In the optimization process, the computational advantage is obtained by exploiting the structure of the Hessian matrix which consists of a Toeplitz plus a Hankel matrix. Two methods have been used for solving the Toeplitz‐plus‐Hankel system of equations. In the first method, the computational time is reduced by using Block–Levinson's recursion for solving the Toeplitz‐plus‐Hankel system of matrices. In the second method, the conjugate gradient method with different preconditioners is used to solve the system. Comparative studies demonstrate the computational advantages of the latter. Both these algorithms have been used to obtain the autocorrelation coefficients of notch filters with different orders. The original filter coefficients are found by spectral factorization and each of these filters have been tested for filtering synthetic as well as real‐life signals. Copyright © 2007 John Wiley & Sons, Ltd.     

Metric Regularity Properties in Bang-Bang Type Linear-Quadratic Optimal Control Problems

Set-Valued and Variational Analysis - The paper investigates the Lipschitz/Hölder stability with respect to perturbations of optimal control problems with linear dynamic and cost functional...     

A combined class of self-scaling and modified quasi-Newton methods

Techniques for obtaining safely positive definite Hessian approximations with self-scaling and modified quasi-Newton updates are combined to obtain ??better?? curvature approximations in line search methods for unconstrained optimization. It is shown that this class of methods, like the BFGS method, has the global and superlinear convergence for convex functions. Numerical experiments with this class, using the well-known quasi-Newton BFGS, DFP and a modified SR1 updates, are presented to illustrate some advantages of the new techniques. These experiments show that the performance of several combined methods are substantially better than that of the standard BFGS method. Similar improvements are also obtained if the simple sufficient function reduction condition on the steplength is used instead of the strong Wolfe conditions.     

Optimal convex hull algorithms on enhanced meshes

In this paper we propose time-optimal convex hull algorithms for two classes of enhanced meshes. Our first algorithm computes the convex hull of an arbitrary set ofn points in the plane inO (logn) time on a mesh with multiple broadcasting of sizen×n. The second algorithm shows that the same problem can be solved inO (1) time on a reconfigurable mesh of sizen×n. Both algorithms achieve time lower bounds for their respective model of computation.This work was supported by NASA under grant NCCI-99.Additional support by the National Science Foundation under grant CCR-8909996 is gratefully acknowledged.     

Reoptimization procedures for bounded variable primal simplex network algorithms

Many algorithms and applications call for the use of a network subprogram which must be optimized numerous times with slight changes to the problem data. Bound and right-hand-side changes to an existing basis tree may yield an infeasible basic solution. This report gives a sequence of steps that modify an existing basic solution to reflect such changes and streamline the reoptimization process.     

Optimal surrender policy for variable annuity guarantees

This paper proposes a technique to derive the optimal surrender strategy for a variable annuity (VA) as a function of the underlying fund value. This approach is based on splitting the value of the VA into a European part and an early exercise premium following the work of Kim and Yu (1996) and Carr et al. (1992). The technique is first applied to the simplest VA with GMAB (path-independent benefits) and is then shown to be possibly generalized to the case when benefits are path-dependent. Fees are paid continuously as a fixed percentage of the fund value. Our approach is useful to investigate the impact of path-dependent benefits on surrender incentives.     

Optimal policies for playing variable wager HI-LO

Use of the HI-LO procedure by the gaming industry is ubiquitous—hence playing strategies of interest to gamblers and machine providers alike. Players’ tactics necessarily depend on goals being pursued and consistent with these, a variety of schemes ranging from the ‘aggressive’ to the ‘timid’ have evolved. Characteristics of the some of the best known of these—as far as they are applicable to a variable wager version of the HI-LO routine—are considered and contrasted. Of interest, results for a relatively risk-aversive scheme, played over a finite number of rounds are reconciled with those obtained asymptotically when maximizing capital growth is the priority.