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

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

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

Theand C > 0 and ρ > 1 are constant parameters. An advantage of the NS penalty method isdeath penalty method simply rejects all infeasible individuals [5] using the following penaltythat it requires only a few parameters to be tuned.Another dynamic penalty method is the adaptive penalty method (AP) [8] that makes useof a feedback from the search process. AP solves the following problem in iteration t:min Lt (z, α, β) = min f (z) +zzmαi (t) hi (z)2 +i=1r2 βj (t) max(0, gj (z)),(2.15)j=1where αi (t) is, respectively, increased, decreased, or left unchanged when the constraint2324for solving continuous nonlinear programming problems (CNLPs) defined as follows:function:Lp (z, α, β) = f (z) + αT P (h(z)) + β T Q(g(z)),⎧⎪⎪⎨+∞P (h(z)) =if h(z) = 0⎪⎪⎩0(Pc ) :minxsubject tof (x)where x = (x1 , . .

. , xv )T ∈ Rv(2.21)h(x) = (h1 (x), . . . , hm (x))T = 0 and g(x) = (g1 (x), . . . , gr (x))T ≤ 0,(2.19)if h(z) = 0,where f is continuous and differentiable, and g and h can be discontinuous, non-differentiable,⎧⎪⎪⎨+∞Q(g(z)) =(2.18)and not in closed form. The goal of solving Pc is to find a constrained local minimum x∗if g(z) > 0(2.20)⎪⎪⎩0if g(z) ≤ 0.with respect to Nc (x∗ ) = {x : x − x∗ ≤ and → 0}, the continuous neighborhood of x∗ .Definition 2.1 Point x∗ is a CLMc , a constrained local minimum of Pc with respect toThis is an exact penalty method.

Given any finite penalty values α > 0 and β > 0,points in Nc (x∗ ), if x∗ is feasible and f (x∗ ) ≤ f (x) for all feasible x ∈ Nc (x∗ ).the minimum point of the penalty function must be feasible and must have the minimumTraditional Lagrangian theory for continuous optimization works for Pc with continu-objective value, and therefore is exactly the CGM of Pm .

Another exact penalty methodous and differentiable constraint functions g and h. The Lagrangian function of Pc withis the discrete penalty method that uses the numbers of violated constraints instead of theLagrange-multiplier vectors λ = (λ1 , . .

. , λm )T ∈ Rm and μ = (μ1 , . . . , μr )T ∈ Rr , is defineddegree of violations in the penalty function [52].as:In summary, methods for finding the global minimum of (2.2) are of limited practicalimportance because the search of a global minimum of a nonlinear function is very computationally expensive. Global optimization techniques like simulated annealing are too slowbecause they only achieve global optimality with asymptotic convergence.L(x, λ, μ) = f (x) + λT h(x) + μT g(x).(2.22)Under the continuity and differentiability assumptions, a CLMc satisfies the followingnecessary KKT condition and sufficient saddle-point condition.a) Necessary Karush-Kuhn-Tucker (KKT) condition [10]. Assuming x∗ is a CLMc and a2.1.2Local optimal penalty methodsTo avoid expensive global optimization, local optimal penalty methods have been developed tolook for constrained local minima (CLM) instead of CGM.

These include Lagrange-multipliermethods and 1 -penalty methods, which are both exact penalty methods. They are designedregular point,1 then there exist unique λ∗ ∈ Rm and μ∗ ∈ Rr such that:∇x L(x∗ , λ∗ , μ∗) = 0,(2.23)/ A(x∗ ) = {i | gi (x∗ ) = 0} (the set of active constraints), and μj > 0where μj = 0 ∀ j ∈1Point x is a regular point [58] if gradient vectors of equality constraints ∇h1 (x), . . . , ∇hm (x) and activeinequality constraints ∇ga1 (x), . .

. , ∇gal (x), ai ∈ A(x) (the set of active constraints), are linearly independent.2526at the solution points.otherwise.The unique x, λ and μ that satisfy (2.23) can be found by solving (2.23) as a systemb) Sufficient saddle-point condition [51, 4]. The concept of saddle points has been studiedof nonlinear equations.

For instance, consider Pc with only equality constraints. The KKTextensively in the past. For continuous and differentiable constraint functions, x∗ is a CLMccondition in (2.23) can be expressed as a system of v + m equations in v + m unknowns:of Pc if there exist unique λ∗ ∈ Rm and μ∗ ∈ Rr that satisfy the following saddle-point⎡condition at x∗ :⎤⎢∇f (x) + λ ∇h(x)⎥F (x, λ) = ⎣⎦ = 0,h(x)T(2.24)L(x∗ , λ, μ) ≤ L(x∗ , λ∗ , μ∗ ) ≤ L(x, λ∗ , μ∗ )(2.25)where ∇h(x)T = [∇h1 (x), . . . , ∇hm (x)] is the Jacobian of the constraints. The v + m un-for all x ∈ Nc (x∗ ) and all λ ∈ Rm and μ ∈ Rr . This condition is only sufficient but notknowns are solvable when the matrix in (2.24) is nonsingular.necessary because there may not exist λ∗ and μ∗ that satisfy (2.25) at each CLMc x∗ of Pc .Because the necessary KKT condition is a system of simultaneous nonlinear equationsTo illustrate the concept, consider the following CNLP with CLMc at x∗ = 5:that cannot be solved in closed form, iterative procedures have been developed to find theminx∗f (x) = −x2subject to h(x) = x − 5 = 0.(2.26)unique x and Lagrange-multiplier values that satisfy the condition.

For example, existingsequential quadratic-programming solvers like SNOPT [32] solve the nonlinear equationsBy applying the KKT condition, we differentiate the Lagrangian function L(x, λ) = −x2 +iteratively by forming a quadratic approximation, evaluating the quadratic model, and up-λ(x − 5) with respect to x and evaluate it at x∗ = 5. We have ∇x L(x, λ)|x∗ = −10 + λ = 0,dating estimates of x and Lagrange multipliers until a solution has been found. Such anwhich implies λ∗ = 10.

However, since ∇2x L(x, λ)|x∗ ,λ∗ = −2 < 0, we know that L(x, λ) isiterative process cannot be used when a problem is partitioned by its constraints into sub-at a local maximum with respect to x at (x∗ , λ∗ ) instead of a local minimum. Hence, thereproblems. Partitioning the constraints amounts to decomposing the system of nonlinearexists no λ∗ that will allow the second inequality in (2.25) to be satisfied at x∗ = 5.equations into parts and solving each independently before resolving inconsistencies. ThereIn practice, it is difficult to use (2.25) for finding the unique x∗ , λ∗ , and μ∗ that satisfyis no known procedure for solving a system of partitioned nonlinear equations efficiently(2.23) because it is expressed as a system of nonlinear inequalities that are more difficult towhen the result requires a unique assignment of each variable.

Moreover, the approach issolve than nonlinear equalities. It is mainly used for verifying the solutions found by solvinglimited to solving CNLPs with continuous and differentiable functions and cannot be ap-(2.23).plied to solve discrete and mixed-integer problems, the limitation is due to the fact that theAnother local optimal exact penalty method for solving CNLPs is the 1 -penalty methodexistence of the Lagrange multipliers depends on the existence of the gradients of constraintand objective functions and the regularity conditions (independence of constraint gradients)2728based on the following 1 -penalty function [34]:1 (z, c) = f (z) + c · max 0, |h1 (z)|, · · · , |hm (z)|, g1 (z), · · · , gq (z)P:P:(2.27)GIts theory shows that there is a one-to-one correspondence between a CLMc and an uncon-A∗strained local minimum of (2.27) when c is larger than a finite threshold c .

The methodBACSA ∨ SB ∨ SC = SPBCSA ∧ SB ∧ SC ∧ SG = SPcannot support constraint partitioning of (1.1) for two reasons. First, the theory was deriveda) Subspace partitioningunder the continuity and differentiability assumptions on constraints similar to those in theb) Constraint partitioningfirst-order KKT condition. In fact, c∗ can be proved to be the maximum of all LagrangeFigure 2.2: An illustration of subspace partitioning and constraint partitioning.

Subspacemultipliers of the corresponding Lagrangian formulation. Second, since there is only onepartitioning decomposes P into a disjunction (∨) of subproblems, where the complexity ofsingle penalty term c on the maximum of all constraint violations in (2.27), it is difficult topartition (2.27) by its constraints and to reach a consistent value of c across the subproblems.In short, using global optimal penalty formulation (2.2) that converts all constraint func-each subproblem is similar to that of P .

In contrast, constraint partitioning decomposes Pinto a conjunction (∧) of subproblems and a set of global constraints (G) to be resolved,where the complexity of each subproblem is substantially smaller than that of P .tions to non-negative functions, a CGMm of Pm always corresponds to an unconstrainedfunction when its penalties are larger than some thresholds.

A constrained local minimumglobal minimum of (2.2) when its penalties are larger than some thresholds. Unfortunately,of a MINLP can, therefore, be found by looking for a local minimum of the correspondingthis result is impractical because finding global minima of an unconstrained nonlinear funcunconstrained penalty function using an existing algorithm and by increasing gradually thetion is computationally expensive. On the other hand, using penalty formulation (2.22), apenalties of violated constraints.constrained local minimum of the original problem does not imply a local minimum of (2.22)at z ∗ because there may not exist feasible penalties there.

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

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