TRUST : a new global optimization methodology, application to artificial neural networks, and analog VLSI implementation

Citation

Cetin, Bedri Cag (1994) TRUST : a new global optimization methodology, application to artificial neural networks, and analog VLSI implementation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/gf87-7y12. https://resolver.caltech.edu/CaltechETD:etd-10192005-153248

Abstract

A new method for unconstrained global function optimization, acronymed TRUST, is introduced. This method formulates optimization as the solution of a deterministic dynamical system incorporating terminal repellers and a novel subenergy tunneling function. Benchmark tests comparing this method to other global optimization procedures are presented, and the TRUST algorithm is shown to be substantially faster.

This algorithm is provably convergent to the global minimum for objective functions of one variable. Theoretically, convergence to a global solution is not guaranteed in the multi-dimensional case. However, in practical applications, TRUST has found the global minimum in all multi-dimensional benchmark functions as a result of its global descent property. The TRUST formulation leads to a simple stopping criterion.

The algorithm is also applied to Backpropagation learning in artificial neural networks in order to overcome the susceptibility to local minima during training, which is associated with gradient descent. TRUST (or Global Descent in this context) was proposed as a candidate for replacing gradient descent in order to eliminate the local minima problem. We test the ability of the new dynamical system to overcome local minima with common benchmark examples and a pattern recognition example. The results demonstrate that the new method does indeed escape encountered local minima, and in most cases converges to the globally optimal solution of a specific problem.

The structure of the TRUST's equations enables an implementation of the algorithm in analog VLSI hardware for further substantial speed enhancement. We have designed, fabricated and tested a terminal repeller circuit and a gradient descent circuit, which constitute the main components of the TRUST's dynamics. Measured chip data, which confirmed the efficient performance of these circuits, are presented. We have also designed a novel global optimization circuit which incorporates the above circuits with additional control logic. This circuit implements the TRUST algorithm, and thus locates the global minimum of arbitrary one-dimensional objective functions. Simulated experiments of this circuit are thoroughly discussed. The convergence time required for the circuit to converge to the global minimum is remarkably at the order of micro-seconds.

Thesis Files