J89 (1121213), страница 7

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

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

. . , m}:α = α + ν ⊗ e2 = α + (ν1 e2,1 , ν2 e2,2 , . . . , νm , e2,m )T .(51)Here, the jth element of e2 is 1 and the others are 0, and the νj is uniformly distributedin [−φj , φj ]. We adjust φj according to the degree of constraint violations, where:φ = w ⊗ h(x) = (w1 h1 (x), w2 h2 (x), . . . , wm hm (x))T .(52)When hi (x) = 0 is satisfied, φi = 0, and αi does not need to be updated. Otherwise,we adjust φi by modifying wi ⎧according to how fast hi (x) is changing:⎪if hi (x) > τ0 T,⎨η0 wi ,wi ←− η1 wi ,(53)if hi (x) < τ1 T,⎪⎩unchanged,otherwise,where η0 = 1.25, η1 =0.95, τ0 = 1.0, and τ1 = 0.01 were chosen experimentally. Whenhi (x) is reduced too quickly (i.e., hi (x) < τ1 T is satisfied), hi (x) is over-weighted,leading to a possibly poor objective value or difficulty in satisfying other underweighted constraints. Hence, we reduce αi ’s neighborhood. In contrast, if hi (x) isreduced too slowly (i.e., hi (x) > τ0 T is satisfied), we enlarge αi ’s neighborhood inorder to improve its chance of satisfaction.

Note that wi is adjusted using T as a reference because constraint violations are expected to decrease when T decreases. Otherdistributions of φj studied include non-symmetric uniform and nonuniform [31].Finally, we use the cooling schedule defined in Fig. 1, which is more aggressive thanthat in (41). We accept the x or x generated according to the Metropolis probabilitydefined in (25). Other probabilities studied include logistic, Hastings, and Tsallis [31].We set the ratio of generating x and x from x to be 20n to m, which means that x isupdated more frequently than α.Example 3 Figure 7 shows the run-time behavior at four temperatures when CSA isapplied to solve the following continuous constrained optimization problem:2 min f (x) = 10n +x2i − 10 cos(2πxi ) , where x = (x1 , x2 ),T (54)x1 , x2i=1subject to |(xi − 3.2)(xi + 3.2)| = 0,i = 1, 2.The objective function f (x) is very rugged because it is made up of a two-dimensionalRastrigin function with 11n (where n = 2) local minima.

There are four constrainedlocal minima at the four corners denoted by rectangles, and a constrained globalminimum at (−3.2, −3.2).Assuming a penalty function Lc (x, α)T = f (x) + α1 |(x1 − 3.2)(x1 + 3.2)| + α2 |(x2 −3.2)(x2 + 3.2)| and that samples in x are drawn in double-precision floating-pointspace, CSA starts from x = (0, 0)T with initial temperature T0 = 20 and a coolingrate κ = 0.95.

At high temperatures (e.g., T0 = 20), the probability of acceptinga trial point is high; hence, the neighborhood size is large according to (50). Largejumps in the x subspace in Fig. 7a are due to the use of the Cauchy distribution forJ Glob Optim554433221100112233445554321012345543(a) T = 2010123452345(b) T = 10.2455443322110011223344555432101(c) T = 8.192Fig. 7223455432101(d) T = 0.45Example illustrating the run-time behavior of CSA at four temperatures in solving (54)generating remote trial points, which increases the chance of getting out of infeasible local minima.

Probabilistic ascents with respect to α also help push the searchtrajectory to feasible regions. As T is reduced, the acceptance probability of a trialpoint is reduced, leading to smaller neighborhoods. Finally, the search converges tothe constrained global minimum at x∗ = (−3.2, −3.2)T .5.2 Implementation details of CPSA for solving continuous problemsWe have observed that the constraints of many application benchmarks do not involvevariables that are picked randomly from their variable sets. Invariably, many constraints in existing benchmarks are highly structured because they model spatial andtemporal relationships that have strong locality, such as those in physical structures,optimal control, and staged processing.Figure 8 shows this point by depicting the regular constraint structure of threebenchmarks.

It shows a dot where a constraint (with unique ID on the x-axis) isrelated to a variable (with a unique ID on the y-axis). When the order of the variablesand that of the constraints are properly arranged, the figure shows a strongly regularconstraint-variable structure.In CPSA, we follow a previously proposed automated partitioning strategy [28] foranalyzing the constraint structure and for determining how the constraints are to bepartitioned. The focus of our previous work is to solve the partitioned subproblems1204035100Variable ID180160140120100806040200Variable IDVariable IDJ Glob Optim80604010 20 30 40 50 60 70 80252015102003005020406080100 120Constraint IDConstraint IDa) TRIMLOSSb) ORTHREGC0010203040506070Constraint IDc) OPTCDEG3Fig.

8 Strongly regular constraint-variable structures in some continuous optimization problems. Adot in each graph represents a variable associated with a constraintusing an existing solver SNOPT [16]. In contrast, our focus here is to demonstrate theimprovement of CPSA over CSA and on their asymptotic convergence property.Based on Pm with continuous variables and represented in AMPL [14], our partitioning strategy consists of two steps. In the first step, we enumerate all the indexingvectors in the AMPL model and select one that leads to the minimum Rglobal , whichis the ratio of the number of global constraints to that of all constraints.

We chooseRglobal as a heuristic metric for measuring the partitioning quality, since a small number of global constraints usually translates into faster resolution. In the second step,after fixing the index vector for partitioning the constraints, we decide on a suitablenumber of partitions.

We have found a convex relationship between the number ofpartitions (N) and the complexity of solving Pm . When N is small, there are very fewsubproblems to be solved but each is expensive to evaluate; in contrast, when N islarge, there are many subproblems to be solved although each is simple to evaluate.Hence, there is an optimal N that leads to the minimum time for solving Pm . To findthis optimal N, we have developed an iterative algorithm that starts from a large N,that evaluates one subproblem under this partitioning (while assuming all the globalconstraints can be resolved in one iteration) in order to estimate the complexity ofsolving Pm , and that reduces N by half until the estimated complexity starts to increase.We leave the details of the algorithm to Wah and Chen [28].Besides the partitioning strategy, CPSA uses the same mechanism and parametersdescribed in Sect. 5.1 for generating trial points in the x, α, and γ subspaces.5.3 Implementation details of GEM for solving continuous problemsThe parameter in GEM were set based on the package developed by Wu and datedAugust 13, 2000 [32].

In generating a neighboring point of x for continuous probilems, we use a Cauchy distribution with density fd (xi ) = π1 σ 2σ+x2 for each variable xi ,iii = 1, . . . , n, where σi is a parameter controlling the Cauchy distribution. We initializeeach σi to 0.1.

For the last 50 probes that perturb xi , if more than 40 probes lead toa decrease of Lm , we increase σi by a factor of 1.001; if less than two probes lead toa decrease of Lm , we decrease σi by a factor of 1.02. We increase the penalty αi forconstraint hi by αi = αi + i |hi (x)|, where i is set to 0.0001 in our experiments. Weconsider a constraint to be feasible and stop increasing its penalty when its violationis less than 0.00001.J Glob Optim5.4 Evaluation results on continuous optimization benchmarksUsing the parameters of CSA and CPSA presented in the previous sections and assuming that samples were drawn in double-precision floating-point space, we report in thissection some experimental results on using CSA and CPSA to solve selected problems from CUTE [8], a constrained and unconstrained testing environment.

We haveselected those problems based on the criterion that at least the objective or one ofthe constraint functions is nonlinear. Many of those evaluated were from real applications, such as semiconductor analysis, chemical reactions, economic equilibrium, andproduction planning. Both the number of variables and the number of constraints inCUTE can be as large as several thousand.Table 1 shows the CUTE benchmark problems studied and the performance ofCPSA, CSA, GEM in (35), P3 in (7), and P4 in (8). In our experiments, we have usedthe parameters of P3 and P4 presented in Sect.

2.2. For each solver and each instance,we tried 100 runs from random starting points and report the average solution found(Qavg ), the average CPU time per run of those successful runs (Tavg ), the best solutionfound (Qbest ), and the fraction of runs there were successful (Psucc ). We underlinethe best Qavg and Qbest among the five solvers when there are differences. We donot list the best solutions of P3 and P4 because they are always worse than those ofCSA, CPSA, and GEM.

Also, we do not report the results on those smaller CUTEinstances with less than ten variables (BT*, AL*, HS*, MA*, NG*, TW*, WO*, ZE*,ZY*) [31] because these instances were easily solvable by all the solvers studied.When compared to P3 , P4 , and GEM, CPSA and CSA found much better solutionson the average and the best solutions on most of the instances evaluated. In addition,CPSA and CSA have a higher success probability in finding a solution for all theinstances studied.The results also show the effectiveness of integrating constraint partitioning withCSA. CPSA is much faster than CSA in terms of Tavg for all the instances tested.

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

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