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

王愛(ài)祥

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

王愛(ài)祥

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

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

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

1 引言

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

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

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

2 移動(dòng)漸近線算法的子問(wèn)題

在每步迭代中，我們考慮子問(wèn)題

事實(shí)上，

我們定義三個(gè)集合

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

其中

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

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

因此，

3 算法

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

定義3.2令

算法3.1

Step3. 計(jì)算

Step4. 修正信賴域半徑

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

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

證明 我們利用反證法證明?？紤]以下三種情況。

4 數(shù)值實(shí)驗(yàn)

初始的信賴域半徑

表1 測(cè)試結(jié)果

數(shù)值測(cè)試的結(jié)果說(shuō)明了算法3.1是有效的。這里選取的測(cè)試函數(shù)的規(guī)模較大，由于移動(dòng)漸近線模型的凸可分性質(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

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