1. 최적 문제 (Optimal Problem) / 최적화 문제 (Optimization Problem)
ㅇ 제약조건 하에, 1 이상의 해답 후보들이 있고, 그 중에 최적 값(해)이 있는 문제
- 최적화 이란?
. 주어진 조건 (제약 조건) 하에, 최대의 효율성(최고의 성능)을 추구
. 즉, 일련의 제약식 하에, 최적 시스템을 발견해내는 설계 프로세스
2. 최적화 문제의 수학적 관점
ㅇ 변수의 어느 영역에서 함수의 극값(최대값/최소값 또는 극대값/극소값)을 구하는 문제
- 1 이상의 변수에 의존하는 함수의 극대 및 극소를 찾는 것
. f'(x) = 0 은 최적점(곡선 위의 평탄한 점)을 나타내며,
. f"(x) = 0 은 극소값(f"(x) > 0)인지 극대값(f"(x) < 0)인지를 나타냄
※ `근 구하기 문제`, `최적화 문제` 비교
- `근 구하기 문제`는, 함수 방정식의 근을 찾는 문제임
. 주로, 해석적 풀이 방식을 사용 (정확한 해를 찾음)
- `최적화 문제`는, 함수의 최소(최대) 값을 찾는 문제임
. 주로, 근사적 풀이 방식을 사용 (근사적 해를 찾음)
3. 최적화 문제의 응용
ㅇ 공학,경제,물리 등 많은 분야에서, 다양한 응용을 갖음
- 성능과 제약조건 간에 이해득실(상충관계)/균형을 따져야하는 수많은 설계 최적화 문제들이 있음
ㅇ 문제 例)
- 例1) 차량의 연료 소모를 최소화하는 이동 경로를 찾는 문제
- 例2) 가장 가까운 길을 찾는 문제
- 例3) 최소비용신장트리를 구하는 문제 등
- 주로, 원하는 목표(함수값을 최소화,최대화)를, 만족시키는 최적의 변수 값을 찾는 문제임
ㅇ 경영 과학에서 `최적화 문제`는,
- 때로는, `수학적 프로그래밍(Mathematical Programming)`이라고도 불리우며,
- 과학적 방법과 기술을 의사 결정 문제에 적용하고, 최상의 해결책을 제시하는 것을,
수학적으로 다루는 분야로써 연구됨
4. 최적화 문제의 표현
※ ☞ 최적화 문제 표현 참조
- 최적화 문제의 수학적 표현 및 필수 요소 셋 : (목적 함수, 결정 변수, 제약 조건)
. 최적화 문제 : 제약 조건 하에 목적 함수를 최소화(최대화)시키는 결정점을 찾는 것
. 목적 함수 : 최적화시키려는 대상
. 결정 변수 : 목적 함수에 극값을 가져다주는 변수 (파라미터)
. 제약 조건 : 해당 문제에 주어지는 제약
5. 최적화 문제의 구분
※ ☞ 최적화 문제 구분 참조
- 제약조건(구속조건) 존재 여부 : 비 구속 최적화 문제, 구속 최적화 문제
- 목적함수(비용함수) 및 제약조건(구속조건)이 선형적 여부
. 선형 프로그래밍 문제(선형계획법), 비선형 프로그래밍 문제
- 차원별 : 일차원/일변수 최적화 문제, 다차원/다변수 최적화 문제
6. 최적화 문제의 용어
※ ☞ 최적화 문제 용어 참조
- 최대값, 최소값, 극값, 극값의 성질을 나타내는 점, 목적함수, 결정변수, 제약조건/구속조건 등
7. 최적화 문제의 본질
ㅇ 결정 변수(파라미터)의 값과 위치를,
- (어느 방향으로 얼만큼) 조금씩 조금씩 변경해가며,
ㅇ 목적 함수를,
- 최적화 (더 이상 변경할 수 없는 지점까지) 시킬 수 있는, 파라미터를 찾아가려는 것
ㅇ 이때,
- 더 이상 최적화 시킬수 없는 지점을, Local Minima, Global Minima 라고 함
ㅇ 물론, 찾아가는 방법(기법)들이 많이 있지만,
- 대부분, 이동할 방향, 이동 크기에 대한 차이로 구분되어짐
8. 최적화 문제의 풀이가 가능한 알고리즘 전략들
ㅇ 욕심쟁이 방법
ㅇ 동적 계획법
ㅇ 백트래킹 등