一种新的求总极值的水平值估计算法

运筹学学报 ›› 2012, Vol. 16 ›› Issue (2): 105-114.

一种新的求总极值的水平值估计算法

楼烨^1,2, 孙胜², 武明楠²

1. 上海科学技术职业学院，上海，201800; 2. 上海大学理学院，上海, 200444

出版日期:2012-06-15 发布日期:2012-06-15
通讯作者: 楼烨

A new level-value estimation method for global minimization

Lou-Ye^1,2, SUN Sheng², WU Ming-Nan²

1. Shanghai Vocational College of Science and Technology, Shanghai 201800, China； 2. School of Sciences, Shanghai University, Shanghai 200444, China

Online:2012-06-15 Published:2012-06-15

摘要/Abstract

摘要： 提出了一种求解总极值问题的新水平值估计算法. 为此, 引入一类变差函数并研究它的性质; 给出基于变差函数的全局最优性条件, 并构造出一种求总极值的水平值估计算法. 为了实现这种算法, 采用了基于重点样本技术的Monte-Carlo方法来计算变差,并利用相对熵算法的主要思想更新取样密度.初步的数值实验说明了算法的有效性.

关键词: 总极值, 变差函数, 水平值估计算法, 重点取样, 相对熵算法

Abstract: In this paper, a new level-value estimation method is proposed for solving global optimization problem. For this purpose, we introduce a deviation function and study its properties. Based the deviation function, we give a global optimality condition, and then propose a conceptual level-value estimation algorithm, and prove the global convergence of the proposed method. For the implementation of the proposed method, we use the Monte-Carlo method with important sampling to compute the deviation, in which the sample density is updated by the main ideas of the cross-entropy method. Some primary numerical
results show the validity of the proposed method.

Key words: global optimization, deviation function, the level-value estimation, important sampling, the cross-entropy method

楼烨, 孙胜, 武明楠. 一种新的求总极值的水平值估计算法[J]. 运筹学学报, 2012, 16(2): 105-114.

Lou-Ye, SUN Sheng, WU Ming-Nan. A new level-value estimation method for global minimization[J]. Operations Research Transactions, 2012, 16(2): 105-114.

参考文献

Pardalos P P, Romeijn H E, Hoang T. Recent developments and trends in global optimization [J]. Journal of Computational and Applied Mathematics, 2000, 124: 209-228.
Zheng Q, Jiang B C, Zhuang S L. A method for finding global extrema [J]. Acta Mathematicae Applicatae Sinica, 1978, 2(1): 161-174.
Phu H X, Hoffmann A. Essential supremum and supremum of summable functions [J]. Numerical Functional Analysis and Optimization, 1996, 17(1/2): 167-180.
Wu D H, Tian W W, Zhang L S, et al. An Algorithm of modified integral-level set method for solving global optimization [J]. Acta Mathematicae Applicatae Sinica, 2001, 24: 100-110.
Tian W W, Wu D H, Zhang L S, et al. Modified integral-level set method for the constrained solving global optimization [J]. Applied Mathematics and Mechanics, 2004, 25: 202-209.
Peng Z, Wu D H, Tian W W. A Level-value estimation method for solving constrained global optimization [J]. Mathematica Numerica Sinica, 2007, 29(3): 284-293.
Wu D H, Yu W Y, Zheng Q. A sufficient and necessary condition for global optimization [J]. Applied Mathematics Letters, 2010, 23(1): 17-21.
Cui H Q, Wang C C, Zheng Q. Optimality conditions and algorithms for integral minimization [J]. Computers and Mathematics with Applications, 2006, 52: 55-64.
Rubinstein R Y. The cross-entropy method for combinational and continuous optimization [J]. Methodology and Computing in Applied Probability, 1999, 2: 127-190.
Rubinstein R Y, Kroese D P. The cross-entropy method: A unified approach to combinatorial optimization, Monte-Carlo simulation and machine learning [M]. Springer: Berlin heidelberg New York, 2004.
Ross S M. Simulation [M]. Beijing: Posts and Telecom Press, 2007.

Ross S M. Simulation [M]. Beijing: Posts and Telecom Press, 2007.
钱敏平, 龚光鲁. 应用随机过程[M]. 北京: 清华大学出版社, 2007.
Paditz L. On the analytical structure of the constant in the nonuniform version of the essen inequality [J]. Statistics, 1989, 20(3): 453-464.

[1]	周心怡, 汪可, 邬冬华, 汪晨. 求解全局最优问题的多重点样本水平值估计的相对熵算法[J]. 运筹学学报, 2019, 23(1): 15-27.
[2]	姚奕荣, 安柳, 陈熙, 郑权. 可达到和可逼近总极小点的存在性和最优性[J]. 运筹学学报, 2012, 16(2): 32-40.