AI를 위한 필수 수학

436

AI

를 위한 필수 수학

이제 구간별 선형 볼록 목적 함수를 가진 최적화 문제를 선형 최적화 문제로 재구성할 수 있다.

min cx

Ax b

x 0

$

$

=

v

v

v

v

v

v

Q

V

min max minmx d

Axb i i i zmxd

Ax b

i

i

z

)$ +

$$$

$

+

Q

V

min min min

c x cz c x x

,

Ax b

ii

i

n

Ax b

zx

zx

ii

i

n

Ax Ax b

xx

ii i

i

n

11

0

1

ii

ii

)) +

$$

$

$

$

$

=

-

=

-

+-

=

+-

+-

TT

Q

Y

V

Y

// /

새로운 결정 변수

z

를 추가했을 때 차원이 증가했음에 유의하자.

예를 들어 절댓값 함수

,maxfx x x x== -

Q

V

E

H

는 구간별 선형 함수이자 볼록 함수다. 목

적 함수에 결정 변수의 절댓값이 포함된 최적화 문제를 다음 두 가지 방법으로 선형 최적화 문

제로 재구성할 수 있다 (단, 목적 함수의 계수

c

i

는 음수가 아닌 값이어야 한다. 그렇지 않으면

목적 함수가 볼록 함수가 아닐 수 있다 ).

10.7.4

선형 최적화의 기하학적 구조

선형 최적화 문제에서의 기하학적 구조를 표준형으로 생각해보자. 표준형은 최솟값을 찾는 알

고리즘에서 가장 활용하기 쉬운 형태이기 때문이다. 기하학은 도형, 선, 평면, 점, 모서리, 꼭짓

점 등을 다룬다. 표준형의 선형 최적화 문제는 다음과 같다.

표준형의 문제는 선형 대수 방정식을 포함한다. 여기서는 최소화 ...