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

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

项目编号： No.61503233

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 其他

项目作者： 顾申申

作者单位： 上海大学

项目金额： 21万元

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

中文关键词： 神经网络；优化；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.

英文关键词： neural network;optimization;0-1 quadratic programming;global optimal algorithm