非正则典范DC规划问题中的外逼近算法研究

项目名称： 非正则典范DC规划问题中的外逼近算法研究

项目编号： No.11201351

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

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 张青华

作者单位： 武汉大学

项目金额： 22万元

中文摘要： 典范DC规划问题是一类重要的非线性规划问题，其算法在工程、经济和管理等领域中有着广泛应用。典范DC规划领域的全局优化算法一般为外逼近法（或称割平面法）。现有的外逼近算法建立在以正则条件为前提的TUY全局最优性条件基础之上，因此在非正则DC问题中不能保证全局收敛性。本课题将基于申请人给出的适用于所有正则和非正则问题的新型全局最优性条件，结合典范DC规划问题自身特性，设计相应的最优性检验方法以及基于外逼近法和割平面法的全局收敛条件体系和搜索方法，从而构造出可适用于所有正则与非正则问题的外逼近算法，证明其全局收敛性并在部分优化模型中予以实现。本课题研究方法和算法设计思路具有鲜明特色和创新性，是申请人在已有研究基础上具有原创性质的探索，拟构造算法在适用范围上显著优于现有的外逼近算法。课题解决的是DC规划领域的重要难题，其成果对非线性规划领域的研究有着重要的理论价值和实际意义。

中文关键词： 全局优化；典范 DC 规划；外逼近算法；正则条件；割平面算法

英文摘要： Canonical DC programs is one important class of nonlinear programming problems, and their algorithms have many practical and theoretical applications in engineering, economics, management and other fields. The global optimization algorithms for canonical DC programs are usually outer approximation algorithms (conjunctive cutting plane algorithms). However, the existing outer approximation algorithms are based on Tuy's optimality condition, which is only applicable to regular canonical DC programs. Therefore, the existing algorithm can not guarantee global convergence in non-regular DC instances. The proposed algorithm will be based on applicant's new necessary and sufficient global optimality condition, and utilize the special structural property of canonical DC programs. Then the project will propose a procedure to check the global optimality condition and build an outer approximation algorithmic framework. Finally, the project will establish a novel outer approximation algorithm that can be applied to solving all regular and non-regular canonical DC problems, and implement it in some well-known mathematical models. The research methodology is innovative and exploratory, and the topic of the project is a major challenge in DC programming fields. The result would be of theorectical significance and practical v

英文关键词： global optimization；canonical DC programs；outer approximation algorithm；regularity condition；cutting plane algorithm