J89 (1121213), страница 2
Текст из файла (страница 2)
The property is proved by modeling the search as aJ Glob Optimstrongly ergodic Markov chain and by showing that CSA and CPSA minimize animplicit virtual energy at any CGM with probability one. The result is significantbecause it extends conventional SA, which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. It alsoestablishes the condition under which optimal solutions can be found in constraintpartitioned nonlinear optimization problems.Last, we evaluate CSA and CPSA in Sect. 5 by solving some benchmarks in continuous space and by demonstrating their effectiveness when compared to other dynamicpenalty methods.2 Previous work on penalty methodsDirect and penalty methods are two general approaches for solving Pm .
Since directmethods are only effective for solving some special cases of Pm , we focus on penaltymethods in this paper.A penalty function of Pm is a summation of its objective and constraint functionsweighted by penalties. Using penalty vectors α ∈ Rm and β ∈ Rr , the general penaltyfunction for Pm is:Lp (z, α, β)T = f (z) + α T P(h(z)) + β T Q(g(z)),(3)where P and Q are transformation functions. The goal of a penalty method is to findsuitable α ∗ and β ∗ in such a way that z∗ that minimizes (3) corresponds to either aCLMm or a CGMm of Pm .
Penalty methods belong to a general approach that cansolve continuous, discrete, and mixed constrained optimization problems, with nocontinuity, differentiability, and convexity requirements.When P(g(z)) and Q(h(z)) are general functions that can take positive and negativevalues, unique values of α ∗ and β ∗ must be found in order for a local minimum z∗ of(3) to correspond to a CLMm or CGMm of Pm .
(The proof is not shown.) However,the approach of solving Pm by finding local minima of (3) does not always work fordiscrete or mixed problems because there may not exist any feasible penalties at z∗ .(This behavior is shown in Example 1 in Sect. 2.1.) It is also possible for the penaltiesto exist at z∗ but (3) is not at a local minimum there. A special case exists in continuous problems when constraint functions are continuous, differentiable, and regular.For those problems, the Karush–Kuhn–Tucker (KKT) condition shows that uniquepenalties always exist at constrained local minima [22].
In general, existing penaltymethods for solving Pm transform g(z) and h(z) in (3) into nonnegative functionsbefore finding its local or global minima. In this section, we review some existingpenalty methods in the literature.2.1 Penalty methods for constrained global optimization2.1.1 Static penalty methodsA static-penalty method [22,24] formulates Pm as the minimization of (3) when itstransformed constraints have the following properties: (a) P(h(z)) ≥ 0 and Q(g(z)) ≥0; and (b) P(h(z)) = 0 iff h(z) = 0, and Q(g(z)) = 0 iff g(z) ≤ 0.
By finding suitablepenalty vectors α and β, an example method looks for z∗ by solving the followingJ Glob Optimproblem with constant ρ > 0:(P1 ) :Tmin Ls (z, α, β)z⎡= min ⎣f (z) +zmραi |hi (z)| +i=1r⎤+ ρ⎦βj gj (z), (4)j=1where gj (z)+ = max(0, gj (z)), and g(z)+ = (g1 (z)+ , .
. . , gr (z)+ )T .Given z∗ , an interesting property of P1 is that z∗ is a CGMm of Pm iff there existfinite α ∗ ≥ 0 and β ∗ ≥ 0 such that z∗ is a global minimum of Ls (z, α ∗∗ , β ∗∗ )T forany α ∗∗ > α ∗ and β ∗∗ > β ∗ . To show this result, note that αi and βj in P1 must begreater than zero in order to penalize those transformed violated constraint functionsρ|hi (z)|ρ and gj (z)+ , which are nonnegative with a minimum of zero. As (4) is tobe minimized with respect to z, increasing the penalty of a violated constraint to alarge enough value will force the corresponding transformed constraint function toachieve the minimum of zero, and such penalties always exist if a feasible solution toPm exists. At those points where all the constraints are satisfied, every term on theright-hand side of (4) except the first is zero, and a global minimum of (4) correspondsto a CGMm of Pm .Example 1 Consider the following simple discrete optimization problem:⎧⎪if y ≥ 0,⎨0,(5)min f (y) = y,if y = −1, −2 subject to y = 0.⎪y∈{−3,−2,⎩−4,if y = −3,−1,0,1,2}Obviously, y∗ = 0.
Assuming a penalty function Lp (y, α)T = f (y) + αy and N d (y) ={y − 1, y + 1}, there is no single α ∗ that can make Lp (y, α ∗ )T a local minimum aty∗ = 0 with respect to y = ±1. This is true because we arrive at an inconsistent α ∗when we solve the following inequalities: Lp (−1, α ∗ )T = f (−1) − α ∗ = −1 − α,∗∗ T0 = Lp (0, α ) ≤Lp (1, α ∗ )T = f (1) + α ∗ = 0 + α,∗α ∗ ≤ −1, when y = −1,⇒α ∗ ≥ 0,when y = 1.On the other hand, by using Ls (y, α)T = f (y) + α |y| and by setting α ∗ = 43 , theCGMd of (5) corresponds to the global minimum of Ls (y, α ∗∗ )T for any α ∗∗ > α ∗ .A variation of the static-penalty method proposed in [17] uses discrete penalty valuesand assigns a penalty value αi (hi (z)) when hi (z) exceeds a discrete level i (resp.,βj (gj (z)) when gj (z)+ exceeds a discrete level j ), where a higher level of constraintviolation entails a larger penalty value.
The penalty method then solves the followingminimization problem:mT(P2 ) : min Ls (z, α, β) = min f (z) +αi (hi (z)) h2i (z)zz+i=1rj=1⎤2βj (gj (z)) gj (z)+ ⎦ .(6)J Glob OptimA limitation common to all static-penalty methods is that their penalties have to befound by trial and error. Each trial is computationally expensive because it involvesfinding a global minimum of a nonlinear function. To this end, many penalty methodsresort to finding local minima of penalty functions. However, such an approach isheuristic because there is no formal property that relates a CLMm of Pm to a localminimum of the corresponding penalty function.
As illustrated earlier, it is possiblethat no feasible penalties exist in order to have a local minimum at a CLMm in thepenalty function. It is also possible for the penalties to exist at the CLMm but thepenalty function is not at a local minimum there.2.1.2 Dynamic penalty methodsInstead of finding α ∗∗ and β ∗∗ by trial and error, a dynamic-penalty method [22,24]increases the penalties in (4) gradually, finds the global minimum z∗ of (4) with respectto z, and stops when z∗ is a feasible solution to Pm . To show that z∗ is a CGMm whenthe algorithm stops, we know that the penalties need to be increased when z∗ is aglobal minimum of (4) but not a feasible solution to Pm . The first time z∗ is a feasible solution to Pm , the solution must also be a CGMm . Hence, the method leads tothe smallest α ∗∗ and β ∗∗ that allow a CGMm to be found.
However, it has the samelimitation as static-penalty methods because it requires computationally expensivealgorithms for finding the global minima of nonlinear functions.There are many variations of dynamic penalty methods. A well known one is thenonstationary method (NS) [18] that solves a sequence of minimization problems withthe following in iteration t:⎡⎤mrρ(P3 ) : min Lt (z, α, β)T = min ⎣f (z) +αi (t) |hi (z)|ρ +βj (t) gj (z)+ ⎦ ,zzi=1j=1(7)where αi (t + 1) = αi (t) + C · |hi (z(t))|,+βj (t + 1) = βj (t) + C · gj (z(t)) .Here, C and ρ are constant parameters, with a reasonable setting of C = 0.01 andρ = 2. An advantage of the NS penalty method is that it requires only a few parametersto be tuned.Another dynamic penalty method is the adaptive penalty method (AP) [6] thatmakes use of a feedback from the search process.
AP solves the following minimization problem in iteration t:⎡⎤mr2T2+(P4 ) : min Lt (z, α, β) = min⎣f (z) +αi (t) hi (z) +βj (t) gj (z) ⎦ , (8)zzi=1j=1where αi (t) is, respectively, increased, decreased, or left unchanged when the constraint hi (z) = 0 is, respectively, infeasible, feasible, or neither in the last iterations.That is,⎧ α (t)i⎪if hi (z(i)) = 0 is feasible in iterations t − + 1, . . . , t,⎨ λ1 ,αi (t + 1) = λ2 · αi (t),if hi (z(i)) = 0 is infeasible in iterations t − + 1, . .
. , t,⎪⎩otherwise,αi (t),(9)J Glob Optimwhere is a positive integer, λ1 , λ2 > 1, and λ1 = λ2 in order to avoid cycles in updates.We use = 3, λ1 = 1.5, and λ2 = 1.25 in our experiments. A similar rule applies tothe updates of βj (t).The threshold penalty method estimates and dynamically adjusts a near-feasiblethreshold qi (t) (resp., qj (t)) for each constraint in iteration t. Each threshold indicatesa reasonable amount of violation allowed for promising but infeasible points duringthe solution of the following problem:⎧⎡ ⎤⎫2 m r⎨+ 2 ⎬g(z)h(z)ji⎦ .(P5 ) :min Lt (z, α, β)T = min f (z) + α(t) ⎣+zz ⎩⎭qi (t)qj (t)i=1j=1(10)There are two other variations of dynamic penalty methods that are not as popular:the death penalty method simply rejects all infeasible individuals [5]; and a penaltymethod that uses the number of violated constraints instead of the degree of violationsin the penalty function [21].2.1.3 Exact penalty methodsBesides the dynamic penalty methods reviewed above that require solving a series ofunconstrained minimization problems under different penalty values, the exact penaltymethods are another class of penalty methods that can yield an optimal solution bysolving a single unconstrained optimization of the penalty function with appropriatepenalty values.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
