封京梅, 卢　楠

(1.陕西广播电视大学 工程管理系, 陕西 西安　710119; 2.西安电子科技大学 数学与统计学院， 陕西 西安　710126)



基于遗传算法与模式搜索的混合算法求解绝对值方程

封京梅1, 卢楠2

(1.陕西广播电视大学 工程管理系, 陕西 西安710119; 2.西安电子科技大学 数学与统计学院， 陕西 西安710126)

摘要：绝对值方程Ax-|x|=b是一类不可微的NP-hard问题.在假设A的奇异值>1的条件下，给出一种新的求解绝对值方程的混合算法：遗传算法和模式搜索法相结合的一种方法.该混合算法充分发挥了遗传算法较强的全局搜索能力和模式搜索法较强的局部搜索能力的优点，有效避开了遗传算法容易陷入早熟收敛，模式搜索法对初始点要求高的缺点，数值实验结果表明了该算法的可行性和有效性.

关键词：绝对值方程； 遗传算法； 模式搜索法

0引言

考虑如下形式的绝对值方程(absolute value equations, AVE)：

Ax-|x|=b

(1)

其中A∈Rn×n,x,b∈Rn,|x|表示对x的各个分量取绝对值.

首先Mangasarian在文献[1]中给出了(1)式有唯一解、非负解、2n个解及无解的充分条件，之后许多学者在(1)式存在唯一解的前提下对其算法进行了深入的研究；文献[2,3]在无任何假设条件下把AVE用半光滑牛顿算法转换为二阶锥互补问题，利用二阶锥互补问题的研究结果，给出了AVE解的凸性；文献[4]给出了求解绝对值方程的非内部连续化算法；文献[5,6]基于极大熵光滑化处理方法，给出了(1)式的极大熵自适应微粒群混合算法、极大熵牛顿算法;文献[7,8]给出了智能算法中的差分进化-单纯形混合算法、交叉熵蝙蝠算……