1. 볼록 최적화 (Convex Optimization)
실수 공간 에서 정의된 함수인 볼록함수 과 아핀 함수 에 대해
Convex Optimization Problem은 다음과 같이 정의한다.
•
: Optimization Variables(Decision Variables)
•
: Object function(목적 함수)
•
: 부등식 제약 조건(Inequality Constraint Function)
•
: 등식 제약 조건(Equality Constraint Function)
볼록 최적화 문제에서의 optimal solution(최적해) 는 제약조건을 모두 만족하는 집합(Constraint Set)에서 목적 함수(Objective Function) 값이 최소가 되는 해를 구하는 것이다.
2. 제약 조건이 없는 최적화
제약조건이 없는 최적화 문제는 목적함수의 값을 최적화(최대화 혹은 최소화)하는 변수 조합을 찾는 문제이다.
목적함수의 기울기(gradient)를 이용해서 변수의 변화량에 따라 목적함수 값이 어떻게 달라지는지 정량적으로 파악할 수 있고, 최소화 문제의 경우, 함수값이 감소하는 기울기 방향으로 이동하면서 최적해를 구할 수 있다.
2.1 최적화 문제에서 고려해야할 것
1.
이동방향(Gradient) : 어느 방향으로 내려갈 것인가?
2.
이동크기(Step size): 한 번에 얼만 큼 이동할 것인가?
→ 그래디언트와 헤시안 행렬을 사용해서 이동방향, 이동크기를 결정
2.2 제약 조건이 없는 최적화 문제에서의 최적화 필요조건
1. 최적성 1차 필요조건 (FONC, First Order Necessary Condition)
미분가능한 함수 에 대한 최적화 문제
minimize 에서 점 가 local minimum 이면 ▽ 이 성립한다.
•
FONC가 점 가 local minimum일 충분조건은 아니다.
→ ▽ 을 만족하는 모든 점 를 제약조건이 없는 최적화 문제에서 정류점이라고 한다.
◦
목적 함수 f 가 convex 함수라면, 제약조건이 없는 최적화 문제에서 정류점 는 global optimum(전역 최적해)이다.
2. 최적성 2차 필요조건 (SONC, Second Order Necessary Condition)
두 번 미분가능한 함수 에 대한 최적화 문제
minimize 에서 점 가 local minimum 이면 (양의 준정부호 행렬, PSD)이 성립한다.
3. 최적성 2차 충분조건
두 번 미분가능한 함수 에 대한 최적화 문제
minimize 에서 점 가 local minimum이 되기 위한 충분조건은 (양의 정부호 행렬, PD)이다.
4. 최적성 2차 필요조건 vs 2차 충분조건
1.
점 에서 2차 필요조건을 만족한다고 해도 항상 해당 점이 국소 최적해는 아니다.
2.
최적성 2차 충분 조건을 만족하지 않는 국소 최적해가 존재할 수도 있다.
그럼 제약 조건이 없는 최적화 문제에서 국소점(local minimum)이 갖는 특징은 무엇일까?
제약 조건이 없는 최적화 문제의 국소 최적해 는
1.
FONC, SONC 필요조건을 반드시 만족한다.
→ 하지만, 이 두 조건은 필요조건이기 때문에 이 둘을 만족하는 모든 점이 모두 국소 최적해는 아님.
2.
대부분의 최적화 문제에서 국소 최적해가 전역최 적해이지만, 항상 국소 최적해가 전역최적해인 것은 아니다.
2. 제약 조건이 없는 볼록최적화
볼록함수인 목적함수에 대한 제약조건이 없는 볼록 최적화 문제가 정의되었을 때의 최적조건(Optimality Condition)에 대해 알아보자.
정리 1. 볼록최적화 문제 제약조건을 만족하는 가 최적해일 필요충분조건
볼록 최적화 문제의 제약조건을 만족하는 x의 집합을 다음과 같은 X라 하자.
{ }
이때 가 볼록최적화 문제의 해일 필요충분분조건은
, 임의의 에 대해 이다.
정리 2. 가 제약조건이 없는 볼록최적화 문제의 해일 필요충분조건
제약조건이 없는 볼록최적화 문제 minimize 의 최적해 는 의 해이다.
제약조건이 없는 볼록 최적화 문제에 대해 임의의 y 에 대해서 (정리1) 이 성립하려면 (정리2)이 우선적으로 성립해야한다.
