Global Optimization Methods

Deterministic Global Search and Nature-Inspired Population Methods

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 16-17.

이 장에서는 nonconvex optimum design problem에서 local minimum을 넘어 더 좋은 basin을 탐색하는 global optimization methods를 정리한다. 먼저 global minimum의 정의와 numerical certification의 한계를 살펴보고, deterministic covering과 zooming을 분석한다. 이어서 stochastic global-local search의 구조를 설명하고, population-based methods인 genetic algorithm, differential evolution, ant colony optimization, particle swarm optimization의 update rules와 exploration-exploitation mechanism을 비교한다.


Global Optimization Problem

Bounded design domain을

\[S_b = \left\{ x\in\mathbb{R}^n: x_{iL}\leq x_i\leq x_{iU},\; i=1,\ldots,n \right\}\]

이라 하고, original constraints까지 만족하는 feasible set을 $S\subseteq S_b$라 하자. Global optimization problem은

\[\underset{x\in S}{\operatorname{minimize}} \quad f(x)\]

이다.

Point $x^{\star}$가 어떤 feasible neighborhood $\mathcal{N}(x^{\star})$에서

\[f(x^{\star})\leq f(x), \qquad \forall x\in S\cap\mathcal{N}(x^{\star})\]

를 만족하면 local minimum이다. 반면 $x_G^{\star}$가

\[f(x_G^{\star})\leq f(x), \qquad \forall x\in S\]

를 만족하면 global minimum이다. 여러 global minimizers가 존재할 수 있지만 objective value는 모두 같다.


Existence and Certification

$S$가 closed and bounded이고 $f$가 $S$에서 continuous이면 Weierstrass theorem에 의해 global minimum은 존재한다. 그러나 존재 정리는 그 point를 계산하는 방법을 제공하지 않는다.

Global minimum도 local minimum이므로 regularity conditions 아래에서 KKT necessary conditions를 만족한다. 하지만 KKT point가 global minimum이라는 결론은 얻을 수 없다. General nonconvex problem에는 convexity 또는 valid global bounds와 같은 추가 구조가 없는 한 global optimality를 판정하는 보편적인 local condition이 없다.

따라서 numerical search가 반환한 best point는 다음 중 하나로 해석해야 한다.

  • Convexity 또는 exhaustive bounding으로 증명된 global solution
  • 주어진 tolerance 안에서 보장된 approximate global solution
  • 제한된 computational budget 안에서 발견한 best-known solution


Global methods는 random element의 사용 여부에 따라 크게 두 종류로 나뉜다.

  • Deterministic methods는 domain partition, bounds, covering, exclusion rule을 정해진 방식으로 적용한다.
  • Stochastic methods는 random samples 또는 random population operations를 사용하여 여러 regions를 탐색한다.

Deterministic finite-exact method는 assumptions가 만족되면 finite computation으로 guarantee를 제공할 수 있지만 dimension이 증가하면 계산량이 매우 커진다. Stochastic method는 넓은 domain을 유연하게 탐색하지만 finite run에서 global optimum을 찾았다는 deterministic certificate는 일반적으로 제공하지 않는다.

많은 global methods는 local optimizer를 반복 호출한다. 따라서 global strategy의 성능은 domain exploration뿐 아니라 각 basin에서 사용하는 local minimization의 robustness에도 의존한다.


Lipschitz Continuity

Deterministic covering method의 대표적인 assumption은 $S_b$에서의 Lipschitz continuity이다. 어떤 $L>0$가 존재하여

\[\left|f(x)-f(y)\right| \leq L\left\|x-y\right\|, \qquad \forall x,y\in S_b\]

를 만족한다고 하자. Center $c$와 radius $r$을 갖는 covered region에서 $|x-c|\leq r$이면

\[f(x) \geq f(c)-Lr\]

이므로 sampled value로 그 region의 lower bound를 만들 수 있다. 이 lower bound가 current best upper bound보다 크면 해당 region을 제거할 수 있다.

실제 문제에서는 valid Lipschitz constant를 계산하거나 검증하기 어렵다. $L$을 작게 추정하면 global basin을 잘못 제거할 수 있고, 지나치게 크게 추정하면 lower bound가 느슨해져 covering efficiency가 떨어진다.


Covering Methods

Covering method는 selected sample points와 associated regions의 union으로 $S_b$ 전체를 덮는다. Tolerance $\epsilon>0$에 대한 approximate solution set은

\[A_{\epsilon} = \left\{ x\in S: f(x)-f(x_G^{\star})\leq\epsilon \right\}\]

로 정의할 수 있다. Method는 반환된 point가 $A_{\epsilon}$에 속하도록 mesh density와 bounds를 조절한다.

Typical procedure는 다음과 같다.

  1. Domain을 intervals, hyperrectangles, 또는 hyperspheres로 partition한다.
  2. 각 region에서 function value와 valid lower bound를 계산한다.
  3. Current best value보다 개선될 수 없는 regions를 제거한다.
  4. Remaining regions를 더 세분하고 tolerance가 충족될 때까지 반복한다.

Covering은 global guarantee를 설명하기 쉬우나 dimension이 증가하면 필요한 cells 수가 급격히 증가한다. Hyperspheres는 complete coverage를 위해 overlap이 필요하고, hyperrectangular mesh도 curse of dimensionality를 피하지 못한다.


Zooming Method

Zooming은 general constrained problem에서 local minimization과 feasible-set truncation을 반복한다. Current local minimum을 $x^{\star}$라 하면 더 낮은 target level을 강제하기 위해

\[f(x) \leq \gamma f(x^{\star})\]

를 original problem에 추가한다. Source convention은

\[0<\gamma<1 \quad\text{if}\quad f(x^{\star})>0,\] \[\gamma>1 \quad\text{if}\quad f(x^{\star})<0\]

이다. 두 경우 모두 right-hand side는 current local value보다 작은 target이 된다.

Modified problem이 feasible하면 새로운 local minimum을 찾고 target을 다시 낮춘다. 이 과정은 이미 발견한 local minimum level을 제거하면서 lower objective region으로 zoom in한다.

Feasible set은 iteration마다 줄어들고 disconnected될 수 있다. Modified problem에서 feasible point를 찾지 못했다는 사실은 global optimality의 증명이 아니므로 여러 starting points와 search limits가 필요하다.


Stochastic methods는 보통 두 phases를 갖는다.

  1. Global phase: $S_b$에서 random points 또는 population을 생성하여 unexplored regions를 조사한다.
  2. Local phase: Promising samples에서 local minimization을 수행하여 candidate minima를 얻는다.

어떤 starting point에서 local method가 동일한 local minimum으로 수렴하는 points의 집합을 그 minimum의 region of attraction이라 한다. Pure multistart는 많은 starting points를 사용하지만 같은 basin에서 local search를 반복할 수 있다. Clustering과 domain-elimination methods는 known minima와 trajectories를 저장하여 이러한 중복을 줄인다.

Stochastic run은 seed에 따라 다른 history와 solution을 만들 수 있다. 따라서 multiple independent runs, best-value stagnation, population diversity, function-evaluation budget을 함께 보고 stopping을 판단해야 한다.


Constraint Handling

많은 global methods는 unconstrained search를 기본으로 하므로 constrained problem에서는 penalty 또는 augmented Lagrangian function을 fitness로 사용한다.

\[\Phi(x) = f(x)+\mathcal{P}(x), \qquad \mathcal{P}(x)\geq0.\]

Penalty가 충분하지 않으면 low-cost infeasible point가 선호될 수 있고, 지나치게 크면 fitness landscape가 ill-conditioned해질 수 있다. Global search의 reported best point는 반드시 original constraints에 대해 다시 검증해야 한다.


Nature-inspired methods는 한 point가 아니라

\[\mathcal{X}^{(k)} = \left\{ x^{(1,k)},\ldots,x^{(N_p,k)} \right\}\]

인 population을 갱신한다. Population diversity는 여러 basins를 탐색하는 exploration을 제공하고, selection 또는 best-point attraction은 promising regions를 집중적으로 조사하는 exploitation을 제공한다.

이 methods는 derivatives를 요구하지 않고 discrete, linked, nondifferentiable variables에도 적용할 수 있다. 반면 finite iterations에서 global optimality를 보장하지 않으며 population size, random operators, stopping budget에 민감하다.


Genetic Algorithm

Genetic algorithm, GA는 각 design을 chromosome으로 encoding하고 population에 selection, crossover, mutation을 반복한다. Constrained problem에서는 cost 대신 penalty function value $f_i$를 사용할 수 있다.

Population에서 가장 큰 recorded cost를 $f_{\max}$라 하면 source의 fitness definition은

\[F_i = (1+\epsilon)f_{\max}-f_i, \qquad \epsilon>0\]

이다. Smaller cost는 larger fitness를 갖는다. Roulette-wheel reproduction probability는

\[P_i = \frac{F_i}{\displaystyle\sum_{j=1}^{N_p}F_j}\]

이다.

  • Selection은 higher-fitness chromosomes를 다음 generation에 더 자주 복제한다.
  • Crossover는 두 parent strings의 segments를 교환하여 characteristics를 조합한다.
  • Mutation은 일부 genes를 바꾸어 population에서 사라진 alternatives를 다시 도입한다.

Selection은 exploitation을 강화하고 crossover는 existing building blocks를 재조합한다. Mutation은 diversity를 유지하여 premature convergence를 완화하지만 mutation rate가 너무 크면 accumulated information이 손실된다.


Differential Evolution

Differential evolution, DE는 real-valued vectors를 직접 사용한다. Initial population은

\[x_j^{(i,0)} = x_{jL} + r_{ij}\left(x_{jU}-x_{jL}\right), \qquad r_{ij}\sim\mathcal{U}(0,1)\]

로 생성할 수 있다.

Generation $k$에서 서로 다른 indices $r_1,r_2,r_3$를 선택하고 scale factor $F$를 사용하여 parent $x^{(p,k)}$의 donor vector를

\[V^{(p,k)} = x^{(r_1,k)} + F\left( x^{(r_2,k)}-x^{(r_3,k)} \right)\]

로 만든다. Population difference가 mutation step의 direction과 scale을 동시에 제공한다.

Binomial crossover는 trial vector $U^{(p,k)}$의 각 component를

\[U_j^{(p,k)} = \begin{cases} V_j^{(p,k)}, & r_{pj}\leq Cr \ \text{or}\ j=j_r, \\ x_j^{(p,k)}, & \text{otherwise} \end{cases}\]

로 결정한다. Random index $j_r$는 trial vector가 donor component를 적어도 하나 포함하도록 한다.

Greedy selection은

\[x^{(p,k+1)} = \begin{cases} U^{(p,k)}, & f\!\left(U^{(p,k)}\right) \leq f\!\left(x^{(p,k)}\right), \\ x^{(p,k)}, & \text{otherwise} \end{cases}\]

이다. 따라서 각 parent position의 fitness는 악화되지 않는다. $F$는 differential mutation의 scale을, $Cr$은 donor components가 trial vector로 전달되는 비율을 조절한다.


Ant Colony Optimization

Ant colony optimization, ACO는 discrete design을 layered graph의 path로 표현한다. 각 link $(i,j)$에 pheromone value $\tau_{ij}$를 두고, current node $i$에서 feasible next-node set을 $D_i$라 하면

\[p_{ij} = \frac{\tau_{ij}} {\displaystyle\sum_{\ell\in D_i}\tau_{i\ell}}, \qquad j\in D_i\]

로 link를 선택한다. 여러 ants가 component를 하나씩 선택하여 feasible solutions를 구성한다.

Iteration 후 모든 links에서 pheromone을

\[\tau_{ij} \leftarrow (1-\rho)\tau_{ij}, \qquad 0<\rho\leq1\]

로 evaporate한다. Ant $k$가 사용한 links에는

\[\tau_{ij} \leftarrow \tau_{ij} + \frac{Q}{f\!\left(x^{(k)}\right)}\]

를 적용한다. Smaller-cost solution은 더 많은 pheromone을 deposit하고, 여러 good solutions가 공유하는 links는 반복적으로 강화된다.

Evaporation은 old information을 줄여 exploration을 유지하고 reinforcement는 successful components의 재사용 확률을 높인다. Evaporation이 너무 약하면 early paths가 search를 지배하고, 너무 강하면 accumulated information이 빠르게 사라진다.


Particle Swarm Optimization

Particle swarm optimization, PSO에서 particle $i$는 current position $x^{(i,k)}$, velocity $v^{(i,k)}$, personal best $x_P^{(i,k)}$를 저장한다. Population 전체의 best position은 $x_G^{(k)}$이다.

Velocity update는

\[\begin{aligned} v^{(i,k+1)} =\;& v^{(i,k)} + c_1r_1 \left( x_P^{(i,k)}-x^{(i,k)} \right) \\ & + c_2r_2 \left( x_G^{(k)}-x^{(i,k)} \right) \end{aligned}\]

이고 position은

\[x^{(i,k+1)} = x^{(i,k)}+v^{(i,k+1)}\]

로 갱신한다. $c_1$은 particle 자체의 history를 따르는 cognitive weight이고, $c_2$는 swarm leader를 따르는 social weight이며 $r_1,r_2\sim\mathcal{U}(0,1)$이다.

New position에서 objective를 평가한 뒤

\[x_P^{(i,k+1)} = \begin{cases} x^{(i,k+1)}, & f\!\left(x^{(i,k+1)}\right) \leq f\!\left(x_P^{(i,k)}\right), \\ x_P^{(i,k)}, & \text{otherwise} \end{cases}\]

로 personal best를 갱신하고, 모든 personal best 중 가장 좋은 point를 $x_G^{(k+1)}$로 둔다. Position bounds는 매 update 후 enforce해야 한다.


Method Comparison

  • Covering은 valid regularity and bounds 아래에서 approximation guarantee를 제공하지만 dimension에 매우 민감하다.
  • Zooming은 constrained local optimizer를 재사용하기 쉽지만 infeasibility-based stopping이 global certificate는 아니다.
  • GA는 discrete encoding과 combinatorial recombination에 적합하지만 encoding과 operator rates에 민감하다.
  • DE는 real vectors와 population differences를 사용하며 update가 단순하고 greedy selection을 갖는다.
  • ACO는 discrete path construction과 linked choices에 자연스럽지만 pheromone stagnation이 발생할 수 있다.
  • PSO는 crossover 없이 personal and global best attraction을 사용하며 continuous design space에 직접 적용된다.

Deterministic methods의 핵심은 valid bounds and coverage이고, nature-inspired methods의 핵심은 population diversity and information sharing이다. 후자는 좋은 design을 빠르게 찾을 수 있지만, repeated success 자체가 global optimality의 proof는 아니다.


Summary

  • Global minimum은 전체 feasible set에서 objective가 가장 작지만, general nonconvex problem에는 보편적인 local certificate가 없다.
  • Lipschitz covering은 sampled values로 regional lower bounds를 만들고 inferior regions를 제거한다.
  • Zooming은 $f(x)\leq\gamma f(x^{\star})$를 추가하여 current local-minimum level 아래로 feasible set을 축소한다.
  • Stochastic methods는 global sampling과 local minimization을 결합하며 regions of attraction의 중복 탐색을 줄여야 한다.
  • GA는 fitness-biased selection, crossover, mutation으로 population을 갱신한다.
  • DE는 scaled population difference로 donor를 만들고 binomial crossover와 greedy selection을 적용한다.
  • ACO는 pheromone-weighted path selection, evaporation, cost-dependent reinforcement를 사용한다.
  • PSO는 personal best와 swarm best를 향하는 velocity로 particles를 이동시킨다.
  • Nature-inspired methods는 derivatives가 필요 없지만 finite-run global optimality를 보장하지 않으며 final feasibility 검증이 필요하다.