Optimization Methods in Finance Chapter 2.1-2.2

 

2.1 The Linear Programming Problem

일반적인 형태의 선형 계획 문제 

선형 계획 문제는 선형 목적 함수를 선형 등식 및 부등식 제약 조건 하에서 최적화하는 문제로, 일반적인 형태는 다음과 같다:

 

여기서:

• C : 목적 함수의 계수 벡터.
• X : 최적화하려는 변수 벡터다.
• ai^Tx=bi​ : 등식 제약 조건의 집합.
• ai^Tx≥bi : 부등식 제약 조건의 집합.
• E와 I는 각각 등식과 부등식 제약 조건의 인덱스 집합.

표준 형태의 선형 계획 문제 (2.2)

선형 계획 문제는 단순화된 표준 형태로 표현될 수 있으며, 이는 다음과 같다:

여기서:

• A : 행렬, b는 상수 벡터.
• x≥0 : 모든 변수 x가 0 이상이어야 함을 의미.

여기서 개인적인 궁금증...

• c^T 가 도대체 뭘까??

전공 때도 LP를 배웠는데 목적함수의 모양이 내가 아는 것과 다르다. 그래서 알아보았다

-> c^T는 벡터의 전치(transpose)를 나타낸다. c는 벡터이고, c^T는 그 벡터를 전치(transpose)하여 행 벡터로 만든 것이다.

 

그게 모니??

그러니까..

• c와 x는 각각 벡터이다.
• c가 n-차원 열 벡터(column vector)라고 할 때, c^T는 같은 벡터를 전치하여 행 벡터(row vector)로 만든 것이다.
• 전치된 벡터 c^T와 x를 곱하면, 두 벡터의 내적(inner product)을 구하게 되어 스칼라(숫자) 값이 된다.

즉, c^Tx는 벡터 c와 x의 요소별 곱을 모두 더한 값이다. 수식으로 나타내면 다음과 같다:

 

이제 내가 아는 형태가 나왔다. 결국 같은 의미였다.

 

예시)

불등식을 등식으로 변환하는 방법

불등식 제약 조건을 비음수로 제한된 여유 변수(slack 또는 surplus 변수)를 도입하여 등식으로 변환할 수 있다.

위의 제약 조건이 불등식으로 이루어져있다. 이때 여유 변수를 도입하여 아래 식으로 만들 수 있다.

2.2 Duality

선형 프로그래밍 문제에서 최적해를 찾는 방법

 

본 문제를 다시 풀어보자

 

이 중 마지막 해 (x1,x2,x3,x4)=(5,2,0,0)가 가장 작은 목표 값을 가지므로, 주어진 해들 중 최선의 해로 보인다. 하지만 이 해가 최적해인지 확인하기 위해서는 더 낮은 목표 값을 가질 수 있는 다른 실행 가능 해가 존재하지 않음을 입증해야 한다.

 

이를 위해 제약 조건을 사용하여 목표 함수의 값에 하한을 설정할 수 있다. 예를 들어, 모든 실행 가능 해에 대해 다음과 같은 제약 조건이 성립해야 한다: 

 

첫 번째 제약 조건을 사용한 하한 추정:

• 위 식은 첫 번째 제약 조건인 2x1+x2+x3=12을 목표 함수 −x1−x2에 적용하는 과정이다.
• 목표 함수에 대해, x1과 x2​는 음수 계수를 가지고 있기 때문에, 이들의 계수를 최소화하는 것이 목적이다.
• 하지만, x3는 목표 함수에 직접 포함되는 것이 아니기 때문에, 이 변수의 값을 최소화(가능한 경우 0으로 설정)하여 x1과 x2​의 영향을 최대한 감소시키는 것이 목표이다.
• 위 부등식은 x1​, x2​, x3​ 값이 모두 0 이상일 때 성립한다.

 

두 번째 제약 조건을 사용한 더 나은 하한 추정:

• 첫 번째 제약조건과 마찬가지로 두 번째 제약 조건 x1+2x2+x4=9을 사용하여 하한을 더욱 개선한다.
• 이 경우에도 x4x4​는 목표 함수에 직접적으로 포함되지 않으므로, 이 변수의 값을 최소화(가능한 경우 0으로 설정)하여 x1x1​과 x2x2​의 영향을 최대한 감소시키는 것이 목표입니다.
• 이를 통해 −x1−x2≥−x1−2x2−x4=−9−x1​−x2​≥−x1​−2x2​−x4​=−9라는 더 강한 부등식을 도출할 수 있습니다.

 

더 나은 하한의 의미

• -9와 -12의 비교: 수치적으로 −9는 −12보다 큰 값이다. 이 경우, −9가 −12보다 "덜 음수"라는 것을 의미합니다. 따라서, −9는 −12보다 목표 값으로서 더 높은 하한을 설정한다. 이는 실제 목표 함수의 최소 가능한 값이 −9 이하로 떨어질 수 없다는 것을 의미하고, 이는 −12보다 더 강한 제약을 가하는 것이다.
• 하한의 역할: 하한이 더 높다는 것은 목표 함수가 그 하한보다 낮은 값을 취할 수 없다는 것을 의미한다. 즉, −9라는 하한은 해가 −9보다 작은 어떤 값을 (예: −10, −11, −12 등) 가질 수 없다는 것을 의미합니다. 반면 −12라는 하한은 목표 함수의 값이 −12 이하로 떨어질 수 있어 -9보다 떨어질 여지를 더 많이 준다.
• 문제의 제약과 최적화: 더 높은 하한을 제공하는 제약 조건은 문제의 해 공간을 더 효과적으로 제한한다. 이는 해가 더 제한된 범위 내에서만 탐색되어야 함을 의미하며, 이는 최적화 과정에서 계산 효율성을 증가시키고, 더 정확하게 최적해를 추정할 수 있게 도와준다.

선형 프로그래밍 문제의 제약 조건을 이용하여 목표 함수의 최소 가능 값을 추정

 

1단계: 제약 조건을 목표 함수와 관련하여 조정

• 제약 조건 1에서 x3의 계수를 -1/3​로 조정하여 더하면: 

• 제약 조건 2에서 x4의 계수를 −1/3​로 조정하여 더하면:

2단계: 두 조정된 제약 조건을 결합

• 두 식을 결합하면:

3단계: 제약 조건의 원래 값 적용

• 제약 조건 1과 2를 사용하여 x3과 x4​를 제거한다:

4단계: 하한 값 계산

최종적으로 식을 단순화하여 목표 함수의 하한을 계산한다:

 

이제 이중화 과정에 대해 설명한다

이중화 과정:

이중화 과정에서는 주어진 선형 프로그래밍 문제의 제약 조건들을 활용하여 목표 함수의 하한을 찾는 전략을 개발합니다. 이를 위해 각 제약 조건에 특정 가중치 (여기서는 y1​ 및 y2​)를 적용하고, 이 가중치들을 사용하여 조합된 식에서 목표 함수의 계수에 해당하는 하한을 설정한다.

 

계산 과정:

1. 가중치 적용: y1과 y2​를 각 제약 조건에 적용하여, 목표 함수 −x1​−x2​의 계수를 모델링한다. 이 과정에서는 목표 함수의 계수가 각 변수에 대해 최소한으로 구성될 수 있도록 조정한다.
2. 최적 가중치 찾기: 최적의 결과를 얻기 위해 y1과 y2​를 선택하는 과정이다. 이들은 각각의 제약 조건의 오른쪽 항 (여기서는 12와 9)과 결합하여 최대 값을 생성할 수 있는 조합을 형성한다. 목적은 12y1+9y2를 최대화하는 것이다.

이중 문제 (Dual Problem):

이중 문제는 원래 문제의 제약 조건과 목표 함수에 대한 대안적 접근을 제공합니다. 이중 문제의 형태는 다음과 같습니다:

• 최대화 문제:

• 제약 조건:

• 여기서 y는 제약 조건의 가중치, b는 원 문제의 제약 조건의 오른쪽 항, A는 원 문제의 계수 행렬, c는 목표 함수의 계수를 나타낸다.

약한 이중성 정리 (Weak Duality Theorem):

이 정리에 따르면, 원 문제 (primal problem)의 어떤 실행 가능한 해의 목표 함수 값은 해당 이중 문제 (dual problem)의 어떤 실행 가능한 해의 목표 함수 값보다 항상 크거나 같다. 즉, 이중 문제의 해는 원 문제의 해보다 목표 값이 더 크거나 같은 하한을 제공한다.

 

이에 대한 증명은 생략한다