王愛祥

改進(jìn)的移動漸近線算法求解無約束優(yōu)化問題

王愛祥

(常州開放大學(xué)，江蘇，常州 213001)

對于求解無約束優(yōu)化問題，提出一個改進(jìn)的移動漸近線方法?；谛刨囉蚍椒ê蜑V子技巧，該方法的全局收斂性得到證明。數(shù)值結(jié)果也說明了算法的有效性。

移動漸近線; 信賴域; 濾子; 無約束優(yōu)化

1 引言

我們考慮利用移動漸近線模型求解如下的無約束優(yōu)化問題

自從移動漸近線方法（method of moving asymptotes）首先被Svanberg在文[1]中提出之后，這種方法就引起了很多學(xué)者的研究興趣，也得到了很大的發(fā)展。Zillober構(gòu)造并證明了非線性約束條件下的移動漸近線的全局收斂算法[2-3]。倪勤利用信賴域方法，證明了簡單界約束下的移動漸近線的全局收斂性質(zhì)[4]。王海軍分別提出了無約束優(yōu)化問題，線性等式約束優(yōu)化問題和線性不等式約束優(yōu)化問題的移動漸近線算法[5-7]。

然而，利用信賴域方法構(gòu)造全局收斂的移動漸近線算法并沒有徹底研究。算法過程中，在接受試驗點(diǎn)時，嚴(yán)格要求目標(biāo)值下降。因此，本文利用濾子技巧，改進(jìn)了移動漸近線算法。濾子技巧首先被Fletcher和文Leyffer在文[8]中提出，之后也有了很多的改進(jìn)，參考文[9-11]。

2 移動漸近線算法的子問題

在每步迭代中，我們考慮子問題

事實(shí)上，

我們定義三個集合

由引理2.1，在迭代中，可取

其中

綜合以上所述，引理2.2成立。證畢。

定理2.1假設(shè)引理2.2成立，有以下結(jié)論成立

因此，

3 算法

本節(jié)給出一個求解無約束優(yōu)化問題（1.1）的算法。首先，定義濾子的概念，然后給出在算法迭代中，接受或拒絕試驗點(diǎn)的判斷準(zhǔn)則。

定義3.2令

算法3.1

Step3. 計算

Step4. 修正信賴域半徑

下面分析算法的收斂性。首先，假設(shè)：

證明 這里的證明類似文[2]中引理4.3，故這里省略。

證明 我們利用反證法證明。考慮以下三種情況。

4 數(shù)值實(shí)驗

初始的信賴域半徑

表1 測試結(jié)果

數(shù)值測試的結(jié)果說明了算法3.1是有效的。這里選取的測試函數(shù)的規(guī)模較大，由于移動漸近線模型的凸可分性質(zhì)且只利用了梯度信息，算法3.1的數(shù)值結(jié)果是理想的。

[1] Svanberg K. The method of moving asymptotes-a new method for structural optimization[J]. International Journal for Numerical Methods in Engineering, 1987, 24:359-373.

[2] Zillober C. A globally convergent version of the method of moving asymptotes[J]. Structural Optimization, 1993, 6:166-174.

[3] Zillober C. Global convergence of a nonlinear programming method using convex approximations[J]. Numerical Algorithms, 2001, 27:256-289.

[4] NI Q. A globally convergent method of moving asymptotes with trust region technique[J]. Optimization Methods and software, 2003, 18:283-297.

[5] WANG H, NI Q . A new method of moving asymptotes for large-scale unconstrained optimization[J]. Applied Mathematics and Computation, 2008, 203:62-71.

[6] WANG H, NI Q, LIU H. A new method of moving asymptotes for large-scale linearly equality-constrained minimization[J]. Acta Mathematicae Applicatae Sinica, 2011, 27(2):317-328.

[7] WANG H, NI Q. A convex approximation method for large scale linear inequality constrained minimization[J]. Asia-Pacific Journal of Operational Research, 2010, 27(1):85-101.

[8] Fletcher R, Leyffer S. Nonlinear programming without a penalty function[J]. Mathematical Programming, 2002, 91(2):239-269.

[9] Fletcher R, Leyffer S, Toint P L. On the global convergence of a filter-SQP algorithm[J]. SIAM Journal on Optimization, 2002, 13(1):44-59.

[10] Gould N I M, Sainviyu C, Toint P L. A filter-trust-region method for unconstrained optimization[J]. SIAM Journal on optimization, 2005, 16(2):341-357.

[11] Gonzaga C C, Karas E, Vanti M. A globally convergent filter method for nonlinear programming[J]. SIAM Journal on Optimization, 2003, 13(3):646-669.

[12] Andrei N. An unconstrained optimization test functions collection. Advanced Modeling and Optimization[J]. 2008, 10:147-161.

[13] 袁亞湘，孫文瑜.最優(yōu)化理論與方法[M]. 北京：科學(xué)出版社, 1997.

An Improved method of moving asymptotes for unconstrained optimization

WANG Ai-xiang

(Changzhou Open University, Changzhou, Jiangsu 213001, China)

An improved method of moving asymptotes for solving unconstrained nonlinear optimization problems is introduced. Based on the trust region method and filter technique, the method of moving asymptotes is shown to be globally convergent. Numerical results are also shown that the algorithm is effective.

method of moving asymptotes; trust region; filter; unconstrained optimization

O242.2

A

10.3969/j.issn.1674-8085.2013.05.004

1674-8085(2013)06-0016-05

2013-03-11；

2013-07-12

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