基于神经网络的无约束0-1二次规划全局最优算法研究

The neural network based algorithms have obvious advantages in solving large scale optimization problems. The Unconstrained 0-1 Quadratic Programming has important theory and wide application. And in recently years, this problem has become a research focus. Since the Unconstrained 0-1 Quadratic Programming is a classic NP-hard problem, it cannot get the global optimal algorithm by applying the neural network itself only. It leads to the fact that applying neural network based algorithm to get the global optimal solution of the unconstrained 0-1 quadratic programming is still a blank field. For this reason, this project is aiming at an neural network based global optimal algorithm for 0-1 Quadratic Programming by analyzing and utilizing geometric characteristics of the objective function isosurface and combining the advantages and properties of neural networks as well as branch and bound method. On one hand, the project will explore the qualitative and quantitative relationship between objective function and isosurface geometry. And based on the theoretical basis, it further explore applying neural network to deal with some significant optimization and sorting problems, since it will improve the efficiency of algorithm for conventional problems. On the other hand, this project will study the optimal conditions of 0-1 quadratic programming by analyzing the geometric characteristics to obtain the polynomial time solvable algorithms for the special problems and their neural network implementations. This project aims at constructing a neural network based global optimal algorithm for 0-1 Quadratic Programming. It will be later on proven its efficiency by numerical simulation. And by doing this, it will hew out a new approach to this difficult problem and expand the application of neural networks.

神经网络优化算法在处理大规模优化问题方面具有明显的优势。无约束0-1二次规划因其具有重要的理论意义和广泛的应用价值，是近年来的研究热点。但是由于该问题是NP难问题，仅仅应用神经网络无法得到该问题的全局最优确定算法，造成利用神经网络算法计算该问题的全局最优解仍属于空白。对此，本项目将通过分析目标函数所蕴含的重要几何性质并充分结合神经网络与分枝定界方法的优势与特点，设计0-1二次规划基于神经网络的算法。一方面探索目标函数与等值面几何形态之间定性与定量关系，并在此理论基础上研究利用神经网络方法来处理关键的优化和排序问题，从而提高求解常规问题算法的效率。另一方面从几何特性出发研究0-1二次规划的最优性条件，设计求解特殊问题的多项式时间算法及其神经网络实现。本项目旨在通过对问题深层次的认识，建立一种基于神经网络的全局最优算法，并通过数值实验证明其高效性，为求解此类难题和拓展神经网络应用开辟新的途径。

0-1二次规划问题是一个经典的整数优化问题并且也是一个众所周知的NP难问题。为了改进0-1二次规划问题的全局优化算法的性能，本项目分别对0-1二次规划的特殊问题和一般问题提出了一系列有效的算法。对于特殊问题，本项目在三对角无约束0-1二次规划问题算法的基础上，提出了五对角和七对角无约束0-1二次规划问题的有效解法，并推导出针对多奇数对角0-1二次规划问题的多项式时间算法。在此基础上引入动态规划的思想，提出了新的适用于多奇数对角带约束0-1二次规划问题的算法。通过算法实现与验证，结果显示相关算法能快速解决特殊的高维问题。对于一般问题，在本项目中我们提出了一种新型的确切解算法。通过研究原问题的几何特性，我们提高了算法计算上界和下界的质量。然后对于推导出的上界和下界算法，我们提出并应用了相关的反馈神经网络模型以提高计算速度。进一步，我们通过FPGA硬件对相关的神经网络算法进行实现来充分利用神经网络的平行结构。数值结果显示我们提出的基于神经网络的分支定界类型的算法具有非常好的效果与效率。