08. Duality
8-1. Lower Bounds in LP
Example) Constraint들의 선형조합으로 Objective function 표현
(1) Problem
\(\begin{array}{ll} \min _{x, y} & x+3 y \\ \text { subject to } & x+y \geq 2 \\ & x, y \geq 0 \end{array}\).
(2) Constraint들의 선형조합으로 Objective Function 꼴 만들기
\(\begin{array}{rr} & x+y \geq 2 \\ + & 0 x \geq 0 \\ + & 2 y \geq 0 \\ = & x+3 y \geq 2 \end{array}\).
\(\rightarrow\) Lower bound \(B=2\)
Example) General Form
(1) Problem
\(\begin{array}{ll} \min _{x, y} & px+qy \\ \text { subject to } & x+y \geq 2 \\ & x, y \geq 0 \end{array}\).
(2) Constraint들의 선형조합으로 Objective Function 꼴 만들기
\[\begin{aligned} &a(x+y) \geq 2 a\\ &+\quad b x \geq 0\\ &+\quad c y \geq 0\\ &=\quad(a+b) x+(a+c) y \geq 2 a \end{aligned}\]\(\rightarrow\) Lower bound \(B=2a\)
where, 아래 조건 충족!
- (1) \(a+b=p\)
- (2) \(a+c=q\)
- (3) \(a, b, c \geq 0\)
(3) Dual LP로 변형하기
- 위 문제 ( = Primal LP )를, 아래와 같이 변형해서 ( = Dual LP ) 풀 수 있다.
- 이 때, 최적화 변수 ( optimization variable )은, Primal LP에서의 “constraint의 개수”와 동일하다.
- 아래의 식에서, dual variable은 \(a,b,c\) 이다.
\(\begin{array}{ll} \max _{a, b, c} & 2 a \\ \text { subject to } & a+b=p \\ & a+c=q \\ a, b, c \geq 0 \end{array}\).
Example) Constraint들의 선형조합으로 Objective function 표현 (2)
(1) Problem
\(\begin{array}{ll} \min _{x, y} & px+qy \\ \text { subject to } & x \geq 0 \\ & y \leq 1 \\ & 3x+2y=2 \end{array}\).
(2) Constraint들의 선형조합으로 Objective Function 꼴 만들기
\(\begin{array}{rr} + & a x \geq 0 \\ + & -b y \geq-b \\ = & (a+3 c) x+(-b+c) y \geq 2 c-b \end{array}\).
\(\rightarrow\) Lower bound \(B=2c - b\)
where, 아래 조건 충족!
- (1) \(a+3c=p\)
- (2) \(-b+c=q\)
- (3) \(a, b \geq 0\)
(3) Dual LP로 변형하기
- 위 문제 ( = Primal LP )를, 아래와 같이 변형해서 ( = Dual LP ) 풀 수 있다.
- 이 때, 최적화 변수 ( optimization variable )은, Primal LP에서의 “constraint의 개수”와 동일하다.
\(\begin{array}{ll} \max _{a, b, c} & 2c-b \\ \text { subject to } & a+3c=p \\ & -b+c=q \\ a, b \geq 0 \end{array}\).
8-2. Duality in general LPs
이번엔, matrix form으로 알아볼 것이다.
(0) Notation (shape)
\(c \in \mathbb{R}^{n}, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^{m}, G \in \mathbb{R}^{r \times n}, h \in \mathbb{R}^{r}\).
(1) Problem
\(\begin{array}{ll} \min _{x} & c^{T} x \\ \text { subject to } & A x=b \\ & G x \leq h \end{array}\).
(2) Constraint들의 선형조합으로 Objective Function 꼴 만들기
\(\begin{aligned} & u^{T}(A x-b)=0 \\ +& v^{T}(G x-h) \leq 0 \\ =& u^{T}(A x-b)+v^{T}(G x-h) \leq 0 \end{aligned}\).
위 부등식을 재 정리하면….
( 참고 : \(u\) 는 “부호 무관”, \(v\) 는 “양수” )
\(\begin{array}{r} u^{T}(A x-b)+v^{T}(G x-h) \leq 0 \\ \underbrace{\left(-A^{T} u-G^{T} v\right)^{T}}_{=c^{T}} x \geq-b^{T} u-h^{T} v \end{array}\).
\(\rightarrow\) Lower bound \(B=-b^{T} u-h^{T} v\)
where, 아래 조건 충족!
- (1) \(c=-A^{T} u-G^{T} v\)
- (2) \(v \geq 0\)
(3) Dual LP로 변형하기
- 위 문제 ( = Primal LP )를, 아래와 같이 변형해서 ( = Dual LP ) 풀 수 있다.
- 이 때, 최적화 변수 ( optimization variable )은, Primal LP에서의 “constraint의 개수”와 동일하다.
\(\begin{array}{ll} \max _{u,v} & -b^{T} u-h^{T} v \\ \text { subject to } & c=-A^{T} u-G^{T} v \\ & v \geq 0 \end{array}\).