约束优化模式搜索法研究进展  

Research Advances on Pattern Searches in Constrained Optimization

作　　者：黄天云[1] 

机构地区：[1]西南民族大学计算机科学与技术学院,成都610041

出　　处：《计算机学报》2008年第7期1200-1215,共16页Chinese Journal of Computers

基　　金：国家民族事务委员会科研项目基金(05XN09)资助

摘　　要：实际工程应用中的优化问题通常包含复杂的约束条件,其目标函数可能是非线性、非连续、不可微甚至随机函数;而约束函数可能是线性、非线性、离散变量集,甚至黑盒函数(例如,由程序代码生成的值集合);约束变量也可能是包含连续、离散或分类值的混合变量.这些复杂的情况,使得没有任何导数/梯度信息可供利用,因此无法利用现有的凸优化技术求解.文中研究如何利用模式搜索法对常见的混合变量约束优化模型进行求解.首先对直接搜索法的发展历史进行概述;特别地,给出模式搜索法统一的数学描述和收敛性分析.对约束条件从无约束(一般模式搜索)到线性约束(广义模式搜索GPS)、非线性约束(GPS过滤法)和混合约束(广义混合变量规划GMVP)的推广以及在边界约束条件下,算法搜索方向从有限集向紧致集的扩展(网格自适应直接搜索MADS),进行了全面分析;在此基础上对该领域尚存在的问题及进一步的研究方向进行了总结.Many complicated optimization models in engineering are mixed-variable constrained, containing high-dimensional continuous, discrete or even categorical variables. The objectives may be non-differentiable and contaminated by random noises, i. e. , the problem is non smooth. No information of the gradient is available or trustworthy. The constraints may be linear or nonlinear, discrete sets, or even black-box functions generated from stochastic simulations or codes. Hence, direct searches that need no recourse to explicit derivatives are revived and become popular since the new century. A historical overview of the direct searches is given in this paper. Specially, the unified mathematical description and convergence analysis of pattern searches in recent years are discussed. Pattern searches in constrained optimization are thoroughly analyzed, from bound and linear constrained problems （Generalized Pattern Searches, GPS）, to non-linear constrained （GPS Filter） and mixed variables constrained programming （GMVP）. The new extension on the poll directions to a dense space in Mesh Adaptive Direct Search（MADS） is also identified. Some existing problems and future directions in this field are pointed out with thoughtful discussions.

关 键 词：约束优化 直接搜索法 模式搜索法 广义模式搜索GPS GPS过滤法 广义混合变量规划GMVP 网格自适应直接搜索MADS 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]