Research on New Global Optimization by Excluding Hyperspheres and Its Applications

本文研究了多维Lipschitz函数的优化（最小化）问题，并将新提出的优化算法应用于神经网络的训练。尚未解决的关键问题是：给出一个算法来检验n维开球的并集是否覆盖另一个n维闭球。如果封闭球没有被n维开放球的并集覆盖，给出一个来自未覆盖区域的点。在本研究中，我们通过发展一个基本定理——降维定理彻底解决了这一问题，该定理认为覆盖条件可以被约简为低维相似条件的集合。这个约简定理是基于一个简单的观察，即两个n维的球体相交会变成一个n-1维的球体。本研究开发的覆盖测试算法判断覆盖情况，计算复杂度为0 (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.