5장. 최적화

5 장. 최적화 박창이 서울시립대학교통계학과 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 1 / 57

학습내용 기초이론제약없는최적화제약있는최적화통계학에서제약최적화문제 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 2 / 57

기초이론 : 일변수함수 I 정리 5.1 ( 중간값정리 ). 함수 f 는구간 [a, b] 에서연속이며실함수라고하자. f (a) < f (b) 이라면 f (a) < c < f (b) 인모든실수 c 에대해 f (x) = c 를 만족하는실수 x (a, b) 가존재한다. 정의 5.1. 정의구역 (a, b) R 1 에서정의된실함수 f 에대해실수 m 이존재하여 f (x + h) f (x) mh lim = 0 h 0 h 일경우 f 는점 x 에서미분가능하다고하며 f (x) = m 으로쓴다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 3 / 57

기초이론 : 일변수함수 II 정의 5.2 ( 근방 ). 양수 ɛ 에대해 a R 의 ɛ- 근방 (neighborhood) 은 로정의된다. N ɛ (a) = {x : x a < ɛ, x R} 정리 5.2 ( 테일러정리 ). 주어진자연수 k 에대하여함수 f 는 x = a 의근방에서 (k + 1) 차도함수를갖는다고하자. p k (x) = f (a) + f (a)(x a) + f (a) 2! 이면 (x a) 2 + + f (k) (a) (x a) k k! f (x) = p k (x) + f (k+1) (c) (x a)k+1 (k + 1)! 이며 x c < x a 인 c 가존재한다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 4 / 57

기초이론 : 일변수함수 III 정의 5.3 ( 함수공간 C k (a, b)). k차도함수 f (k) 가구간 [a, b] 에서연속일경우 f 는 k번연속적으로미분가능하다고하고, 이러한 k 번연속적으로미분가능한 (continuously differentiable) 함수들의집합을 C k (a, b) 으로나타낸다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 5 / 57

기초이론 : 일변수함수 IV 정의 5.4 ( 국소최소점 ). f 는구간 (a, b) R에서정의된실함수라고할때 f (x ) f (x) 단 x (a, b) N ɛ (x ) (1) 을만족시키는 ɛ > 0이존재하는경우 f (x ) 를국소최소 (local minimum) 라하고 x 를국소최소점 (local minimum point) 이라고한다. 한편 (1) 에서 f (x ) f (x) 이라면 f (x ) 를국소최대 (local maximum) 라하고 x 를국소최대점 (local maximum point) 이라부른다. 정리 5.3. f C 2 (a, b) 를가정하자. 만일 x 이국소최소점이면 f (x ) = 0이고 f (x ) 0이다. 만약 f (x ) = 0이고 f (x ) > 0 이면 x 는국소최소점이다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 6 / 57

기초이론 : 일변수함수 V 예 5.1. 구간 ( 1, 1) 에서정의된함수 f (x) = x 3 를고려 f (x) = 0이지만 x = 0는 f 에대한극소점이아님극소점을보장하기위해서는 f (x ) > 0라는조건을확인 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 7 / 57

기초이론 : 다변수함수 I 정의 5.5 ( 근방 ). 양수 ɛ에대해 a R p 의 ɛ-근방 (neighborhood) 은 N ɛ (a) = {x R p : x a < ɛ} 로정의된다. 정의 5.6 ( 국소최소값 ). f 는열린집합 (open set) V R p 에서정의된함수라고할때 f (x ) f (x) 단 x V N ɛ (x ) (2) 을만족하는양수 ɛ이존재하면 f (x ) 를국소최소라하고 x 를국소최소점이라고한다. 한편 (2) 에서 f (x ) f (x) 이라면 f (x ) 를국소최대라하고 x 를국소최대점이라부른다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 8 / 57

기초이론 : 다변수함수 II 정의 5.7 ( 전도함수 ). 실함수 f 는열린집합 V R p 에서 정의되었으며 x V 라하자. m R p 이존재하여 f (x + h) f (x) m h lim = 0 h 0 h 인경우 f 는점 x 에서미분가능하다고하며 f (x) = m 로쓴다. f 가 E 의모든점에서미분가능하면 f 는 E 에서 미분가능하다고한다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 9 / 57

기초이론 : 다변수함수 III 정의 5.8 ( 편도함수 ). 각 j = 1,..., p 에대해 f 의 x j 에대한 편도함수는 f j (x) = D j f (x) = f f (x + he j ) f (x) (x) = lim x j h 0 h 로정의하는데 e j = (0,..., 1,..., 0) R p 는 j 번째좌표벡터를 나타낸다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 10 / 57

기초이론 : 다변수함수 IV 그래디언트 (gradient): f (x) = ( f (x),..., f ) (x) x 1 x p 헤시안 (Hessian): 2 f (x) = ( 2 ) f (x) x j x i i,j 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 11 / 57

기초이론 : 다변수함수 V 정리 5.4. 실함수 f 는열린집합 V R p 에서정의되었으며점 x V 에서미분가능하다고하자. 그러면, 편미분 f j (x) 들은존재하며 f (x) = f (x) 로주어진다. 모든 j = 1,..., p에대해 x j 에대한편도함수 f j (x) 들이존재한다고해도반드시 f 가 x에서미분가능하지는않음 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 12 / 57

기초이론 : 다변수함수 VI 실습 5.1. f (0, 0) = 0 이고 f (x 1, x 2 ) = x1x2 x 2 1 +x2 2 단 x = (x 1, x 2 ) 0 로정의 0 에서편미분값 f 1 (0) 및 f 2 (0) 들은존재하지만 f 는 0 에서불연속 f (h, h) = h 2 / h 2 = h 2 / h = h 이므로대각선방향으로는 미분불가능 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 13 / 57

기초이론 : 다변수함수 VII z x1 x2 0.10 0.05 0.00 0.05 0.10 0.06 0.04 0.02 0 0 0.02 0.04 0.06 0.06 0.04 0.02 0.02 0.04 0.06 0.10 0.05 0.00 0.05 0.10 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 14 / 57

기초이론 : 다변수함수 VIII 정리 5.5. 편도함수 f j (x) 들이 x 의근방에서정의되며 x 에서 연속이면 f 는 x 에서미분가능하며 이다. f (x) = f (x) 정의 5.9 ( 방향도함수 ). f 의 d 로의방향도함수 (directional derivative) f (x; d) = lim h 0 f (x + hd) f (x) h 를정의할수있다. h 0 또는 h 0 인경우에 f (x; d) 는한쪽 방향도함수라부른다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 15 / 57

기초이론 : 다변수함수 IX f 가 x에서미분가능한경우에 f (x; d) = d f (x) 이성립정리 5.6. 함수 f 는열린집합 V R p 에서정의되고 f 와 2 f 이 V 에서연속이라고하자. 만약 x 이국소최대점이면 f (x ) = 0이고 2 f (x ) 는준음정치 (semi-negative definite) 이다. 만일, f (x ) = 0이고 2 f (x ) 가음정치 (negative definite) 이면 x 는국소최대점이다. 정의 5.10. f (x) = 0 및 2 f (x) 가음정치인것은각각국소최소점이되기위한일차조건및이차조건이라한다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 16 / 57

기초이론 : 다변수함수 X 실습 5.2. f (x) = x1 3 + x 2 3 3x 1 12x 2 + 20 f 1 (x) = 3x1 2 3, f 2 (x) = 3x2 2 12, f 11 (x) = 6x 1, f 22 (x) = 6x 2, f 12 (x) = 0, det ( 2 f (x) ) = 36x 1 x 2 일차조건 f (x) = 0을만족하는점들 : (±1, ±2) 2 f (1, 2) = diag(6, 12) 는양정치이므로점 (1, 2) 는국소최소값 2 f ( 1, 2) = diag( 6, 12) 과 2 f (1, 2) = diag(6, 12) 들은부정치 (indefinite) 이므로 (1, 2) 와 ( 1, 2) 들은안장점 2 f ( 1, 2) = diag( 6, 12) 는음정치이므로 ( 1, 2) 는국소최대점 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 17 / 57

기초이론 : 다변수함수 XI z x1 x2 3 2 1 0 1 2 3 0 25 5 10 s m 35 m 5 10 15 20 25 30 s 30 35 15 40 2 1 0 1 2 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 18 / 57

기초이론 : 볼록함수 I 정의 5.11. 임의의 x 1, x 2 V 와 0 λ 1에대하여 λx 1 + (1 λ)x 2 V 이면집합 V 는볼록 (convex) 하다고말한다. 집합 V R p 가볼록하다는것은 V 에속하는임의의두점사이의선분이다시 V 상에있게됨을의미정의 5.12. 임의의 x 1, x 2 V 와 0 λ 1에대하여 λf (x 1 ) + (1 λ)f (x 2 ) f (λx 1 + (1 λ)x 2 ) (3) 이면함수 f 는집합 V 위의볼록함수다. 식 (3) 에서 x 1 = x 2 인경우에만등식이성립하면 f 는순볼록 (strictly convex) 함수라고부른다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 19 / 57

기초이론 : 볼록함수 II f 가매끄러운함수인경우에는 f 가 V 상에서 ( 순 ) 볼록함수일 필요충분조건은모든 x V 에대하여 2 f (x) 이 ( 순 ) 양정치행렬 영역 V R p 상에서매끄러운함수 f 에대한제약없는최소화는 x = argmin f (x) x V 를찾는문제. 그러한 x 를 f 의 V 상의전역최소점 (global minimum point) 이라함 정리 5.7. f 가볼록함수이면 f 의임의의국소최소점은 전역최소점이다. 정리 5.8. 만약 f 가미분가능하고볼록인함수이면 x 이최적 (optimal) 일필요충분조건은 f (x ) = 0 이다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 20 / 57

일변수비선형방정식에대한뉴튼방법 I 일변수함수의최적화문제 x = argmin x [a,b] f (x) 에대한 일반적인접근법은일변수비선형방정식 f (x) = 0 에해법을적용 뉴튼법의아이디어 함수 f 는미분가능하고도함수 f 이연속이며근 x R 를 갖는다고가정 x 0 R: 근 x 에대한초기추측값 x 0 에서의접선 : f (x) = f (x 0 )(x x 0 ) + f (x 0 ) 접선이 x- 축과만나는점 : x 1 = x 0 f (x0) f (x 0) 다음추측값 : x 2 = x 1 f (x1) f (x 1) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 21 / 57

일변수비선형방정식에대한뉴튼방법 II 알고리즘 5.1. 일변수비선형식에대한뉴튼알고리즘 초기값 : x 0 i = 1,..., M 에대해수렴할때까지다음을수행 1. 다음식에따라갱신 2. 수렴조건확인 x i+1 = x i f (x i) f (x i ) 출력 : x M 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 22 / 57

일변수비선형방정식에대한뉴튼방법 III 알고리즘의수렴성 f (x ) 0 이고 f 이 x 에서유한하고연속이며초기치 x 0 가 x 에 충분히가까우면 x i 은매우빠른속도로 x 로수렴 해의값은미지이므로함수 f 의해근방에서의행태 (behavior) 나 초기치가해에가까운지여부는실제로는알기어려움 x i x 라고하면 f 와 f 의연속성에의하여 ( x = lim x i f (x ) i) i f (x i ) 이므로 f (x ) < 이면 f (x ) = 0 = lim i x i f (lim i x i ) f (lim i x i ) = x f (x ) f (x ) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 23 / 57

일변수비선형방정식에대한뉴튼방법 IV 실습 5.4 ( 절편이없는선형로지스틱회귀 ) x 1,..., x 19 : 분포 U( 0.8, 1.2) 에서얻은특정랜덤표본의관측값 y i Bernoulli(p i ). 단 p i = 1 1+e βx i, β = 5 η i (b) = bx i p i (b) = 1 1 + e η i (b) 19 { l(b) = y i η i (b) log (1 )} + e η i (b) s(b) = i(b) = i=1 19 i=1 19 i=1 {(y i p i (b)) x i } {p i (b) (1 p i (b)) x i } 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 24 / 57

일변수비선형방정식에대한뉴튼방법 V 0.0 0.2 0.4 0.6 0.8 1.0 v s y l (a) (b) 13 12 11 10 9 8 1 2 3 456 0.5 0.0 0.5 1.0 x 0 2 4 6 8 10 b (c) (d) 1 0 5 10 15 20 25 30 0 1 2 3 2 3 456 0 2 4 6 8 10 b 0 2 4 6 8 10 b 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 25 / 57

최강알고리즘 I d가 x 0 에서함수 f 의감소방향 (descent direction): 적절한 ɛ > 0에대하여 f (x 0 + λd) < f (x 0 ) 단 0 < λ < ɛ d가감소방향일필요충분조건은 d f (x 0 ) < 0임 Cauchy-Schwarz 부등식 : d f (x 0 ) / d f (x 0 ) 등호는 d = ± f (x 0 ) 일때성립하며 f (x 0 ) 는함수 f 가 x 0 에서가장빨리증가하는방향 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 26 / 57

최강알고리즘 II 최대하강또는최강법 (steepest descent) x 1 = x 0 λ f (x 0 ) 로 x를갱신스텝반감법 (step-halving): f (x i + s k d) < f (x i ) 를만족하는비음정수 (nonnegative integer) k를찾고 λ = 2 k 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 27 / 57

최강알고리즘 III 알고리즘 5.2 최강알고리즘 초기값 : x 0 i = 1,..., M 에대해수렴할때까지다음을수행 1. 현재값 x i 를이동시킬방향 d = f (x i ) 를선택한다. 2. f (x i + λd) < f (x i ) 를만족하도록 λ 를찾는다. 3. x i+1 = x i + λd 로갱신한다. 4. 수렴조건확인 출력 : x M 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 28 / 57

뉴튼 - 랩슨알고리즘 I 해에대한초기추측값 x 0 가주어지면 f (x) 에대한선형방정식 f (x 0 ) + 2 f (x 0 )(x x 0 ) = 0 (4) 의해 x 1 = x 0 [ 2 f (x 0 ) ] 1 f (x0 ) 는다음의추측값 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 29 / 57

뉴튼 - 랩슨알고리즘 II 알고리즘 5.3 ( 뉴튼 - 랩슨알고리즘 ) 초기값 : x 0 i = 1,..., M 에대해수렴할때까지다음을수행 1. 현재값 x i 를이동시킬방향 d = [ 2 f (x i ) ] 1 f (xi ) 를선택한다. 2. f (x i + λd) < f (x i ) 를만족하도록 λ 를찾는다. 3. x i+1 = x i + λd 로갱신한다. 4. 수렴조건확인 출력 : x M 알고리즘 5.3 에서 λ 는스텝반감법으로구할수있음 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 30 / 57

뉴튼 - 랩슨알고리즘 III 최강법과뉴튼랩슨방법의비교예함수 : f (x 1, x 2 ) = (x 1 1) 2 + (x 2 1) 2 x 1 x 2 최소점 : (2, 2) 초기점 ( 10, 3) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 31 / 57

뉴튼 - 랩슨알고리즘 IV 10 5 0 5 10 1 107 56 7891 3 4 2 0.3 4.81 25.25 0.5 1.0 1.5 2.0 2.5 3.0 5 0.3 4 7 91 8 6 1.97 1.89 1.57 10 5 0 5 10 0.5 1.0 1.5 2.0 2.5 3.0 10 5 0 5 10 1 107 2 10 5 0 5 10 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 32 / 57

제약있는최적화문제 I 제약최적화문제 최소화 f (x) 제한조건 f i (x) 0, i = 1,..., n I h i (x) = 0, i = 1,..., n E (5) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 33 / 57

제약있는최적화문제 II 용어 x R p : 최적화변수 (optimization variable) f : R p R: 목적함수 (objective function) 혹은비용함수 (cost function) f i (x) 0: 부등제약 (inequality constraint), f i : R p R: 부등제약함수 h i (x) 0: 등제약 (equality constraint), h i : R p R: 등제약함수특정 x가 (5) 의제약조건들을만족하는경우에 x는실현가능한 (feasible) 점모든실현가능한점들의집합 : 실현가능집합 (feasible set) 또는제약집합 (constraint set) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 34 / 57

제약있는최적화문제 III (5) 의최적값 P = inf {f (x) : f i (x) 0, i = 1,..., n I, h i (x) = 0, i = 1,..., n E } (6) P 는 ± 의값을갖는것이허용 P = : 문제가실현불가능 ( 공집합의최대하계이 ) P = : 아래로한계가없음 (k 이면 f (x k ) 인실현가능한 x k 들이존재 ) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 35 / 57

여유변수 f i (x) 0 는 f i (x) + s i = 0 인 s i 0 가존재한다는것과동치 (5) 는다음과동치 최소화 f (x) 제한조건 s i 0, i = 1,..., n I f i (x) + s i = 0, i = 1,..., n I h i (x) = 0, i = 1,..., n E (7) s i 는여유변수 (slack variable) 라고하며 s R n I 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 36 / 57

볼록최적화 볼록최적화 (convex optimization) 문제 최소화 f (x) 제한조건 f i (x) 0, i = 1,..., n I a i x = b i, i = 1,..., n E. (8) 과같은형태를갖는데 f, f 1,..., f ni 들은볼록함수볼록최적화의부가조건 1. 목적함수는볼록함수 2. 부등제약함수는볼록함수 3. 등제약함수 h i (x) = a i x b i 는아핀 (affine) 볼록최적화문제의실현가능집합은볼록 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 37 / 57

선형과이차계획법 I 선형계획법 (linear program; LP): 목적과제약함수들이모두 아핀인경우의최적화문제 최소화 제한조건 c x + d Gx h Ax = b (9) 로서 G R n I p, A R n E p, h R n I, b R n E 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 38 / 57

선형과이차계획법 II 이차계획법 (quadratic program; QP): 목적함수가이차함수이고 제약조건이아핀인볼록최적화문제 1 최소화 2 x Px + q x + r 제한조건 Gx h Ax = b. (10) 여기서 P R p p 인양정치행렬이고, G R n I p, A R n E p 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 39 / 57

선형과이차계획법 III 실습 5.6 직선 2x 1 x 2 = 5 위의점으로서원점에서가장가까운점? 단, A = 라그랑즈함수는 최소화 [ ] 2 1 및 a = 5 f (x) = 1 2 x 2 제한조건 A x = 5 (11) L(x, λ) = 1 2 이고 x, λ 들은다음식들의해 ( x 2 1 + x2 2 ) + λ1 (2x 1 x 2 5) L λ 1 = 0, L x 1 = 0, L x 2 = 0. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 40 / 57

선형과이차계획법 IV L/ λ = 2x 1 x 2 5: 제한조건 L = x 1 + 2λ = 0 및 L = x 2 λ = 0 (12) x 1 x 2 λ = 1, 최소점 x = (2, 1), 최소값 f (2, 1) = 5/2 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 41 / 57

z 선형과이차계획법 V x1 x2 q 0 5 10 15 20 25 1 0 1 2 3 4 0 1 2 3 4 1 x 2 x 1 4 3 2 1 0 1 2 4 6 8 x 10 12 14 y1 5 4 3 2 1 0 1 x 1 0 1 2 3 4 1 0 1 2 3 4 5 x 1 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 42 / 57

쌍대성 I 최적화문제 (5) 와연관된라그랑즈함수 : L(x, λ, ν) = f (x) + λ i f i (x) + n I i=1 n E i=1 ν i h i (x) 벡터 λ 과 ν 는문제 (5) 와관련된쌍대변수 (dual variable) 또는 라그랑즈승수벡터 라그랑즈쌍대함수 (dual function): g(λ, ν) = inf x L(x, λ, ν) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 43 / 57

쌍대성 II (5) 에대한라그랑즈쌍대문제 최대화 g(λ, ν) 제한조건 λ 0 (13) (λ, ν ) 가 (13) 에대하여최적이면 (λ, ν ) 는쌍대최적또는최적라그랑즈승수 D : 라그랑즈쌍대문제의최적값약쌍대성 (weak duality): D P P D : 원문제의최적쌍대격차 (optimal duality gap) 강쌍대성 (strong duality): D = P 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 44 / 57

등제약이차계획에대한쌍대성 I 등제약이차계획 최소화 제한조건 A x = a. f (x) = 1 2 x C 1 x b x 라그랑즈함수 : L(x, λ) = f (x) + λ (A x a) L f = 0에서 x x + Aλ = 0를얻고, 즉 C 1 x + Aλ = b이며 L λ = 0에서제한조건 A x = a을얻음 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 45 / 57

등제약이차계획에대한쌍대성 II x = C(b Aλ) = Ce라하면쌍대함수는다음과같다. g(λ) = L(x, λ) = 1 ( ) 2 e C C 1 Ce b Ce + λ A Ce a = 1 2 e Ce λ a (b Aλ) Ce = 1 2 e Ce λ a = 1 2 (b Aλ) C(b Aλ) λ a. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 46 / 57

등제약이차계획에대한쌍대성 III 정리 5.9. 제한조건하에서 f 의최소값은제한조건없는 g 의 최대값과같으며최소점 x 와최대점 λ 는 을만족한다. C 1 x = b Aλ 및 A x = a 정리 5.10. A x = a 에대해 g(λ) L(x, λ) f (x) 이며 C 1 x + Aλ = b 일때등호는성립하고 g(λ) = f (x) 인데이는 다음과같이정리된다. max( g) = max λ λ min y L = min y max L = min f. λ A y=a 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 47 / 57

등제약이차계획에대한쌍대성 IV 예 5.2. 피타고리스법칙과쌍대성 G = R(A), G : G 와수직인부분공간 피타고라스정리 : (G 와거리 ) 2 + (G 와거리 ) 2 = (b 의거리 ) 2 (G 와거리 ) 2 = min λ b Aλ 2 = b P G b 2 G 와수직인벡터들은 A x = 0 를만족하며 G 는 A 의 영공간이므로 ( ) (G 와거리 ) 2 = min b A x=0 x 2 = min x x 2b x + b b A x=0 위식들로부터 ( ) 0 = min b λ Aλ 2 + min x x 2b x A x=0 즉, 쌍대성 0 = min f + min g 을얻음 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 48 / 57

최적조건 I 원시문제가볼록이면 KKT 조건은원시와쌍대최적일충분조건이됨함수 f,..., f ni, h 1,..., h ne 들은미분가능하고 ( 따라서정의역이열린집합이고 ) 볼록이라고가정 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 49 / 57

최적조건 II 정리 5.11. f i 는볼록, h i 는아핀, 점 x, λ, ν 들은 KKT 조건 f i ( x) 0, h i ( x) = 0, λ i 0 λ i f i ( x) = 0, f ( x) + n I i=1 λ i f i ( x) + n E i=1 ν i h i ( x) = 0, i = 1,..., n I i = 1,..., n E i = 1,..., n I i = 1,..., n I 을만족시킨다고하자. 그러면 x 과 ( λ, ν) 는원시최적과쌍대 최적으로서쌍대격차가영이다. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 50 / 57

적용예 : 이산형확률분포의최가추정 I 범주 y = 1,..., K 에대한확률질량함수 f (y π) = π y Y 1,..., Y n 은 Y 의분포로부터의랜덤표본이 ( n ) l(π) = log π Yi = i=1 n K log π Yi = N k log π k, i=1 k=1 단 N k = #{i : Y i = k} 최대 - 가능도추정량 : 최소화 l(π) 제한조건 π k 0, k = 1,..., K K k=1 π k = 1. 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 51 / 57

적용예 : 이산형확률분포의최가추정 II 라그랑즈함수 : L(π, λ, ν) = K k=1 N k log π k + ( K k=1 λ K ) k( π k ) + ν k=1 π k 1 L/ π j = N j p j λ j + ν = 0 에서 ˆπ j = N j ν λ j, for j = 1,..., K 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 52 / 57

적용예 : 이산형확률분포의최가추정 III 쌍대함수 g(λ, ν) = L(ˆπ, λ, ν) K = N k log = k=1 ( Nk ν λ k K N k log N k + k=1 ) K k=1 λ k N k ν λ k + ν K N k log(ν λ k ) + n ν k=1 ( K k=1 N k ν λ k 1 ) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 53 / 57

적용예 : 이산형확률분포의최가추정 IV log(ν λ k ) 는 λ k 에대하여감소함수이므로 λ k = 0 인경우에 g 의 최대값 g(ν) = K k=1 N k log ν ν = n log ν ν 의최대화 g(ν) ν = n ν 1 = 0 으로부터 ν = n j = 1,..., K 에대하여 ˆπ j = N j ν λ j = N j n 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 54 / 57

적용예 : 라소의쌍대성 I 주어진벡터 y R n 와 n p 행렬 X 에대하여라소추정량 ˆβ: 1 최소화 2 y X β 2 제한조건 p j=1 β j s (14) (14) 는적절한 γ 0 에대해 L 1 - 벌점최소화문제 최소화 1 2 y X β 2 + γ p j=1 β j (15) 와동치 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 55 / 57

적용예 : 라소의쌍대성 II β 의양수부분과음수부분을도입하여 β = u v, u 0, v 0 이되게하고 A = X X 및 b = X y 라하면식 (15) 는 최소화 1 2 (u v) A(u v) + b (u v) + γ p j=1 β j 제한조건 u 0 및 v 0 (16) 의해 쌍대문제를이차계획법에맞는형태로식을변환하면 최소화 1 2 η (X X ) 1 η η ˆβ LS 제한조건 γ η i γ 단 i = 1,..., p γ 0 (17) 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 56 / 57

적용예 : 라소의쌍대성 III 실제문제에서는계산의효율성을고려하여이차계획법은거의사용되지않으며해의자취 (solution path) 를구함 이차계획을이용하는경우에는 γ 의격자점수만큼적합을해야함 또한이차계획은 γ 의값에따라수치적으로불안정하고속도가 매우느려질수있음 자취알고리즘은해가벌점모수 γ 에대하여조각별선형함수라는 점에착안함 자취알고리즘을이용하는경우 γ 가고정된경우의이차계획법의 2-3 배정도의계산량이필요 박창이 ( 서울시립대학교통계학과 ) 5 장. 최적화 57 / 57