A Level-Value Estimation Algorithm and Its Stochastic Implementation for Global Optimization

Peng Zheng(pv068shu.edu.cn)

Abstract: We present a new method for finding global optimum of the continuous optimization problems, namely Level-Value Estimation algorithm (hereafter LVEM). First, we define the variance function $v(c)$ and the mean deviation function $m(c)$ with a single variable (the level value $c$) which both depend on the optimized function $f(x)$, and verify them having some good properties which fulfils to find the roots of the equation $v(c)=0$ by Newton's method. We also prove that the largest root of this equation must be equivalent to the global optimum of the corresponding optimization problem. Then we establish the algorithm LVEM based on using Newton's method to solve the equation $v(c)=0$, and prove its convergence. In the implementable algorithm of LVEM (shortening as ILVEM), we employ importance sampling to calculate integral in the expressions $v(c)$ and $m(c)$. Using the ideas of the cross-entropy method, we update parameters of probability density function at each iteration. We verify the algorithm ILVEM satisfying the convergent condition of inexact Newton's method, and then prove the convergence of ILEVM. Lots of numerical results show that ILVEM is effective.

Keywords: Global Optimization; Level-Value Estimation Algorithm; Variance Function; Stochastic Implementation; the Cross-Entropy Method

Category 1: Global Optimization

Citation: unpublished

Download: [PDF]

Entry Submitted: 12/06/2007
Entry Accepted: 12/06/2007
Entry Last Modified: 12/06/2007

Modify/Update this entry