AI를 위한 필수 수학

432

AI

를 위한 필수 수학

min cx

Ax b

$

$

v

v

v

v

Q

V

실행 가능한 집합

Ax b$

v

v

는 다면체

260

다. 이는 평평한 경계를 가진 유한 개의 반공간

half

-

space

의 교차점으로 생각할 수 있다. 이 다면체는 경계가 있거나 경계가 없을 수 있다. 곧 이에 대한

예시를 살펴보겠다.

표준형

standard

form

계산과 단체법, 내부점법과 같은 알고리즘 개발에 편리하다. 결정 변수는 음수가 될 수 없으므

로 모든 좌표가 음수가 아닌 제

1

사분면의 고차원 유사체인 제

1

하이퍼옥턴트

hyperoctant

에서만 최

적 해를 찾는다. 또한 제약 조건은 부등식이 아닌 항상 등식이어야 하며, 다면체의 내부가 아닌

경계에 있게 된다. 이는 표준형으로 작성된 선형 최적화 문제다.

min cx

Ax b

x 0

$

$

=

v

v

v

v

v

v

Q

V

표준형의 선형 문제를 직관적으로 이해하는 쉬운 방법이 있다. 바로 비용

cx$

v

v

Q

V

를 최소화하는

방식으로 행렬

A

의 열들로부터 벡터

b

v

를 합성하는 것이다.

일반형 선형 최적화 문제와 표준형 선형 최적화 문제 간의 변환은 매우 쉽다. 일반형 선형 최적

화 문제를 표준형으로 변환하기 위해서는 잉여 변수

surplus

variables

와 여유 변수

slack

variables

를 도입

해야 한다. 하지만 이 과정에서 차원이 달라진다는 점에 유의하자.

xx34

12

$