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

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

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

We then compare the performance of our solver withChapter 2other leading solves on these continuous and mixed-integer benchmarks.Finally, in Chapter 6, we briefly summarize the research work we have presented in thisPrevious Workthesis, and point out future directions to extend this research.In this chapter, we first review existing penalty methods for solving constrained optimizationproblems and discuss their assumptions and limitations.

We then review existing partitioningmethods for solving mathematical programming problems, and point out what is new in ourproposed constraint partitioning approach. Finally, we survey existing automated planningalgorithms and show that most of them solve a problem as a whole without partitioning.2.1Existing Penalty MethodsIn this section, we survey existing penalty methods for constrained optimization. The concepts of saddle points and penalty formulations are important and form the basis of ourtheory presented in Chapter 3.Penalty methods belong to a general approach that can solve continuous, discrete, andmixed constrained optimization problems, with no continuity, differentiability, and convexityrequirements.

Penalty methods are the primary methods for solving constrained problems.A penalty function of Pm is a summation of its objective and its constraint functionsweighted by penalties. Using penalty vectors α ∈ Rm and β ∈ Rr , the general penaltyfunction for Pm is:Lp (z, α, β) = f (z) + αT P (h(z)) + β T Q(g(z)),1718(2.1)Penalty Functions for Constraint ProgrammingGlobal OptimalityLocal Optimality2.1.1Global optimal penalty methodsA static-penalty method [58, 70] formulates Pm as the minimization of (2.1) when the constraints of Pm are transformed by P and Q with the following properties: a) P (h(z)) ≥ 0Inexact PenaltyExact PenaltyExact Penaltyand Q(g(z)) ≥ 0; and b) P (h(z)) = 0 iff h(z) = 0, and Q(g(z)) = 0 iff g(z) ≤ 0.

Withpenalty vectors α and β, an example static-penalty method solves the following problemStaticPenaltyDynamicPenaltyDeathPenaltyDiscretePenaltyLagrangianl1−PenaltyFigure 2.1: A classification of existing penalty methods.where P and Q are transformation functions. The goal of a penalty method is to find suitable∗∗∗α and β in such a way that x that minimizes (2.1) corresponds to either a constrainedglobal minimum (CGM) that is feasible and has the best objective value in the entire searchspace, or a constrained local minimum (CLM) that is feasible and has the best objectivevalue in a pre-defined neighborhood.

Penalty methods belong to a general approach that cansolve continuous, discrete, and mixed constrained optimization problems, with no continuity,with constant ρ ≥ 1:min Ls (z, α, β) = min f (z) +xzmαi |hi (z)|ρ +i=1rρ βjmax(0, gj (z)).(2.2)j=1A static penalty method can be an exact or inexact penalty method, depending on thevalue of ρ. It is an exact penalty method when ρ = 1 and an inexact penalty method whenwhen ρ > 1 [10, 58, 70]. That is, when ρ = 1, there exist finite penalty values α and β suchthat the point minimizing the penalty function is exactly the CGM of Pm .

However, whenρ > 1, the static penalty method is an inexact method and will converge to the CGM asthe penalty values approach infinity. We illustrate this property by an example.differentiability, and convexity requirements.We show a classification of existing penalty methods in Figure 2.1. Penalty methods canExample 1. Consider the following simple optimization problem:be classified into global optimal penalty methods that look for CGM solutions of Pm and localminxoptimal penalty methods that look for CLM solutions of Pm . By another dimension, penaltysubject to :methods can be classified into exact penalty methods that can find exact CGM or CLMpoints under finite penalty values, and inexact penalty methods in which the minimizationf (x) = x(2.3)h(x) = x = 10(2.4)Obviously, the CGM is at x∗ = 10.

The static penalty function for this problem is:of a penalty function does not lead to exact CGM or CLM points [10, 58, 9, 70]. Instead,successive minimizations of an inexact penalty function with increasing penalty values leadLp (x, α) = f (x) + α|h(x)|ρ = x + α|x − 10|ρto points infinitely close to a CGM or CLM solution. Inexact penalty methods converge toa CGM or CLM solution as the penalty values approach infinity.19We consider two cases:20(2.5)b) When ρ > 1, differentiating Lp and setting the result to zero:a) When ρ = 1, the penalty function becomes:Lp (x, α) = f (x) + α|h(x)|ρ = x + α|x − 10|(2.6)dLp (x, α) = 1 + ρα|x − 10|ρ−1 = 0,dx(2.11)we can show that there exists a finite penalty value α∗ = 1 such that for any penalty valueswe have that the minimum of Lp is at:satisfying:α∗∗ ≥ α∗ = 1,1 ρ−1−1.x = 10±ρα(2.7)the point that minimizes Lp (x, α∗∗ ) is exactly at the CGM x∗ = 10.

To see this, we need toshow that:(2.12)We can see that the static penalty method is an inexact penalty method because x in(2.12) that minimizes Lp is not exactly at the CGM x∗ = 10. However, x will converge toLp (x, α∗∗ ) ≥ Lp (x∗ , α∗∗ ) = Lp (10, α∗∗) = 10, ∀x ∈ R.x∗ = 10 as the penalty value α approaches infinity.(2.8)A variation of the static-penalty method proposed in [40] uses discrete penalty valuesWe show that (2.8) is true for both x > 10 and x < 10. When x > 10, we have:and assigns a penalty value αi (hi (z)) when hi (z) exceeds a discrete level i (resp., βj (g(z))Lp (x, α∗∗ ) = x + α∗∗ (x − 10) > x > 10,∀x > 10 ;(2.9)when max(0, g(z)) exceeds a discrete level j ), where a higher level of constraint violationentails a larger penalty value.

The penalty method then solves the following problem:When x < 10, we have:min Ls (z, α, β) = min f (z) +zLp (x, α∗∗ ) = x + α∗∗ (10 − x) = 10α∗∗ − (α∗∗ − 1)x= (α∗∗ − 1)(10 − x) + 10 ≥ 10,∀x < 10,zmαi (hi (z)) h2i (z) +i=1r2 .(2.13)βj (gj (z)) max(0, gj (z))j=1(2.10)It is an inexact penalty method and requires the setting of many parameters. A limitationwhere the last inequality is true because α∗∗ ≥ α∗ = 1 and x < 10.Therefore, we have shown that Lp (x, α∗∗ ) is minimized exactly at the CGM x∗ = 10 forcommon to all static-penalty methods is that it is generally very difficult to set the suitablepenalty values statically.

Also, these methods were developed for finding CGM and cannotrelate a CLM of Pm to a local minimum of the corresponding penalty function. Therefore,all finite penalty values α∗∗ > 1.they are computationally expensive because they involve finding a global minimum of a2122nonlinear penalty function. Techniques like simulated annealing [49] can be used, althoughthey only achieve global optimality with asymptotic convergence.Instead of finding the penalty values by trial and error, a dynamic-penalty method [58, 70]increases the penalties in (2.2) gradually, finds the global minimum z ∗ of (2.2) with respectto z for each combination of penalties, and stops when z ∗ is a feasible solution to Pm . Likehi (z) = 0 is respectively, infeasible, feasible, or neither in the last iterations.

That is,⎧⎪⎪⎪αi (t)/λ1 if hi (z(i)) = 0 is feasible in iterations t − + 1, . . . , t⎪⎪⎪⎨αi (t + 1) = λ2 · αi (t) if hi (z(i)) = 0 is infeasible in iterations t − + 1, . . . , t⎪⎪⎪⎪⎪⎪⎩αi (t)otherwise.(2.16)the static penalty methods, a dynamic penalty methods can be an exact or inexact method,depending on the value of ρ. Moreover, it has the same limitation as all static-penaltymethods because it requires finding global minima of nonlinear functions.where is a positive integer, λ1 , λ2 > 1 and λ1 = λ2 in order to avoid cycles in updates. βis updated in a similar fashion.There are many variations of dynamic penalty methods.

A well-known one is the nonstationary method (NS) [42] that solves a sequence of problems with the following problemin iteration t:The threshold dynamic penalty method estimates and adjusts dynamically 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 during themin Lt (z, α, β) = min f (z) +zzmαi (t) |hi (z)|ρ +i=1rρ βj (t) max(0, gj (z)),(2.14)j=1min Lt (z, α, β) = min f (z) + α(t)αi (t + 1) = αi (t) + C · |hi (z(t))|,wheresolution of the following problem:zz m hi (z) 2qi (t)i=1+2r max(0, gj (z))j=1qj (t).(2.17)βj (t + 1) = βj (t) + C · max(0, gj (z(t)),There are two other variations of global penalty methods that are exact methods.

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

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