求解全局优化问题的滤子方法及其应用

The main consideration of the item is how to use the filter technique for some algorithms, such as filled function method, genetic algorithm so that to solve the noncovex global optimization. The new algorithms will be presented and their characters will be styded in the item. We are also planning to apply the new algorithms into some practical problems, such as ecnomical lotting size model. At the same time, we will find several globally optimal conditions for some special programming in order to make them be the convergence criterion of the algorithm. There exists a lot of methods for unconstrained global optimization, but many problems need dealing with yet. Furthmore, there still exists a few of research result for constraied global optimizations. So, it is a important work how to use the efective methods to solve the nonconvex optimizations in the good way. The filter method is a technique for finding constrained local minimizer, and it is recognized because of its nice behavior in numerical caculation. On the other hand , the filled functions and the genetic algorithm are the practical method for global optimization. We will deepen and perfect the study on filled function and genetic algorithm. at the same time, the new algorithm will be presented using the filtration characters of the filter and the properties of the algorithm will be proved. We will deal with the difficulties caused by the minimizer on the border in effective way and analize the numerrical results in practical applications;We will try combine genetic method with filled functions for solving global problems in better way. Meanwhile, the globally optimal conditions on indefinite quadratic programming will be presented, in which the data of the problem self are concerned without Lagrange multiplier.

本项目考虑将滤子技术应用到求解非凸全局优化的一些算法：填充函数、打洞函数、遗传算法等，给出新的算法，讨论性质，并将它们应用在经济批量模型求解等实际问题中，同时对某些特殊规划寻求可以成为算法终止准则的全局最优条件。虽然求解无约束的非凸全局优化问题已有了一些方法，但仍有许多问题需要解决，而且对约束全局问题的研究仍然比较少。滤子方法是求解约束优化局部最优解的一个技巧，因其良好的数值效果得到大家的认可。而填充函数方法和遗传算法是求解全局优化问题的有效算法。我们将一方面深化和完善对填充函数方法和遗传方法的研究，另一方面利用滤子的过滤特性提出全新的算法，证明方法的理论性质，有效处理局部极小点出现在边界上对求解带来的困难，分析方法在实际应用中的计算效果；尝试遗传算法和填充函数方法的结合，提高全局问题的效率。同时在理论上建立不用Lagrange乘子，只用问题本身的数据来表示约束不定二次规划的全局最优条件。

最优化问题出现在生产和社会的各行各业中, 其数学模型往往是多极值的全局优化问题. 然而求解非凸全局优化问题的理论和算法是一类比较困难的问题, 主要原因有两个, 一个是难以找到实用的全局最优性条件, 一个是算法陷在局部最优点难以跳出或者找不到下降方向. 本项目根据问题的难点, 主要做了两方面的工作: 1. 对非凸全局优化问题提出了一些基于滤子技术的算法; 2. 针对0-1整数规划提出了几个局部和全局最优性条件, 并给出了几个背包问题的算法. .滤子技术因其良好的数值结果被用于求解局部优化问题, 而辅助函数方法和随机方法是求解多极值全局优化问题有效方法. 为优化非凸全局优化问题的求解方法, 本项目将滤子技术应用到填充函数方法, 遗传算法, 广义投影方法等方法中, 给出了一些新的算法及其理论性质, 特别的对于带约束的非凸问题进行了有益的探讨. 滤子技术应用到全局优化问题中未曾在其它文献见到. 在辅助函数类的算法中借助于滤子的过滤性, 以滤子作为判断标准在算法上替代了收敛准则, 对算法的有效性起了重要作用, 因为缺乏实用的收敛准则. 在随机算法中, 利用滤子的过滤性而不用适应度函数来判定个体的优劣，可以保证子代的优化性和进化的顺利进行，也避免了使用罚函数作为适应度函数需要选择罚参数的问题和由此引起的计算不稳定问题..对于不定0-1二次规划提出了显式的局部和全局最优性条件, 将局部最优性条件归类在1-flip, 2-flip和 k-flip邻域内, 并在价值向量和价值矩阵的定义下, 提出了算法,使得在1-flip和2-flip情况下可在多项式时间内得到局部解. 提出了局部最优解和全局最优解之间的关键联系. 另外还给出了几个二次背包问题的有效算法.