AI를 위한 필수 수학

456

AI

를 위한 필수 수학

그림

10-13

플레이어

1

의 최소 최대 문제의 쌍대 문제는 플레이어

2

의 최대 최소 문제와 같다.

제약 조건

,,yyy111

123

###

은 불필요하다. 모든

y

값은 음수가 아니며 그 합이

1

이기 때

문이다. 마찬가지로 제약 조건

,xx11

12

##

도 불필요하다. 이러한 상황은 선형 최적화 문제

를 공식화할 때 자주 발생한다.

원문제 또는 쌍대 문제를 풀면 각 플레이어의 최적 전략을 찾을 수 있다. 플레이어

1

이 첫 번째

행을

x

1

=

0

.

25

의 확률로, 두 번째 행을

x

2

=

0

.

75

의 확률로 선택하면 이때 기대 보수는

2

.

5

다.

이 전략을 사용할 경우 플레이어

1

은

2

.

5

이상을 잃지 않을 것으로 예상된다. 플레이어

2

가 첫

번째 열을

y

1

=

0

.

5

확률로, 세 번째 열을

y

3

=

0

.

5

확률로 선택하면 기대 보수는

2

.

5

다. 이 전략

으로 플레이어

2

는

2

.

5

이상의 이득을 얻을 것으로 예상된다.

선형 제약 조건이 있는 이차 함수의 최적화, 라그랑주 승수, 최소 최대 정리, 쌍대성

선형 제약 조건을 가진 이차 문제

quadratic

problem

는 깔끔한 구조를 가지고 있으며 다양한 응용 분

야에서 활용될 뿐만 아니라 최적화 개념들이 어떻게 상호 연결되는지 이해하는 데 많은 도움이

된다. 이차 문제는 다음과 같은 형태를 가진다. ...