Chen Disser (1121212), страница 12
Текст из файла (страница 12)
Thesolution process is not applicable to constraint partitioning, because it updates all variablesand Lagrange multipliers in each iteration and cannot be carried out in a partition-andresolve approach. In contrast, ESP supports partitioned searches by allowing an extendedregion of penalty values. Another advantage of constraint partitioning based on ESPC isthat it leads to subproblems of similar nature but of a smaller scale, and any existing solvercan be used to solve the subproblems. This feature extends the applicability of our approach.1 -penalty function discussed in Chapter 2. Unlike the Lagrangian function which uses theoriginal constraint function and requires exact penalty values, our formulation transformseach constraint function into a nonnegative function and does not require exact penalty values.
Because ESPC does not require unique penalty values in satisfying Theorem 3.3, the3.1.4Search procedures for finding extended saddle pointsAs is discussed in the last section, a CLMc of Pc can be found by gradually increasing α∗∗and β ∗∗ , while minimizing Lc (x, α∗∗ , β ∗∗ ), until α∗∗ > α∗ and β ∗∗ > β ∗ . This observationsearch can be carried out in a partitioned fashion in which we solve each subproblem byallows us to solve Pc by an iterative search in Figure 3.2a. (The algorithm for solving Pdlooking for penalty values that are larger than the ones required by the original solution.is similar and is not shown.) Assuming α∗∗ and β ∗∗ have been found in the outer loopThis is not possible if the search were formulated as the solution of a system of nonlinearand according to the second inequality in (3.4), the inner loop looks for a local minimumequations.
Second, unlike the 1 -penalty function in (2.27) that has a single penalty termc, there are multiple penalty terms in the penalty function that allow the condition to bepartitioned. Moreover, unlike the 1 -penalty theory that requires continuity and differentia-of Lc (x, α∗∗ , β ∗∗ ) in order to find x∗ . If a feasible solution to Pc is not found at the localminimum x of Lc (x, α∗∗ , β ∗∗ ), the penalties corresponding to the violated constraints areincreased. The process is repeated until a CLMc is found or when α∗∗ (resp. β ∗∗ ) is largerbility, Theorem 3.3 was developed for general constraint functions that are not necessarilythan its maximum bound ᾱ (resp.
β̄), where ᾱ (resp. β̄) is chosen to be so large that itcontinuous and differentiable.exceeds α∗ (resp. β ∗ ).ESPC overcomes some deficiencies of previous work. Unlike previous global penalty55Figure 3.2b shows the pseudo code which solves Pm by looking for x∗ , y ∗, α∗∗ , and56α −→ 0; β −→ 0;repeatincrease αi by δ if (hi (x) = 0 and αi < ᾱi ) for i = 1, . . . , m;increase βj by δ if (gj (x) 0 and βj < β̄j ) for j = 1, .
. . , r;repeatperform descent of Lc (x, α, β) with respect to x;until a local minimum of Lc (x, α, β) is found;until (αi > ᾱi for all hi (x) = 0 and βj > β̄j for all gj (x) 0)or a CLMc of Pc is found.a) Direct implementation of (3.4) to look for CLMc of Pc .α −→ 0; β −→ 0;repeatincrease αi by δ if (hi (x) = 0 and αi < ᾱi ) for i = 1, . . . , m;increase βj by δ if (gj (x) 0 and βj < β̄j ) for j = 1, . . . , r;repeatperform descent of Lm (x, y, α, β) with respect to x for given y;until a local minimum of Lm (x, y, α, β) with respect to x is found;repeatperform descent of Lm (x, y, α, β) with respect to y for given x;until a local minimum of Lm (x, y, α, β) with respect to y is found;until (αi > ᾱi for all hi (x) = 0 and βj > β̄j for all gj (x) 0)or a CLMm of Pm is found.b) Direct implementation of (3.21) and (3.22) to look for CLMm of PmFigure 3.2: Iterative procedures to look for CLMc of Pc and CLMm of Pm .Figure 3.2b) generates fixed points that are necessary but not sufficient to satisfy (3.4)(resp.
(3.21) and (3.22)).To cope with this issue, we discuss some additional strategies in the procedure to lookfor CLMm . These procedures are general and are applicable when looking for CLMc andCLMd .First, when α∗∗ and β ∗∗ reach their upper bounds during a search but a local minimumof Lm (x, y, α∗∗, β ∗∗ ) does not correspond to a CLMm of Pm , then a different local minimumof the function will need to be found. Instead of restarting the search from a new startingpoint, reducing α∗∗ and β ∗∗ will change the terrain and “lower” the barrier of the penaltyfunction, thereby allowing a local search to continue on the same trajectory and move toanother local minimum of the penalty function.
By repeatedly increasing α∗∗ and β ∗∗ to theirupper bounds and by reducing them to some lower bounds, a local search algorithm will beable to visit multiple local minima of the penalty function. Alternatively, it is possible toescape from a local minimum of the penalty function by using a global search algorithm inthe inner loops. Since these two strategies offset each other in their effects, only one of themβ ∗∗ that satisfy Theorem 3.4.
By performing descents of Lm (x, y, α, β) in the continuousand discrete neighborhoods in the two inner loops, it looks for a local minimum (x∗ , y ∗) ofLm (x, y, α, β) with respect to (x , y ) ∈ Nm (x, y). The outer loop increases the penalties ofviolated constraints and stops when a CLMm is found or when α∗∗ (resp. β ∗∗ ) exceeds itsmaximum bound ᾱ (resp. β̄).will need to be applied.Second, because functions in some applications may not be in closed form and theirgradients are unavailable, it is hard to locate local minima of the 1 -penalty function in thiscase.
To cope with this issue, probes can be generated based on deterministic, probabilistic,or genetic mechanisms and be accepted based on deterministic or stochastic criteria. ForBecause Lc (x, α∗∗ , β ∗∗ ) and Lm (x, y, α∗∗, β ∗∗ ) may have many local minima and some ofthem do not correspond to constrained local minima even when α∗∗ > α∗ and β ∗∗ > β ∗ , it ispossible for the iterative procedures in Figure 3.2 to terminate without finding a constrainedlocal minimum. The following theorem summarizes this observation.∗∗example, in our experiments on SGPlant (ASPEN) (Section 4.2.1), new probes generatedusing ASPEN’s built-in mechanism during the descent of the 1 -penalty function are acceptedbased on the Metropolis probability when Ld increases. This mechanism allows descents aswell as occasional ascents of the penalty function.
In more general cases, as is illustrated inTheorem 3.5 When ᾱ > α and β̄ > β , the iterative procedure in Figure 3.2a (resp.the stochastic constrained simulated annealing (CSA) algorithm [89], new probes generated5758are accepted based on the Metropolis probability when Lm increases along one of the x or ycan be unbounded.In this section, we solve Pt in (3.23) by finding solution z that is a CLMm with respectdimension and decreases along the α or β dimension.to feasible solutions in its mixed neighborhood Nm (z). After showing that z satisfies the3.2ESPC under Constraint PartitioningESPC in (3.16), we decompose the ESPC into a set of necessary conditions that collectivelyare sufficient.
Pt is then solved by finding an extended saddle point in each stage and byIn this section, we provide a formal definition of MINLPs under constraint partitioning andresolving those violated global constraints using appropriate penalties.the related definitions of partitioned neighborhood and constrained local optima. By applyTo simplify our discussion, we do not partition solution z into discrete and continuousing ESPC to the partitioned problem, we decompose the condition into a set of necessaryparts in the following derivation, although it is understood that each partition will need toconditions that collectively are sufficient.be further decomposed in the same way as in Theorem 3.4.
To enable the partitioning of the3.2.1ESPC into independent necessary conditions, we define a mixed neighborhood of solution zBasic definitions for partitioned MINLPsas follows:Consider Pt , a version of (1.1) whose constraints can be partitioned into N + 1 stages. Staget, t = 0, . . . , N, of Pt has local state vector z(t) = (z1 (t), . . . , zut (t))T , where z(t) includes allvariables that appear in any of the local constraints in stage t. Since the partitioning is byDefinition 3.10 Nb (z), the mixed neighborhood of z for a partitioned problem, is definedas:constraints, the N + 1 state vectors z(0), . . . , z(N) may overlap with each other.Nb (z) =Nt=0The formulation of Pt is as follows:Np(t) (z) =N / z(t), zi = zi ,z z (t) ∈ Nm (z(t)) and ∀zi ∈(3.24)t=0where Nm (z(t)) is the mixed-space neighborhood of variable vector z(t) in stage t.(Pt ) :minzsubject toandJ(z)(3.23)Intuitively, Nb (z) is separated into N + 1 neighborhoods, each perturbing z in only oneh(t) (z(t)) = 0,g (t) (z(t)) ≤ 0(local constraints)H(z) = 0,G(z) ≤ 0(global constraints).of the stages of Pt , while keeping the overlapped variables consistent in other stages.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
