张慧雯,王 薇,李 民,徐以汎

(1.华东理工大学数学系,上海 200237)

(2.复旦大学管理学院,上海 200433)

1 引言与假设

本文讨论如下带线性约束的全局优化问题,

其中f(x):Rn→R为非凸函数,A为m×n阶矩阵,b=(b1,b2,b3,···,bm)T∈Rm.对约束问题(1.1),称所有满足约束的点为可行点,由所有可行点组成的集合X={x∈Rn:Ax≤b}为可行域.一般说来,问题(1.1)有多个极小值,用传统方法求解只能得到局部最优,而且对于全局最优解的判定条件至今都缺少实用的研究成果,这都使得问题求解仍然面临着许多困难.

填充函数法是求解多极值最优化问题的常用算法之一,其主要思想是:在求得问题的一个局部极小点后,构造填充函数.通过极小化该填充函数,寻找比当前局部极小点更优的点,进而得到更优的极小值[1−5].与其他方法相比,该算法思想简单,而且仅用到经典算法,所以易于实现且效率较高,同时也可以推广到其他非线性问题以及离散数学规划的求解中[6].

滤子技术最早由Fletcher和Leyffer提出,他们详细讨论了滤子作为代替罚函数的工具在局部优化算法中的一些应用[7,8].之后滤子技术在局部优化问题的求解中被认为是一种更有效的方法,因其良好的数值效果,许多学者继续进行了一系列的相关研究[9−11].

梯度投影算法自从被Rosen[12]提出后就引起了广泛的注意和系统的研究[13,14],由于该方法简单、实际应用的数值效果好,在一些更有效的近代算法中也继续沿用了它的基本思想[15,16].本文为了优化填充函数算法,将滤子技术和改进的梯度……