정적 최적화 Static Optimization

본 글은 Frank Lewis 의 책 Optimal Control 3rd Ed.를 공부하며 작성한 글입니다.

 

비구속 최적화 Optimization without Constraints

스칼라 값으로 정의한 성능 지표(Performance Index) $L(u)$는 control 혹은 decision vector $u \in \mathbb{R}^m$의 함수이다. 제어 벡터 $u$를 이용하여 성능 지표 $L(u)$을 최소화하고자 한다.

최적화 문제를 풀고자 성능 지표에 대한 테일러 급수를 전개하면 다음과 같다.

$$dL = L_u^T du + \frac{1}{2} du^T L_{uu} du + \mathcal{O}(3)$$

$L_u$는 제어 벡터에 대한 성능 지표의 기울기(Gradient) 열 벡터 이며, $L_{uu}$는 헤세 행렬(Hessian matrix)이다. $L_{uu}$는 curvature matrix라고도 부른다.

임계점 혹은 정점 (Critical 혹은 Stationary point)는 제어 벡터에 대해서 증분 $dL$이 0인 지점이다. 임계점에서는 $L_u = 0$이며, 임계점이 지역 최소점(Local minimum)이기 위해서, curvature matrix는 양의 정정행렬, $L_{uu} > $이다.

$L_{uu}$가 음의 정정 행렬(Negative definite)이면 지역 최대점, 부정부호(indefinite)라면 안장점(Saddle point)이다. 준정부호(Semi-definite)라면 좀 더 알아봐서 임계점의 종류를 판별해야한다.

참고로 Critical point는 미분 불가능한 점"이거나" $f'(x)=0$인 점이며, Stationary point는 미분 가능"하면서" $f'(x)=0$인 점이다.

구속 최적화 Optimization with Constraints

제어 벡터 $u \in \mathbb{R}^m$, 상태 벡터 $x \in \mathbb{R}^n$에 대한 성능 지표 $L(x,u)$에 대해 정의하자. 구속 최적화 문제는 다음의 구속 조건 constraint equation을 만족하면서 성능 지표 $L(x,u)$를 최소화 하는 제어 벡터 $u$를 결정하는 방법이다.

$$f(x,u) = 0$$

구속 조건을 만족하는 지역 최소점을 위한 필요 충분 조건을 찾고자, 3가지 관점을 고려하면서 직관을 얻어보자.

 

라그랑지 승수와 해밀토니언 Lagrange Multipliers and the Hamiltonian

필요 조건 Neccessary Conditions

Stationary point에서, $df=0$일 때 1차 근사인 $dL=0$이다. (1)

$$\cases{dL = L_u^T du + L_x ^T dx = 0 \\ df = f_u du + f_x dx = 0}$$

위 식으로부터 자코비 행렬 $f_x$가 정칙(nonsingular)이라면, 다음과 같이 쓸 수 있다. (2)

$$dx = -f_x^{-1} f_u du  \rightarrow dL=\left(L_u^T - L_x^T f_x^{-1} f_u \right) du$$

$du$를 이항하여 정리하면 다음과 같다. (3)

$$\left. \frac{\partial L}{\partial u} \right|_{df = 0} = \left( L_u^T - L_x^T f_x^{-1} f_u \right)^T = L_u - f_u^T f_x^{-T} L_x $$

1차 근사가 0이여야 하므로, minimum을 위한 필요 조건은 다음과 같이 정리된다. (4)

$$L_u - f_u^T f_x^{-T} L_x = 0$$

 

---

 

충분 조건을 찾기 전에, 두 가지 방법으로 식을 조사해보면 식 (1.2-1)으로부터 대수 방정식을 정리할 수 있다.

$$\left[ \matrix{dL \\ df } \right] = \left[ \matrix{ L_x^T & L_u^T \\ f_x & f_u } \right] \left[ \matrix{ dx \\ du} \right] = 0$$

위 선형 방정식의 집합은 stationary point을 정의하며, 반드시 $dx, du$에 대한 해를 가진다. Critical point 는 가운데의 $(n+1)\times (n+m)$ 계수 행렬이 $n+1$보다 작은 rank를 가지면 얻을 수 있다. 이 말인 즉슨, 열이 반드시 선형 종속적(Linearly dependent)이기 때문에, 다음을 만족하는 벡터 $\lambda \in \mathbb{R}^n$이 존재한다. (5)

$$\left[ \matrix{1 & \lambda^T} \right] \left[ \matrix{L_x^T & L_u^T \\ f_x & f_u } \right] = 0$$

식으로부터, 다음을 얻을 수 있다. (6)

$$\lambda^T = -L_x^T f_x^{-1}$$

위의 $\lambda$를 라그랑지 승수 Lagrange multiplier라 한다. 추가적인 의미를 더 뽑고자, 식 (1)에 $du=0$이라 하면

$$\left. \frac{\partial L}{\partial f} \right|_{du = 0} = \left( L_x^T f_x^{-1} \right)^T = - \lambda$$

이는 제어 벡터가 일정할 때, 구속 조건의 변화에 따른 성능 지표의 영향을 보여준다.

 

식 4로부터 분석에 사용할 접근 방법을 진행시켜보자. 해밀토니안 Hamiltonian 함수를 정의하기 위해 성능 지표에 구속조건을 포함해보자. (7)

$$H(x,u,\lambda) = L(x,u)+ \lambda^T f(x,u) $$

여기서 $\lambda \in \mathbb{R}^n$은 아직 결정되지 않은 Lagrange multiplier이다. critical point에 이르는 $x, u, \lambda$를 결정하기 위해 다음을 진행한다. (8)

$$dH = H_x^T dx + H_u^T du + H_\lambda^T d\lambda$$

참고로 $H_\lambda = f(x,u)$ 이다.

그래서 $H_\lambda=0$인 제어 벡터 $u$를 선택하면 구속조건 $f(x,u)=0$으로부터 상태 벡터 $x$가 결정된다. 이 상황에서 Hamiltonian은 성능 지표와 같다. (9)

$$\left. H \right|_{f=0} =L$$

그리고 $f=0$이라면 식 2와 같이 $dx$를 $du$에 대해 구할 수 있다. 그러면 둘의 관계에 대해서 설명하지 않아도 되며, 다음을 만족하는 Lagrange multiplier $\lambda$를 선택하자. (10)

$$H_x = 0$$

그렇다면 식 (8)의 증분 $dx$는 더이상 $dH$에 영향을 주지 않는다. 참고로 다음과 같은 식으로부터 $\lambda$가 값을 가지게 된다. (11)

$$\frac{\partial H}{\partial x} =L_x + f_x^T \lambda =0$$

위의 식 (9)와 (11)으로부터 (12)

$$dL = dH + H_u^T du$$

$H=L$이기 때문에, stationary point가 되려면 결국은 다음과 같은 stationary condition 을 적용해야한다. (13)

$$H_u = 0$$

요약하면 구속 조건 $f(x,u)$를 만족하는 성능 지표 $L(x,u)$의 최소점을 위한 필요 조건은 다음과 같다. (14)

$$\cases{ \frac{\partial H}{\partial \lambda} = f & = 0 \\ \frac{\partial H}{\partial x} = L_x + f_x^T \lambda & = 0 \\ \frac{\partial H}{\partial u} = L_u + f_u^T \lambda & = 0 } $$

위 식으로부터 $x, u, \lambda$를 결정할 수 있다. 대부분 $\lambda$의 값이 관심사는 아니지만, 관심사인 $x, u, L$을 결정하는데 필요하다.

라그랑지 승수법 Lagrange Multipliers Method의 유용성은 다음과 같이 요약할 수 있다.

1. 실제로 $dx$와 $du$는 독립적인 증분이 아니지만, 결정되지 않은 multiplier $\lambda$를 도입함으로써 추가의 자유도를 확보할 수 있으며, 증분들이 독립적인 것 마냥 $dx$와 $du$를 만드는 $\lambda$를 선택할 수 있다. 그러므로, 독립적으로 $H$의 기울기를 0으로 만듦으로써 critical point를 구할 수 있다.
2. 그리고 Lagrange multiplier를 도입함으로써 구속 조건 $f(x,u)=0$를 만족하는 $L(x,u)$ 최소화 문제를 구속조건이 없는 해밀토니언 $H(x,u,\lambda)$를 최소화 하는 문제로 바꿀 수 있다.

---

 

충분 조건 Sufficient Conditions

식 (14)는 Stationary(Critical) point를 결정한다. 이제 "이 점이 최소인가"를 보장할 필요가 있다.

(15)

(16)

최소에 대한 충분 조건을 찾으려면, 2차 항을 분석해봐야한다.

 첫번째로, 위 식에 $du$에 대한 $dx$의 종속성을 포함할 필요가 있다. 그리고 $H_x=0$, $H_u=0$, $df=0$인 critical point 를 찾았다고 하자. 그러면 (17)

$$dx = -f_x^{-1} f_u du + \mathcal{O}(2)$$

$$dL = \frac{1}{2} du^T \left[ \matrix{-f_u^T f_x^{-T} & 1} \right] \left[ \matrix{H_{xx} & H_{xu} \\ H_{ux} & H_{uu}} \right] \left[ \matrix{-f_x^{-1} f_u \\ I } \right] du + \mathcal{O}(3) $$

최소임을 확신하려면, 모든 증분 $du$에 대해서 $dL$은 항상 양수여야한다.

만약 curvature matrix with constant $f$ 가 0과 같다면 이를 보장한다. (18)

$$L_{uu}^f \equiv \left[ \matrix{-f_u^T f_x^{-T} & 1} \right] \left[ \matrix{H_{xx} & H_{xu} \\ H_{ux} & H_{uu}} \right] \left[ \matrix{-f_x^{-1} f_u \\ I } \right] >0 $$

$$L_{uu}^f = H_{uu} - f_u^T f_x^{-T} H_{xu} - H_{ux} f_x^{-1} f_u + f_u^T f_x^{-T} H_{xx} f_x^{-1} f_u$$

 

선형 구속 조건을 가지는 2차 성능 지표

다음 2차 성능 지표를 보자. (20)

$$L(x,u) = \frac{1}{2} x^T Q x + \frac{1}{2} u^T R u$$

선형 구속 조건은 다음과 같다. (21)

$$f(x,u) = x + Bu+ c =0$$

위를 Static Linear Quadratic Problem (LQ) 문제라고 한다.

해밀토니언 $H$은 다음과 같다. (22)

$$H= \frac{1}{2} x^T Q x + \frac{1}{2} u^T R u + \lambda^T \left( x + Bu+ c =0 \right) $$

Stationary point를 위한 조건은 다음과 같다.

$$\cases{ \frac{\partial H}{\partial \lambda}= x + Bu+ c &= 0 \\ \frac{\partial H}{\partial x } = Qx+ \lambda &= 0 \\ \frac{\partial H}{\partial u} = Ru + B^T \lambda &= 0 } $$

위 문제를 풀고자 정리를 하면

$$u=-R^{-1} B^T \lambda$$

$$\lambda=-Qx$$

$$\lambda=Q\left( Bu+c \right)$$

$$u=R^{-1}B^T Q \left( Bu + c \right)$$

위로부터 정리하면 (23)

$$u = - \left( R+B^T QB \right)^{-1} B^T Qc$$

$$x= - \left( I - B\left( R+B^T QB \right)^{-1} B^T Q \right) c$$

$$\lambda = \left(Q - QB\left( R+B^T QB \right)^{-1} B^T Q \right) c = \left(Q^{-1}+BR^{-1} B^T \right)^{-1} c$$

식 (23)의 제어 벡터으로부터 최소임을 검증하기 위해, 식 (18)의 constrainted curvature matrix 를 결정하자.(24)

$$L_{uu}^f = R+B^T Q B$$

$R,Q>0$이므로 $L_{uu}^f>0$이다.

최적 값 $L^*$는 다음과 같다. (25)

$$L^* = \frac{1}{2} x^T \left( Q + QBR^{-T} R R^{-1} B^T Q \right) x $$

$$L^* = \frac{1}{2} x^T \left( Q + QBR^{-1} B^T Q \right) x $$

$$L^* = \frac{1}{2} x^T Q^T \left( Q^{-T} + BR^{-1} B^T  \right) Qx $$

$x$에 대한 $\lambda$ 식으로부터

$$L^* = \frac{1}{2} c^T \left( \cdot \right)^{-1} \left( \cdot \right) Qx $$

$$L^* = \frac{1}{2} c^T \left( \cdot \right)^{-1} \left( \cdot \right) \lambda $$

$$L^* = \frac{1}{2} c^T \lambda $$

 

 

 

끝.

---

[1] Lewis F. L., Vrabie D. L. and Syrmos V, L., Optimal Control, 3rd ed., Wiley, 2012.