[Linear Algebra] 제한된 최적화(constrained optimization)

제한된 최적화(constrained optimization)

관련된 내용

• 이차형식(Quadratic forms)
• 이차형식의 부호

이차 형식의 변수 x에 대해 극대값 또는 극소값을 찾을 수 있습니다. 이를 위해서는 변수벡터 x를 단위 벡터로 전환하는 것으로 시작합니다.

ℝⁿ 차원의 벡터 x가 단위 벡터라면 식 1이 성립합니다.

$$\tag{식 1}‖x‖= 1 →‖x^2‖= 1 ↔ x^Tx = 1$$

예 1)

제한 조건 $x^Tx = 1$에서의 $Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2$의 극대값과 극소값을 결정합니다.

제한 조건 $x^Tx = 1$를 나타내면 다음과 같습니다.

x1, x2,x3=symbols("x1 x2 x3")
x=Matrix(3, 1, [x1, x2, x3])
print(np.array(x))

[[x1]
 [x2]
 [x3]]

xTx=x.T*x
eq=Eq(xTx[0], 1)
eq

x12 + x22 + x32 = 1

식 2는 $x_1$이 최대인 경우 Q(x)가 최대이며 $x_3$가 최대인 경우 Q(x)의 최소임를 나타냅니다.

\begin{align}\tag{식 2} x = [1, 0, 0] & → Q(x) ≤ 9 \\x = [0, 0, 1] &→ Q(x) ≥ 3\end{align}

Q(x)는 식3과 같이 2차식 행렬로 나타낼 수 있습니다.

\begin{align}\tag{식 3}Q(x)&=x^TAx \\ & = \begin{bmatrix} x_1& x_2& x_3\end{bmatrix} \begin{bmatrix} 9& 0& 0\\0& 4& 0\\0& 0& 3\end{bmatrix}\begin{bmatrix}x_1\\ x_2\\ x_3 \end{bmatrix}\end{align}

위 행렬 A의 부호를 결정하기 위해 고유값을 확인합니다.

A=np.array([[9,0,0],[0,4,0],[0,0,3]])
d, P=la.eig(A)
print(d)

[9. 4. 3.]

모든 고유값이 양수이므로 행렬 A는 양의 정부호 행렬입니다. 즉, Q(x) > 0입니다. 또한 이 행렬의 고유행렬은 정규직교행렬입니다.

print(np.isclose(P.T, la.inv(P)))

[[ True  True  True]
 [ True  True  True]
 [ True  True  True]]

행렬의 고유벡터와 고유값 사이에 식 4가 성립합니다.

\begin{align}Ax& = λx\\ x^TAx& = λx^Tx\\\tag{식 4} Q(x)& = λx^{-1}x\\& = λ\\∵\;& x^Tx = 1\end{align}

결과적으로 이차식을 나타내는 행렬 A의 변수의 범위가 고유벡터내에서 존재하는 조건에서 최대와 최소는 고유값으로 결정할 수 있습니다. 이 예의 경우 A의 고유값 중의 최대와 최소는 각각 9와 3으로 위에서 계산한 값과 같습니다.

예 2)

위 예에서 이차식의 최대값을 나타내는 단위 고유 벡터 u1 이라고 하면 x ^Tu1 = 0의 제약 조건을 첨가할 경우 극대값을 계산해 봅니다

u1=P[:,0]
print(u1)

[1. 0. 0.]

Eq((x.T*Matrix(u1))[0], 0)

1.0x1=0

즉, 조건은 첫번째 최대에 대응하는 항이 0이 되는 것으로 최대값은 두번째로 큰 고유값이 됩니다.

x1, 0
eq=x.T*A*x
eq[0].subs(x1, 0)

4x22+3x32

제한된 최대와 최소

대칭 행렬 A의 가장 크고 작은 고유값이 각각 M과 m이고 x^Tx = 1의 제한 조건에서 A의 최대와 최소값은 각각 M과 m이 됩니다.

행렬 A의 특정한 고유값에 대응하는 고유벡터가 0이 되는 변수의 조건은 그에 대응하는 고유값이 제거됨을 의미합니다. 즉, 제일 큰 고유벡터 u₁의 조건 x^Tu₁ = 0은 u1에 대응하는 고유값을 제외합니다.