17-02-03 Primal-Dual Algorithm

Primal-Dual 알고리즘을 정의하기 위해 먼저 τ(x,u)를 다음과 같이 정의하자

τ(x,u):=h(x)Tumwithh(x)0,u0

참고로 Barrier method에서의 tμ를 Primal-Dual 알고리즘에서는 τσ로 재정의하여 표기한다.

τ=1t,σ=1μ

Primal-Dual Algorithm

Primal-Dual 알고리즘은 다음과 같다.

  1. σ를 선택 (σ(0,1))
  2. (x0,u0,v0)를 선택 (h(x0)<0. u0>0)
  3. 다음 단계를 반복 (k=0,1,...)
    * Newton step 계산 :
    (x,u,v)=(xk,uk,vk)
    τ:=στ(xk,uk) 계산
    τ에 대해 (Δx,Δu,Δv) 계산
    * Backtracking으로 step length θk를 선택
    * Primal-Dual 업데이트 :
    (xk+1,uk+1,vk+1):=(xk,uk,vk)+θk(Δx,Δu,Δv)
  4. 종료 조건 : h(xk+1)Tuϵ and (rprim22+rdual22)1/2ϵ 조건을 만족하면 중지

알고리즘은 각 단계 별로 Newton step을 실행하여 (Δx,Δu,Δv)를 계산하고 Primal-Dual 업데이트를 하여 (xk+1,uk+1,vk+1)를 구한다. 단, Backtracking line search를 통해 Primal-Dual 변수가 feasible해 지도록 θk를 선택한다. 알고리즘은 surrogate duality gap과 primal and dual residual이 ϵ 보다 작아지면 종료한다.

Primer-Dual 알고리즘에서 Newton step을 한번만 실행하기 때문에 정확한 해을 찾기 보다는 해의 방향을 구한 것으로 볼 수 있다. 따라서, 그 방향으로 이동하면서 feasible set으로 들어올 수 있도록 적절한 step length를 구해야 한다.

즉, 알고리즘의 각 스텝에서 θ를 구해서 primal-dual 변수를 업데이트한다.

x+=x+θΔx,u+=u+θΔu,v+=v+θΔv

이 과정에는 두 가지 주요 목표가 있다.

  • h(x)<0,u>0의 조건을 유지하는 것
  • r(x,u,v)을 감소시키는 것

이를 위해 다단계 백트랙킹 선형 검색(multi-stage backtracking line search)을 사용한다.

Stage 1: dual feasibility u>0

처음에는 u+θΔu0를 만족하는 가장 큰 스텝 θmax1으로 시작한다.

θmax=min{1, min{uiΔui:ui<0}}

위의 식은 다음과 같이 유도된다.

u+θΔu0uθΔuu/Δuθ such that Δu>0

이는 u를 feasible하게 만드는 과정이다.

Stage 2: primal feasibility h(x)<0

그 다음엔 파라미터 α,β(0,1)로 하고 θ0.99θmax로 설정한 후 다음 업데이트를 수행 한다.

  • hi(x+)<0,i=1,...m를 만족할 때까지, θ=βθ를 업데이트

이는 x를 feasible하게 만드는 과정이다.

Stage 3 : reduce r(x,u,v)

  • r(x+,u+,v+)(1αθ)r(x,u,v)를 만족할 때까지, θ=βθ를 업데이트

Stage 3의 update 식은 기존의 backtracking line search 알고리즘과 동일하다.

위의 식에서 우항은 다음과 같이 유도될 수 있다. 먼저 Newton’s method에서 다음 결과를 얻는다.

Δw=(Δx,Δu,Δv)r(w)1r(w)r(w)r(w)Δw

위의 식에서 r(w)Δwr(w)이므로 이를 아래 Taylor 1차 근사식에 대입한다.

r(w+θΔw)r(w)+r(w)(θΔw)(1θ)r(w)

결과적으로 r(w+αθΔw)(1αθ)r(w)가 된다.