Chen Disser (1121212), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Thesize of Nb (z) defined in (3.24) is smaller than the Cartesian product of the neighborhoodsacross all stages.(t)Here, h=(t)(t)(h1 , . . . , hmt )Tand g(t)=(t)(g1 , . . . ,(t)g r t )Tare local-constraint functions in stageTt that involve z(t); and H = (H1 , . . . , Hp ) and G = (G1 , . . .

, Gq )T are global-constraintfunctions that involve z ∈ X × Y , the original variables. We assume that J is continuousand differentiable with respect to its continuous variables, that f is lower bounded, and that3.2.2Necessary and sufficient ESPC for partitioned subproblemsBy considering Pt as a MINLP and by defining the corresponding 1 -penalty function, wecan apply Theorem 3.3 as follows.g and h are general functions that are not necessarily continuous and differentiable and that5960Definition 3.11 Let Φ(z, γ, η) = γ T |H(z)|+η T max(0, G(z)) be the sum of the transformedglobal constraint functions weighted by their penalties, where γ = (γ1 , .

. . , γp ) ∈ R andTpProof. We prove the theorem by showing the equivalence of (3.27) and the combined(3.28) and (3.29).η = (η1 , . . . , ηq ) ∈ R are the penalty vectors for the global constraints. Then the 1 -penalty“⇒” part: Given z ∗ that satisfies (3.27), we show that it also satisfies (3.28) and (3.29).function for Pt in (3.23) and the corresponding 1 -penalty function in stage t are defined asSince for all t = 0, . . . , N, any z ∈ Np (z ∗ ) is also a point in Nb (z ∗ ); hence, the secondfollows:inequality in (3.28) is implied by the second inequality in (3.27). The first inequality inTqLm (z, α, β, γ, η) = J(z) +N α(t)T |h(t) (z(t))| + β(t)T max(0, g (t) (z(t)) +Φ(z, γ, η),(3.25)t=0Γd (z, α(t), β(t), γ, η) = J(z) + α(t)T |h(t) (z(t))| + β(t)T max(0, g (t) (z(t))) + Φ(z, γ, η),(3.26)(t)(3.28) and the inequality in (3.29) are obvious, as all the constraints are satisfied at z ∗ .“⇐” part: We prove this part by contradiction.

Assuming that z ∗ satisfies (3.28) and(3.29) but not (3.27), the first inequality in (3.27) cannot be violated because the firstinequality in (3.28) and the inequality in (3.29) imply that all local and global constraintsmtwhere α(t) = (α1 (t), . . . , αmt (t))T ∈ Rrand β(t) = (β1 (t), . . . , βrt (t))T ∈ R t are thepenalty vectors for the local constraints in stage t.(t )Lemma 3.1 Plan z is a CLMm of (3.23) with respect to Nb (z) if and only if there existfinite nonnegative α∗ , β ∗ , γ ∗ and η ∗ such that the following ESPC is satisfied:for all α ∈ R,β∈Rdefinition of Nb (z) in (3.24)) such that:(3.30)(3.27)This implies that the second inequality in (3.28) is not satisfied at t = t , which contradictswhere α∗∗ > α∗ ≥ 0, β ∗∗ > β ∗ ≥ 0, γ ∗∗ > γ ∗ ≥ 0, and η ∗∗ > η ∗ ≥ 0,PNi=0 riz ∗ .

That is, there exist z ∈ Nb (z ∗ ) and a unique t where z ∈ Nb (z ∗ ) (according to theLm (z ∗ , α∗∗ , β ∗∗ , γ ∗∗ , η ∗∗ ) Lm (z, α∗∗ , β ∗∗ , γ ∗∗ , η ∗∗ ).Lm (z ∗ , α, β, γ, η) ≤ Lm (z ∗ , α∗∗ , β ∗∗ , γ ∗∗ , η ∗∗ ) ≤ Lm (z, α∗∗ , β ∗∗ , γ ∗∗ , η ∗∗ ),PNi=0 miare satisfied. Therefore, it must be the second inequality in (3.27) that is not satisfied atour assumption that z ∗ satisfies (3.28) and (3.29). Our argument proves that any z ∗ that∗, γ ∈ R , η ∈ R , and z ∈ Nb (z ).pqsatisfies (3.28) and (3.29) must also satisfy (3.27). Based on Lemma 3.2.2, we next show the partitioning of (3.27) into multiple conditions.Theorem 3.6 Partitioned necessary and sufficient ESPC on CLMm of Pt . Given Nb (z), theESPC in (3.27) can be rewritten into N + 2 necessary conditions that, collectively, are suf-Theorem 3.6 shows that the original ESPC in Theorem 3.3 can be partitioned into N + 1necessary conditions in (3.28) and an overall necessary condition in (3.29) on the globalconstraints across the subproblems.

A close examination shows that local extended saddlepoints that satisfy (3.28) in Stage t are local minima of (3.26) with respect to z (the secondficient:Γd (z , α(t), β(t), γ , η ) ≤ Γd (z , α(t) , β(t) , γ , η ) ≤ Γd (z, α(t) , β(t) , γ , η (3.28)),inequality of (3.28)), when α(t)∗∗ and β(t)∗∗ are larger than some thresholds α(t)∗ and β(t)∗Lm (z ∗ , α∗∗ , β ∗∗ , γ, η) ≤ Lm (z ∗ , α∗∗ , β ∗∗ , γ ∗∗ , η ∗∗(3.29)),such that all the constraints in Stage t are forced to be satisfied (the first inequality of (3.28)).∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗In essence, points that satisfy (3.28) in Stage t is a solution to the following MINLP, whose(t)mrfor all z ∈ Np (z ∗ ), α(t) ∈ R t , β(t) ∈ R t , γ ∈ Rp , η ∈ Rq , and t = 0, . .

. , N.6162Lm(z, α, β, γ, η)⏐γ,η to find γ ∗∗ and η ∗∗objective is biased by the violated global constraints:minJ(z) + γ T |H(z)| + η T max(0, G(z))subject toh(t) (z(t)) = 0 and g (t) (z(t)) ≤ 0.z(t)(3.31)minz(0) J(z) + γ T |H(z)| + η T max(0, G(z))minz(N) J(z) + γ T |H(z)| + η T max(0, G(z))subject to h(0)(z(0)) = 0 and g (0) (z(0)) ≤ 0subject to h(N) (z(N )) = 0 and g (N) (z(N )) ≤ 0a) Partitioned search to look for points that satisfy (3.29) and (3.31)γ −→ 0; η −→ 0;repeat// increase the penalties on violated global constraints //increase γi by δ if (Hi (z) = 0 and γi < γ̄i ) for i = 1, .

. . , p;increase ηj by δ if (Gj (z) 0 and ηj < η̄j ) for j = 1, . . . , q;for t = 0 to N // iterate over all N + 1 stages to solve (3.31) in each stage //apply an existing solver or the procedure in Figure 3.2b to solve (3.31)end for;until (γi > γ̄i for all Hi (z) = 0 and ηj > η̄j for all Gj (z) 0) or a CLMm of Pt isfound.The bias on the violated global constraints when solving (3.31) is important because it leadsthe search towards points that minimize this bias.

When the penalties on the violated globalconstraints are large enough, solving (3.31) will lead to points, if they exist, that satisfy theglobal constraints.In short, finding points that satisfy (3.27) can be reduced to solving multiple MINLPs,b) Implementation for finding CLMm of Pt that satisfies (3.29) and (3.31)where the problem in Stage t defined by (3.31) can be handled easily by an existing solver,Figure 3.3: The partition-and-resolve procedure to look for CLMm of Pt .and to the reweighting of violated global constraints defined in (3.29).in Section 3.1.4 are needed to help escape from infeasible local minima of the 1 -penalty3.2.3The partition-and-resolve procedurefunction.Figure 5.2 presents the partition-and-resolve procedure that looks for points satisfying theconditions in Theorem 3.6.

The inner loop of stage t in Figure 5.2b solves (3.31) by lookingfor an extended saddle point that satisfies (3.28). This can be done by the procedure in3.3Asymptotic Convergence of StochasticPartitioned SearchFigure 3.2b, using fixed γ and η specified in the outer loop. Another way is to solve (3.31)directly using an existing solver. This is possible because (3.31) is a well-defined MINLP.As is illustrated in Chapters 4 and 5, we can use an existing solver to solve the partitionedplanning subproblems defined by (3.31). After solving the subproblems, the penalties onthe violated global constraints are increased in the outer loop.

The process is repeated untila CLMm to Pt has been found or when γ and η exceed their maximum bounds. Similarto the result in Theorem 3.5, the procedure in Figure 5.2 generates fixed points that arenecessary but not sufficient to satisfy (3.21) and (3.22). Hence, additional steps describedThe partitioned procedure outlined in Figure 3.3 is guaranteed to stop at a fixed point ofthe 1 − penalty function but may not converge to a CLM. In this section, we proposed astochastic partitioned-search procedure to look for extended saddle points.

The procedurecarries out a process of simulated annealing (SA) in the joint space of multiple partitionedsubproblems and converges to a constrained global minimum of the original problem.Simulated annealing (SA) [1, 35] is a method for solving unconstrained optimizationproblems. It performs stochastic descents of the objective function using a control parameter called temperature. The complete theory for proving the asymptotic convergence of6364SA on unconstrained optimization is based on a discrete Markov chain model. The con-Suppose the constraints of Pe are partitioned into N + 1 stages as follows:strained simulated annealing (CSA) [89] algorithm extends SA to solve constrained DNLPs(Pet ) :and converges asymptotically with probability one to a constrained global minimum.

TheCSA algorithm performs stochastic ascents in the original-variable space and descents inminysubject tothe penalty space. In each step, CSA generates a probe in a user-defined neighborhood byandJ(y)(3.33)h(t) (y(t)) = 0,H(y) = 0,(local constraints)(global constraints),perturbing either the original variables or the penalty vector. Each probe is accepted usinga Metropolis probability controlled by a temperature. It has been proved that CSA using awhere stage t, t = 0, . . .

, N, has local state vector y(t) = (y1 (t), . . . , yut (t))T , and y(t) includeslogarithmic schedule to reduce temperatures converges asymptotically with probability oneall the variables that appear in any of the local constraints in stage t.The 1 −penalty function for Pe under constraint partitioning is as follows:to a constrained global minimum [89, 92].Since the Markov chain model is discrete, our study will be limited to DNLPs formulatedin Pd only.

Note that the results can be extended to CNLPs and MNLPs when continuousL(y, α, γ) = f (y) +Nα(t)|h(t) (y(t))| + γ|H(y)|(3.34)t=0variables are discretized. A detailed analysis of discretization has been studied before [98].To simplify the presentation, without loss of generality, we study the following equality-From Theorem 3.6, the subproblem we need to solve in each stage t, t = 0, · · · , N, isconstrained DNLP in this section:defined as follows:(Pe ) :minysubject tof (y) where y ∈ D w(3.32)(t)Psub :h(y) = 0,miny(t)subject towhere D w is the discrete search space.3.3.1J(y) + γ T |H(y)|(3.35)h(t) (y(t)) = 0Constraint Partitioned Simulated Annealing (CPSA)Our objective is to find the constrained global minimum CGMd to Pe defined as follows:Algorithm∗∗Definition 1. A point y ∈ D is a CGMd to the DNLP in Pe if and only if h(y ) = 0wand f (y ∗) ≤ f (y) ∀y ∈ D w .

Характеристики

Список файлов лекций