AI를 위한 필수 수학

461

Chapter 10 -

운용 과학

imum bbA

min cost f

A

2

1

t

1

$=

-

S

1-

vv

Q

V

또한 최적의 그림자 가격은 다음과 같다.

b

p

db

df

AA

t1

1

==

) -

-

S

v

v

v

Q

V

마지막으로 알아야 할 점은 고차원에서 안장점의 특성이다.

1

차원 제약 조건 문제의 경우 라

그랑주 함수(

x

v

와

p

v

의 함수)의

2

차 도함수가 한 변수에 대해서는 음수, 다른 변수에 대해서는

양수인 것이 특징이었다. 이에 대응하는 고차원 문제에서의 특징은 다음과 같다. 헤시안 행렬

Hessian

matrix

(

2

차 도함수 행렬 )의 고유값이 한 변수 집합에 대해서는 음수이고 다른 변수 집합에

대해서는 양수이므로 한 변수 집합에 대해서는 오목, 다른 변수 집합에 대해서는 볼록하다. 이

는 한 변수 집합에 대해서는 볼록하고 다른 변수 집합에 대해서는 오목한 고차원 목적 함수의

최적화 문제에도 적용되며, 해당 함수의 그래프가 안장점을 갖는다는 특징을 의미한다. 라그랑

주 함수의 경우 안장점은 제약 조건 문제의 최솟값을 갖는 지점과 정확히 일치한다.

운용 과학 분야에서 널리 사용되는 선형 제약 조건이 있는 선형 최적화 문제에도 적용될까? 그

답은 ‘예’다. 단, 문제 내의 모든 계수 부호가 올바른 경우에만 적용할 수 있다. 앞서 살펴본 최

대 흐름 최소 절단 문제와

2

인 제로섬 게임의