17-02-03 Primal-Dual Algorithm
Primal-Dual 알고리즘을 정의하기 위해 먼저
참고로 Barrier method에서의
Primal-Dual Algorithm
Primal-Dual 알고리즘은 다음과 같다.
를 선택 ( ) 를 선택 . ) - 다음 단계를 반복 (
)
* Newton step 계산 :
계산
에 대해 계산
* Backtracking으로 step length 를 선택
* Primal-Dual 업데이트 :
- 종료 조건 :
and 조건을 만족하면 중지
알고리즘은 각 단계 별로 Newton step을 실행하여
Backtracking line search
Primer-Dual 알고리즘에서 Newton step을 한번만 실행하기 때문에 정확한 해을 찾기 보다는 해의 방향을 구한 것으로 볼 수 있다. 따라서, 그 방향으로 이동하면서 feasible set으로 들어올 수 있도록 적절한 step length를 구해야 한다.
즉, 알고리즘의 각 스텝에서
이 과정에는 두 가지 주요 목표가 있다.
의 조건을 유지하는 것 을 감소시키는 것
이를 위해 다단계 백트랙킹 선형 검색(multi-stage backtracking line search)을 사용한다.
Stage 1: dual feasibility
처음에는
위의 식은 다음과 같이 유도된다.
이는
Stage 2: primal feasibility
그 다음엔 파라미터
를 만족할 때까지, 를 업데이트
이는
Stage 3 : reduce
를 만족할 때까지, 를 업데이트
Stage 3의 update 식은 기존의 backtracking line search 알고리즘과 동일하다.
위의 식에서 우항은 다음과 같이 유도될 수 있다. 먼저 Newton’s method에서 다음 결과를 얻는다.
위의 식에서
결과적으로