Interior Point·중심 경로와 Newton

경계 안쪽에서만 움직이기

닫힌 구간 [0,1]에서 cx를 최소화하자. 로그 장벽은 경계 제약을 내부에서만 정의되는 목적함수로 바꾼다.

실습의 t는 2의 선택한 지수승이다. t가 커지면 원래 목적함수의 영향이 상대적으로 강해진다. c>0이면 0 쪽, c<0이면 1 쪽으로 당긴다. c=0에서는 원래 문제의 모든 가능점이 최적이지만 장벽은 중점 하나를 고른다. 원래 문제와 장벽 문제를 구분하는 첫 예다.

정확한 중심점은 비교 기준

미분하면 B′=tc−1/x+1/(1−x), B″=1/x²+1/(1−x)²>0이다. 따라서 장벽 최소점은 유일하다. C=tc≥0에서 수치적으로 안정적인 형태는

C<0이면 x(C)=1−x(−C)의 대칭을 사용한다. 큰 수끼리 거의 같아진 값을 빼는 공식을 유리화한 결과다. 그림의 파란 기준점은 이 해석적 중심점이다. 이를 Newton이 계산한 현재 점으로 바꿔 표시하지 않는다.

실제 Newton 반복과 선 탐색

선택한 내부 시작점에서 Δx=−B′/B″를 계산한다. 전체 Newton 보폭은 경계 밖으로 나갈 수 있다. 먼저 해당 경계까지 거리의 99% 이내로 보폭을 제한한다. 이어 Armijo 계수 0.01의 충분 감소 조건을 만족할 때까지 보폭을 절반씩 줄인다.

표에는 실제 수락한 보폭, backtracking 횟수, 반복점이 기록된다. 주황 선은 정규화한 장벽 B/t 위의 이산 반복점들을 연결한다. 연속 시간 궤적이 아니다. 파란 곡선은 [0.001,0.999]라는 유한 창에서만 그린다. 진짜 경계에서는 장벽이 무한대로 발산하며, 유한 창 밖의 계산된 반복점도 그림 범위에 포함한다.

중심 경로 간극과 현재 점 인증

정확한 중심점에서 λL=1/(txₜ), λU=1/[t(1−xₜ)]로 두자. 두 값은 비음수이고 c−λL+λU=0을 만족하므로 −λU는 쌍대 하한이다.

이 식은 정확한 중심점에서 성립한다. 유한 번 Newton을 수행한 현재 점은 정상성 잔차가 남는다. 그 점의 역슬랙을 곧바로 승수로 사용하면 쌍대 정상성이 깨질 수 있어 하한이라고 부를 수 없다.

실습은 모든 현재 가능점에 대해 정확한 중심점에서 얻은 쌍대 하한을 사용한다. 현재 인증 간극은 cx_current+λU이며 일반적으로 2/t와 다르다. 두 숫자를 별도로 표시하는 이유다. 간극은 목적 오차의 상한이지 오차 자체가 아니다.

직접 풀기와 종료 판단

c=1, t=1이면 중심점은 약 0.381966, 중심 간극은 2다. t=16에서는 중심점 약 0.058609, 간극 0.125다. 이제 t=256, 시작점 0.5, 반복 0회로 두자. 현재 간극은 약 0.503922인데 중심 간극은 0.0078125다. t를 키우는 일만으로 내부 장벽 문제가 풀리지 않았음을 확인한다.

c<0에서 위쪽 경계 근처로 대칭적으로 이동하는지 보자. c=0이면 실제 목적 오차는 모든 가능점에서 이미 0이지만 중심 인증 간극은 양수다. 따라서 충분한 종료 기준과 정확한 오차를 혼동하면 안 된다. 실무에서는 장벽 매개변수뿐 아니라 내부 반복의 정확도와 가능성도 함께 확인한다.

더 읽기: Boyd와 Vandenberghe, Convex Optimization.