최적설계 | 제약조건 문제 수치해법(4): 부정확 이동거리 탐색법

1. 부정확 이동거리 탐색법

   앞서 다룬 황금분할 탐색법은 구간감소법 중에서는 좋은 성능을 보이지만, 여전히 많은 함수값 계산을 요구하기 때문에 실제 공학 응용문제에서는 비효율적이다. 따라서 대부분의 알고리즘에서는 근사적이지만 수용 가능한 이동거리를 결정하는 부정확 이동거리 탐색법(inexact line search method)이 사용되고 있다. 해당 탐색법은 강하함수에 대해서 특정 조건이 만족될 때까지 여러 다른 이동거리를 시도한다. 수용 가능한 이동거리를 결정하기 위해 시험 이동거리 순열을 아래와 같이 정의한다.
 

$$ \begin{align} t_j = \left(\mu\right)^j;~~~~j=0,1,2,\cdots \end{align}$$

 

   시험 이동거리 순열에서 µ=0.5가 대표적으로 사용되며, 기본 이동거리는 t₀=1로 시작한다. 강하함수에 대해서 강하조건이라고 부를 특정 조건이 만족되지 않으면 시험 이동거리는 이전 시험의 절반으로 줄어든다. 해당 과정은 강하조건이 만족될 때까지 계속한다.

 

2. 강하조건

   k번째 반복 단계에서 시험 이동거리에 대해 강하조건을 확인하기 위한 설계점은 아래와 같이 계산된다. 이때 사용되는 탐색방향 벡터는 현재 설계점에 대해서 이차계획문제를 풀이하여 구한 벡터이다.
 

$$ \begin{align} \mathbf{x}^{\left(k+1,j\right)} = \mathbf{x}^{\left(k\right)} + t_j \mathbf{d}^{\left(k\right)} \end{align}$$

 

   k번째 반복 단계에서 수용 가능한 이동거리, 즉 강하함수를 이용하여 아래에 나타낸 강하조건을 만족하는 이동거리는 α_k=t_j로 결정되는데, 이때 결정되는 이동거리는 강하조건을 만족하는 시험 이동거리 중에서 가장 큰 수이다. 이때 상수 γ는 0과 1 사이의 지정된 상수이다. 최적화 알고리즘의 매 반복마다 강하함수가 일정량만큼 감소해야 하므로, 강하조건은 수렴하는 알고리즘을 얻기 위해 매 반복마다 만족해야 하는 중요한 조건이다.

 

$$ \begin{align} \mathbf{\Phi} \left(\mathbf{x}^{\left(k+1,j\right)}\right) \leq \mathbf{\Phi} \left(\mathbf{x}^{\left(k\right)}\right) - t_j \gamma \left\| \mathbf{d^{\left(k\right)}} \right\|^2 \end{align}$$

 
   강하조건을 나타내는 부등식의 우변에서 시험 이동거리만이 유일한 변수이다. 그러나 시험 이동거리를 변경할 때마다 설계점 또한 변경되며, 이에 따라 목적함수와 제약조건 함수값도 새롭게 갱신되므로, 부등식 좌변의 강하함수 또한 새롭게 갱신된다. 실제 계산에서 강하조건 확인을 위해 다음과 같은 부등식 표현을 사용하기도 한다.
 

$$ \begin{align} \mathbf{\Phi} \left(\mathbf{x}^{\left(k+1,j\right)}\right) + t_j \gamma \left\| \mathbf{d}^{\left(k\right)} \right\|^2 \leq \mathbf{\Phi} \left(\mathbf{x}^{\left(k\right)}\right) \end{align}$$

 

3. 예제

   다음 비선형·제약조건 문제에 대해 초기 설계점 (40, 0.5)에서 탐색방향은 (25.798, 0.597), 벌칙인자는 43699.135, 강하함수는 32515.215로 계산되었다. 해당 단계에서 부정확 이동거리 탐색법을 적용하여 설계 변화량에 대한 이동거리를 계산해보자. 이때 상수 γ는 0.5로 선택한다. 
 

$$ \begin{align} \mathrm{minimize}~~~~&f = x_1^2 + 320x_1x_2 \\\\ \mathrm{subject~to}~~~~ &g_1 = \frac{1}{100}\left( x_1 - 60x_2\right) \leq 0 \\\\ &g_2 = 1 - \frac{x_1\left(x_1-x_2\right)}{3600} \leq 0 \\\\ &g_3 = -x_1 \leq 0 \\\\ &g_4 = -x_2 \leq 0 \end{align}$$

 

   기본 시험 이동거리 t₀=1을 시작으로 부정확 이동거리 탐색을 실시한다. 주어진 탐색방향에서 시험 설계점은 다음과 같이 계산된다.

 

$$ \begin{align} \mathbf{x}^{\left(1,0\right)} &= \mathbf{x}^{\left(0\right)} + t_0 \mathbf{d}^{\left(0\right)} \\\\ &= \begin{bmatrix} 40 \\ 0.5 \end{bmatrix} + 1 \times \begin{bmatrix} 25.798 \\ 0.597 \end{bmatrix} \\\\ &= \begin{bmatrix} 65.798 \\ 1.097 \end{bmatrix} \end{align}$$

 
   강하조건을 만족하는지 확인하기 위해 시험 설계점에 대해서 강하함수를 계산한다. 먼저 시험 설계점에 대해서 최대 제약조건 위배량 인자를 계산하면 다음과 같다.
 

$$ \begin{align} V\left(\mathbf{x}^{\left(1,0\right)}\right) &= \mathrm{max}\left\{ 0;~~g_1\left(\mathbf{x}^{\left(1,0\right)}\right),g_2\left(\mathbf{x}^{\left(1,0\right)}\right),g_3\left(\mathbf{x}^{\left(1,0\right)}\right),g_4\left(\mathbf{x}^{\left(1,0\right)}\right) \right\} \\\\ &= \mathrm{max}\left\{ 0;~~-0.0,-0.183,-65.798,-1.097\right\} \\\\ &= 0 \end{align}$$

 
   위 연산을 기반으로 시험 설계점에 대해서 강하함수를 계산하면 다음과 같다.
 

$$ \begin{align} \Phi \left( \mathbf{x}^{\left(1,0\right)} \right) &= f \left( \mathbf{x}^{\left(1,0\right)} \right) + RV \left( \mathbf{x}^{\left(1,0\right)} \right) \\\\ &= 27427 + 43699.135 \times 0 \\\\ &= 27427 \end{align}$$

 

   첫 번째 시험 설계점에 대해서 강하조건을 검토한다. 첫 번째 시험 설계점에서의 강하함수를 초기 설계점에서의 강하함수와 비교하였을 때 그 값이 감소하였으므로, 즉 강하조건을 만족하므로 해당 시험 이동거리 t₀=1는 수용 가능하다. 

 

$$ \begin{align} \mathbf{\Phi} \left(\mathbf{x}^{\left(1,0\right)}\right) + t_0 \gamma \left\| \mathbf{d}^{\left(0\right)} \right\|^2 &= 27427 + 1 \times 0.5 \times \left( 25.798^2 + 0.597^2 \right) \\\\ &= 27760 \\\\ &\leq \mathbf{\Phi} \left(\mathbf{x}^{\left(0\right)}\right) \\\\ &= 32515.215 \end{align}$$

 
   따라서 해당 단계에서의 이동거리는 다음과 같이 결정된다.
 

$$ \begin{align} \therefore~\alpha_0 = t_0 = 1 \end{align}$$

 
 
 
 
 

[함께 읽으면 좋은 페이지]

 

최적설계 | 비제약조건 문제 수치해법(3): 구간감소법

최적설계 | 제약조건 문제 수치해법(3): 순차 이차계획법 SQP

 

 

 

 

 

참고문헌
- Arora, J. S. (2016). Introduction to optimum design. Elsevier.