Variable Metric Algorithm

Fletcher, R. A New Approach to Variable Metric Algorithms. Comput J13 317 (1970). 

Self-scaling Variable Metric Algorithms", Math. Programming, 1976, 10, (1), 70-90. 

L. C. W. Dixon, SIAM J. Opt., 1,475 (1991). On the Impact of Automatic Differentiation on the Relative Performance of Parallel Truncated Newton and Variable Metric Algorithms. 

Han, S. P. (1976), Superlinearly Convergent Variable Metric Algorithms for General Nonlinear Programming Problems, Mathematical Programming, Vol. 11, pp. 263—282. 

Fletcher, R. (1970) A new approach to variable metric algorithms. Computer Journal, 13 (13), 317-322,... 

Owing to the constraints, no direct solution exists and we must use iterative methods to obtain the solution. It is possible to use bound constrained version of optimization algorithms such as conjugate gradients or limited memory variable metric methods (Schwartz and Polak, 1997 Thiebaut, 2002) but multiplicative methods have also been derived to enforce non-negativity and deserve particular mention because they are widely used RLA (Richardson, 1972 Lucy, 1974) for Poissonian noise and ISRA (Daube-Witherspoon and Muehllehner, 1986) for Gaussian noise. 

There are many variants of this kind of algorithm and examples of some of them may be found in chapter 4 of ref. 8. It should also be pointed out that such methods may be combined with those variable metric methods which estimate A-1, so that instead of calculating A 1 at every stage, an estimate of it may be obtained merely by updating the previously calculated matrix. Some examples of studies undertaken by such a combined method may be found in the review by Yde.27... 

Non-linear programming is a fast growing subject and much research is being done and many new algorithms appear every year. It seems to the Reporters that the current area of major interest in the field is the area of variable-metric methods, particularly those not needing accurate linear searches. Unfortunately, from a quantum chemical point of view, such methods are liable to be of use only in exponent and nuclear position optimization and in this context, as we have seen, Newton-like methods are also worth serious consideration. 

The default method in GAUSSIAN 88-92 (BERNY) employs a variable metric method which takes a Newton-Raphson step if the correct number of negative eigenvalues is found in the Hessian and aborts otherwise. While this action may avoid wasting computer time on a fruitless search for a stationary point, in many cases the algorithm can recover from this situation by simply... 

As a rule, independent data points are required to solve a harmonic function with N variables numerically. Because a gradient is a vector N long, the best one can hope for in a gradient-based minimizer is to converge in N steps. However, if one can exploit second-derivative information, an optimization could converge in one step, because each second derivative is an V x V matrix. This is the principle behind the variable metric optimization algorithms such as Newton-Raphson method. 

The same idea can be developed in the case of a non-Euclidean metric such as the city-block metric or L,-norm (Section 31.6.1). Here we find that the trajectories, traced out by the variable coefficient kj are curvilinear, rather than linear. Markers between equidistant values on the original scales of the columns of X are usually not equidistant on the corresponding curvilinear trajectories of the nonlinear biplot (Fig. 31.17b). Although the curvilinear trajectories intersect at the origin of space, the latter does not necessarily coincide with the centroid of the row-points of X. We briefly describe here the basic steps of the algorithm and we refer to the original work of Gower [53,54] for a formal proof. 

Johnson, M. (1985) Relating metrics, lines, and variables defined on graphs to problems in medicinal chemistry. In Graph theory and its applications to algorithms and computer science, Alavi, Y., et al. (eds.), John Wiley Sons, New York, pp. 457-470. 

F Lindgren, P Geladi, S Rannar, and S Wold. Interactive variable selection (IVS) for PLS. Part I. Theory and algorithms. J. Chemo-metrics, 8 349-363, 1994. 

Some ftirther research activities can be related to the use of some (heuristic) algorithms to speed up the optimmn search, such as those proposed in (Lisniansky and Levitin 2003 Taboada et al. 2008). Furthermore, alternative performance metrics for a performa-bility evaluation of the system can be investigated, such as the call set-up delay, and a variable service demand level can be considered. 

---