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

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

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

Based on a penalty formulation,our theory offers a necessary and sufficient condition for constrained local optima. Theunique feature of this condition is that, the condition is true over an extended region ofpenalty values, instead of a set of unique values.We then extend the theory and apply it to NLPs under constraint partitioning and derivea set of partitioned necessary conditions to reduce the search complexity in revolving globalconstraints under constraint partitioning.

The theory facilitates constraint partitioning byproviding a set of necessary conditions, one for each subproblem, to characterize the constrained local optima. It reduces the complexity by defining a much smaller search space ineach subproblem for backtracking. It is significantly stronger than the partial filtering basedon local constraints alone, as it incorporates violated global constraints and the objectiveinto its local constrained optimality condition.3.1Necessary and Sufficient Extended Saddle-PointConditionWe describe in this section our theory of extended saddle points in discrete, continuous, andmixed spaces based on an 1 -penalty function.

We show a necessary and sufficient conditionunder a relaxed range of penalties. Since the result for MINLPs is derived based on the4344results for continuous and discrete NLPs, we will first develop the theory for continuous andwhere Ch and Cg are, respectively, the sets of indices of continuous equality and continuousdiscrete problems before presenting a unified theory for mixed problems.active inequality constraints. Constraint qualification is always satisfied if Ch and Cg are3.1.1empty sets.ESPC for continuous optimizationWe first state the necessary and sufficient ESPC on CLMc of Pc in (2.21), based on anIntuitively, constraint qualification at x∗ ensures the existence of finite α and β that leadto a local minimum of (3.1) at x∗ . Consider a neighboring point x∗ + p infinitely close to1 -penalty function that transforms the constraints of Pc into non-negative functions.x∗ , where the objective function f at x∗ decreases along p and all active constraints at x∗Definition 3.1 The 1 -penalty function for Pc in (2.21) is defined as follows:have zero subdifferentials along p.

In this case, all the active constraints at x∗ + p are alsoLc (x, α, β) = f (x) + αT |h(x)| + β T max(0, g(x)),(3.1)where |h(x)| = (|h1 (x)|, . . . , |hm (x)|)T and max(0, g(x)) = (max(0, g1(x)), . . . , max(0, gr (x)))T ;satisfied, and it will be impossible to find finite α and β in order to establish a local minimumof (3.1) at x∗ with respect to x∗ + p. To ensure a local minimum of (3.1) at x∗ , the abovescenario must not be true for any p at x∗ .and α ∈ Rm and β ∈ Rr are penalty vectors.In continuous space, we need the following constraint-qualification condition in order torule out the special case in which all continuous constraints have zero subdifferential alongOur constraint-qualification condition requires the subdifferential of at least one activeconstraint at x∗ to be non-zero along each and every direction p. For CNLPs, the conditionrules out the case in which there exists a direction p at x∗ along which all active constraintsa direction.Definition 3.2 Dx (φ(x ), p), the subdifferential of function φ at x ∈ X along directionp ∈ X, represents the rate of change of φ(x ) under an infinitely small perturbation along p.are continuous and have zero subdifferentials.

Note that our condition is less restricted thanthe regularity condition in KKT that requires the linear independence of gradients of activeconstraint functions.That is,The following theorem states the ESPC when the constraint qualification is satisfied.Dx (φ(x ), p) = lim→0φ(x + p) − φ(x ).(3.2)Theorem 3.1 Necessary and sufficient ESPC on CLMc of Pc . Suppose x∗ ∈ Rv is a pointin the continuous search space of Pc and satisfies the constraint-qualification condition (3.3),Definition 3.3 Constraint-qualification condition.

Solution x∗ ∈ X of Pc meets the con-then x∗ is a CLMc of Pc if and only if there exist finite α∗ ≥ 0 and β ∗ ≥ 0 such that thestraint qualification if there exists no direction p ∈ X along which the subdifferentials offollowing is satisfied:continuous equality and continuous active inequality constraints are all zero. That is,Lc (x∗ , α, β) ≤ Lc (x∗ , α∗∗ , β ∗∗ ) ≤ Lc (x, α∗∗ , β ∗∗ ) where α∗∗ > α∗ ≥ 0 and β ∗∗ > β ∗ ≥ 0,(3.4) ∃ p ∈ X such that Dx (hi (x∗ ), p) = 0 and Dx (gj (x∗ ), p) = 0 ∀i ∈ Ch and j ∈ Cg ,(3.3)for all x ∈ Nc (x∗ ), α ∈ Rm , and β ∈ Rr . Here, α∗∗ > α∗ (resp.

β ∗∗ > β ∗ ) means that each4546→3) If there exists a discontinuous active inequality constraint gk along −p , then for a smallelement of α∗∗ (resp. β ∗∗ ) is larger than the corresponding element of α∗ (resp. β ∗ ).enough , there exists a finite positive ξ such that:Proof. The proof consists of two parts.“⇒” part: Given x∗ , we need to prove that there exist finite α∗∗ > α∗ ≥ 0 and β ∗∗ >max(0, gk (x)) > ξ > 0.(3.8)β ∗ ≥ 0 that satisfy (3.4). The inequality on the left of (3.4) is true for all α and β becauseIf we set βk∗∗ > βk∗ = 1 and when is small enough, then from (3.8):x∗ is a CLMc , which implies that |h(x∗ )| = 0 and max(0, g(x∗ )) = 0.To prove the inequality on the right of (3.4), we prove for any x ∈ Nc (x∗ ) that there existfinite α∗ and β ∗ such that the inequality is satisfied for any α∗∗ > α∗ and β ∗∗ > β ∗ . LetLc (x, α∗∗ , β ∗∗ ) = f (x) +βj∗∗ max(0, gj (x))j=1> f (x∗ ) = Lc (x∗ , α∗∗ , β ∗∗ ).1) If all the constraints are inactive inequality constraints, then x ∈ Nc (x∗ ) is also a(3.5)r→≥ f (x) + βk∗∗ max(0, gk (x)) > f (x∗ ) + ∇x f (x∗ )T −p + o(2 ) + βk∗ ξscalar.

We consider the following four cases.Lc (x, α∗∗ , β ∗∗ ) = f (x) ≥ f (x∗ ) = Lc (x∗ , α∗∗ , β ∗∗ ).αi∗∗ |hi (x)| +i=1→−x = x∗ + −p , where →p = 1 is a unit directional vector and is an infinitely small positivefeasible point. Hence, (3.4) implies f (x) ≥ f (x∗ ) and, regardless the choice of the penalties,m(3.9)4) Other than inactive inequality constraints, if there are equality and active inequality−constraints that are continuous along →p , then according to the constraint-qualification condition, there must exist an equality constraint or an active inequality constraint that has→p , then for a small enough2) If there exists a discontinuous equality constraint hk along −−non-zero subdifferential along →p .

Suppose there exists an equality constraint hk that has→non-zero subdifferential along −p (the case with an active inequality constraint is similar),, there exists a finite positive ξ such that:→which means |Dx (hk (x∗ ), −p )| > 0. If we set αk∗∗ >∗|hk (x)| > ξ > 0 = hk (x ).then:If we set αk∗∗ > αk∗ = 1 and when is small enough, then from (3.6):∗∗Lc (x, α , β ) = f (x) +mαi∗∗ |hi (x)|+i=1r∗∗∗∗> f (x ) = Lc (x , α , β ).47mαi∗∗ |hi (x)| +rβj∗∗ max(0, gj (x))j=1→−≥ f (x) + αk∗∗ |hk (x)| ≥ f (x∗ ) + ∇x f (x∗ )T −p + o(2 ) + αk∗∗ |Dx (hk (x∗ ), →p )|βj∗∗ max(0, gj (x)) →→≥ f (x∗ ) + αk∗∗ Dx (hk (x∗ ), −p + o(2 )p ) − ∇x f (x∗ )T −j=1∗Lc (x, α∗∗ , β ∗∗ ) = f (x) +i=1→p + o(2 ) + αk∗ ξ≥ f (x) + αk∗∗ |hk (x)| > f (x∗ ) + ∇x f (x∗ )T −∗and when is small enough,(3.6)−p if (3.6) were false.The above must be true because hk (x) would be continuous along →∗∗→p||∇x f (x∗ )T −→|Dx (hk (x∗ ),−p )|> f (x∗ ) = Lc (x∗ , α∗∗ , β ∗∗ )(3.10)(3.7)48The inequality on the right of (3.4) is proved after combining Cases (1) to (4).**and g(x∗ ) ≤ 0.

Since |h(x∗ )| = 0 and max(0, g(x∗ )) = 0, the inequality on the right of(3.4) ensures that x∗ is a local minimum when compared to all feasible points in Nc (x∗ ).Therefore, x∗ is a CLMc . α= 10 = α***α80= 20 > α*60Lc(x,20)is feasible because the inequality on the left of (3.4) can only be satisfied when h(x∗ ) = 0Lc(x,10)“⇐” part: Assuming (3.4) is satisfied, we need to prove that x∗ is a CLMc . Point x∗403020100-10-20-30-40-5040200-2012345678-409x123456789xFigure 3.1: An illustration that (3.4) is satisfied when α∗∗ > α∗ = 10 for the CNLP problemIntuitively, (3.4) shows that a local minimum of (3.1) with respect to x corresponds to aCLMc of Pc (second inequality of (3.4)) when α∗∗ and β ∗∗ are larger than some thresholds α∗in (2.26). Lc (x, α∗∗ ) is a strict local minimum around x∗ = 5 when α∗∗ > α∗ but is not onewhen α∗∗ = α∗ .∗and β such that all the constraints of Pc are forced to be satisfied (first inequality of (3.4)).Since a local minimum of (3.1) can be found easily by many existing search algorithms, ourresult improves over the static-penalty approach, which is defined with respect to difficultto-find global minima of (2.2).

We can find a CLMc to Pc by gradually increasing α∗∗ andβ ∗∗ , while minimizing Lc (x, α∗∗ , β ∗∗ ), until α∗∗ > α∗ and β ∗∗ > β ∗ .It is interesting to note that α∗ and β ∗ can be much smaller than the corresponding c∗ inthe static and dynamic penalty methods. Continuing on the example in (2.26), static andtheory can be found in the original papers [91, 98].Consider the DNLP whose f , g and h are not necessarily continuous and differentiablewith respect to y.(Pd ) :minysubject towhere y = (y1 , .

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

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