Research on New Global Optimization by Excluding Hyperspheres and Its Applications

本研究探讨多维Lipschitz函数的最佳化（最小化）问题，并将新提出的最佳化演算法应用于神经网路的训练。尚未解决的关键问题是：给出一个检验一个N维开球面的并集是否覆盖另一个N维闭球面的算法。在本研究中，我们通过发展一个基本定理--降维定理来彻底解决这个问题，该定理指出覆盖条件可以被降维为一个低维的相似条件的集合。这个约化定理是基于一个简单的观察，即两个n维球面的相交成为一个n-1维球面。本文提出的覆盖测试算法以O（NK^<N+1>）的计算复杂度判断覆盖条件，其中K是开球的个数。该算法反复使用降维定理直到条件变为平凡，并利用覆盖测试算法，通过提出神经网络目标函数Lipschitz常数的估计方法，建立了神经网络的快速学习方法。

This research treats the problem of optimizing (minimizing) the multi-dimensional Lipschitz function and applies the newly proposed optimization algorithm to neural network training. The key problem which has been unsolved is :Give an algorithm which tests if a union of N-dimensional open spheres covers another N-dimensional closed sphere. And if the closed sphere is not covered by the union of N-dimensional open spheres, give a point from the uncovered region.In this research, we completely solved this problem by developing a fundamental theorem named dimension reduction theorem which states that the covering condition can be reduced to a collection of similar conditions of lower dimension. This reduction theorem is based on a simple observation that the intersection of two spheres of dimension n becomes a sphere of dimension n-1. The covering test algorithm developed in this research judges the covering condition with the computational complexity of O (NK^<N+1>), where K is the number of open spheres. This algorithm repeatedly uses the dimension reduction theorem until the conditions become trivial.By using the proposed covering test algorithm, we also established a fast learning method for neural networks by developing an estimation method of Lipschitz constant for the neural network objective function.