최적화 관련 내용 정리

최적화: 주어진 제약조건 하에서 목적함수의 값을 최소 또는 최대로 하는 해를 구하는 문제.

현실 속에서 문제를 푸는 방법

1. 문제를 최적화 문제로 formulation
  상수, 변수, 제약조건, 목적함수를 통해 문제 구성

2. 알고리즘을 통한 해 구하기

3. 계산 결과를 분석, 검증

4. 최적화 문제와 알고리즘 재검토

 

어려운 문제를 부분 문제(subproblem)으로 나누거나 완화 문제(relaxation problem)으로 풀 수 있다. 

 

minimizer (최소자): 특정 최적화 문제에서 목적함수를 최소로 만드는 값

• 선형 계획 문제: 목적함수가 선형이고, 모든 제약조건이 선형 등식 혹은 부등식으로 나타낼 수 있는 최적화 문제
• 비선형 계획 문제: 목적함수나 제약 조건이 비선형함수로 나타난 문제 (2차함수 등)
• 조합 최적화 문제: 결정변수가 정수값, 또는 {0, 1}이라는 이산적인 값을 갖는 최적화 문제. 해의 집합이 순열이나 네트워크 같은 조합된 구조를 가진다. 
• 정수계획 문제: 모든 변수가 정수값을 갖는 선형 계획 문제
• 혼잡 정수 계획 문제: 일부 변수가 정수값을 갖는 선형 계획 문제
• 쌍대문제: 어떤 최적화 문제의 최적값에 대해서 좋은 상한을 구하는 문제. (dual problem)
• 주 문제: 쌍대 문제의 본래 문제 (primal problem)

 

쌍대정리

목적함수를 최대화하는 상황해서, 선형 계획 문제의 최적값의 좋은 상한을 구하는 문제는 목적함수를 최소화하는 쌍대문제로 변형할 수 있었다. 선형 계획 문제에 최적해가 존재한다면 그 쌍대 문제에도 최적해가 존재하고 일치한다.

Ball

open ball: 어떤 점을 중심으로 반지름이 $r$인 구의 내부를 의미. 반지름이 $r \ge 0$인 오픈볼의 표현은 다음과 같음

$$  B(x^*;r) = \{x \in \mathbb R^n: ||x-x^*|| < r \} $$

closed ball의 경우는 등호가 추가된 형태

$$  B(x^*;r) = \{x \in \mathbb R^n: ||x-x^*|| \le r \} $$

 

Point

극점 극대점, 극소점 : 함숫값이 국소적으로 최대, 최소인 점

임계점(critical point) : 모든 방향으로의 미분계수가 0인 점

안장점 (saddle point) : 임계점이지만 극점이 아닌점 즉,

a stationary point(정태점)  is a point on the surface of the graph where all its partial derivatives are zero

 

Upper bound (상계)

수열 $\mathbf a = (a_1, a_2, a_3, \dots)$가 주어졌을 때, 모든 (자연수) $n$에 대하여

$$ a_n \leq B $$

위를 만족시키는 실수 $B$가 존재하면 수열 $\mathbf a$를 위로 유계라 하고, $B$를 수열의 상계라고 부른다.

즉, 위로 경계가 존재한다는 뜻이고 상계는 상한 경계라는 뜻이다.

 

Supremum (the least upper bound)

상계 중에서 가장 작은 것을 최소상계 또는 상한이라고 부른다.