求解绝对值方程的光滑牛顿算法

张焱娇

(天津大学，天津300072)

绝对值方程一般数学表达式如下:

其中:|x|表示的是对x的每个分量取绝对值.本文中研究的矩阵A和B矩阵为方阵:

绝对值方程是Rohn在中首次出提出的.目前求解绝对值方程的算法针对B=－I，

[1－5]中讨论了绝对值方程(1)(2)和(3)的一些性质.下面简单列举一下这些性质:如果绝对值等式(1)、(2)、(3)是可解的，则绝对值方程或者有惟一解，或者有多重解[3]，一般的绝对值规划(1)可以转换成一个线性互补问题[4].

Mangasarian提出算法是:将绝对值等式(3)转化成分段线性的凹极小化问题，利用连续化线性算法来求解.之后在参考文献[6]又中提出了一种广义牛顿法来求解绝对值方程(3)，要求A的奇异值严格大于1，此方法的有线性收敛性质已经得到了证明.之后Oleg Prokopyev在参考文献[7]中将绝对值方程(3)问题转化为0－1混合线性规划来进行求解.本文所做的工作是利用光滑牛顿算法来求解问题(2)和(3)，光滑化的思想[8－9].

本文中证明了在矩阵A的主对角线上的元素的绝对值大于矩阵B的主对角元素的绝对值，矩阵A、B对于可交换条件下，算法是适定的，具有全局收敛性质.根据参考文献[10－11]，绝对值方程的可解性问题是一个NP难的问题，所以本文不讨论绝对值方程解的存在性.

现将本文所使用的符号如下:对于向量x∈Rn，若x＞0表示的是向量x的每个分量都大于0;‖x‖表示向量x的欧式范数，对于向量y，s∈ Rn对于函数F:Rn→Rm，F'(x)表示函数F在点的Jacobi矩阵.

1 算法设计

1.1 NCP 函数

定义 设函数φ(a，b):R×R→R，如果满足φ(a，b)=0⇔a≥0，b≥0，且 ab=0 性质.

1.2 光滑牛顿法

定理1 对于绝对值等式Ax+B|x|=b，其中……