廣義線性互補問題的極大熵牛頓算法

王愛祥

?

廣義線性互補問題的極大熵牛頓算法

王愛祥

(常州廣播電視大學信息與工程學院，江蘇，常州 213001)

借助一類特殊的絕對值方程，將廣義線性互補問題等價轉化為非線性方程組?；跇O大熵函數，提出了一個牛頓算法，證明了算法的局部收斂性。數值結果也驗證了算法的有效性。

廣義線性互補問題；絕對值方程；極大熵；牛頓算法

0 引言

廣義線性互補問題（1）經常出現在偏微分不等式的有限差分法求解中，非線性網絡，控制理論以及機械工程應用方面。同時，它也是經典的線性互補問題

的一個擴展。文獻[1]研究了廣義線性互補問題（1）解的存在性。文獻[2]建立了廣義線性互補問題（1）的無約束優化問題的轉化形式，并用下降算法來求解。文獻[3]給出了一個信賴域算法來求解廣義線性互補問題（1）。文獻[4]給出了非光滑的L-M算法，在適當條件下，證明了算法的全局收斂性。

本文不同于以往算法，而是將廣義線性互補問題（1）轉化成一個新的絕對值方程組，并且建立了一個牛頓算法來求解。

1 廣義線性互補問題的解

下面給出廣義線性互補問題唯一可解的充要條件。根據定理3[1]有

引理1.1對任意，，廣義線性互補問題

定理1.1 廣義線性互補問題（1）等價于絕對值方程

證明 考慮每一個分量，根據

可知廣義線性互補問題(1)等價于

證畢。

由定理1.1可知，廣義線性互補問題（1）可以轉化為絕對值方程（1.1）來進行求解。

2 極大熵函數

的解就是絕對值方程（2.1）的解且

證畢。

3 牛頓算法及其局部收斂性

下面給出牛頓算法進行求解。

算法3.1

步驟1 計算

下面分析算法的收斂性和收斂速度。

引理3.1 證明類似于文獻[7]，此處省略。

證畢。

4 數值算例

例1（隨機測試）求解廣義線性互補問題

隨機生成初始向量

迭代結果為

運算結果表1所示。

表1 計算結果

Table 1 Computing result

考慮數值精度，計算

可見，算法提高了數值的精度。這也說明了算法的有效性。

本文基于極大熵建立了求解廣義線性互補問題的一個牛頓算法，證明了算法的收斂性。然而，算法過程中涉及到矩陣求逆，因此初始點的選取還有一定的要求。同時，算法僅能保證局部收斂。如何構造全局收斂的有效算法有待于進一步思考與研究。

[1] 張超, 修乃華. 關于擴張的垂直線性互補問題的V-P性質[J]. 北方交通大學學報, 2003,27(6): 86-91.

[2] Tseng P, Yamashita N, Fukushima M. Equivalence of complementarity problems to differentiable minimization: A unified approach [J]. SIAM J Optim, 1996, 6:446-460.

[3] Jiang H, Fukushima M, Qi L, Sun D. A trust region method for solving generalized complementarity problems [J]. SIAM J Optim, 1998, 8:140-157.

[4] Wang Y, Ma F, Zhang J. A nonsmooth L-M method for solving the generalized nonlinear complementarity problem [J]. Appl Math Optim, 2005, 52:73-92.

[5] 鄧永坤，張萍. 絕對值方程的光滑牛頓算法 [J]. 黑龍江科技學院學報, 2011, 21(6): 499-502.

[6] 李興斯. 一類不可微優化問題的有效解法 [J]. 中國科學:A輯, 1994, 24(4): 371-377.

[7] 李慶揚,莫孜中,祁力群. 非線性方程組的數值解法[M]. 北京:科學出版社, 1987: 8-50.

MAXIMUM ENTROPY NEWTON ALGORITHM FOR GENERALIZED LINEAR COMPLEMENTARITY PROBLEM

WANG Ai-xiang

(School of Information and Engineering, Changzhou Radio and Television University, Changzhou, Jiangsu 213001, China)

The generalized linear complementarity problem is converted to nonlinear equations by a specialized case of absolute value equations. Based on the maximum entropy function, the Newton method is established and the convergence of maximum entropy Newton method is studied. Numerical results imply that the algorithm is effective.

generalized linear complementarity problem; absolute value equations; maximum entropy; Newton method

1674-8085(2013)02-0025-03

O242.2

A

10.3969/j.issn.1674-8085.2013.02.005

2012-10-06；

2013-01-18

王愛祥(1984-)，男，江蘇興化人，助教，碩士，主要從事計算數學研究(E-mail: wax84@163.com).