0–1型二次规划的光滑函数法  

Smoothing Function Method for 0–1 Quadratic Programming

作　　者：王若鹏[1] 徐红敏[1] 

机构地区：[1]北京石油化工学院数理系,北京102617

出　　处：《工程数学学报》2012年第2期219-226,共8页Chinese Journal of Engineering Mathematics

基　　金：北京市自然科学基金(4082012);北京市属高等学校人才强教计划资助项目(IHLB)~~

摘　　要：本文针对工程设计、经济分析及计算机辅助设计等领域出现的0–1型二次规划问题,提出了Newton型的光滑迭代算法.首先利用NCP函数将0–1规划转化为不可微优化问题,然后通过构造不可微问题的光滑一致逼近,将组合优化问题转化成了可微的无约束优化问题,克服了已有算法收敛速度慢且计算结构复杂的缺点.文中给出了算法的迭代格式,证明了光滑函数的有关性质及其算法收敛性.通过理论分析及数值仿真证明了该算法对初始点不敏感,收敛速度快,且数值稳定,从而验证了模型和算法的可行性及有效性.In this paper,a novel smoothing function method basing on Newton method is presented to solve 0–1 quadratic programming which have been extensively used in engineering design,economic analysis and CAD etc.First of all,we propose the unconstrained indifferential optimization model through NCP function,and present an approximate algorithm differential function.Then,we transfer the problem to the unconstraint optimization problem.The theoretical analysis and numerical experiment illustrate that the algorithm is fast and insensitive to the initial point,and the smoothing function method is feasible and effective for 0–1 quadratic programming.

关 键 词：0–1规划 光滑函数 NCP函数 算法 

分 类 号：O221[理学—运筹学与控制论]