解线性等式约束优化问题的模式搜索过滤集方法

doi:10.15960/j.cnki.issn.1007-6093.2015.03.012

运筹学学报 ›› 2015, Vol. 19 ›› Issue (3): 96-107.doi: 10.15960/j.cnki.issn.1007-6093.2015.03.012

解线性等式约束优化问题的模式搜索过滤集方法

陈宁¹, 孙文瑜^1,*, 袁锦昀²

1. 南京师范大学数学科学学院，江苏省大规模复杂系统数值模拟重点实验室，南京, 210023; 2. 巴西巴拉那联邦大学数学系，巴西巴拉那州库里提巴, 81531--990

收稿日期:2015-05-20 出版日期:2015-09-15 发布日期:2015-09-15

A pattern search filter method for linearly equality-constrained optimization problems

CHEN Ning¹, SUN Wenyu^1,*, YUAN Jinyun²

1. School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210023, China; 2. Department of Mathematics, The Federal University of Parana (UFPR), CEP 81531-990, Curitiba, Parana, Brazil

Received:2015-05-20 Online:2015-09-15 Published:2015-09-15
Contact: 孙文瑜 wysun@njnu.edu.cn

摘要/Abstract

摘要：

提出一个解线性等式约束无导数优化的模式搜索过滤集算法，该算法将过滤集技术嵌入无导数优化算法中以改善算法的效率. 建立了新算法的总体收敛性, 初步的数值试验结果表明新算法是有效的.

关键词: 无导数优化, 模式搜索算法, 过滤集技术, 约束优化, 总体收敛性

Abstract:

In this paper a pattern search filter algorithm for linearly equality-constrained derivative-free optimization is proposed. In this work we embed a filter technique in a derivative-free optimization algorithm which improves the efficiency of algorithms. The global convergence of new algorithm is established. Initial numerical results show that the new algorithm is efficient.

Key words: derivative-free optimization, pattern searchalgorithm, filter technique, constrained optimization, globalconvergence

陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.

CHEN Ning, SUN Wenyu, YUAN Jinyun. A pattern search filter method for linearly equality-constrained optimization problems[J]. Operations Research Transactions, 2015, 19(3): 96-107.

参考文献

Conn A R, Scheinberg K, Vicente L N. Global convergence of general derivative-free trust-region algorithms to first and second order critical points [J]. SIAM J. Optim, 2009, 20: 387-415.

Lucidi S, Sciandrone M. On the global convergence of derivative-free methods for unconstrained optimization [J]. SIAM J. Optim, 2002, 13: 97-116.

Powell M J D. On trust region method for unconstrained minimization without derivatives [J]. Math. Prog, 2003, 97: 605-623.

Powell M J D. On the use of quadratic models in unconstrained minimization without derivatives [J]. Optimization Methods and Software, 2004, 19: 399-411.

Sun W, Yuan Y. Optimization Theory and Methods: Nonlinear Programming [M]. New York: Springer, 2006.

Xue D, Sun W. On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure [J]. Science China Mathematics, 2014, 57: 1287-1302.

Zhang L, Sun W, Sampaio R J B, Yuan J. A wedge trust region method with self-correcting geometry for derivative-free optimization [J]. Numerical Algebra, Control and Optimization, 2015, 5: 169-184.

Nelder J A, Mead R. A simple method for function minimization [J]. Computer Journal, 1965, 7: 308-313.

Feng Y, Zhang X S, Liu L Y. Grid-based methods for linearly equality constrained optimization problems [J]. J. Appl. Math. and Computing, 2007, 23: 269-279.

Lewis R M, Torczon V. Pattern search methods for linearly constrained minimization [J]. SIAM J. Optim, 2000, 10: 917-941.

Liu L Y, Zhang X S. Generalized pattern search methods for linearly equality constrained optimization problems [J]. Applied Math. and Comput, 2006, 181: 527-535.

Xu D, Sun W. On filter-grid pattern search method for unconstrained optimization [J]. Technical Report No. 2008-08-01, School of Mathematical Sciences, Nanjing Normal University, August, 2008.

Powell M J D. Direct search algorithms for optimization calculations [J]. Acta Numerica, 1998, 7: 287-336.

Kolda T G, Lewis R M, Torczon V. Optimization by direct search: a new perspective on some classical and modern methods [J]. SIAM Rev, 2003, 45: 385-482.

Conn A R, Scheinberg K, Vicente L N. Introduction to Derivative-Free Optimization [M]. Philadelphia: SIAM, 2009.

Box G E P. Evolutionary operation: A method for increasing industrial productivity [J]. Appl. Statist. 1957, 6: 81-101.

Hook R, Jeeves T A. ``Direct search'' solution of numerical and statistical problems [J]. J. Assoc. Comput. Mach, 1961, 8: 212-229.

Torczon V. On the convergence of pattern search algorithms [J]. SIAM J. Optim, 7 (1997) 1-25.

Lewis R M, Torczon V. Pattern search algorithms for bound constrained minimization [J]. SIAM J. Optim, 1999, 9: 1082-1099.

Audet C, J E Dennis. A pattern search filter method for nonlinesr progamming without derivatives [J]. SIAM J. Optim. 2004, 14: 980-1010.

Coope I D, Price C J. Frame based methods for unconstrained optimization [J]. J. Optimiz. Theory Appl, 2000, 107: 261-274.

Coope I D, Price C J. On the convergence of grid-based methods for unconstrained optimization [J]. SIAM J. Optim, 2001, 11: 859-869.

Wu T, Sun L P. A filter-based pattern search method for unconstrained optimization [J]. Numer. Math. A Journal of Chinese Universities (English Series), 2006, 15: 209-216.

Fletcher R, Leyfier S. Nonlinear programming without a penalty function [J]. Math. Program, 2002, 91: 239-269.

Chen Y, Sun W. A dwindling filter line search method for unconstrained optimization [J]. Mathematics of Computation 2015, 84: 187-208.

Fletcher R, Leyfier S, Toint Ph L. On the global convergence of a filter-SQP algorithm [J]. SIAM J. Optim, 2002, 13: 44-59.

Gould N I M, Leyffer S, Toint Ph L, A multidimensional filter algorithm for nonlinear equations and nonlinear least-squares [J]. SIAM J. Optim, 2004, 15: 17-38.

Li C, Sun W, On filter-successive linearization methods for nonlinear semidefinite programming [J]. Science in China Series A, 2009, 52(11): 2341-2361.

Sun W, Xu D. A filter-trust-region method based on conic model for unconstrained optimization [J]. Science China: Mathematics 55(2012) 527-543.

Miele A, Huang H Y, Heideman J C. Sequential gradient-restoration algorithm for the minimization of constrained functions, ordinary and conjugate gradient versions [J]. J. Optimiz. Theory Appl, 1969, 4: 213-243.

Huang H Y, Aggerwal A K. A class of quadratically convergent algorithms for constrained function minimization [J]. J. Optimiz. Theory Appl, 1975, 16: 447-485.

[1]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[2]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[3]	刘水霞, 陈国庆. 求解互补约束优化问题的乘子松弛法[J]. 运筹学学报, 2014, 18(4): 119-130.
[4]	戴彧虹，刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18(1): 69-92.
[5]	刘媛媛, 欧宜贵. 基于非单调技术的ODE型混合方法[J]. 运筹学学报, 2013, 17(3): 11-22.
[6]	孟志青，高嵩 . 非线性约束优化的光滑化平方根罚函数[J]. 运筹学学报, 2013, 17(2): 70-80.
[7]	白富生, 罗晓艳. 基于二次函数光滑化逼近的修正低阶罚函数[J]. 运筹学学报, 2012, 16(2): 9-22.
[8]	刘水霞, 陈国庆. 互补约束优化问题的乘子序列部分罚函数算法[J]. 运筹学学报, 2011, 15(4): 55-64.
[9]	钱小燕, 施庆生, 刘浩, 石岿然. 大规模无约束优化的一族有限存储LBFGS类算法[J]. 运筹学学报, 2011, 15(3): 9-18.

解线性等式约束优化问题的模式搜索过滤集方法

A pattern search filter method for linearly equality-constrained optimization problems

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价