Research on New Global Optimization by Excluding Hyperspheres and Its Applications

排除超球面的新全局优化研究及其应用

基本信息

批准号：
08455175
负责人：
SAKANIWA Kohichi
金额：
$ 2.94万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08455175/
关键词：
Global Optimization Excluding Hypersphere Covering Method Covering Test Dimension Reduction Lipschitz function Neural Network Fast Training

项目摘要

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.

本研究针对多维 Lipschitz 函数的优化（最小化）问题，并将新提出的优化算法应用于神经网络训练。尚未解决的关键问题是：给出一个算法来测试 N 维开球的并集是否覆盖另一个 N 维闭球。如果闭球没有被 N 维开球的并集覆盖，则从未覆盖的区域给出一个点。在这项研究中，我们通过发展一个称为降维定理的基本定理彻底解决了这个问题，该定理指出覆盖条件可以简化为较低维度的相似条件的集合。该简化定理基于一个简单的观察，即两个维度为 n 的球体的交集变成维度为 n-1 的球体。本研究开发的覆盖测试算法以O(NK^<N+1>)的计算复杂度来判断覆盖条件，其中K是开球的数量。该算法重复使用降维定理，直到条件变得微不足道。通过使用所提出的覆盖测试算法，我们还通过开发神经网络目标函数的Lipschitz常数估计方法，建立了神经网络的快速学习方法。